杀人游戏
不知道你是否玩过杀人游戏，这里的杀人游戏可没有法官，警察之类的人，只有土匪，现在已知有N个土匪站在一排，每个土匪都有一个编号，从1到N，每次杀人时从还活着的土匪中，编号从小到大的找第3个人，然后杀掉，继续往下，直到找遍，然后继续从剩下的土匪中，编号从小到大找到第3个活着的土匪，然后杀掉。比如，现在有10个土匪，第一次杀掉3，6，9号的土匪，第二次杀掉4，8号土匪，第三次杀掉5号土匪，第四次杀掉7号土匪，第五次杀掉10号土匪，我们看到10号土匪是最后一个被杀掉的（1，2号土匪运气好，不会被杀！）。现在给定你一个N，问你最后一个被杀掉的土匪的编号是多少？这题自己想来很久，没想法了。不知大家有没有解法？
[ 本帖最后由 我思故我在 于 2009-2-27 22:49 编辑 ] 和三进制关系比较大 原帖由 我思故我在 于 2009-2-27 18:47 发表 http://bbs.emath.ac.cn/images/common/back.gif
每次杀人时从还活着的土匪中，编号从小到大的找到3个人，然后杀掉，继续 ...
应该是“编号从小到大的找到第3个人”吧
类似猴子选大王问题！可能还有一些其他的名字，也是很经典的问题！
楼主google一下“猴子选大王”，看看有没有启示！
有一点和“猴子选大王问题”不一样，就是猴子们要围成一个圈，循环的数数 是 第3个……
谢谢楼上朋友。
我看下猴子选大王。 应该是1，2之一 楼上注意，应该是在你发帖之后，楼主作了修改
此题貌似过难了
终止数字生成：
#include <stdio.h>
int main()
{ int a;
long w=3;
for(a=0;a<50;a++)
{ w=(3*w-1)/2;
printf("%d\n",w);
}
return 0;
}
注意其中应用了c整数'除'运算的向下取整
所以不用去算通项了
具体见：http://www.research.att.com/~njas/sequences/A003312
这是模拟代码：#include <stdio.h>
#define Max 100
int main()
{ int num,a,b=1,end,N;
for(N=3;N<Max+1;N++)
{ for(a=0;a<N+1;a++)num=a;
while(b!=0)for(a=3,b=0;a<N+1;a++)if(num!=0)
{ if(b%3==0)num=0,end=a;
b++;
}
/*if(N==end)*/printf("%d\t%d\n",N,end);
b=1;
}
return 0;
}
[ 本帖最后由 没——问题 于 2009-3-4 17:04 编辑 ]
回复 6# 没——问题 的帖子
呵呵，此题我已解开。待到周未有空之时我写一下解题报告。 恩....我一直不清楚楼主是让写代码（不大可能这样吧，太容易了:Q: ），还是让给出通项公式（个人感觉又太难了...:L ）如果是代码那么就是6楼的了，两个等价（一个模拟，一个递推）
如果你在找通项公式，6楼的代码可以为你提供验证数据
回复 8# 没——问题 的帖子
呵呵，其实我的本意是通过找通项公式来写代码。这样高效…… 今天周末，我来给个报告：实际上，这是一个来自HDOJ的编程题。原题比这里的还难。（http://acm.hdu.edu.cn/showproblem.php?pid=2211）
下面我们先来看下原题的描述：
不知道你是否玩过杀人游戏，这里的杀人游戏可没有法官，警察之类的人，只有土匪，现在已知有N个土匪站在一排，每个土匪都有一个编号，从1到N，每次杀人时给定一个K值，从还活着的土匪中，编号从小到大的找到K个人，然后杀掉，继续往下，直到找遍，然后继续从剩下的土匪中，编号从小到大找到第K个活着的土匪，然后杀掉。比如，现在有10个土匪，K为3，第一次杀掉3，6，9号的土匪，第二次杀掉4，8号土匪，第三次杀掉5号土匪，第四次杀掉7号土匪，第五次杀掉10号土匪，我们看到10号土匪是最后一个被杀掉的（从1到K-1的土匪运气好，不会被杀！）。现在给定你一个N和一个K，问你最后一个被杀掉的土匪的编号是多少。
在Input里还说明了N和K的范围：N（N<2^31） K（3<=K<=100&&K<N）。
这道题看了范围之后就知道用暴力是绝对不行的。
肯定是找规律的题目。没有其它技巧。
假设N个人，每次找剩下的人中的第K个，那么N在一段连续的范围内有一个固定的值， 那么我们这里就需要构造这些固定的值，
第一个就一定是K（N==K），以后假设前一个是F1，则后一个是F2，
如果F1*K/(K-1)正好是整数，即F1整除(K-1)，那么F2=F1*K/(K-1)-1，
如果F1不整除(K-1)，那么F2=F1*K/(K-1)取整。对于K＝3时，有如下的序列：
3，4，5，7，10，……
所以对于7到9之间的数字N，最后一定是7，就这个规律。
有以下数据验证（以k=3为例）：
n 最后被杀的人
3 3 1
-------------
4 4 2
-------------
5 5 3
6 5
-------------
7 7 4
8 7
9 7
-------------
1010 5
1110
1210
1310
-------------
1414 6
1514
1614
1714
1814
1914
-------------
2020 7
2120
2220
2320
2420
2520
2620
2720
2820
-------------
2929 8
3029
. .
. .
. .
4229
-------------
4343 9
4443
4543
. .
. .
. .
6343
6464
6564
. .
. .
. .
9464
-------------
9595 10
9695
. .
. .
. .
141 95
--------------
142 142 11
143 142
.
.
.
211 142
---------------
212 212 12
. . .
. . .
. . .
*/
于是便可以简单的解决了程序：
#include<iostream>
using namespace std;
__int64 a;
int main()
{
int i,j,k,n,t;
for(i=3;i<=100;i++)
{
a=i;
for(j=2;;j++)
{
if( (i*a)%(i-1)==0 ) a=(i*a)/(i-1)-1;
else a=(i*a)/(i-1);
if(a>=(2147483648/i)*(i-1)) break;
}
}
cin>>t;
while(t--)
{
cin>>n>>k;
for(i=1;;i++)
{
if(a>n){printf("%I64d\n",a); break;}
}
}
return 0;
}
OVER……
页:
[1]
2