【文章內(nèi)容簡介】 報 0。 現(xiàn)在我們把他們的編號做一下轉(zhuǎn)換： k 0 k+1 1 k+2 2 ... ... k2 n2 k1 n1 變換后就完完全全成為了 (n1)個人報數(shù)的子問題 . 假如我們知道這個子問題的解：例如 x是最終的勝利者，那么根據(jù)上面這個表把這個 x變回去不剛好就是 n個人情況的解嗎？！！變回去的公式很簡單，可以推出來 為 ： x39。 =(x+k)%n 如何知道 (n1)個人報數(shù)的問題的解？對，只要知道 (n2)個人的解就行了。 (n2)個人的解呢？當然是先求 (n3)的情況 這顯然就是一個倒推問題！ 下面寫遞推公式： 令 f[i]表示 i個人玩游戲報 m退出最后勝利者的編號，最后的結(jié)果自然是 f[n] f[1]=0。 f[i]=(f[i1]+m)%i。 (i1) 有了這個公式，我們要做的就是從 1n順序算出 f[i]的數(shù)值，最后結(jié)果是 f[n]。因為實際生活中編號總是從 1開始，我們輸出 f[n]+1 由于是逐級遞推，不需要保存每個 f[i]，程序也是異常簡單： 翻譯成 C 語言如下代碼所示 int main() { int n, m, i, s=0。 scanf(%d%d, amp。n, amp。m)。 for (i=2。 i =n。 i++) s=(s+m)%i。 printf (The winner is %d\n, s+1)。 } 類似的匯編代碼亦可推之 . 武漢理工大學《匯編語言程序設計課程設計報告》 9 【 流程框圖 】 省略部分細節(jié) ,詳見算法描述 武漢理工大學《匯編語言程序設計課程設計報告》 10 （含 測試方法和測試結(jié)果 ） 源程序 DATA SEGMENT TABLE LABEL WORD COUNT = 1 REPT 200 DW COUNT COUNT = COUNT + 1 ENDM ?？梢赃x擇編號數(shù)的上限 PRINT1 DB 39。Please input the number of the people(less than 200):$39。 。用 CX寄存器保存編號數(shù) PRINT2 DB 39。Please the flag:$39。用 DI 寄存器保存標志值 MESS DB 39。$39。 DATA ENDS CODE SEGMENT ASSUME CS:CODE,DS:DATA START: MOV AX,DATA MOV DS,AX LEA SI,TABLE 。SI 指向首地址， BX 作為移動指針 MOV BX,0 MOV DX,0 。DX 作為計數(shù)器 CALL PRINT 。執(zhí)行該子程序后返回輸入的編號數(shù)和標志值 ,分別為 CX和 DI L0:MOV AX,0 L1:MOV AX,[SI+BX] 。依次取出 TABLE 中的數(shù)據(jù) CMP AX,0 JZ L2 。AX 等于 0的時候跳轉(zhuǎn) CMP AX,0FFH JZ L3 。AX 等于 201 的時候跳轉(zhuǎn) ADD DX,1 。計數(shù)器加 1 CMP DX,DI 。比較與標志值是否一致 JZ L4 。一致則跳轉(zhuǎn) L2:ADD BX,2 。取下一個數(shù)據(jù) JMP L1 L3:MOV BX,0 。重置 JMP L1 L4:MOV AX,[SI+BX] 。取出數(shù)值 CALL OUTDEC MOV AX,0 武漢理工大學《匯編語言程序設計課程設計報告》 11 MOV [SI+BX],AX MOV DX,0 LOOP L0 MOV AH,4CH INT 21H OUTDEC PROC PUSH AX PUSH DX PUSH CX PUSH BX MOV CL,100 DIV CL 。AX=AX/100,AL 保存商 ,AH 保存余數(shù) MOV BL,AH MOV DL,AL OR DL,30H 。轉(zhuǎn)換成字符輸出 MOV AH,02H 。顯示輸出 DL=輸出字符 INT 21H MOV CL,10 MOV BH,0 MOV AX,BX DIV CL MOV DL,AL MOV BL,AH OR DL,30H MOV AH,02H 。顯示輸出 DL=輸出字符 INT 21H MOV DL,BL OR DL,30H MOV AH,02H 。顯示輸出 DL=輸出字符 INT 21H POP BX POP CX