大整数阶乘程序设计(共30页).doc

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

2）用该大整数计算n的阶乘并显示出来n∈[1,100]）注：为了简化，可不考虑负数，则遇上形如“2-4”这样的表达式需要报错2、程序执行过程（1）系统从键盘读入自然数n，直到输入了合法的n为止2）输出运算的结果，为便于观察结果，每输出四位中间插入空格，格式如下（例如，n=12）：12!= 4790 0160 0（3）询问用户是否继续进行，用户选择“是”，直到输入合法为止，转（1），否则退出程序3、算法要求及提示（1）因为n较大时，n!的结果将超出长整形的保存范围，因此结果不能用long int型的变量来保存本算法要求用链表来存储2）链表的每一个节点存储结果的一位数字，因此结果的输出实际上是链表的遍历问题，同时要先考虑用多少位来表示大整数4、其他要求（1）输入时具备一定的容错性判断，如输入的不是数字，或输入的数超过范围等等2）变量、函数命名符合规范3）注释详细：每个变量都要求有注释说明用途；函数有注释说明功能，对参数、返回值也要以注释的形式说明用途；关键的语句段要求有注释解释4）程序的层次清晰，可读性强二、 需求分析1）课题要求已说明结果不能用long int型的变量来保存，要求用链表来存储。

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

本算法数据用单链表来存储链表的每一个节点存储结果的一位数字，因此结果的输出实际上是链表的遍历问题，同时要先考虑用多少位来表示大整数首先申请一个结点类并赋数据域初值1，然后遍历单链表逐个的数据域与i（1到n）相乘；乘完后重新遍历，对每个结点的数据域处理，若小于10则跳过；否则，判断下一结点是否存在，若存在则该数据域除10取余，下一结点的数据域加上该数据域除10的结果，若不存在则申请新结点空间，处理同上；全部乘完并处理完后，遍历单链表并输出各自的数据域即可，注意每四个输出一个空格4、流程图输入n开始N在1到100之间？ 是 否计算n！ 是 是 是否继续？输出n！ 是 结束 否 四.详细设计1.阶乘函数作为BigInteger类中的函数，在主函数通过定义大整数类对象调用，阶乘函数的定义如下：void BigInteger::jiecheng(){ Node *cur,*cc; Node *head=new Node;//存放第一个节点,值为1 head->data=1; head->pre=head->next=NULL; for(i=2;i<=n;i++)//从2开始连乘到n { cur=head; jinwei=0; while(1) { temp=i*(cur->data)+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; } } cout<next)cur=cur->next;//遍历到最高位 while(cur)//从最高位到最低位打印 { cc=cur; if(i==4) { i=0; cout<< ; } cout<data; cur=cur->pre; i++; delete cc; } }2．阶乘加法函数的重载定义：void BigInteger::operator +( BigInteger p1){ Node *cur,*cc,*cur1,*cc1; head=new Node;//存放第一个节点,值为1 head->data=1; head->pre=head->next=NULL; for(i=2;i<=n;i++)//从2开始连乘到n { cur=head; jinwei=0; while(1) { temp=i*(cur->data)+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; } } head1=new Node;//存放第一个节点,值为1 head1->data=1; head1->pre=head1->next=NULL; for(i=2;i<=p1.n;i++)//从2开始连乘到n { cur1=head1; jinwei=0; while(1) { temp=i*(cur1->data)+jinwei; cur1->data=temp%10;//取个位存下来,如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; } } if(n>p1.n)//若this.n大于等于p1.n { cur=head; cur1=head1; while(cur&&cur1)//同时遍历两个单链表。