大數(shù)階乘與快速排序算法(匯編)

1、微機原理課程設計說明書設計題目：大數(shù)階乘與排序?qū)?業(yè) 班 級 學 生 指導教師 2014 年 春季 學期 目錄目錄1一課設目的與要求21.課設目的22.題目要求2二基本原理2 1.大數(shù)階乘原理設計22.排序原理設計2三架構(gòu)設計2四方案實現(xiàn)與測試3五分析總結(jié)6六參考文獻6一課設目的與要求1.課設目的：檢驗和提高學生在匯編語言程序設計，微機原理與接口應用方面分析問題與解決問題的能力2.題目要求 ：1).要求實現(xiàn)用匯編語言編寫設計一個求解大數(shù)的階乘精確值的程序；采用字節(jié)型數(shù)組存放階乘結(jié)果的每個數(shù)字位，采用逐位相乘，再對每一位規(guī)格化來實現(xiàn)；輸出結(jié)成結(jié)果的位數(shù)及尾零的個數(shù)。2).用匯編語言編寫設計快速排

2、序與希爾排序程序，注意合理使用堆棧，以避免堆棧溢出，進一步動態(tài)顯示排序過程。二基本原理1.大數(shù)階乘原理設計：我們在處理一個大于一定范圍的數(shù)的階乘時，無論使用什么類型去保存運算結(jié)果都必然會發(fā)生溢出，這勢必會導致運算結(jié)果出錯。使用數(shù)組來模擬數(shù)字，這樣無論結(jié)果數(shù)字有多大，只要數(shù)組的長度夠長就能表示出來，用這個辦法可以進行大數(shù)據(jù)的運算。2排序原理設計：快速排序原理:首先任意選取一個數(shù)據(jù)（通常選用數(shù)組的第一個數(shù)）作為關鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序。三架構(gòu)設計核心思想就是把計算結(jié)果每一位上的數(shù)字保存到一個數(shù)組成員中，例如：把112保存至數(shù)組

3、中，保存結(jié)果應該是result0 2result1 1result2 1把整個數(shù)組看成一個數(shù)字，這個數(shù)字和一個數(shù)相乘的時候，需要每一位都和這個乘數(shù)進行相乘運算還需要把前一為的進位加上。運算方法和小學數(shù)學是一樣的，乘積的個位是當前位上應該表示的數(shù)字，10位以上的需要進位。因為乘數(shù)不可能大于10000，所以乘數(shù)和一個小于10的書相乘的時候不會大于100000，再加上前一位的進位用一個int型數(shù)據(jù)來保持這個結(jié)果就沒有問題。寫法如下：int 結(jié)果 = resultx * 乘數(shù) + 進位;每一位的計算結(jié)果有了，把這個結(jié)果的個位數(shù)拿出來放到這個數(shù)組元素上：resultx = 結(jié)果%10;接下來的工作就是計

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

5、值，即3中Aj不小于key,4中Ai不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i=j這一過程一定正好是i+或j-完成的時候，此時令循環(huán)結(jié)束）。希爾排序原理：先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止4 方案實現(xiàn)與測試大數(shù)階乘源代碼：inc

6、lude io32.inc.datainfoMsg byte '請輸入你要求的階乘',13,10,0errorMsg byte '你輸入的數(shù)小于0',13,10,0account byte '階乘的位數(shù)為：',13,10,0zeroaccount byte '尾零的個數(shù)為：',13,10,0inputnum dword 0bufferNum dword 100000 dup (0),0temp dword 0arrayNum dword 1carry dword 0.codestart:mov eax,1mov bufferNum

7、0,eaxmov eax,offset infoMsgcall dispmsgcall readsidmov inputnum ,eaxcmp eax,0jl DONE;輸入的數(shù)小于0;輸入的數(shù)不小于0mov ebx,2OUTER:cmp ebx,inputnumjg FINISH;完成計算 外層循環(huán)用ebxmov ecx,1mov eax,0mov carry,eaxFLAG1:cmp ecx,arrayNumjg OUTIN;大于1跳出內(nèi)循環(huán) 內(nèi)層循環(huán)用ecxmov eax,ebxmul bufferNumecx*4-4add eax,carryadc edx,0;還要加進位標志，也就是說

8、加了上一步的進位push ebxmov ebx,0ahdiv ebxpop ebxmov bufferNumecx*4-4,edxmov carry,eaxinc ecxjmp FLAG1OUTIN:cmp carry,0jz FLAG2mov eax,1add arrayNum,eax;所用到的數(shù)組的個數(shù)mov edx,0mov eax,carrypush ebxmov ebx,0ahdiv ebxpop ebxpush edxmov eax,arrayNumpush ebxmov ebx,04hmul ebxpop ebxsub eax,4 pop edxmov bufferNumeax,

9、edx;保存余數(shù)到數(shù)組mov edx,0mov eax,carrypush ebxmov ebx,0ahdiv ebxpop ebxmov carry,eaxjmp OUTIN ;循環(huán)保存余數(shù)直到進位只剩個位FLAG2:inc ebxjmp OUTERFINISH:;輸出結(jié)果mov ecx,arrayNumFLAG3:cmp ecx,0jle OVERmov eax,bufferNumecx*4-4call dispsidmov eax,0dec ecxjmp FLAG3DONE:cmp edi,0je OVERmov eax,offset errorMsgcall dispmsgOVER:c

10、all dispcrlfMOV eax,offset accountcall dispmsgMOV eax,arrayNumcall dispuidcall dispcrlfmov ecx,1mov edi,0zero:mov eax,bufferNumecx*4-4cmp eax,0jne F0inc ediinc ecxcmp ecx,arrayNumjge F0jmp zeroF0:MOV eax,offset zeroaccountcall dispmsgmov eax,edicall dispuidcall dispcrlfexit 0end start快速排序源代碼：include

11、 io32.inc includelib msvcrt.lib ;這里是引入類庫 相當于 #include了 printf PROTO C :PTR DWORD, :VARARG ;聲明一下我們要用的函數(shù)頭 MAXSIZE =1000.data count dword 0 arrBytes DWORD MAXSIZE dup (0) szFormat BYTE " %d", 09h, 0 szFormat1 BYTE 0ah, 0 ;換行 in_msg byte '請輸入排序數(shù)據(jù)(-1 結(jié)束)',10,13,0 out_msg byte '快速(降序

12、)排序結(jié)果如下：',10,13,0 notice byte '.testing.',10,13,0.code dumparray PROC array:PTR DWORD, arrsize:DWORDmov eax,offset noticecall dispmsg mov EBX, offset arrBytes mov ECX, arrsize xor ESI, ESI Tag1:push ecx INVOKE printf, OFFSET szFormat, DWORD PTR EBX+ESI pop ecx add ESI, 4 LOOP Tag1 INVOKE

13、 printf, OFFSET szFormat1 RET dumparray ENDP readInArray proc pCount:DWORD xor ebx,ebx again:mov eax,offset in_msgcall dispmsgxor eax,eaxcall readsidcmp eax,0jl DONEmov arrBytes4*ebx,eaxinc ebxjmp again DONE:mov count,ebx ret readInArray endpqsort PROC array:PTR DWORD, lowitem:DWORD, highitem:DWORD

14、LOCAL pivot:DWORD ;定義局部變量 MOV EBX, array MOV EDX, lowitem MOV ESI, lowitem MOV EDI, highitem CMP ESI, EDI JGE TagEnd MOV EAX, DWORD 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

15、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 MOV DWORD PTR EBX+ESI*4, EAX INC ESI Tag3: INC EDX LOOP Tag1 DEC ESI PUSH ESI INVOKE qsort, array, lowitem, ESI POP ESI INC ESI INC ESI INVOKE qsort, array, ESI, highitem TagEnd: RETqsort ENDPmain : invoke readInArray ,addr count xor eax,eax INVOKE dumparray, ADDR arrBytes, count MOV EAX, count DEC EAX INVOKE qsort, ADDR arrBytes, 0, EAX mov eax,offset out_msg call dispmsg INVOKE dumparray, ADDR arrBytes, count RETend main大數(shù)階乘測試結(jié)果截圖：快速排序測試結(jié)果截圖：