大整數(shù)階乘程序設計

1、-. z.程序設計報告 2010 / 2011學年 第 一 學期 題 目： 大整數(shù)階乘 專 業(yè) 計算機科學與技術(shù) 學 生 姓 名 *賽班 級 學 號 B09040121 指 導 教 師 楊一濤 指 導 單 位 計算機學院 日 期 評 分 細 則評分項優(yōu)秀良好中等差遵守機房規(guī)章制度上機時的表現(xiàn)學習態(tài)度程序準備情況程序設計能力團隊合作精神課題功能實現(xiàn)情況算法設計合理性用戶界面設計報告書寫認真程度內(nèi)容詳實程度文字表達熟練程度答復下列問題準確度簡 短 評 語教師簽名：年月日評分等級備注評分等級有五種：優(yōu)秀、良好、中等、及格、不及格大整數(shù)階乘課題內(nèi)容和要求1、系統(tǒng)的根本功能及要求1寫一個類BigInte

2、ger，并有如下成員函數(shù)operator+/ operator-/ operator*/ operator，即整數(shù)的四則運算并重載運算符。2用該大整數(shù)計算n的階乘并顯示出來。n1,100注：為了簡化，可不考慮負數(shù)，則遇上形如“2-4這樣的表達式需要報錯。2、程序執(zhí)行過程1系統(tǒng)從鍵盤讀入自然數(shù)n，直到輸入了合法的n為止。2輸出運算的結(jié)果，為便于觀察結(jié)果，每輸出四位中間插入空格，格式如下例如，n=12：12!= 4790 0160 03詢問用戶是否繼續(xù)進展，用戶選擇“是，直到輸入合法為止，轉(zhuǎn)1，否則退出程序。3、算法要求及提示1因為n較大時，n!的結(jié)果將超出長整形的保存*圍，因此結(jié)果不能用long

3、 int型的變量來保存。本算法要求用鏈表來存儲。2鏈表的每一個節(jié)點存儲結(jié)果的一位數(shù)字，因此結(jié)果的輸出實際上是鏈表的遍歷問題，同時要先考慮用多少位來表示大整數(shù)。4、其他要求1輸入時具備一定的容錯性判斷，如輸入的不是數(shù)字，或輸入的數(shù)超過*圍等等。2變量、函數(shù)命名符合規(guī)*。3注釋詳細：每個變量都要求有注釋說明用途；函數(shù)有注釋說明功能，對參數(shù)、返回值也要以注釋的形式說明用途；關(guān)鍵的語句段要求有注釋解釋。4程序的層次清晰，可讀性強。需求分析1課題要求已說明結(jié)果不能用long int型的變量來保存，要求用鏈表來存儲。，首先要定義一個節(jié)點類，在這里定義一個雙向節(jié)點類。2定義一個BigInteger大整數(shù)類，

4、使其能夠存放大數(shù)階乘，并實現(xiàn)其的四則運算。3對輸入整數(shù)的合法性進展檢查，必須考慮用戶各種輸入情況。三.概要設計1使用單鏈表存儲數(shù)據(jù)，結(jié)點類定義如下：class Node int data; Node* ne*t;/指向大數(shù)的高位 Node* pre;/指向大數(shù)的低位 friend class BigInteger;2.使用大整數(shù)類來進展大整數(shù)四則算法的重載，在主函數(shù)中通過定義大整數(shù)對象調(diào)用，大整數(shù)類定義如下：class BigInteger/定義大整數(shù)類public:Node *head,*head1;int n,temp,i,jinwei;BigInteger();/無參構(gòu)造函數(shù)BigInt

5、eger();/析構(gòu)函數(shù)void jiecheng();/階乘函數(shù)void operator +( BigInteger p1);/加法運算重載聲明void operator -( BigInteger p1);/減法運算重載聲明 void operator *( BigInteger p1);/乘法運算重載聲明void operator /( BigInteger p1);/除法運算重載聲明;3.算法設計說明：因為n較大時，n!的結(jié)果將超出長整形的保存*圍，因此結(jié)果不能用long int型的變量來保存。本算法數(shù)據(jù)用單鏈表來存儲。鏈表的每一個節(jié)點存儲結(jié)果的一位數(shù)字，因此結(jié)果的輸出實際上是鏈表的

6、遍歷問題，同時要先考慮用多少位來表示大整數(shù)。首先申請一個結(jié)點類并賦數(shù)據(jù)域初值1，然后遍歷單鏈表逐個的數(shù)據(jù)域與i1到n相乘；乘完后重新遍歷，對每個結(jié)點的數(shù)據(jù)域處理，假設小于10則跳過；否則，判斷下一結(jié)點是否存在，假設存在則該數(shù)據(jù)域除10取余，下一結(jié)點的數(shù)據(jù)域加上該數(shù)據(jù)域除10的結(jié)果，假設不存在則申請新結(jié)點空間，處理同上；全部乘完并處理完后，遍歷單鏈表并輸出各自的數(shù)據(jù)域即可，注意每四個輸出一個空格。4、流程圖輸入n開場N在1到100之間？ 是 否計算n！ 是是是否繼續(xù)？輸出n！ 是完畢 否四.詳細設計1.階乘函數(shù)作為BigInteger類中的函數(shù)，在主函數(shù)通過定義大整數(shù)類對象調(diào)用，階乘函數(shù)的定義如

7、下：void BigInteger:jiecheng()Node *cur,*cc;Node *head=new Node;/存放第一個節(jié)點,值為1 head-data=1; head-pre=head-ne*t=NULL;for(i=2;idata)+jinwei; cur-data=temp%10;/取個位存下來,如91*2=182,取2存儲 jinwei=temp/10;/十位和百位作為進位,取18為進位 if(cur-ne*t=NULL) break; cur=cur-ne*t; while(jinwei!=0)/如果乘完一個i發(fā)現(xiàn)還有進位,就必須新增結(jié)點,由于進位可能是多位數(shù)，所以必

8、須用 /while cc=new Node; cc-data=jinwei%10; cc-pre=cur; cc-ne*t=NULL; cur-ne*t=cc; cur=cc; jinwei/=10; coutnne*t)cur=cur-ne*t;/遍歷到最高位 while(cur)/從最高位到最低位打印 cc=cur; if(i=4) i=0; cout ; coutdata; cur=cur-pre; i+; delete cc; 2階乘加法函數(shù)的重載定義：void BigInteger:operator +( BigInteger p1)Node *cur,*cc,*cur1,*cc1;

9、head=new Node;/存放第一個節(jié)點,值為1 head-data=1; head-pre=head-ne*t=NULL;for(i=2;idata)+jinwei; cur-data=temp%10;/取個位存下來,如91*2=182,取2存儲 jinwei=temp/10;/十位和百位作為進位,取18為進位 if(cur-ne*t=NULL) break; cur=cur-ne*t; while(jinwei!=0)/如果乘完一個i發(fā)現(xiàn)還有進位,就必須新增結(jié)點,由于進位可能是多位數(shù)，所以必須用 /while cc=new Node; cc-data=jinwei%10; cc-pre

10、=cur; cc-ne*t=NULL; cur-ne*t=cc; cur=cc; jinwei/=10; head1=new Node;/存放第一個節(jié)點,值為1 head1-data=1; head1-pre=head1-ne*t=NULL; for(i=2;idata)+jinwei; cur1-data=temp%10;/取個位存下來,如91*2=182,取2存儲 jinwei=temp/10;/十位和百位作為進位,取18為進位 if(cur1-ne*t=NULL) break; cur1=cur1-ne*t; while(jinwei!=0)/如果乘完一個i發(fā)現(xiàn)還有進位,就必須新增結(jié)點,

11、由于進位可能是多位數(shù)，所以必須用 /while cc1=new Node; cc1-data=jinwei%10; cc1-pre=cur1; cc1-ne*t=NULL; cur1-ne*t=cc1; cur1=cc1; jinwei/=10; if(np1.n)/假設this.n大于等于p1.ncur=head;cur1=head1;while(cur&cur1)/同時遍歷兩個單鏈表，其中有一個完畢就停頓遍歷cur-data+=cur1-data;/cur的數(shù)據(jù)域等于cur的數(shù)據(jù)域與cur1的數(shù)據(jù)域的和cur=cur-ne*t;cur1=cur1-ne*t;cur=head;/cur指向頭

12、結(jié)點do/利用階乘函數(shù)中的算法處理單鏈表各個節(jié)點的數(shù)據(jù)域if(cur-datadata=10)if(cur-ne*t)cur-ne*t-data+=cur-data/10;cur-data=cur-data%10;elseNode *q=new Node;q-ne*t=cur-ne*t;cur-ne*t=q;q-data+=cur-data/10;cur-data=cur-data%10;while(cur=cur-ne*t);cur=head,i=0; while(cur-ne*t)cur=cur-ne*t;/遍歷到最高位 while(cur)/從最高位到最低位打印 cc=cur; if(i

13、=4) /每輸出四個空一格 i=0; cout ; coutdata; cur=cur-pre; i+; delete cc; elsecur=head;cur1=head1;while(cur&cur1)/同時遍歷兩個單鏈表，其中有一個完畢就停頓遍歷cur1-data+=cur-data;/cur1的數(shù)據(jù)域等于cur1的數(shù)據(jù)域與m的數(shù)據(jù)域的和cur1=cur1-ne*t;cur=cur-ne*t;cur1=head1;do/利用階乘函數(shù)中的算法處理單鏈表各個節(jié)點的數(shù)據(jù)域if(cur1-datadata=10)if(cur1-ne*t)cur1-ne*t-data+=cur1-data/10;

14、cur1-data=cur1-data%10;elseNode *q=new Node;q-data=0;q-ne*t=cur1-ne*t;cur1-ne*t=q;q-pre=cur1;q-data+=cur1-data/10;cur1-data=cur1-data%10;while(cur1=cur1-ne*t);cur1=head1,i=0; while(cur1-ne*t)cur1=cur1-ne*t;/遍歷到最高位 while(cur1)/從最高位到最低位打印 cc=cur1; if(i=4) /每輸出四個空一格 i=0; cout ; coutdata; cur1=cur1-pre;

15、 i+; delete cc; 3階乘減法函數(shù)的重載定義：void BigInteger:operator -( BigInteger p1)if(n=p1.n)/假設this.n等于p1.ncoutdata=1; head-pre=head-ne*t=NULL;for(i=2;idata)+jinwei; cur-data=temp%10;/取個位存下來,如91*2=182,取2存儲 jinwei=temp/10;/十位和百位作為進位,取18為進位 if(cur-ne*t=NULL) break; cur=cur-ne*t; while(jinwei!=0)/如果乘完一個i發(fā)現(xiàn)還有進位,就必

16、須新增結(jié)點,由于進位可能是多位數(shù)，所以必須用 /while cc=new Node; cc-data=jinwei%10; cc-pre=cur; cc-ne*t=NULL; cur-ne*t=cc; cur=cc; jinwei/=10; head1=new Node;/存放第一個節(jié)點,值為1 head1-data=1; head1-pre=head1-ne*t=NULL; for(i=2;idata)+jinwei; cur1-data=temp%10;/取個位存下來,如91*2=182,取2存儲 jinwei=temp/10;/十位和百位作為進位,取18為進位 if(cur1-ne*t=

17、NULL) break; cur1=cur1-ne*t; while(jinwei!=0)/如果乘完一個i發(fā)現(xiàn)還有進位,就必須新增結(jié)點,由于進位可能是多位數(shù)，所以必須用 /while cc1=new Node; cc1-data=jinwei%10; cc1-pre=cur1; cc1-ne*t=NULL; cur1-ne*t=cc1; cur1=cc1; jinwei/=10; if(np1.n)/假設this.n大于p1.n cur=head;cur1=head1;while(cur&cur1)/同時遍歷兩個單鏈表，其中有一個完畢就停頓遍歷cur-data-=cur1-data;cur=c

18、ur-ne*t;cur1=cur1-ne*t;cur=head;do/遍歷單鏈表if(cur-datane*t-data-=1;/p的后繼結(jié)點的數(shù)據(jù)域減1cur-data+=10;/p的數(shù)據(jù)域加10while(cur=cur-ne*t);cur=head,i=0; while(cur-ne*t)cur=cur-ne*t;/遍歷到最高位 while(cur)/從最高位到最低位打印 cc=cur; if(i=4) /每輸出四個空一格 i=0; cout ; coutdata; cur=cur-pre; i+; delete cc; else cur=head;cur1=head1;while(cu

19、r&cur1)/同時遍歷兩個單鏈表，其中有一個完畢就停頓遍歷cur1-data-=cur-data;cur1=cur1-ne*t;cur=cur-ne*t;cur1=head1;do/遍歷單鏈表if(cur1-datane*t)/假設cur1的數(shù)據(jù)域小于0cur1-ne*t-data-=1;/cur1的后繼結(jié)點的數(shù)據(jù)域減1cur1-data+=10;/cur1的數(shù)據(jù)域加10while(cur1=cur1-ne*t);cur1=head1,i=0; while(cur1-ne*t)cur1=cur1-ne*t;/遍歷到最高位cout-;while(cur1)/從最高位到最低位打印 cc1=cur

20、1; if(i=4) /每輸出四個空一格 i=0; cout ; coutdata; cur1=cur1-pre; i+; delete cc1;4階乘乘法函數(shù)重載的定義：void BigInteger:operator *( BigInteger p1)Node *cur,*cur1,*cc,*cc1;head=new Node;/存放第一個節(jié)點,值為1 head-data=1; head-pre=head-ne*t=NULL;for(i=2;idata)+jinwei; cur-data=temp%10;/取個位存下來,如91*2=182,取2存儲 jinwei=temp/10;/十位和百

21、位作為進位,取18為進位 if(cur-ne*t=NULL) break; cur=cur-ne*t; while(jinwei!=0)/如果乘完一個i發(fā)現(xiàn)還有進位,就必須新增結(jié)點,由于進位可能是多位數(shù)，所以必須用 /while cc=new Node; cc-data=jinwei%10; cc-pre=cur; cc-ne*t=NULL; cur-ne*t=cc; cur=cc; jinwei/=10; for(i=1;idata)+jinwei; cur1-data=temp%10;/取個位存下來,如91*2=182,取2存儲 jinwei=temp/10;/十位和百位作為進位,取18為

22、進位 if(cur1-ne*t=NULL) break; cur1=cur1-ne*t; while(jinwei!=0)/如果乘完一個i發(fā)現(xiàn)還有進位,就必須新增結(jié)點,由于進位可能是多位數(shù)，所以必須用 /while cc1=new Node; cc1-data=jinwei%10; cc1-pre=cur1; cc1-ne*t=NULL; cur1-ne*t=cc1; cur1=cc1; jinwei/=10; cur1=head,i=0; while(cur1-ne*t)cur1=cur1-ne*t;/遍歷到最高位 while(cur1)/從最高位到最低位打印 cc1=cur1; if(i=

23、4) /每輸出四個空一格 i=0; cout ; coutdata; cur1=cur1-pre; i+; delete cc1; 5階乘除法函數(shù)重載的定義：void BigInteger:operator/(BigInteger p1)if(n=p1.n)/假設this.n等于p1.ncout1endl;elseif(np1.n)cout0p1.n)Node *cur,*cc;head=new Node;/存放第一個節(jié)點,值為1 head-data=1; head-pre=head-ne*t=NULL;for(i=p1.n+1;idata)+jinwei; cur-data=temp%10;

24、/取個位存下來,如91*2=182,取2存儲 jinwei=temp/10;/十位和百位作為進位,取18為進位 if(cur-ne*t=NULL) break; cur=cur-ne*t; while(jinwei!=0)/如果乘完一個i發(fā)現(xiàn)還有進位,就必須新增結(jié)點,由于進位可能是多位數(shù)，所以必須用 /while cc=new Node; cc-data=jinwei%10; cc-pre=cur; cc-ne*t=NULL; cur-ne*t=cc; cur=cc; jinwei/=10; cur=head,i=0; while(cur-ne*t)cur=cur-ne*t;/遍歷到最高位 while(cur)/從最高位到最低位打印 cc=cur; if(i=4) /每輸出四個空一格 i=0; cout ; coutdata; cur=cur-pre; i+; delete cc; 五、數(shù)據(jù)測試及其結(jié)果分析數(shù)據(jù)測試測試界面：輸入錯誤整數(shù)：1230輸入正確整數(shù)：12接著輸入y接著輸入5接著輸入n接著輸入6接著輸入52.結(jié)果分析:剛開場運行，程序首先提示用戶程序是計算大整數(shù)的階乘及其四則運算的功能，并提示用戶按照輸入一個自然