02大数阶乘-算法分析

大数阶乘

——算法分析&程序设计算法设计方案一：链表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/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进位变量：intcarry=0pt=firstcout<<pt->datapt->data<10YNpt=pt->linkpt->data<100YNcout<<‘00’cout<<‘0’cout<<pt->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; else break;}while(1);

while(carry){ 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]

movdwordptr[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,[eax+ecx]; movecx,1000;

divecx