約瑟夫問題:M個人圍成一圈，從第一個人開始依次從1到N循環(huán)報數，每當報數為N時此人出圈，直到剩一人為止？這個問題可以用數學方法解決。有n個人（編號為0~（n-1）），他們從0開始計數并從（m-1）退出

約瑟夫問題:M個人圍成一圈，從第一個人開始依次從1到N循環(huán)報數，每當報數為N時此人出圈，直到剩一人為止？

這個問題可以用數學方法解決。有n個人（編號為0~（n-1）），他們從0開始計數并從（m-1）退出，剩下的人繼續(xù)從0開始計數（在使用數學方法時，我們應該注意從0開始計數，因為余數將得到0的解）本質上是一個遞歸。n-1人數與n-1人數之間存在遞歸關系。假設第K個人被刪除，那么0，1，2，3，…，K-2，K-1，K，…，n-1//原始序列（1）0，1，2，3，…，K-2，K，…，n-1//第K個人被刪除，即序列號為K-1的人被刪除。（2） k，k 1，…，n-1，0，1，…，k-2//從序列號k開始，報告0（3）0，1，…，n-k-1，n-k from k 1，…，n-2//進行數字轉換。此時，排隊的是n-1人。經過（4）轉換，完全成為（n-1）個數報告的子問題。注意，（1）和（4）是同一個問題，唯一的區(qū)別是數字。比較（4）和（3）不難看出，（3）中“0”之后的數字（（n-3）k）%n=k-3，（（n-2）k）%n=k-2，對于（3）中“0”之前的數字，由于它小于n，也可以看作（0 k）%n=k，（1 k）%n=k 1，因此我們可以得到這樣一個規(guī)則：設（3）中的某個數為x”，而（4）中相應的數為x，然后是：X “=（X）k）%n。當X是最后一個剩下的人數時，當隊列中只剩下一個人時，很明顯X=0。這時，當有兩個人的時候，我們可以回到X對應的數字，當有三個人到n個人的時候，我們可以回到X對應的數字，X的序列號就是這個數字。遞歸表達式如下：#include<stdio。H>int main（）{int m，N，s=0 scanf（%d%d”，&m，&n）for（int i=2I<=mi）s=（s N）%i printf（%dN”，s 1）返回0}