新微赢技术网

标题: [求助]一道ACM的题 [打印本页]

---

作者: 绝对标致    时间: 2009-11-4 00:51
标题: [求助]一道ACM的题
http://acm.pku.edu.cn/JudgeOnline/problem?id=1012
能否给个思路？

---

作者: 阿咏    时间: 2009-11-4 00:51
I can not understand the description there. Sorry.

---

作者: X~iao~ping    时间: 2009-11-4 00:51
这是我写的程序，不过运行效率有点低


// 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

也不知道对不对

---

作者: 小嘛怪    时间: 2009-11-4 00:51
前四个结果肯定没有问题，但后面的我就没有办法验证了

---

欢迎光临 新微赢技术网 (http://bbs.weiying.cn/)

Powered by Discuz! X3.2