Joseph问题
题目描述:
原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是1的人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此反复直到所有的人全部出列为止。比如当n=6，m=5的时候，出列的顺序依次是5，4，6，2，3，1。
现在的问题是：假设有k个好人和k个坏人。好人的编号的1到k，坏人的编号是k+1到2k。我们希望求出m的最小值，使得最先出列的k个人都是坏人。
输入:
仅有的一个数字是k（0 < k <14）。
输出:
 使得最先出列的k个人都是坏人的m的最小值。
输入样例:
4
输出样例:
30
程序：
#include "stdio.h"
long k, m, begin;
int check(long remain)
{
 long result = ( begin+m-1  ) % remain;
 if (result>=k)
    {begin = result; return 1;}
 else return 0;
}
main()
{
 long i, find = 0;
 FILE *fp,*fp1;
 fp=fopen("d:\\a.txt","r");
 fp1=fopen("D:\\b.txt","w");
 fscanf(fp,"%ld", &k);
 for (m = k;!find; m++)
    {
     find = 1; begin = 0;
     for (i = 0; i < k; i++)
 if (!check(2*k-i))
           {find = 0; break;}
 }
 fprintf(fp1,"%ld\n",m-1);
 fclose(fp);
 fclose(fp1); 
}

评论