n!非递归算法的设计与实现

printf("%d",a[i]);
} /
void m(float n) {
long int i;
int sum;
if(n)
{
for(i=1,sum=1;i<=n;i++)
sum*=i;
printf("%d!=%d",(int)n,sum);
}
else printf("0!=1");
}
void main()
（4）当n=999时，结果如图6.4
图6.4当n=999时，运行结果
（5）当n=3.4时，结果如图6.,5
图6.5当n=3.4时，运行结果
所得结果与预测结果一样。
7
在执行函数的过程中，对上述提到的各种情况做了判断和提示，如：
输入负数，系统会提示“输入错误，请重新输入：”；
输入大于999的数，系统会提示“输入错误，请重新输入：”；
设计内容：
利用非递归算法实现n！的计算，在设计过程中应注意n值大小与数据类型表数范围之间的关系，并尽可能求出较大n值的阶乘。
要求:
1）阐述设计思想，画出流程图；
2）说明测试方法，写出完整的运行结果；
3）从时间、空间对算法分析；
4）较好的界面设计；
5）编写课程设计报告。
以上要求中第一个阶段的任务完成后，先将设计说明书的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。
void f(float n){
long int a[N],i,j,length,k,up;
a[0]=1600;a[1]=4790;length=2; //12!=479001600
for(j=13;j<=n;j++)
{
for(k=0,up=0;k<length;k++)
a[k]*=j;
for(k=0;k<length;k++)
参考文献
[1] 严蔚敏，吴伟民.数据结构(C语言版)[M].北京：清华大学出版社,2011
[2]谭浩强.C程序设计[M]. 北京：清华大学出版社,2010（3）
}
void f(float n){
long int a[N],i,j,length,k,up;//i,j为计数器，length为数组存储的长度
a[0]=1600;a[1]=4790;length=2;//12!=479001600，初始化f[0]和f[1]以便于求解大于12的阶乘
for(j=13;j<=n;j++)
本次课程设计的目的是：通过本次课程设计，可以使大家了解缓存中数据的存储范围，提高自学能力，增强团队合作意识。
2 需求分析
本次n!非递归算法的课程设计中主要用到的知识有：数组、函数、栈，选择条件中的结构语句（if…else），和循环结构语句中的语句while()语句、do…while()语句和for()语句，选择语句if的运用。
{
int sum,flog=1,g;
float n;
while(flog==1) //根据标签的值判断循环是否结束
{
printf("请输入整数n:"); //输入要求阶乘的数n
scanf("%f",&n);
while(n<0||n>999||n!=(int)n) //判断n是否合法
{
printf("输入错误,请重输入整数n:"); //如果输入不合法，重新输入n
成绩：教师签名：年月日
教研室意见
总成绩：室主任签名：年月日
注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。
课程设计任务书
2011—2012学年第2学期
专业：计算机科学与技术学号：1021024042姓名：赵娜
课程设计名称：数据结构课程设计
设计题目：n！非递归算法的设计与实现
完成期限：自2012年2月20日至2012年3月3日共2周
scanf("%f",&n);
}
if(n>12)
f(n); //如果n大于12调用函数f(n)
else
m(n); //如果n小于等于12调用函数m(n)
printf("\n\n"); //换行
printf("是否需要继续计算,输入1继续计算,输入0结束: "); //是否继续求n阶乘
fflush(stdin);
指导教师（签字）：教研室主任（签字）：
批准日期：2012年2月20日
摘 要
设计了一个用非递归算法实现n!的软件，该软件具有计算从1到999之间整数的阶乘的运算的功能。本计算器采用VC++作为软件开发环境，采用数组存储运算的结果，用栈输出运算结果，用递推法实现了整数的阶乘运算，界面清晰，易于为用户所接受。
子函数f(n)的流程图见图4.2
图4.2子函数f(n)的流程图
子函数m(n)的流程图见图4.3
图4.3子函数m(n)的流程图
5
#include<stdio.h>
#define N 10000 /*12!=479001600;*/ //定义数组的存储单元数
#define size 100000 //定义size,用于求解数组的最大存储位数
将n定义为float型，便于查看n是否为整数；
本次试验分为两个模块：
(1).当n小于都等于12时，实现阶乘的模块m(n): 直接用sum*=i;实现求n的阶乘，相对简单，容易就算。
(2).当n大于12时，如果用long型结果就会溢出，所以实现阶乘需调用的模块f(n):采用数组存放计算的结果，用队列输出运行结果。由于计算结果较大，将结果除以数组最大存储位数，将高位结果存放在数组的起始地址上，将低位的结果存放在数组的末端地址上，最后采用队列输出运行结果。
对n!的非递归的算法，主要是运用非递归的算法实现n的阶乘。
限制条件：
(1).要求的n必须是整数；
(2). n的范围；
(3).数据类型和表数范围。
3 概要设计
递归和非递归算法是相通的，递归是一种直接或间接调用自身的算法，而非递归不调用自身函数
递推采用的是递归和归并法，而非递推只采用递归法。递推法一般容易溢出，所以一般都采用递推法分析，而用非递推法设计程序。
}
}
printf("%5d!=",(int)n);//输出n
printf("%d",a[length-1]);//输出高位的运行结果
for(i=length-2;i>=0;i--)//将运算结果的第二个最高位到最低位的值输出
printf("%d",a[i]); }
4.2流程图
主函数流程图见图4.1
图4.1主函数流程图
void f(float n){ //当n大于12时调用函数f()
long int a[N],i,j,length,k,up;//定义变量 a[],i,j,length,k,up
}
voidm(float n){ ///当n小于等于12时调用函数m()
long int i; //定义变量i
int sum; //定义变量sum，用于存放求得阶乘的结果
{
for(k=0,up=0;k<length;k++)
a[k]*=j;
for(k=0;k<length;k++)
{
a[k]+=up;
up=a[k]/size;// 计算向高位进的数值
a[k]=a[k]%size;//计算当前位的数值
}
if(up)//判断是否需追加数组长度
{来自百度文库
length+=1;
a[length-1]=up;//将进位的值存放到数组最后一位上
{
a[k]+=up;
up=a[k]/size; //进位的数值
a[k]=a[k]%size; //当前位的数值
}
if(up)
{
length+=1;
a[length-1]=up;
}
}
printf("%5d!=",(int)n); //输出n
printf("%d",a[length-1]);
for(i=length-2;i>=0;i--)
8 总结
本次开学前两周是课程设计，尽管比起这种自由的设计我更喜欢上课，但是我知道我们所学的知识都是为了应用，而课程设计就是一个很好的检验我们能力的平台。本次课程设计让我受益匪浅，本次的课程设计主要是对所学过的知识和一些没接触过的知识进行结合运用，不仅是巩固了自己所学的知识，而且把知识与实践相结合，使得自己在自学方面有所提高。这学期我所做的课程设计是n!的非递归算法的实现，在做本次课程设计的时候，自己也相继遇到了很多问题，很多自己的不足之处也暴露了出来，比如：刚开始自己写的代码只能算到12的阶乘，但是因为知道了自己哪里有不足，所以可以针对不足去弥补：翻阅资料、和同学探讨，使得学到的东西更深刻，更透彻，所以本次课程设计使我对非递归算法和进位有了更好的理解。经过这段时间的上机实践学习，我对数据结构和C语言有了更进一步的认识和了解，要想学好它要重在实践，要通过不断地练习和上机编程才能熟练地掌握它。当然，在上机的同时也要有一定的C语言理论知识，这样才能使理论和实践相互促进，在这两方面都有所提高。与此同时，我也认识到了查阅资料和团队的重要性。资料为我们提供了很好的知识，我们没事时应该多翻阅相关资料使得我们的能力更进一步，当自己看不懂时可以和同学讨论，不仅增加了彼此的友谊同时而且使我们对知识的理解更深。通过本次课程设计，我对非递归算法和进位都有了更深的了解，和更加熟练的应用。虽然过去编写程序也经常用到递归，但是当时根本就不了解递归算法和非递归算法的优缺点，现在知道大多数程序采用递归算法来分析，而采用非递归算法来实现，因为递归算法容易溢出，非递归算法更节省空间。在上机实践中，我发现了自己的基础还不是很扎实。有些代码自己还是不能准确地写出来，查看资料的时候有的代码看不懂，有时候还会因为空间分配等问题造成程序错误，但是经过多次实践，一些小的错误自己已经可以很容易解决了，遇到一些较难的问题时，我还是要查看教材和其他的资料来帮助自己解决问题。这种习惯极好地补充了我在程序设计中不足的知识。这使我更深刻地体会到，不管学习那种编译语言，不仅要动脑，更要动手去做。在以后的学习中，我会更加注重实践操作能力的培养，让自己的各方面能力都有所提高。
输入小数，系统会提示“输入错误，请重新输入：”。
本次设计的函数，能求出较大整数的阶乘，能实现循环运算和退出功能。
算法的时间复杂度为：
当n<=12时，O(n)=n;
当n>12时，O（n）=n*length*length;
算法的空间复杂度为:
当n<=12时，O（n）=3≈1;
当n>12时，O（n）=length;
scanf("%d",&g);
printf("\n");
if(g==1) flog=1;
else flog=0;
}
}
6
（1）当n=-3时，结果如图6.1
图6.1当n=-3时，运行结果
（2）当n=0时结果如图6.2
图6.2当n=0时，运行结果
（3）当n=12时，结果如图6.,3
图6.3当n=12时，运行结果
数据结构课程设计
设计说明书
n！非递归算法的设计与实现
学生姓名
赵娜
学号
1021024042
班级
信管102班
成绩
指导教师
曹记东
数学与计算机科学学院
2012 年 3 月 3 日
数据结构课程设计评阅书
题目
n！非递归算法的设计与实现
学生姓名
赵娜
学号
1021024042
指导教师评语及成绩
成绩：教师签名：年月日
答辩教师评语及成绩
(3).模块调用关系如图3.1所示
图3.1 模块调用图
4
4.1定义存储结构和部分代码
#include<stdio.h>
#define N 10000 /*12!=479001600;*/ //定义数组的长度为10000
#define size 100000 //定义size,用于规定数组的最大存储位数
关键词：n!;非递归;数组;栈
1 课题描述
尽管递归算法是一种自然且合乎逻辑的解决问题的方式，但递归算法的执行效率通常比较差。因此在求解许多问题时常采用递归算法来分析问题，用非递归方法来求解问题；另外一些程序不支持递归算法来求解问题，所以我们都会用非递归算法来求解问题。
本次课程设计主要内容是：用非递归算法实现n!的计算，由于计算机中数据的存储范围有限，而又要求出尽可能大的n的阶乘的值，用数组构造n的运算结果的存储结构,用栈的存储方式，最后输出n!的运算结果。