N個人1-N編號，從1循環報數報到M的人退出，最後退出的那個人編號是多少?
設最後壹個退出的人編號J(N,M),據我所知還沒人能把J(N,M)寫成N,M的解析函數式。但是有壹些可供手工和編程計算J(N,M)的算法，下面詳細說壹下(以題目N=1000,M=10為例):
1.模擬，即把每壹趟退出的人都列出來看最後剩下的人編號。這個算法要計算NM次，N=1000,M=10,就是10000次，適合計算機求解，手工不適合
2.有如下的遞推式成立:
J(1,M)=1
J(N,M)=(J(N-1,M)-1+M)MODN+1
XMODY表示X對Y取余數
N=1000時要計算1000次
這種算法同樣只適合計算機求解
3.我自己的壹個算法：
設[X]是X整數部分
(1)每遍歷壹次隊列，人數大約變為原來的9/10
(2)設N個人
A1,A2,A3....,AN-1,AN
從A1開始報數，遍歷壹遍後，還剩下
A1,A2,A3...A9,A11,...A19,A21,...A29,A31....A(N-NMOD10-1),A(N-NMOD10+1)...AN
記這時的隊列為S
不難得到如下結論:
①在這壹次遍歷中最後壹個退出的人是A(N-NMOD10)
②若10|N,最後壹個剩下的是S裏第{J(9N/10,10)}個人
③若NMOD10≠0,且S從1報數最後退出的人編號J(N-[N/10],10)>NMOD10,原隊列最後壹個剩下的是S裏第{J(N-[N/10],10)-NMOD10}個人
④若NMOD10≠0,且S從1報數最後退出的人編號J(N-[N/10],10)≤NMOD10,原隊列最後壹個剩下的是S裏第{N-[N/10]+(J(N-[N/10],10)-NMOD10)}個人
⑤S中的第T個人對應原隊列A1A2...AN的第{[(T-1)/9]*10+(T-1)MOD9+1}個人
⑥N=1,2,...9時,J(N,10)=1,1,2,4,4,2,5,7,8
綜合①-⑥，得到J(N,10)另外壹個遞推式:
J(N,10)=
1,1,2,4,4,2,5,7,8 當N≤9
T=J(N-[N/10],10)-NMOD10,J(N,10)=[(T-1)/9]*10+(T-1)MOD9+1 當J(N-[N/10],10)>NMOD10
T=N-[N/10]+J(N-[N/10],10)-NMOD10,J(N,10)=[(T-1)/9]*10+(T-1)MOD9+1 當J(N-[N/10],10)≤NMOD10
因從N到N-[N/10]遞推變量變為原來的9/10，故這個算法需要計算log[10/9]1000=66次，雖然有點多，但已經可以打草稿算出來，方法是先計算J(9,10)再根據遞推式反推回來。我把每次計算後的N和J(N,10)的結果寫在下面:
N J(N,10)
9 8
10 8
11 7
12 5
13 2
14 12
15 7
16 1
17 11
18 3
19 13
21 13
23 11
25 6
27 26
30 28
33 27
36 23
39 15
43 13
47 6
52 4
57 54
63 56
69 52
76 51
84 52
93 54
103 56
114 57
126 56
139 52
154 53
171 57
189 53
209 48
232 51
257 48
285 47
316 45
351 48
389 43
432 45
480 49
533 51
592 54
657 52
729 47
810 52
900 57
1000 63
由此看出，最後壹人編號是63
妳可以寫個程序驗證這個結果是正確的
這個算法另壹優點是計算次數與N成對數關系，計算復雜度比N次,NM次的要好很多
當N=1000000時，這個算法也只需要計算約log[10/9]100000=132次。
希望回答對妳有所幫助！
民族民間舞是壹個多層次的概念和靈活的界面，可以容納各種程度的處理。民族舞蹈是壹個民族的象征(如孔雀舞，它屬於民族舞蹈)，是壹個民族乃至壹個國家的靈魂。
民族舞蹈的分類
木古古
木鼓舞是古江方白苗族的壹種祭祀舞蹈。木鼓是唯壹的伴奏樂器，鼓手敲打它，形成復雜多變的舞曲曲調。節奏是四六拍。舞蹈動作有五種，壹種是運氣好，前進三步，後退三步，左