匯編課程設計-約瑟夫環(huán)程序設計.doc

此文檔收集于網絡，如有侵權，請聯系網站刪除學 號： 0120910340228匯編課程設計題 目約瑟夫環(huán)程序設計學 院計算機科學與技術學院專 業(yè)計算機科學與技術專業(yè)班 級計算機科學與技術0902班姓 名 XX指導教師 XX2011年12月30日課程設計任務書學生姓名： XX 專業(yè)班級 XX 指導教師： XX 工作單位：計算機科學與技術學院 _題目: 約瑟夫環(huán)程序設計初始條件：理論：完成了匯編語言程序設計課程，對微機系統結構和80系列指令系統有了較深入的理解，已掌握了匯編語言程序設計的基本方法和技巧。實踐：完成了匯編語言程序設計的4個實驗，熟悉了匯編語言程序的設計環(huán)境并掌握了匯編語言程序的調試方法。要求完成的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求）進一步理解和掌握較復雜程序的設計方法，掌握子程序結構的設計和友好用戶界面的設計。具體的設計任務及要求：1） 有 n個人圍成一圈，他們的編號為1到n。第一個人從1開始順序報數，凡報到m時，該人退出圈子。其后的人再從1開始順序報數，直到最后的一個人退出圈子為止。輸出依次退出圈子人的序號。n和m的值從鍵盤輸入，且均小于200。2） 程序采用子程序結構，結構清晰；3） 友好清晰的用戶界面，能識別輸入錯誤并控制錯誤的修改。在完成設計任務后，按要求撰寫課程設計說明書；對課程設計說明書的具體要求請見課程設計指導書。閱讀資料：1）IBMPC匯編語言程序設計實驗教程實驗2.42）IBMPC匯編語言程序設計（第2版）例6.11時間安排：設計安排一周：周1、周2：完成系統分析及設計。周3、周4：完成程序調試，和驗收。周5：撰寫課程設計報告。指導教師簽名： 年 月 日系主任（或責任教師）簽名： 年 月 日目 錄1.需求說明 42.設計說明 4 2.1 簡要分析 4 2.2 概要設計 4 2.2.1 主要模塊 4 2.2.2 主函數結構.73.算法描述. 8 3.1 算法描述. 8 3.2 流程框圖 94.源程序與執(zhí)行結果 10 4.1 源程序 10 4.2 執(zhí)行結果15 4.2.1 測試方法15 4.2.2 測試結果.15 4.3 調試結果 185.使用說明.196.總結20約瑟夫環(huán)程序設計1.需求說明4） 有 n個人圍成一圈，他們的編號為1到n。第一個人從1開始順序報數，凡報到m時，該人退出圈子。其后的人再從1開始順序報數，直到最后的一個人退出圈子為止。輸出依次退出圈子人的序號。n和m的值從鍵盤輸入，且均小于200。5） 程序采用子程序結構，結構清晰；6） 友好清晰的用戶界面，能識別輸入錯誤并控制錯誤的修改。2.設計說明2.1 簡要分析 要正確、友好地完成用匯編語言設計約瑟夫環(huán)，我們應該完成以下幾個功能：（1） 相關的交互提示用語（2） 定義的數據段中包含0-200（3） 編號數n的輸入（4） 標志數m的輸入（5） 輸入設置為只允許輸入三位數字,其余均不顯示（6） 顯示的結果是所有的退出序列,并使用箭標連接2.2 概要設計2.2.1 主要模塊（1）變量的定義DATA SEGMENT TABLE LABEL WORD COUNT = 1 REPT 200 DW COUNT COUNT = COUNT + 1 ENDM PRINT1 DB Please input the number of the people(less than 200):$PRINT2 DB Please the flag:$ MESS DB -$ DATA ENDS（2）編號數n輸入的處理n1:MOV AH,07H INT 21H CMP AL,0 JB n1 CMP AL,9 JA n1 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H MOV CX,AX MOV BX,CX n2:MOV AH,07H INT 21H CMP AL,0 JB n2 CMP AL,9 JA n2 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H MOV DX,10 MUL DX MOV CX,AX MOV AX,BX MOV BX,100 MUL BX ADD CX,AX n3:MOV AH,07H INT 21H CMP AL,0 JB n3 CMP AL,9 JA n3 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H MOV DX,AX ADD CX,DX PUSH CX MOV AX,CX MOV CX,2 MUL CX MOV BP,AX MOV AX,SI+BP MOV AX,0FFH MOV SI+BP,AX CALL CTRL LEA DX,PRINT2 MOV AH,09H INT 21H CALL CTRL （3）標志數m的輸入處理n4:MOV AH,07H INT 21H CMP AL,0JB n4CMP AL,9JA n4MOV DL,ALMOV AH,02HINT 21HMOV AH,0 SUB AL,30H MOV CX,AX MOV BX,CX n5:MOV AH,07H INT 21HCMP AL,0JB n5CMP AL,9JA n5MOV DL,ALMOV AH,02HINT 21H MOV AH,0 SUB AL,30H MOV DX,10MUL DXMOV CX,AXMOV AX,BX MOV BX,100 MUL BX ADD CX,AX n6:MOV AH,07HINT 21HCMP AL,0JB n6CMP AL,9JA n6MOV DL,ALMOV AH,02HINT 21HMOV AH,0SUB AL,30HMOV DX,AXADD CX,DX MOV DI,CX 2.2.2 主函數結構START: MOV AX,DATA MOV DS,AX LEA SI,TABLE MOV BX,0 MOV DX,0; CALL PRINT 3.算法描述【求解思路】我們知道第一個人(編號一定是m%n-1) 出列之后，剩下的n-1個人組成了一個新的約瑟夫環(huán)（以編號為k=m%n的人開始）:k k+1 k+2 . n-2, n-1, 0, 1, 2, . k-2并且從k開始報0。現在我們把他們的編號做一下轉換：k - 0k+1 - 1k+2 - 2.k-2 - n-2k-1 - n-1變換后就完完全全成為了(n-1)個人報數的子問題.假如我們知道這個子問題的解：例如x是最終的勝利者，那么根據上面這個表把這個x變回去不剛好就是n個人情況的解嗎？！變回去的公式很簡單，可以推出來為：x =(x+k)%n如何知道(n-1)個人報數的問題的解？對，只要知道(n-2)個人的解就行了。(n-2)個人的解呢？當然是先求(n-3)的情況 - 這顯然就是一個倒推問題！下面寫遞推公式：令fi表示i個人玩游戲報m退出最后勝利者的編號，最后的結果自然是fnf1=0;fi=(fi-1+m)%i; (i1)有了這個公式，我們要做的就是從1-n順序算出fi的數值，最后結果是fn。因為實際生活中編號總是從1開始，我們輸出fn+1由于是逐級遞推，不需要保存每個fi，程序也是異常簡單：翻譯成C語言如下代碼所示int main() int n, m, i, s=0; scanf(%d%d, &n, &m); for (i=2; i $ 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作為計數器 CALL PRINT ;執(zhí)行該子程序后返回輸入的編號數和標志值,分別為CX和DIL0:MOV AX,0 L1:MOV AX,SI+BX ;依次取出TABLE中的數據 CMP AX,0 JZ L2 ;AX等于0的時候跳轉 CMP AX,0FFH JZ L3 ;AX等于201的時候跳轉 ADD DX,1 ;計數器加1 CMP DX,DI ;比較與標志值是否一致 JZ L4 ;一致則跳轉L2:ADD BX,2 ;取下一個數據 JMP L1 L3:MOV BX,0 ;重置 JMP L1 L4:MOV AX,SI+BX ;取出數值 CALL OUTDEC MOV AX,0 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保存余數 MOV BL,AH MOV DL,AL OR DL,30H ;轉換成字符輸出 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 CMP CX,1 JZ L5 LEA DX,MESS ;顯示箭標 MOV AH,09H INT 21H L5:POP DX POP AX RET OUTDEC ENDP PRINT PROC PUSH AX PUSH DX PUSH BX LEA DX,PRINT1 MOV AH,09H ;顯示字符串 INT 21H CALL CTRL n1:MOV AH,07H ;輸入編號數n不回顯 INT 21H CMP AL,0 ;每次輸入均驗證是否為0-9,否則輸入無效 JB n1 CMP AL,9 JA n1 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H ;轉換成實際數值 MOV CX,AX MOV BX,CX ;將最高位數值存入BX n2:MOV AH,07H INT 21H CMP AL,0 JB n2 CMP AL,9 JA n2 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H ;轉換成實際數值 MOV DX,10 MUL DX MOV CX,AX MOV AX,BX ;將最高位數值存入AX MOV BX,100 MUL BX ;將最高位數乘以100,作為百位 ADD CX,AX ;把百位數存入CX n3:MOV AH,07H INT 21H CMP AL,0 JB n3 CMP AL,9 JA n3 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H MOV DX,AX ADD CX,DX ;把個位數存入CX,并入棧保存 PUSH CX MOV AX,CX MOV CX,2 MUL CX ;計算在TABLE中所對應的偏移字節(jié) MOV BP,AX MOV AX,SI+BP ;取出TABLE中對應的數值 MOV AX,0FFH MOV SI+BP,AX CALL CTRL ;換行 LEA DX,PRINT2 MOV AH,09H ;顯示字符串 INT 21H CALL CTRL ;換行 n4:MOV AH,07H ;輸入標志數m不回顯 INT 21H CMP AL,0 JB n4 CMP AL,9 JA n4 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H ;轉換成實際數值 MOV CX,AX MOV BX,CX ;將最高位數值存入BX n5:MOV AH,07H INT 21H CMP AL,0 JB n5 CMP AL,9 JA n5 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H ;轉換成實際數值 MOV DX,10 MUL DX MOV CX,AX MOV AX,BX ;將最高位數值存入AX MOV BX,100 MUL BX ;將最高位數乘以100,作為百位 ADD CX,AX ;把百位數存入CX n6:MOV AH,07H INT 21H CMP AL,0 JB n6 CMP AL,9 JA n6 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H MOV DX,AX ADD CX,DX ;把個位數存入CX MOV DI,CX ;存入DI CALL CTRL POP CX POP BX POP DX POP AX RET PRINT ENDP CTRL PROC PUSH AX PUSH DX MOV AH,02H MOV DL,0AH ;打印換行符 INT 21H MOV DL,0DH ;打印回車符 INT 21H POP DX POP AX RET CTRL ENDP CODE ENDS END START 4.2 執(zhí)行結果4.2.1 測試方法 本次測試我們采用的是通過提示用語，依次輸入編號數和標志數,都為三位數,未滿100的數高位為0. 輸入的測試數據n與m均小于200,測試類型3種 (1)nm 測試例子:n=100 m=10 (2) nm 測試例子:n=50 m=100(3)n=m 測試例子:n=100 m=100 (4) 大于200的錯誤測試另外測試過程中嘗試輸入除數字以外的字符是無法顯示的,這點無法截圖顯示4.2.2 測試結果測試1測試2測試3 測試4錯誤結果分析：數據段之定義到200,事實上可以擴展定義到200-999如下圖所示:4.3調試結果 使用debug命令檢查程序的數據段是否出錯5.使用說明 本次課程設計使用第三方的匯編IDE-WinMasm配合MASM 5.0進行實驗,IDE截圖如下:操作過程為:先編寫源代碼保存為Joseph.asm,然后在IDE中新建工程,經過編譯后在x86系統環(huán)境下運行編譯的程序即可得出結果.6.總結 本次匯編語言課程設計是約瑟夫環(huán)的程序設計,之前在C+語言以及數據結構的課程中均有過了解,所以這次上手還算比較容易,但是中途也遇到了匯編程序特有的難題,那就是輸入的問題。課程設計的要求是輸入兩個小于200的整數,然而匯編語言中規(guī)定的中斷功能一次只能輸入一個字符,這與題目要求相悖甚遠,一時竟陷入了編程困惑中,最后經過簡單的思考發(fā)現只需要多次使用07H或01H中斷就可以完成這個