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

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

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