杀人游戏

我思故我在

不知道你是否玩过杀人游戏，这里的杀人游戏可没有法官，警察之类的人，只有土匪，现在已知有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之一

没——问题

楼上注意，应该是在你发帖之后，楼主作了修改

此题貌似过难了
终止数字生成：

1. 
   
2. #include <stdio.h>
   
3. int main()
   
4. {     int a;
   
5.        long w=3;
   
6. 
   
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;
   
5.         
   
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<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
-------------
10  10      5
11  10
12  10
13  10
-------------
14  14      6
15  14
16  14
17  14
18  14
19  14
-------------
20  20      7
21  20
22  20
23  20
24  20
25  20
26  20
27  20
28  20
-------------
29  29     8
30  29   
.   .
.   .
.   .
42  29
-------------
43  43     9
44  43
45  43
.   .
.   .
.   .
63  43
64  64
65  64
.   .
.   .
.   .
94  64
-------------
95  95     10
96  95
.   .
.   .
.   .
141 95
--------------
142 142    11
143 142   
.
.
.
211 142
---------------
212 212     12
.   .         .
.   .         .  
.   .         .
*/

于是便可以简单的解决了程序：

#include<iostream>
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……