n！非递归算法的设计与实现1 课题描述尽管递归算法是一种自然且合乎逻辑的解决问题的方式，但递归算法的执行效率通常比较差。
因此在求解许多问题时常采用递归算法来分析问题，用非递归方法来求解问题；另外一些程序不支持递归算法来求解问题，所以我们都会用非递归算法来求解问题。
本次课程设计主要内容是：用非递归算法实现n!的计算，由于计算机中数据的存储范围有限，而又要求出尽可能大的n的阶乘的值，用数组构造n的运算结果的存储结构,用栈的存储方式，最后输出n!的运算结果。
本次课程设计的目的是：通过本次课程设计，可以使大家了解缓存中数据的存储范围，提高自学能力，增强团队合作意识。
2 需求分析本次n!非递归算法的课程设计中主要用到的知识有：数组、函数、栈，选择条件中的结构语句（if…else），和循环结构语句中的语句while()语句、do…while()语句和for()语句，选择语句if的运用。
对n!的非递归的算法，主要是运用非递归的算法实现n的阶乘。
限制条件：(1).要求的n必须是整数；(2). n的范围；(3). 数据类型和表数范围。
递归和非递归算法是相通的，递归是一种直接或间接调用自身的算法，而非递归不调用自身函数递推采用的是递归和归并法，而非递推只采用递归法。
递推法一般容易溢出，所以一般都采用递推法分析，而用非递推法设计程序。
将n定义为float型，便于查看n是否为整数；本次试验分为两个模块：(1).当n小于都等于12时，实现阶乘的模块m(n): 直接用sum*=i;实现求n的阶乘，相对简单，容易就算。
(2).当n大于12时，如果用long型结果就会溢出，所以实现阶乘需调用的模块f(n): 采用数组存放计算的结果，用队列输出运行结果。
由于计算结果较大，将结果除以数组最大存储位数，将高位结果存放在数组的起始地址上，将低位的结果存放在数组的末端地址上，最后采用队列输出运行结果。
(3).模块调用关系如图3.1所示图3.1 模块调用图4.1定义存储结构和部分代码#include<stdio.h>#define N 10000 /*12!=479001600;*/ //定义数组的长度为10000#define size 100000 //定义size,用于规定数组的最大存储位数void f(float n){ //当n大于12时调用函数f()long int a[N],i,j,length,k,up; //定义变量 a[],i,j,length,k,up}void m(float n){ ///当n小于等于12时调用函数m()long int i; //定义变量iint sum; //定义变量sum，用于存放求得阶乘的结果}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++){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; //将进位的值存放到数组最后一位上}}printf("%5d!=",(int)n); //输出nprintf("%d",a[length-1]); //输出高位的运行结果for(i=length-2;i>=0;i--) //将运算结果的第二个最高位到最低位的值输出printf("%d",a[i]); }4.2 流程图主函数流程图见图4.1图4.1 主函数流程图子函数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,用于求解数组的最大存储位数void f(float n){long int a[N],i,j,length,k,up;a[0]=1600;a[1]=4790;length=2; //12!=479001600for(j=13;j<=n;j++){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;}}printf("%5d!=",(int)n); //输出nprintf("%d",a[length-1]);for(i=length-2;i>=0;i--)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(){int sum,flog=1,g;float n;while(flog==1) //根据标签的值判断循环是否结束{printf("请输入整数n:"); //输入要求阶乘的数nscanf("%f",&n);while(n<0||n>999||n!=(int)n) //判断n是否合法{printf("输入错误,请重输入整数n:"); //如果输入不合法，重新输入nscanf("%f",&n);}if(n>12)f(n); //如果n大于12调用函数f(n)elsem(n); //如果n小于等于12调用函数m(n)printf("\n\n"); //换行printf("是否需要继续计算,输入1继续计算,输入0结束: "); //是否继续求n阶乘fflush(stdin);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时，运行结果7 结果分析在执行函数的过程中，对上述提到的各种情况做了判断和提示，如：输入负数，系统会提示“输入错误，请重新输入：”；输入大于999的数，系统会提示“输入错误，请重新输入：”；输入小数，系统会提示“输入错误，请重新输入：”。
本次设计的函数，能求出较大整数的阶乘，能实现循环运算和退出功能。
算法的时间复杂度为：当n<=12时，O(n)=n;当n>12时，O（n）=n*length*length;算法的空间复杂度为:当n<=12时，O（n）=3≈1;当n>12时，O（n）=length;8 总结本次开学前两周是课程设计，尽管比起这种自由的设计我更喜欢上课，但是我知道我们所学的知识都是为了应用，而课程设计就是一个很好的检验我们能力的平台。
本次课程设计让我受益匪浅，本次的课程设计主要是对所学过的知识和一些没接触过的知识进行结合运用，不仅是巩固了自己所学的知识，而且把知识与实践相结合，使得自己在自学方面有所提高。
这学期我所做的课程设计是n!的非递归算法的实现，在做本次课程设计的时候，自己也相继遇到了很多问题，很多自己的不足之处也暴露了出来，比如：刚开始自己写的代码只能算到12的阶乘，但是因为知道了自己哪里有不足，所以可以针对不足去弥补：翻阅资料、和同学探讨，使得学到的东西更深刻，更透彻，所以本次课程设计使我对非递归算法和进位有了更好的理解。
经过这段时间的上机实践学习，我对数据结构和C语言有了更进一步的认识和了解，要想学好它要重在实践，要通过不断地练习和上机编程才能熟练地掌握它。
当然，在上机的同时也要有一定的C语言理论知识，这样才能使理论和实践相互促进，在这两方面都有所提高。
与此同时，我也认识到了查阅资料和团队的重要性。
资料为我们提供了很好的知识，我们没事时应该多翻阅相关资料使得我们的能力更进一步，当自己看不懂时可以和同学讨论，不仅增加了彼此的友谊同时而且使我们对知识的理解更深。
通过本次课程设计，我对非递归算法和进位都有了更深的了解，和更加熟练的应用。
虽然过去编写程序也经常用到递归，但是当时根本就不了解递归算法和非递归算法的优缺点，现在知道大多数程序采用递归算法来分析，而采用非递归算法来实现，因为递归算法容易溢出，非递归算法更节省空间。
在上机实践中，我发现了自己的基础还不是很扎实。
有些代码自己还是不能准确地写出来，查看资料的时候有的代码看不懂，有时候还会因为空间分配等问题造成程序错误，但是经过多次实践，一些小的错误自己已经可以很容易解决了，遇到一些较难的问题时，我还是要查看教材和其他的资料来帮助自己解决问题。
这种习惯极好地补充了我在程序设计中不足的知识。
这使我更深刻地体会到，不管学习那种编译语言，不仅要动脑，更要动手去做。
在以后的学习中，我会更加注重实践操作能力的培养，让自己的各方面能力都有所提高。