02.大数阶乘——算法分析&程序设计

《02.大数阶乘——算法分析&程序设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、大数阶乘——算法分析&程序设计算法设计方案一：链表Ax链表n=链表C链表A=链表C方案二：链表Axintn=链表B链表A=链表B方案三：链表Axintn=链表A乘法计算8803362X109!=83880080036286288003628cin>>nn>2把n装入链表An=n-1作为乘数A=A*nYN输出A删除链表程序结束结点：node数据域：node->data指针域：node->link头指针：first工作指针：pt进位变量：intcarry=0pt=firstpt->data=pt->data*n+carrycarry=pt->data/

2、1000pt->data=pt->data%1000pt->link!=0YNpt=pt->linkCarry!=0YNpt->link=newnodept->link->link=NULLpt=pt->linkpt->data=carry%1000carry=carry/1000880362ptpt0carry8388008003628628pt3cin>>nn>2把n装入链表An=n-1作为乘数A=A*nYN输出A删除链表程序结束结点：node数据域：node->data指针域：node->link头指针：first工作指针：pt进位变量：in

3、tcarry=0pt=firstcout<datapt->data<10YNpt=pt->linkpt->data<100YNcout<<‘00’cout<<‘0’cout<datapt->link!=0YN效率分析//乘法实现intcarry=0;do{ptA=ptAstart;do{carry=ptA->num*n+carry;ptA->num=carry%1000;carry=carry/1000;if(ptA->prior!=NULL)ptA=ptA->prior;elsebreak;}while(1);while(ca

4、rry){ptA->prior=newnode;ptA->prior->next=ptA;ptA->prior->prior=NULL;ptA=ptA->prior;ptAhead=ptA;ptA->num=carry%1000;carry=carry/1000;};ptA=ptAstart;n--;}while(n>2);效率分析carry=ptA->num*n+carry;moveax,dwordptr[ptA]movecx,dwordptr[eax]imulecx,dwordptr[n]addecx,dwordptr[carry]movdwo

5、rdptr[carry],ecxptA->num=carry%1000;moveax,dwordptr[carry]cdqmovecx,3E8hidiveax,ecxmoveax,dwordptr[ptA]movdwordptr[eax],edxcarry=carry/1000;moveax,dwordptr[carry]cdqmovecx,3E8hidiveax,ecxmovdwordptr[carry],eax__asm{movebx,ptA;movebx,[ebx];moveax,n;mulebx;movecx,carry;leaeax,[e

6、ax+ecx];movecx,1000;divecx;movcarry,eax;moveax,ptA;mov[eax],edx;}总结利用链表存储大数，适当增大结点位数可提高效率如果用单链表，需在输出前原地逆置