joseph.cpp

这是经典的joseph算法

 // 我真诚地保证：
    
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。


 
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。

// 我从未抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。

  // 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
  // 00548261 王璐

//文件名称：joseph

//项目名称：acm1012

//创建者：王璐

//创建时间：2006.10.17

//最后修改时间：2006.10.17

//功能： 解决Joseph问题，即共有k个好人k个坏人，先删除掉k个坏人。

//文件中的函数名称和简单功能描述：bool jos(int k,int m)//用来判断对于k个坏人时，按m报数是否能够
//                                                     先删除掉所有坏人
//                                void findres()//该函数用来计算出每一个测试数据对应的结果，即m值

//文件中定义的全局变量和简单功能描述：int result[14];因为输入的测试数据不会大于13；所以可以
//                                     用一个数组来记录每一个输入数据的答案




#include<iostream.h>

int result[14];//因为输入数据不会大于13，所以可以用一个全局数组先把所有的结果记录下来，然后
                // 按照测试数据输出答案

bool jos(int k,int m)//这个函数用来判断当输入为k时，即有k个坏人时，按照m报数能否先将坏人都删除掉
{
	int len=2*k;//len表示目前圈内共有多少人，初始化为2k，k个好人k个坏人
	int pos=1;//pos用来记录报数到达的位置，初始化为1；
	int i;//用来记录被删除的坏人数
	for(i=1;i<=k;i++)
	{
		pos=(pos+m-1)%len;//pos像一个指针，从开始位置数m个人，这时的数要取对len的余数
		if(pos==0)//如果pos刚好走到最后一位，则赋值为len
		{
			pos=len;
		}
		if(pos<=k)//如果pos小于等于k,那也就是说它现在指的是好人，会删除一个好人，说明m不符合条件
		{
			return false;//返回false
		}
		len--;//其他时候符合条件，删除一个坏人，圈长减一
	}
	return true;//如果for循环完成，说明m符合条件，返回true
}



void findres()//该函数用来计算出每一个测试数据对应的结果，即m值
{
	int k;//好人和坏人分别有k个
	int m;//报数为m
	bool res;//用来记录m是否是要求的值
	for(k=1;k<14;k++)//k是每一个输入数据
	{
		for(m=k+1;;m++)//m要从k+1开始，因为m不大于k时一定不符合条件
		{
			res=jos(k,m);//计算结果
			if(res)//如果合适，记录下来，进入下一数据的计算
			{
				result[k]=m;
				break;
			}
		}
	}
}


void main()
{
    findres();//先计算出每一个测试数据对应的m值

	int i;
	cin>>i;//输入测试数据
	while(i)
	{
		cout<<result[i]<<endl;//输出结果
		cin>>i;
	}
}