杀人游戏

我思故我在

不知道你是否玩过杀人游戏，这里的杀人游戏可没有法官，警察之类的人，只有土匪，现在已知有N个土匪站在一排，每个土匪都有一个编号，从1到N，每次杀人时从还活着的土匪中，编号从小到大的找第3个人，然后杀掉，继续往下，直到找遍，然后继续从剩下的土匪中，编号从小到大找到第3个活着的土匪，然后杀掉。比如，现在有10个土匪，第一次杀掉3，6，9号的土匪，第二次杀掉4，8号土匪，第三次杀掉5号土匪，第四次杀掉7号土匪，第五次杀掉10号土匪，我们看到10号土匪是最后一个被杀掉的（1，2号土匪运气好，不会被杀！）。现在给定你一个N，问你最后一个被杀掉的土匪的编号是多少？ 这题自己想来很久，没想法了。不知大家有没有解法？ [ 本帖最后由 我思故我在 于 2009-2-27 22:49 编辑 ]

无心人

和三进制关系比较大

kon3155

原帖由 我思故我在 于 2009-2-27 18:47 发表 每次杀人时从还活着的土匪中，编号从小到大的找到3个人，然后杀掉，继续 ...

应该是“编号从小到大的找到第3个人”吧 类似猴子选大王问题！可能还有一些其他的名字，也是很经典的问题！ 楼主google一下“猴子选大王”，看看有没有启示！ 有一点和“猴子选大王问题”不一样，就是猴子们要围成一个圈，循环的数数

我思故我在

是 第3个…… 谢谢楼上朋友。 我看下猴子选大王。

无心人

应该是1，2之一

没——问题

楼上注意，应该是在你发帖之后，楼主作了修改 此题貌似过难了 终止数字生成：

2. #include <stdio.h>
3. int main()
4. { int a;
5. long w=3;
7. for(a=0;a<50;a++)
8. { w=(3*w-1)/2;
9. printf("%d\n",w);
10. }
11. return 0;
12. }

复制代码

注意其中应用了c整数'除'运算的向下取整 所以不用去算通项了 具体见：http://www.research.att.com/~njas/sequences/A003312 这是模拟代码：

1. #include <stdio.h>
2. #define Max 100
3. int main()
4. { int num[Max],a,b=1,end,N;
6. for(N=3;N<Max+1;N++)
7. { for(a=0;a<N+1;a++)num[a]=a;
8. while(b!=0)for(a=3,b=0;a<N+1;a++)if(num[a]!=0)
9. { if(b%3==0)num[a]=0,end=a;
10. b++;
11. }
12. /*if(N==end)*/printf("%d\t%d\n",N,end);
13. b=1;
14. }
15. return 0;
16. }

复制代码

[ 本帖最后由 没——问题 于 2009-3-4 17:04 编辑 ]

我思故我在

呵呵，此题我已解开。待到周未有空之时我写一下解题报告。

没——问题

恩....我一直不清楚楼主是让写代码（不大可能这样吧，太容易了 ），还是让给出通项公式（个人感觉又太难了... ） 如果是代码那么就是6楼的了，两个等价（一个模拟，一个递推） 如果你在找通项公式，6楼的代码可以为你提供验证数据

我思故我在

呵呵，其实我的本意是通过找通项公式来写代码。这样高效……

我思故我在

今天周末，我来给个报告： 实际上，这是一个来自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 using namespace std; __int64 a[101][100000]; int main() { int i,j,k,n,t; for(i=3;i<=100;i++) { a[1]=i; for(j=2;;j++) { if( (i*a[j-1])%(i-1)==0 ) a[j]=(i*a[j-1])/(i-1)-1; else a[j]=(i*a[j-1])/(i-1); if(a[j]>=(2147483648/i)*(i-1)) break; } } cin>>t; while(t--) { cin>>n>>k; for(i=1;;i++) { if(a[k]>n) {printf("%I64d\n",a[k][i-1]); break;} } } return 0; } OVER……