有趣c语言题之杀人游戏

àì夳堔傛蜴生んèń 2022-04-22 13:06 173阅读 0赞

杀人游戏  
Problem Description

不知道你是否玩过杀人游戏，这里的杀人游戏可没有法官，警察之类的人，只有土匪，现在已知有N个土匪站在一排，每个土匪都有一个编号，从1到N，每次杀人时给定一个K值，从还活着的土匪中，编号从小到大的找到K个人，然后杀掉，继续往下，直到找遍，然后继续从剩下的土匪中，编号从小到大找到第K个活着的土匪，然后杀掉。比如，现在有10个土匪，K为3，第一次杀掉3，6，9号的土匪，第二次杀掉4，8号土匪，第三次杀掉5号土匪，第四次杀掉7号土匪，第五次杀掉10号土匪，我们看到10号土匪是最后一个被杀掉的（从1到K-1的土匪运气好，不会被杀！）。现在给定你一个N和一个K，问你最后一个被杀掉的土匪的编号是多少。

Input

第一行有一个T（T<=10000），接下来有T组数据，每组中包含一个N（N<2^31）和一个K（3<=K<=100&&K<N）。

Output

对于每组数据，输出最后被杀的土匪的编号。

Sample Input

1 10 3

Sample Output

Author

wangye

Recommend

wangye

解题思路：

其实这是一道比较典型的约瑟夫环的问题

[http://baike.baidu.com/link?url=RnHDh0kg0uEeh-H\_a4ZRMI1d3pZ1qbJYpwLdcY3VvZ8LwLxsVNmGODmIilRKhgBnmI3phVO\_lLOavxcQgALT1\_][http_baike.baidu.com_link_url_RnHDh0kg0uEeh-H_a4ZRMI1d3pZ1qbJYpwLdcY3VvZ8LwLxsVNmGODmIilRKhgBnmI3phVO_lLOavxcQgALT1]

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后\[1\] 结果+1即为原问题的解。

约瑟夫环运作如下：  
1、一群人围在一起坐成\[2\] 环状（如：N）  
2、从某个编号开始报数（如：K）  
3、数到某个数（如：M）的时候，此人出列，下一个人重新报数  
4、一直循环，直到所有人出列\[3\] ，约瑟夫环结束

不过当年萌新的我是不知道这么个东西的 ，但是差不多想明白了其规律性，假设m个土匪，那么第一轮死亡的人编号为k的倍数，第二轮死亡的依次是k+1，2K+2，3K+3……

(m-1)/(k-1)为该周期m前面死亡的人数，即m之前所对应的差值

\#include<stdio.h>  
int kill(int n,int k) //杀人游戏  
\{if(n==k) //如相等，则最后一个人死亡  
return k;  
int m;m=kill(n-n/k,k); //杀人游戏递归 m为最后编号 //printf("%d\\n",m);  
return (m-1)/(k-1)+m; //找到m后还原上轮m编号 /*m-1为当前轮m前面的人，因为上轮已经死人了，所以是k-1 (m-1)/(k-1)为该周期m前面死亡的人数，即m之前所对应的差值*/  
\}  
int main()\{  
int t,x;  
int n,k; //n为剩余人数，k为周期数  
scanf("%d",&t);  
while(t–)\{  
scanf("%d%d",&n,&k);  
x=kill(n,k);  
printf("%d\\n",x);  
\}  
return 0;  
\}

[http_baike.baidu.com_link_url_RnHDh0kg0uEeh-H_a4ZRMI1d3pZ1qbJYpwLdcY3VvZ8LwLxsVNmGODmIilRKhgBnmI3phVO_lLOavxcQgALT1]: http://baike.baidu.com/link?url=RnHDh0kg0uEeh-H_a4ZRMI1d3pZ1qbJYpwLdcY3VvZ8LwLxsVNmGODmIilRKhgBnmI3phVO_lLOavxcQgALT1_