大数阶乘与快速排序算法-汇编

1、微机原理与接口技术(B)课程设计设计题目：大数阶乘与排序院 系计算机科学与工程 专业班级 软件工程122 组 员 夏晓鹏 3120921055 （组长） 黄 康 3120921058 翁林涛 3120921054 指导教师 王战敏 起始时间2015.6.292015.7.3 2015 年 春季 学期设计任务 （1）基本要求：用汇编语言编写设计一个求解大数的阶乘精确值的程序。设计提示：采用字节型数组存放阶乘结果的每个数字位，采用逐位相乘，再对每一位规格化来实现。进一步设计要求：输出阶乘结果的位数及尾零的个数。 （2）基本要求：用汇编语言编写设计快速排序和希尔排序。设计提示：注意设置合理堆栈容量，

2、以避免堆栈溢出。进一步设计要求：动态显示排序过程。 评语(教师填写) 组号：（ ）序号：（ ）任务：（ 7 , 8 ）题目：求解大数的阶乘，排序成员学号姓名分配任晓鹏排序及编码设计23120921058黄康求解大数的阶乘及编码设计33120921054翁林涛寻找参考资料辅助编程算法分析及总结微机原理课程设计选题表题目1、2不选，题目7、8合并目录一系统总模块设计41.大数阶乘42.快速排序4二小组任务分工5 1.大数阶乘原理设计52.排序原理设计5 3. 希尔排序原理设计.5三子系统设计方案51.大数阶乘52.快速排序5 3. 希尔排序.,.6四子系统主要程序流程图6

3、1.大数阶乘流程图62.快速排序流程图7五方案实现与测试91.1大数阶乘源代码91.2大数阶乘测试结果截图122.1快速排序源代码132.2快速排序测试结果截图15六小组设计和心得体会16七小组设计总结.17八参考文献.17一 系统总模块设计模块图：大数阶乘：快速排序：二小组任务分工描述每个人应完成的任务：我们在处理一个大于一定范围的数的阶乘时，无论使用什么类型去保存运算结果都必然会发生溢出，这势必会导致运算结果出错。使用数组来模拟数字，这样无论结果数字有多大，只要数组的长度够长就能表示出来，用这个办法可以进行大数据的运算。2排序原理设计：快速排序原理:首先任意选取一个数据（通常选用数组的第一

4、个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。3排序原理设计：希尔排序原理: 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量=1(<<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。三子系统设计方案 大数阶乘：核心思想就是把计算结果每一位上的数字保存到一个数组成员中，例如：把112保存至数组中，保存结果应该是result0 2result1 1resu

5、lt2 1把整个数组看成一个数字，这个数字和一个数相乘的时候，需要每一位都和这个乘数进行相乘运算还需要把前一为的进位加上。运算方法和小学数学是一样的，乘积的个位是当前位上应该表示的数字，10位以上的需要进位。因为乘数不可能大于10000，所以乘数和一个小于10的书相乘的时候不会大于100000，再加上前一位的进位用一个int型数据来保持这个结果就没有问题。写法如下：int 结果 = resultx * 乘数 + 进位;每一位的计算结果有了，把这个结果的个位数拿出来放到这个数组元素上：resultx = 结果%10;接下来的工作就是计算出进位：进位 = 结果 / 10;这样一位一位的把整个数组计

6、算一遍，最后可能还有进位，用同样的方法，把进位的数值拆成单个数字，放到相应的数组元素中。最后输出一下结果，从最高位吧数字打印一遍就OK了。快速排序：1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；2）以第一个数组元素作为关键数据，赋值给key，即key=A0；3）从j开始向前搜索，即由后开始向前搜索(j-)，找到第一个小于key的值Aj，将Aj赋给Ai；4）从i开始向后搜索，即由前开始向后搜索(i+)，找到第一个大于key的Ai，将Ai赋给Aj；5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中Aj不小于key,4中Ai不大于key的时候改变j、i的值，使得

7、j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i=j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。希尔排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<<d2<d1)，即所有记录放在同一组中进行直接插入排序为止四、子系统主要程序流程图大数阶乘：快速排序：五 方案实现与测试大数阶乘源代码：.datainfoMsg byte &#

8、39;请输入你要求的阶乘',13,10,0errorMsg byte '你输入的数小于0',13,10,0account byte '阶乘的位数为：',13,10,0zeroaccount byte '尾零的个数为：',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;输入的数小于0;输入的数不小于0;完成计算 外层循环用ebxmov ebx,2 OUTER:cmp ebx,inputnumjg FINISH ;内层循环1用ecx mov ecx,1mov eax,0mov carry,eaxFLAG1:cmp ecx,arrayNum ;相当于判断j<=digit？jg OUTIN;大于1跳出内循环 mov eax,ebxmul bufferNumecx*4-4add eax,carry ;这三句与c中这句相当：temp=aj-1*i+carry;adc e

10、dx,0;还要加进位标志，也就是说加了上一步的进位push ebxmov ebx,0ahdiv ebxpop ebxmov bufferNumecx*4-4,edxmov carry,eaxinc ecxjmp FLAG1;内层循环2用carry OUTIN:cmp carry,0jz FLAG2;mov eax,1add arrayNum,eax;所用到的数组的个数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;保存余数到数组mov edx,0mov eax,carrypush ebxmov ebx,0ahdiv ebxpop ebxmov carry,eaxjmp OUTIN ;循环保存余数直到进位只剩个位 FLAG2:inc ebxjmp OUTER;输出结果 FINISH:mov ecx,arrayNum FLAG3:cmp ecx,0jle ACCOUNTmov eax,bufferNumecx*4-4call dispsidmov eax,0dec ecxjmp FLAG3;出错显示信息 DONE:cmp edi,0je

12、ACCOUNTmov eax,offset errorMsgcall dispmsg;显示结果的位数 ACCOUNT:call dispcrlfMOV eax,offset accountcall dispmsgMOV eax,arrayNumcall dispuidcall dispcrlf;用来计算尾0的个数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大数阶乘测试结果截图：快速排序源代码： includelib msvcrt.lib ;这里是引入类库 相当于 #include了 printf PROTO C:PTR DWORD, :VARARG ;声明一下我们要用的函数头 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 '请输入排序数据(000 结束)',10,13,0 out_msg byte '快速(降序)排序结果如下：',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 调用API函数 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 ;定义局部变量 中点 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始终指向中心数，EDX指向下一个数 Tag3: INC EDX LOOP Tag1 DEC ESI PUSH ESI INVOKE qsort, array, lowitem, ESI ;对前半段排序 POP ESI INC ESI INC ESI ;入栈时ESI少一个，对于出栈先加1，投入计算时再加1 INVOKE qsort, array, ESI, highitem ;对后半段排序 TagEnd: RETqsort ENDPmain : invoke readInArray ,addr count;读入数

19、列到数组 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快速排序测试结果截图：六 小组设计和心得体会黄康：在这接近一周的时间里，我主要做大数阶乘的实现，首先由于它和我们传统意义上计算阶乘有着很大的区别，所以接受一个新的理念就是一件难事，然后把其转换为程序代码的操作又是一大难事。所以以后要多多动手，想的和做的还有很大区别。在实现过程中我主要参考以前c语言程序的思想，但还是碰到了很多问题，尤其在于实现数据存储的过程中由于计算机位数的限制，我采用了数组进行存储，结果过程中还是遇到了很多问题，最后都一一解决。 夏晓鹏： 通过一星期的学习，我学会了通过汇编语言