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

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

這個問題可以用數(shù)學(xué)方法解決。有n個人（編號為0~（n-1）），他們從0開始計數(shù)并從（m-1）退出，剩下的人繼續(xù)從0開始計數(shù)（在使用數(shù)學(xué)方法時，我們應(yīng)該注意從0開始計數(shù)，因為余數(shù)將得到0的解）本質(zhì)上是一個遞歸。n-1人數(shù)與n-1人數(shù)之間存在遞歸關(guān)系。假設(shè)第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//進(jìn)行數(shù)字轉(zhuǎn)換。此時，排隊的是n-1人。經(jīng)過（4）轉(zhuǎn)換，完全成為（n-1）個數(shù)報告的子問題。注意，（1）和（4）是同一個問題，唯一的區(qū)別是數(shù)字。比較（4）和（3）不難看出，（3）中“0”之后的數(shù)字（（n-3）k）%n=k-3，（（n-2）k）%n=k-2，對于（3）中“0”之前的數(shù)字，由于它小于n，也可以看作（0 k）%n=k，（1 k）%n=k 1，因此我們可以得到這樣一個規(guī)則：設(shè)（3）中的某個數(shù)為x”，而（4）中相應(yīng)的數(shù)為x，然后是：X “=（X）k）%n。當(dāng)X是最后一個剩下的人數(shù)時，當(dāng)隊列中只剩下一個人時，很明顯X=0。這時，當(dāng)有兩個人的時候，我們可以回到X對應(yīng)的數(shù)字，當(dāng)有三個人到n個人的時候，我們可以回到X對應(yīng)的數(shù)字，X的序列號就是這個數(shù)字。遞歸表達(dá)式如下：#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}