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

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

2、序與希爾排序程序，注意合理使用堆棧，以避免堆棧溢出，進(jìn)一步動(dòng)態(tài)顯示排序過程。二基本原理1.大數(shù)階乘原理設(shè)計(jì)：我們在處理一個(gè)大于一定范圍的數(shù)的階乘時(shí)，無論使用什么類型去保存運(yùn)算結(jié)果都必然會發(fā)生溢出，這勢必會導(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ù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過程稱為一趟快速排序。三架構(gòu)設(shè)計(jì)核心思想就是把計(jì)算結(jié)果每一位上的數(shù)字保存到一個(gè)數(shù)組成員中，例如：把112保存至數(shù)組

3、中，保存結(jié)果應(yīng)該是result0 2result1 1result2 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í)候不會大于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ì)

4、算出進(jìn)位：進(jìn)位 = 結(jié)果 / 10;這樣一位一位的把整個(gè)數(shù)組計(jì)算一遍，最后可能還有進(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步中，沒找到符合條件的

5、值，即3中Aj不小于key,4中Ai不大于key的時(shí)候改變j、i的值，使得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)橹? 方案實(shí)現(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 '尾零的個(gè)數(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;完成計(jì)算 外層循環(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;還要加進(jìn)位標(biāo)志，也就是說

8、加了上一步的進(jìn)位push ebxmov ebx,0ahdiv ebxpop ebxmov bufferNumecx*4-4,edxmov carry,eaxinc ecxjmp FLAG1OUTIN:cmp carry,0jz FLAG2mov 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 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ù)直到進(jìn)位只剩個(gè)位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 ;這里是引入類庫 相當(dāng)于 #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é)果截圖：