大整数阶乘程序设计

1、程序设计报告（ 2010 / 2011学年 第 一 学期 ）题 目： 大整数阶乘 专 业 计算机科学与技术 学 生 姓 名 张赛 班 级 学 号 B09040121 指 导 教 师 杨一涛 指 导 单 位 计算机学院 日 期 2010.9.30 评 分 细 则评分项优秀良好中等差遵守机房规章制度上机时的表现学习态度程序准备情况程序设计能力团队合作精神课题功能实现情况算法设计合理性用户界面设计报告书写认真程度内容详实程度文字表达熟练程度回答问题准确度简 短 评 语教师签名： 年 月 日评分等级备注评分等级有五种：优秀、良好、中等、及格、不及格大整数阶乘一、 课题内容和要求1、系统的基本功能及要求

2、（1）写一个类BigInteger，并有如下成员函数operator+/ operator-/ operator*/ operator，即整数的四则运算并重载运算符。（2）用该大整数计算n的阶乘并显示出来。（n1,100）注：为了简化，可不考虑负数，则遇上形如“2-4”这样的表达式需要报错。2、程序执行过程（1）系统从键盘读入自然数n，直到输入了合法的n为止。（2）输出运算的结果，为便于观察结果，每输出四位中间插入空格，格式如下（例如，n=12）：12!= 4790 0160 0（3）询问用户是否继续进行，用户选择“是”，直到输入合法为止，转（1），否则退出程序。3、算法要求及提示（1）因为n

3、较大时，n!的结果将超出长整形的保存范围，因此结果不能用long int型的变量来保存。本算法要求用链表来存储。（2）链表的每一个节点存储结果的一位数字，因此结果的输出实际上是链表的遍历问题，同时要先考虑用多少位来表示大整数。4、其他要求（1）输入时具备一定的容错性判断，如输入的不是数字，或输入的数超过范围等等。（2）变量、函数命名符合规范。（3）注释详细：每个变量都要求有注释说明用途；函数有注释说明功能，对参数、返回值也要以注释的形式说明用途；关键的语句段要求有注释解释。（4）程序的层次清晰，可读性强。二、 需求分析1）课题要求已说明结果不能用long int型的变量来保存，要求用链表来存储

4、。，首先要定义一个节点类，在这里定义一个双向节点类。2）定义一个BigInteger大整数类，使其能够存放大数阶乘，并实现其的四则运算。 3）对输入整数的合法性进行检查，必须考虑用户各种输入情况。三.概要设计1使用单链表存储数据，结点类定义如下：class Node int data; Node* next;/指向大数的高位 Node* pre;/指向大数的低位 friend class BigInteger;2.使用大整数类来进行大整数四则算法的重载，在主函数中通过定义大整数对象调用，大整数类定义如下：class BigInteger/定义大整数类public:Node *head,*hea

5、d1;int n,temp,i,jinwei;BigInteger();/无参构造函数BigInteger();/析构函数void jiecheng();/阶乘函数void operator +( BigInteger p1);/加法运算重载声明void operator -( BigInteger p1);/减法运算重载声明 void operator *( BigInteger p1);/乘法运算重载声明void operator /( BigInteger p1);/除法运算重载声明;3.算法设计说明：因为n较大时，n!的结果将超出长整形的保存范围，因此结果不能用long int型的变量

6、来保存。本算法数据用单链表来存储。链表的每一个节点存储结果的一位数字，因此结果的输出实际上是链表的遍历问题，同时要先考虑用多少位来表示大整数。首先申请一个结点类并赋数据域初值1，然后遍历单链表逐个的数据域与i（1到n）相乘；乘完后重新遍历，对每个结点的数据域处理，若小于10则跳过；否则，判断下一结点是否存在，若存在则该数据域除10取余，下一结点的数据域加上该数据域除10的结果，若不存在则申请新结点空间，处理同上；全部乘完并处理完后，遍历单链表并输出各自的数据域即可，注意每四个输出一个空格。4、流程图输入n开始N在1到100之间？ 是 否计算n！ 是 是 是否继续？输出n！ 是 结束 否 四.详

7、细设计1.阶乘函数作为BigInteger类中的函数，在主函数通过定义大整数类对象调用，阶乘函数的定义如下：void BigInteger:jiecheng()Node *cur,*cc;Node *head=new Node;/存放第一个节点,值为1 head-data=1; head-pre=head-next=NULL;for(i=2;idata)+jinwei; cur-data=temp%10;/取个位存下来,如91*2=182,取2存储 jinwei=temp/10;/十位和百位作为进位,取18为进位 if(cur-next=NULL) break; cur=cur-next; w

8、hile(jinwei!=0)/如果乘完一个i发现还有进位,就必须新增结点,由于进位可能是多位数，所以必须用 /while cc=new Node; cc-data=jinwei%10; cc-pre=cur; cc-next=NULL; cur-next=cc; cur=cc; jinwei/=10; coutnnext)cur=cur-next;/遍历到最高位 while(cur)/从最高位到最低位打印 cc=cur; if(i=4) i=0; cout ; coutdata; cur=cur-pre; i+; delete cc; 2阶乘加法函数的重载定义：void BigInteger

9、:operator +( BigInteger p1)Node *cur,*cc,*cur1,*cc1;head=new Node;/存放第一个节点,值为1 head-data=1; head-pre=head-next=NULL;for(i=2;idata)+jinwei; cur-data=temp%10;/取个位存下来,如91*2=182,取2存储 jinwei=temp/10;/十位和百位作为进位,取18为进位 if(cur-next=NULL) break; cur=cur-next; while(jinwei!=0)/如果乘完一个i发现还有进位,就必须新增结点,由于进位可能是多位数

10、，所以必须用 /while cc=new Node; cc-data=jinwei%10; cc-pre=cur; cc-next=NULL; cur-next=cc; cur=cc; jinwei/=10; head1=new Node;/存放第一个节点,值为1 head1-data=1; head1-pre=head1-next=NULL; for(i=2;idata)+jinwei; cur1-data=temp%10;/取个位存下来,如91*2=182,取2存储 jinwei=temp/10;/十位和百位作为进位,取18为进位 if(cur1-next=NULL) break; cur

11、1=cur1-next; while(jinwei!=0)/如果乘完一个i发现还有进位,就必须新增结点,由于进位可能是多位数，所以必须用 /while cc1=new Node; cc1-data=jinwei%10; cc1-pre=cur1; cc1-next=NULL; cur1-next=cc1; cur1=cc1; jinwei/=10; if(np1.n)/若this.n大于等于p1.ncur=head;cur1=head1;while(cur&cur1)/同时遍历两个单链表，其中有一个结束就停止遍历cur-data+=cur1-data;/cur的数据域等于cur的数据域与cur

12、1的数据域的和cur=cur-next;cur1=cur1-next;cur=head;/cur指向头结点do/利用阶乘函数中的算法处理单链表各个节点的数据域if(cur-datadata=10)if(cur-next)cur-next-data+=cur-data/10;cur-data=cur-data%10;elseNode *q=new Node;q-next=cur-next;cur-next=q;q-data+=cur-data/10;cur-data=cur-data%10;while(cur=cur-next);cur=head,i=0; while(cur-next)cur=

13、cur-next;/遍历到最高位 while(cur)/从最高位到最低位打印 cc=cur; if(i=4) /每输出四个空一格 i=0; cout ; coutdata; cur=cur-pre; i+; delete cc; elsecur=head;cur1=head1;while(cur&cur1)/同时遍历两个单链表，其中有一个结束就停止遍历cur1-data+=cur-data;/cur1的数据域等于cur1的数据域与m的数据域的和cur1=cur1-next;cur=cur-next;cur1=head1;do/利用阶乘函数中的算法处理单链表各个节点的数据域if(cur1-dat

14、adata=10)if(cur1-next)cur1-next-data+=cur1-data/10;cur1-data=cur1-data%10;elseNode *q=new Node;q-data=0;q-next=cur1-next;cur1-next=q;q-pre=cur1;q-data+=cur1-data/10;cur1-data=cur1-data%10;while(cur1=cur1-next);cur1=head1,i=0; while(cur1-next)cur1=cur1-next;/遍历到最高位 while(cur1)/从最高位到最低位打印 cc=cur1; if(

15、i=4) /每输出四个空一格 i=0; cout ; coutdata; cur1=cur1-pre; i+; delete cc; 3阶乘减法函数的重载定义：void BigInteger:operator -( BigInteger p1)if(n=p1.n)/若this.n等于p1.ncoutdata=1; head-pre=head-next=NULL;for(i=2;idata)+jinwei; cur-data=temp%10;/取个位存下来,如91*2=182,取2存储 jinwei=temp/10;/十位和百位作为进位,取18为进位 if(cur-next=NULL) brea

16、k; cur=cur-next; while(jinwei!=0)/如果乘完一个i发现还有进位,就必须新增结点,由于进位可能是多位数，所以必须用 /while cc=new Node; cc-data=jinwei%10; cc-pre=cur; cc-next=NULL; cur-next=cc; cur=cc; jinwei/=10; head1=new Node;/存放第一个节点,值为1 head1-data=1; head1-pre=head1-next=NULL; for(i=2;idata)+jinwei; cur1-data=temp%10;/取个位存下来,如91*2=182,取

17、2存储 jinwei=temp/10;/十位和百位作为进位,取18为进位 if(cur1-next=NULL) break; cur1=cur1-next; while(jinwei!=0)/如果乘完一个i发现还有进位,就必须新增结点,由于进位可能是多位数，所以必须用 /while cc1=new Node; cc1-data=jinwei%10; cc1-pre=cur1; cc1-next=NULL; cur1-next=cc1; cur1=cc1; jinwei/=10; if(np1.n)/若this.n大于p1.n cur=head;cur1=head1;while(cur&cur1

18、)/同时遍历两个单链表，其中有一个结束就停止遍历cur-data-=cur1-data;cur=cur-next;cur1=cur1-next;cur=head;do/遍历单链表if(cur-datanext-data-=1;/p的后继结点的数据域减1cur-data+=10;/p的数据域加10while(cur=cur-next);cur=head,i=0; while(cur-next)cur=cur-next;/遍历到最高位 while(cur)/从最高位到最低位打印 cc=cur; if(i=4) /每输出四个空一格 i=0; cout ; coutdata; cur=cur-pre;

19、 i+; delete cc; else cur=head;cur1=head1;while(cur&cur1)/同时遍历两个单链表，其中有一个结束就停止遍历cur1-data-=cur-data;cur1=cur1-next;cur=cur-next;cur1=head1;do/遍历单链表if(cur1-datanext)/若cur1的数据域小于0cur1-next-data-=1;/cur1的后继结点的数据域减1cur1-data+=10;/cur1的数据域加10while(cur1=cur1-next);cur1=head1,i=0; while(cur1-next)cur1=cur1-

20、next;/遍历到最高位cout-;while(cur1)/从最高位到最低位打印 cc1=cur1; if(i=4) /每输出四个空一格 i=0; cout ; coutdata; cur1=cur1-pre; i+; delete cc1;4阶乘乘法函数重载的定义：void BigInteger:operator *( BigInteger p1)Node *cur,*cur1,*cc,*cc1;head=new Node;/存放第一个节点,值为1 head-data=1; head-pre=head-next=NULL;for(i=2;idata)+jinwei; cur-data=tem

21、p%10;/取个位存下来,如91*2=182,取2存储 jinwei=temp/10;/十位和百位作为进位,取18为进位 if(cur-next=NULL) break; cur=cur-next; while(jinwei!=0)/如果乘完一个i发现还有进位,就必须新增结点,由于进位可能是多位数，所以必须用 /while cc=new Node; cc-data=jinwei%10; cc-pre=cur; cc-next=NULL; cur-next=cc; cur=cc; jinwei/=10; for(i=1;idata)+jinwei; cur1-data=temp%10;/取个位存

22、下来,如91*2=182,取2存储 jinwei=temp/10;/十位和百位作为进位,取18为进位 if(cur1-next=NULL) break; cur1=cur1-next; while(jinwei!=0)/如果乘完一个i发现还有进位,就必须新增结点,由于进位可能是多位数，所以必须用 /while cc1=new Node; cc1-data=jinwei%10; cc1-pre=cur1; cc1-next=NULL; cur1-next=cc1; cur1=cc1; jinwei/=10; cur1=head,i=0; while(cur1-next)cur1=cur1-nex

23、t;/遍历到最高位 while(cur1)/从最高位到最低位打印 cc1=cur1; if(i=4) /每输出四个空一格 i=0; cout ; coutdata; cur1=cur1-pre; i+; delete cc1; 5阶乘除法函数重载的定义：void BigInteger:operator/(BigInteger p1)if(n=p1.n)/若this.n等于p1.ncout1endl;elseif(np1.n)cout0p1.n)Node *cur,*cc;head=new Node;/存放第一个节点,值为1 head-data=1; head-pre=head-next=NUL

24、L;for(i=p1.n+1;idata)+jinwei; cur-data=temp%10;/取个位存下来,如91*2=182,取2存储 jinwei=temp/10;/十位和百位作为进位,取18为进位 if(cur-next=NULL) break; cur=cur-next; while(jinwei!=0)/如果乘完一个i发现还有进位,就必须新增结点,由于进位可能是多位数，所以必须用 /while cc=new Node; cc-data=jinwei%10; cc-pre=cur; cc-next=NULL; cur-next=cc; cur=cc; jinwei/=10; cur=head,i=0; while(cur-next)cur=cur-next;/遍历到最高位 while(cur)/从最高位到最低位打印 cc=cur; if(i=4) /每输出四个空一格 i=0; cout ; coutdata; cur=cur-pre; i+; delete cc; 五、数据测试及其结果分析1. 数据测试测试界面：输入错误整数：1230输入正确整数：12接着输入y接着输入5接着输入n接着输入6接着输入52.结果分析:刚开始运行，程序首先提示用户程序是计算大整数的阶乘及其四则运算的功能，并提示用户按照输入一个自然数；如果输入的数