2495 - 约瑟夫
时间限制 : 1 秒
内存限制 : 128 MB
约瑟夫的问题是出了名的。从N个人中，编号为1，2，。。，N站在圈，每个m都会被枪决，只有最后剩下的人能够活命。
约瑟夫是足够聪明的选择最后剩下的人的位置，从而拯救了他的生命，给我们的有关事件的消息。
例如，当n=6，M=5，那么被杀的顺序是5，4，6，2，3，1
现在假设有k个好人和k个坏人。在圈内的前k个是好人好人和后k个是坏人。
您必须确定一个最小的m，使得好人被杀前，坏人全部都被杀掉。
题目输入
每一行输入一个k值，输入为0时，结束（0<k<14）
题目输出
输出能够满足的m
输入/输出样例
输入格式
3 4 0
输出格式
5 30
C语言解答
#include<stdio.h> int main() { int s[28]; int k,m,temp; int i,k2,t; while(scanf("%d",&k),k) { for(m=k+1;;m++) { t=m; k2=2*k; for(i=0;i<k;i++){//k次查找 temp=t%k2; if(temp==0) temp=k2; if(temp-k<=0) break; else t=m-(k2-temp); k2--; } if(i>=k) { printf("%d\n",m); break;} } } return 0; }
C++解答
#include<iostream> using namespace std; int main(void) { int Joseph[14]={0}; int k; while(cin>>k) { if(!k) break; if(Joseph[k]) { cout<<Joseph[k]<<endl; continue; } int n=2*k; int ans[30]={0}; int m=1; for(int i=1;i<=k;i++) { ans[i]=(ans[i-1]+m-1)%(n-i+1); if(ans[i]<k) { i=0; m++; } } Joseph[k]=m; cout<<m<<endl; } return 0; }