博文
joseph问题(2006-09-24 13:34:00)
摘要：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))
&nbs......