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

此文檔收集于網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系網(wǎng)站刪除學(xué) 號： 0120910340228匯編課程設(shè)計題 目約瑟夫環(huán)程序設(shè)計學(xué) 院計算機科學(xué)與技術(shù)學(xué)院專 業(yè)計算機科學(xué)與技術(shù)專業(yè)班 級計算機科學(xué)與技術(shù)0902班姓 名 XX指導(dǎo)教師 XX2011年12月30日課程設(shè)計任務(wù)書學(xué)生姓名： XX 專業(yè)班級 XX 指導(dǎo)教師： XX 工作單位：計算機科學(xué)與技術(shù)學(xué)院 _題目: 約瑟夫環(huán)程序設(shè)計初始條件：理論：完成了匯編語言程序設(shè)計課程，對微機系統(tǒng)結(jié)構(gòu)和80系列指令系統(tǒng)有了較深入的理解，已掌握了匯編語言程序設(shè)計的基本方法和技巧。實踐：完成了匯編語言程序設(shè)計的4個實驗，熟悉了匯編語言程序的設(shè)計環(huán)境并掌握了匯編語言程序的調(diào)試方法。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）進一步理解和掌握較復(fù)雜程序的設(shè)計方法，掌握子程序結(jié)構(gòu)的設(shè)計和友好用戶界面的設(shè)計。具體的設(shè)計任務(wù)及要求：1） 有 n個人圍成一圈，他們的編號為1到n。第一個人從1開始順序報數(shù)，凡報到m時，該人退出圈子。其后的人再從1開始順序報數(shù)，直到最后的一個人退出圈子為止。輸出依次退出圈子人的序號。n和m的值從鍵盤輸入，且均小于200。2） 程序采用子程序結(jié)構(gòu)，結(jié)構(gòu)清晰；3） 友好清晰的用戶界面，能識別輸入錯誤并控制錯誤的修改。在完成設(shè)計任務(wù)后，按要求撰寫課程設(shè)計說明書；對課程設(shè)計說明書的具體要求請見課程設(shè)計指導(dǎo)書。閱讀資料：1）IBMPC匯編語言程序設(shè)計實驗教程實驗2.42）IBMPC匯編語言程序設(shè)計（第2版）例6.11時間安排：設(shè)計安排一周：周1、周2：完成系統(tǒng)分析及設(shè)計。周3、周4：完成程序調(diào)試，和驗收。周5：撰寫課程設(shè)計報告。指導(dǎo)教師簽名： 年 月 日系主任（或責任教師）簽名： 年 月 日目 錄1.需求說明 42.設(shè)計說明 4 2.1 簡要分析 4 2.2 概要設(shè)計 4 2.2.1 主要模塊 4 2.2.2 主函數(shù)結(jié)構(gòu).73.算法描述. 8 3.1 算法描述. 8 3.2 流程框圖 94.源程序與執(zhí)行結(jié)果 10 4.1 源程序 10 4.2 執(zhí)行結(jié)果15 4.2.1 測試方法15 4.2.2 測試結(jié)果.15 4.3 調(diào)試結(jié)果 185.使用說明.196.總結(jié)20約瑟夫環(huán)程序設(shè)計1.需求說明4） 有 n個人圍成一圈，他們的編號為1到n。第一個人從1開始順序報數(shù)，凡報到m時，該人退出圈子。其后的人再從1開始順序報數(shù)，直到最后的一個人退出圈子為止。輸出依次退出圈子人的序號。n和m的值從鍵盤輸入，且均小于200。5） 程序采用子程序結(jié)構(gòu)，結(jié)構(gòu)清晰；6） 友好清晰的用戶界面，能識別輸入錯誤并控制錯誤的修改。2.設(shè)計說明2.1 簡要分析 要正確、友好地完成用匯編語言設(shè)計約瑟夫環(huán)，我們應(yīng)該完成以下幾個功能：（1） 相關(guān)的交互提示用語（2） 定義的數(shù)據(jù)段中包含0-200（3） 編號數(shù)n的輸入（4） 標志數(shù)m的輸入（5） 輸入設(shè)置為只允許輸入三位數(shù)字,其余均不顯示（6） 顯示的結(jié)果是所有的退出序列,并使用箭標連接2.2 概要設(shè)計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）編號數(shù)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）標志數(shù)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 主函數(shù)結(jié)構(gòu)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?，F(xiàn)在我們把他們的編號做一下轉(zhuǎn)換：k - 0k+1 - 1k+2 - 2.k-2 - n-2k-1 - n-1變換后就完完全全成為了(n-1)個人報數(shù)的子問題.假如我們知道這個子問題的解：例如x是最終的勝利者，那么根據(jù)上面這個表把這個x變回去不剛好就是n個人情況的解嗎？！變回去的公式很簡單，可以推出來為：x =(x+k)%n如何知道(n-1)個人報數(shù)的問題的解？對，只要知道(n-2)個人的解就行了。(n-2)個人的解呢？當然是先求(n-3)的情況 - 這顯然就是一個倒推問題！下面寫遞推公式：令fi表示i個人玩游戲報m退出最后勝利者的編號，最后的結(jié)果自然是fnf1=0;fi=(fi-1+m)%i; (i1)有了這個公式，我們要做的就是從1-n順序算出fi的數(shù)值，最后結(jié)果是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作為計數(shù)器 CALL PRINT ;執(zhí)行該子程序后返回輸入的編號數(shù)和標志值,分別為CX和DIL0: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 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 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 ;輸入編號數(shù)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 ;轉(zhuǎn)換成實際數(shù)值 MOV CX,AX MOV BX,CX ;將最高位數(shù)值存入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 ;轉(zhuǎn)換成實際數(shù)值 MOV DX,10 MUL DX MOV CX,AX MOV AX,BX ;將最高位數(shù)值存入AX MOV BX,100 MUL BX ;將最高位數(shù)乘以100,作為百位 ADD CX,AX ;把百位數(shù)存入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 ;把個位數(shù)存入CX,并入棧保存 PUSH CX MOV AX,CX MOV CX,2 MUL CX ;計算在TABLE中所對應(yīng)的偏移字節(jié) MOV BP,AX MOV AX,SI+BP ;取出TABLE中對應(yīng)的數(shù)值 MOV AX,0FFH MOV SI+BP,AX CALL CTRL ;換行 LEA DX,PRINT2 MOV AH,09H ;顯示字符串 INT 21H CALL CTRL ;換行 n4:MOV AH,07H ;輸入標志數(shù)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 ;轉(zhuǎn)換成實際數(shù)值 MOV CX,AX MOV BX,CX ;將最高位數(shù)值存入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 ;轉(zhuǎn)換成實際數(shù)值 MOV DX,10 MUL DX MOV CX,AX MOV AX,BX ;將最高位數(shù)值存入AX MOV BX,100 MUL BX ;將最高位數(shù)乘以100,作為百位 ADD CX,AX ;把百位數(shù)存入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 ;把個位數(shù)存入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í)行結(jié)果4.2.1 測試方法 本次測試我們采用的是通過提示用語，依次輸入編號數(shù)和標志數(shù),都為三位數(shù),未滿100的數(shù)高位為0. 輸入的測試數(shù)據(jù)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的錯誤測試另外測試過程中嘗試輸入除數(shù)字以外的字符是無法顯示的,這點無法截圖顯示4.2.2 測試結(jié)果測試1測試2測試3 測試4錯誤結(jié)果分析：數(shù)據(jù)段之定義到200,事實上可以擴展定義到200-999如下圖所示:4.3調(diào)試結(jié)果 使用debug命令檢查程序的數(shù)據(jù)段是否出錯5.使用說明 本次課程設(shè)計使用第三方的匯編IDE-WinMasm配合MASM 5.0進行實驗,IDE截圖如下:操作過程為:先編寫源代碼保存為Joseph.asm,然后在IDE中新建工程,經(jīng)過編譯后在x86系統(tǒng)環(huán)境下運行編譯的程序即可得出結(jié)果.6.總結(jié) 本次匯編語言課程設(shè)計是約瑟夫環(huán)的程序設(shè)計,之前在C+語言以及數(shù)據(jù)結(jié)構(gòu)的課程中均有過了解,所以這次上手還算比較容易,但是中途也遇到了匯編程序特有的難題,那就是輸入的問題。課程設(shè)計的要求是輸入兩個小于200的整數(shù),然而匯編語言中規(guī)定的中斷功能一次只能輸入一個字符,這與題目要求相悖甚遠,一時竟陷入了編程困惑中,最后經(jīng)過簡單的思考發(fā)現(xiàn)只需要多次使用07H或01H中斷就可以完成這個