1、微機(jī)原理與接口技術(shù)(B)課程設(shè)計(jì)設(shè)計(jì)題目：大數(shù)階乘與排序院 系計(jì)算機(jī)科學(xué)與工程 專業(yè)班級(jí) 軟件工程122 組 員 夏曉鵬 3120921055 （組長） 黃 康 3120921058 翁林濤 3120921054 指導(dǎo)教師 王戰(zhàn)敏 起始時(shí)間2015.6.292015.7.3 2015 年 春季 學(xué)期設(shè)計(jì)任務(wù) （1）基本要求：用匯編語言編寫設(shè)計(jì)一個(gè)求解大數(shù)的階乘精確值的程序。設(shè)計(jì)提示：采用字節(jié)型數(shù)組存放階乘結(jié)果的每個(gè)數(shù)字位，采用逐位相乘，再對(duì)每一位規(guī)格化來實(shí)現(xiàn)。進(jìn)一步設(shè)計(jì)要求：輸出階乘結(jié)果的位數(shù)及尾零的個(gè)數(shù)。 （2）基本要求：用匯編語言編寫設(shè)計(jì)快速排序和希爾排序。設(shè)計(jì)提示：注意設(shè)置合理堆棧容量，

2、以避免堆棧溢出。進(jìn)一步設(shè)計(jì)要求：動(dòng)態(tài)顯示排序過程。 評(píng)語(教師填寫) 組號(hào)：（ ）序號(hào)：（ ）任務(wù)：（ 7 , 8 ）題目：求解大數(shù)的階乘，排序成員學(xué)號(hào)姓名分配任曉鵬排序及編碼設(shè)計(jì)23120921058黃康求解大數(shù)的階乘及編碼設(shè)計(jì)33120921054翁林濤尋找參考資料輔助編程算法分析及總結(jié)微機(jī)原理課程設(shè)計(jì)選題表題目1、2不選，題目7、8合并目錄一系統(tǒng)總模塊設(shè)計(jì)41.大數(shù)階乘42.快速排序4二小組任務(wù)分工5 1.大數(shù)階乘原理設(shè)計(jì)52.排序原理設(shè)計(jì)5 3. 希爾排序原理設(shè)計(jì).5三子系統(tǒng)設(shè)計(jì)方案51.大數(shù)階乘52.快速排序5 3. 希爾排序.,.6四子系統(tǒng)主要程序流程圖6

3、1.大數(shù)階乘流程圖62.快速排序流程圖7五方案實(shí)現(xiàn)與測(cè)試91.1大數(shù)階乘源代碼91.2大數(shù)階乘測(cè)試結(jié)果截圖122.1快速排序源代碼132.2快速排序測(cè)試結(jié)果截圖15六小組設(shè)計(jì)和心得體會(huì)16七小組設(shè)計(jì)總結(jié).17八參考文獻(xiàn).17一 系統(tǒng)總模塊設(shè)計(jì)模塊圖：大數(shù)階乘：快速排序：二小組任務(wù)分工描述每個(gè)人應(yīng)完成的任務(wù)：我們?cè)谔幚硪粋€(gè)大于一定范圍的數(shù)的階乘時(shí)，無論使用什么類型去保存運(yùn)算結(jié)果都必然會(huì)發(fā)生溢出，這勢(shì)必會(huì)導(dǎo)致運(yùn)算結(jié)果出錯(cuò)。使用數(shù)組來模擬數(shù)字，這樣無論結(jié)果數(shù)字有多大，只要數(shù)組的長度夠長就能表示出來，用這個(gè)辦法可以進(jìn)行大數(shù)據(jù)的運(yùn)算。2排序原理設(shè)計(jì)：快速排序原理:首先任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一

4、個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過程稱為一趟快速排序。3排序原理設(shè)計(jì)：希爾排序原理: 先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量=1(<<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂Ｈ酉到y(tǒng)設(shè)計(jì)方案 大數(shù)階乘：核心思想就是把計(jì)算結(jié)果每一位上的數(shù)字保存到一個(gè)數(shù)組成員中，例如：把112保存至數(shù)組中，保存結(jié)果應(yīng)該是result0 2result1 1resu

5、lt2 1把整個(gè)數(shù)組看成一個(gè)數(shù)字，這個(gè)數(shù)字和一個(gè)數(shù)相乘的時(shí)候，需要每一位都和這個(gè)乘數(shù)進(jìn)行相乘運(yùn)算還需要把前一為的進(jìn)位加上。運(yùn)算方法和小學(xué)數(shù)學(xué)是一樣的，乘積的個(gè)位是當(dāng)前位上應(yīng)該表示的數(shù)字，10位以上的需要進(jìn)位。因?yàn)槌藬?shù)不可能大于10000，所以乘數(shù)和一個(gè)小于10的書相乘的時(shí)候不會(huì)大于100000，再加上前一位的進(jìn)位用一個(gè)int型數(shù)據(jù)來保持這個(gè)結(jié)果就沒有問題。寫法如下：int 結(jié)果 = resultx * 乘數(shù) + 進(jìn)位;每一位的計(jì)算結(jié)果有了，把這個(gè)結(jié)果的個(gè)位數(shù)拿出來放到這個(gè)數(shù)組元素上：resultx = 結(jié)果%10;接下來的工作就是計(jì)算出進(jìn)位：進(jìn)位 = 結(jié)果 / 10;這樣一位一位的把整個(gè)數(shù)組計(jì)

6、算一遍，最后可能還有進(jìn)位，用同樣的方法，把進(jìn)位的數(shù)值拆成單個(gè)數(shù)字，放到相應(yīng)的數(shù)組元素中。最后輸出一下結(jié)果，從最高位吧數(shù)字打印一遍就OK了。快速排序：1）設(shè)置兩個(gè)變量i、j，排序開始的時(shí)候：i=0，j=N-1；2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A0；3）從j開始向前搜索，即由后開始向前搜索(j-)，找到第一個(gè)小于key的值A(chǔ)j，將Aj賦給Ai；4）從i開始向后搜索，即由前開始向后搜索(i+)，找到第一個(gè)大于key的Ai，將Ai賦給Aj；5）重復(fù)第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中Aj不小于key,4中Ai不大于key的時(shí)候改變j、i的值，使得

7、j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變。另外，i=j這一過程一定正好是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束）。希爾排序：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹顾摹⒆酉到y(tǒng)主要程序流程圖大數(shù)階乘：快速排序：五 方案實(shí)現(xiàn)與測(cè)試大數(shù)階乘源代碼：.datainfoMsg byte &#

8、39;請(qǐng)輸入你要求的階乘',13,10,0errorMsg byte '你輸入的數(shù)小于0',13,10,0account byte '階乘的位數(shù)為：',13,10,0zeroaccount byte '尾零的個(gè)數(shù)為：',13,10,0inputnum dword 0bufferNum dword 100000 dup (0),0arrayNum dword 1carry dword 0.code start:START:mov eax,1mov bufferNum0,eaxmov eax,offset infoMsgcall dispms

9、gcall readsidmov inputnum ,eaxcmp eax,0jl DONE;輸入的數(shù)小于0;輸入的數(shù)不小于0;完成計(jì)算 外層循環(huán)用ebxmov ebx,2 OUTER:cmp ebx,inputnumjg FINISH ;內(nèi)層循環(huán)1用ecx mov ecx,1mov eax,0mov carry,eaxFLAG1:cmp ecx,arrayNum ;相當(dāng)于判斷j<=digit？jg OUTIN;大于1跳出內(nèi)循環(huán) mov eax,ebxmul bufferNumecx*4-4add eax,carry ;這三句與c中這句相當(dāng)：temp=aj-1*i+carry;adc e

10、dx,0;還要加進(jìn)位標(biāo)志，也就是說加了上一步的進(jìn)位push ebxmov ebx,0ahdiv ebxpop ebxmov bufferNumecx*4-4,edxmov carry,eaxinc ecxjmp FLAG1;內(nèi)層循環(huán)2用carry OUTIN:cmp carry,0jz FLAG2;mov eax,1add arrayNum,eax;所用到的數(shù)組的個(gè)數(shù)mov edx,0mov eax,carrypush ebxmov ebx,0ahdiv ebxpop ebxpush edxmov eax,arrayNumpush ebxmov ebx,04hmul ebxpop ebxsub

11、 eax,4 pop edxmov bufferNumeax,edx;保存余數(shù)到數(shù)組mov edx,0mov eax,carrypush ebxmov ebx,0ahdiv ebxpop ebxmov carry,eaxjmp OUTIN ;循環(huán)保存余數(shù)直到進(jìn)位只剩個(gè)位 FLAG2:inc ebxjmp OUTER;輸出結(jié)果 FINISH:mov ecx,arrayNum FLAG3:cmp ecx,0jle ACCOUNTmov eax,bufferNumecx*4-4call dispsidmov eax,0dec ecxjmp FLAG3;出錯(cuò)顯示信息 DONE:cmp edi,0je

12、ACCOUNTmov eax,offset errorMsgcall dispmsg;顯示結(jié)果的位數(shù) ACCOUNT:call dispcrlfMOV eax,offset accountcall dispmsgMOV eax,arrayNumcall dispuidcall dispcrlf;用來計(jì)算尾0的個(gè)數(shù)mov ecx,1mov edi,0 zero:mov eax,bufferNumecx*4-4cmp eax,0jne F0inc ediinc ecxcmp ecx,arrayNumjge F0jmp zero F0:MOV eax,offset zeroaccountcall d

13、ispmsgmov eax,edicall dispuidcall dispcrlfmov ecx,arrayNum CLEAN:cmp ecx,0je STARTmov eax,0mov bufferNumecx*4-4,0dec ecxjmp CLEANexit 0end start大數(shù)階乘測(cè)試結(jié)果截圖：快速排序源代碼： includelib msvcrt.lib ;這里是引入類庫 相當(dāng)于 #include了 printf PROTO C:PTR DWORD, :VARARG ;聲明一下我們要用的函數(shù)頭 MAXSIZE =1000.data count dword 0 arrBytes D

14、WORD MAXSIZE dup (0) szFormat BYTE " %d", 09h, 0 szFormat1 BYTE 0ah, 0 ;換行 in_msg byte '請(qǐng)輸入排序數(shù)據(jù)(000 結(jié)束)',10,13,0 out_msg byte '快速(降序)排序結(jié)果如下：',10,13,0 notice byte '.',10,13,0.code dumparray PROC array:PTR DWORD, arrsize:DWORDmov eax,offset noticecall dispmsg mov EBX,

15、 offset arrBytes mov ECX, arrsize xor ESI, ESI Tag1:push ecx INVOKE printf, OFFSET szFormat, DWORD PTR EBX+ESI;invoke 調(diào)用API函數(shù) pop ecx add ESI, 4 LOOP Tag1 INVOKE printf, OFFSET szFormat1 RET dumparray ENDP readInArray proc pCount:DWORD xor ebx,ebx again:mov eax,offset in_msgcall dispmsgxor eax,eaxca

16、ll readsidcmp eax,000je DONEmov arrBytes4*ebx,eaxinc ebxjmp again DONE:mov count,ebx ret readInArray endpqsort PROC array:PTR DWORD, lowitem:DWORD, highitem:DWORD;排序 LOCAL pivot:DWORD ;定義局部變量 中點(diǎn) MOV EBX, array MOV EDX, lowitem MOV ESI, lowitem MOV EDI, highitem CMP ESI, EDI JGE TagEnd MOV EAX, DWORD

17、 PTR EBX+EDX*4 MOV pivot, EAX MOV EAX, EDI SUB EAX, ESI MOV ECX, EAX INC EDX Tag1: MOV EAX, pivot CMP EAX, DWORD PTR EBX+EDX*4 JL Tag2 JMP Tag3 Tag2: MOV EAX, DWORD PTR EBX+EDX*4 XCHG EAX, DWORD PTR EBX+ESI*4+4 MOV DWORD PTR EBX+EDX*4, EAX MOV EAX, DWORD PTR EBX+ESI*4 XCHG EAX, DWORD PTR EBX+ESI*4+4

18、 MOV DWORD PTR EBX+ESI*4, EAX INC ESI ;ESI始終指向中心數(shù)，EDX指向下一個(gè)數(shù) Tag3: INC EDX LOOP Tag1 DEC ESI PUSH ESI INVOKE qsort, array, lowitem, ESI ;對(duì)前半段排序 POP ESI INC ESI INC ESI ;入棧時(shí)ESI少一個(gè)，對(duì)于出棧先加1，投入計(jì)算時(shí)再加1 INVOKE qsort, array, ESI, highitem ;對(duì)后半段排序 TagEnd: RETqsort ENDPmain : invoke readInArray ,addr count;讀入數(shù)

19、列到數(shù)組 xor eax,eax INVOKE dumparray, ADDR arrBytes, count;輸出排序前數(shù)列 MOV EAX, count DEC EAX INVOKE qsort, ADDR arrBytes, 0, EAX;排序 mov eax,offset out_msg call dispmsg INVOKE dumparray, ADDR arrBytes, count;輸出排序后數(shù)列 RETend main快速排序測(cè)試結(jié)果截圖：六 小組設(shè)計(jì)和心得體會(huì)黃康：在這接近一周的時(shí)間里，我主要做大數(shù)階乘的實(shí)現(xiàn)，首先由于它和我們傳統(tǒng)意義上計(jì)算階乘有著很大的區(qū)別，所以接受一個(gè)新的理念就是一件難事，然后把其轉(zhuǎn)換為程序代碼的操作又是一大難事。所以以后要多多動(dòng)手，想的和做的還有很大區(qū)別。在實(shí)現(xiàn)過程中我主要參考以前c語言程序的思想，但還是碰到了很多問題，尤其在于實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)的過程中由于計(jì)算機(jī)位數(shù)的限制，我采用了數(shù)組進(jìn)行存儲(chǔ)，結(jié)果過程中還是遇到了很多問題，最后都一一解決。 夏曉鵬： 通過一星期的學(xué)習(xí)，我學(xué)會(huì)了通過匯編語言