约瑟夫问题的Python和C++求解方法

么是约瑟夫问题？
约瑟夫问题是一个有趣的数学游戏，游戏规则如下：
1、N个人围成一个圈，编号从1开始，依次到N。
2、编号为M的游戏参与者开始报数，报数从1开始，后面的人报数接龙，直到K为止，报数为K的人将出局。
3、出局者的下一个玩家接着从1开始报数，如此循环，直到剩下一个玩家时游戏结束，这个玩家就是游戏获胜者。
那么问题来了，哪个编号是游戏获胜者呢？
下面通过简单的几行python/' target='_blank'>python代码来解决这个问题：

#!/usr/bin/env Python # Joseph Problem def joseph(total, begins, count):   queue = range(1, total + 1)   death = (begins + count - 2) % len(queue)   for times in range(total - 1):     print 'out: ', queue[death]     del queue[death]     death = (death + count -1) % len(queue)   print 'survivor: ', queue[0] 

joseph()函数中，参数total即上面提到的N，begins即M，count及K，每次循环报数out一个编号，最后剩下的survivor便是游戏获胜者。

而C++的通常实现方法如下：

#include <iostream>using namespace std;void main(){ int N=0,C=0; cout<<"Please enter the number of people:N="; cin>>N; cout<<"Please enter:C="; cin>>C; int i=0,j=0,n=N,s=0; int *a=new int [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;}

这是C++语言常见的机试题目，以下程序实现从控制台输入人数N，C并将剔除出队列的人员编号按顺序输出到控制台上。