约瑟夫问题的Python和C++求解方法
约瑟夫问题是一个有趣的数学游戏,游戏规则如下:
1、N个人围成一个圈,编号从1开始,依次到N。
2、编号为M的游戏参与者开始报数,报数从1开始,后面的人报数接龙,直到K为止,报数为K的人将出局。
3、出局者的下一个玩家接着从1开始报数,如此循环,直到剩下一个玩家时游戏结束,这个玩家就是游戏获胜者。
那么问题来了,哪个编号是游戏获胜者呢?
下面通过简单的几行python代码来解决这个问题:
#!/usr/bin/envpython #JosephProblem defjoseph(total,begins,count): queue=range(1,total+1) death=(begins+count-2)%len(queue) fortimesinrange(total-1): print'out:',queue[death] delqueue[death] death=(death+count-1)%len(queue) print'survivor:',queue[0]
#include<iostream> usingnamespacestd; voidmain() { intN=0,C=0; cout<<"Pleaseenterthenumberofpeople:N="; cin>>N; cout<<"Pleaseenter:C="; cin>>C; inti=0,j=0,n=N,s=0; int*a=newint[N]; for(i=0;i<N;i++) { a[i]=1; } while(0!=n) { s+=a[j]; if(C==s) { a[j]=0; s=0; --n; if(0!=n) { cout<<j+1<<"->"; } else { cout<<j+1<<endl; } } j=(j+1)%N; } delete[]a; }