这是我写的程序，不过运行效率有点低
// The Joseph's problem is notoriously known.
// For those who are not familiar with the original problem:
// from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed,
// and only the life of the last remaining person will be saved.
// Joseph was smart enough to choose the position of the last remaining person,
// thus saving his life to give us the message about the incident.
// For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.
// Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys.
// You have to determine such minimal m that all the bad guys will be executed before the first good guy.
#include <iostream>
#include <fstream>
#include <windows.h>
//用来检查m值是否符合要求
bool check(int k,int m)
{
int dead=0; //已经处死的坏人个数
int num=2*k; //剩余的全部人数
int next=m%num; //下一个要处死的人的位置
if(!next)
next=num; //末尾的情况
//共有2k个人，第一个被处死的人的位置为a1=m%num,
//第二个被处死的人的位置为a2=(a1-1+m%(num-1))%(num-1),
//第三个被处死的人的位置为a3=(a2-1+m%(num-2))%(num-2),
//........................................
//只要an>k,处死的就是坏人
while(dead<k&&next>k)
{
++dead; //处死的是坏人
--num;
if(!(next=(next-1+m%num)%num)) //下一个处死的人的位置
next=num; //末尾的情况
}
return dead==k; //已经处死全部坏人，返回true否则false
}
//约瑟夫函数
int joseph(int k)
{
//第一个处死的人为坏人的充要条件是(2n-1)k<m<=2nk,其中n=1,2,3......
//我就是根据这个条件搜索，然后交由check判断是否符合条件
int m=0;
int n=1;
bool find=false;
while(!find)
{
m=(2*n-1)*k+1;
while(m<=2*n*k&&!(find=check(k,m)))
{
++m;
}
++n;
}
return m;
}
int main()
{
const char* inputfile="input.txt"; //输入文件
const char* outputfile="output.txt"; //输出文件
std::ifstream input(inputfile);
if(!input)
{
std::cout<<"An error occurs while opening "<<inputfile<<std::endl;
return -1;
}
std::ofstream output(outputfile,std::ios::out);
if(!output)
{
std::cout<<"An error occurs while opening "<<outputfile<<std::endl;
return -1;
}
DWORD start_time=::GetTickCount();
int k;
while(input>>k&&k!=0)
{
output<<joseph(k)<<std::endl;
}
std::cout<<::GetTickCount()-start_time<<std::endl;
input.close();
output.close();
return 0;
}
1到15的结果为
2
7
5
30
169
441
1872
7632
1740
93313
459901
1358657
2504881
13482720
25779600
也不知道对不对
[此贴子已经被作者于2006-11-1 9:53:24编辑过]
2006-10-28 23:43
