欢迎来到天天文库
浏览记录
ID:5504363
大小:338.50 KB
页数:10页
时间:2017-11-16
《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;}总结利用链表存储大数,适当增大结点位数可提高效率如果用单链表,需在输出前原地逆置
此文档下载收益归作者所有