循环与递归算法实验.doc

_目录实验一 循环与递归算法的应用- 3 -一、实验目的- 3 -二、实验内容- 3 -三、实验步骤- 4 -四.程序调试及运行结果分析- 6 -五.实验总结- 6 -附录：程序清单 （程序过长，可附主要部分）- 7 -实验一 循环与递归算法的应用 一、实验目的1掌握循环、递归算法的基本思想、技巧和效率分析方法。2熟练掌握循环和递归的设计要点，清楚循环和递归的异同。3学会利用循环、递归算法解决实际问题。二、实验内容 1.问题描述：题目一：打印图形编写程序：根据参数n打印具有下面规律的图形，如，当n=4时，图形如下：1 5 2 8 6 3 10 9 7 4 题目二：回文判断判断s字符串是否为“回文”的递归程序。题目三：计算前n项和根据参数n，计算1+2+n。要求：用循环和递归分别实现2.数据输入：个人设定，由键盘输入。3.要求：1）上述题目中学号为单数的做题目一和三，双数做二和三。上机前，完成程序代码的编写2）独立完成实验及实验报告三、实验步骤1.理解算法思想和问题要求；2.编程实现题目要求；3.上机输入和调试自己所编的程序；4.验证分析实验结果；5.整理出实验报告。附：实验报告的主要内容一实验目的二问题描述三算法设计解答第二题，思路为设计一个递归函数，并定义三个参数字符数组s100、整型变量len和i。在函数中利用条件语句判断第一个和最后一个字符是否相同，依次往下进行比较判断，如果是回文数返回1，不是则返回0。并在主函数中利用条件语句将0、1转化为自然语言。Main函数输入字符调用递归函数进行判断是则返回1，否返回0转化成自然语言后输出 图2.1 程序运行流程图第三题计算1到n的数值总和，用循环算法需要设计一层循环，将语句sum+=i；计算n次累加得出结果。但是循环算法相比在时间效率上不如递归算法。所以，可以用递归算法计算较为简单，以n=1为终止条件，多次调用自身即可得出答案。fact(n) fact(n-1) fact(2) fact(1) 递归 回溯图3.1 递归算法示意图四.程序调试及运行结果分析1) 运行程序后，输入asdfghgfdsa 进行判断，运行成功是回文数则返回1值转化为自然语言输出：是回文数。图2.2 判断回文数2) 运行程序后，输入n的数值为100由计算机计算1到100的数字相加之和，运行成功则输出正确结果。图3.2 计算总和五.实验总结这次实验的两道题都用到了递归，递归算法虽然是我们以前已经学过的内容，但是通过这次实验我真正用起来的时候，才发现真的不知从何下手。后来通过书上和老师上课讲解的例题发现，递归算法设计的关键找出递归关系和递归终止条件。递归关系就是使问题向边界条件转化的规则。比如第二题利用条件语句判断第一个和最后一个字符是否相同，依次往下进行比较判断，如果是回文数返回1，不是则返回0。第三题终止条件就是n是否等于1，结束时返回结果。这次实验也使我掌握了构造递归算法的方法技巧，使我更加深入的了解掌握了递归算法，收获较大。附录：程序清单 （程序过长，可附主要部分）第二题程序如下：#include #include int huiwen(char s100,int len,int i)if(i(len-1)/2)if(si=slen-1-i)return 1;elsereturn 0;elseif(si=slen-1-i)return huiwen(s,len,i+1);/如果满足回文条件才递归elsereturn 0;int main()char s100;int len;int n;cins;len=strlen(s);n=huiwen(s,len,0);if(n=1)cout是回文数endl;elsecout不是回文数endl;return 0;第三题程序如下：循环：#includeusing namespace std;int main()int n,i,sum=0;cinn;for(i=1;i=n;i+)sum+=i;cout结果是：sumendl;return 0;递归：#includeusing namespace std;int fact(int n);int main()int n,c;cinn;c=fact(n);cout结果是：cendl;return 0;