设为首页收藏本站

新微赢技术网

 找回密码
 注册
搜索
热搜: 回贴
查看: 639|回复: 3
打印 上一主题 下一主题

[求助]一道ACM的题

[复制链接]
跳转到指定楼层
1#
发表于 2009-11-4 00:51:12 | 只看该作者 回帖奖励 |正序浏览 |阅读模式
http://acm.pku.edu.cn/JudgeOnline/problem?id=1012
能否给个思路?
4#
发表于 2009-11-4 00:51:15 | 只看该作者
前四个结果肯定没有问题,但后面的我就没有办法验证了
回复 支持 反对

使用道具 举报

3#
发表于 2009-11-4 00:51:14 | 只看该作者
这是我写的程序,不过运行效率有点低


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

也不知道对不对
回复 支持 反对

使用道具 举报

2#
发表于 2009-11-4 00:51:13 | 只看该作者
I can not understand the description there. Sorry.
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

申请友链|小黑屋|最新主题|手机版|新微赢技术网 ( 苏ICP备08020429号 )  

GMT+8, 2024-11-18 23:33 , Processed in 0.093523 second(s), 9 queries , Gzip On, Memcache On.

Powered by xuexi

© 2001-2013 HaiAn.Com.Cn Inc. 寰耽

快速回复 返回顶部 返回列表