么是約瑟夫問題？
約瑟夫問題是一個有趣的數學游戲，游戲規則如下：
1、N個人圍成一個圈，編號從1開始，依次到N。
2、編號為M的游戲參與者開始報數，報數從1開始，后面的人報數接龍，直到K為止，報數為K的人將出局。
3、出局者的下一個玩家接著從1開始報數，如此循環，直到剩下一個玩家時游戲結束，這個玩家就是游戲獲勝者。
那么問題來了，哪個編號是游戲獲勝者呢？
下面通過簡單的幾行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并將剔除出隊列的人員編號按順序輸出到控制臺上。
新聞熱點
疑難解答
圖片精選
