02大數(shù)階乘-算法分析

大數(shù)階乘

——算法分析&程序設計算法設計方案一：鏈表Ax鏈表n=鏈表C 鏈表A=鏈表C方案二：鏈表Axintn=鏈表B 鏈表A=鏈表B方案三：鏈表Axintn=鏈表A乘法計算8803362X109!=83880080036286288003628cin>>nn>2把n裝入鏈表An=n-1作為乘數(shù)A=A*nYN輸出A刪除鏈表程序結(jié)束結(jié)點：node數(shù)據(jù)域：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作為乘數(shù)A=A*nYN輸出A刪除鏈表程序結(jié)束結(jié)點：node數(shù)據(jù)域：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效率分析//乘法實現(xiàn)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