实验1：循环与递归算法实验

《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期第九周一、实验目的1、理解递归的概念和分治法的基本思想2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。

1、求n个元素的全排。

（30分）2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。

（30分）3、设有n=2k个运动员要进行网球循环赛。

设计一个满足要求的比赛日程表。

（40分）提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。

三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include "iostream"using namespace std;#define N 100void Perm(int* list, int k, int m){if (k == m){for (int i=0; i<m; i++)cout << list[i] << " ";cout << endl;return;}else{for (int i=m; i<k; i++){swap(list[m], list[i]);Perm(list, k, m+1);swap(list[m], list[i]);}}}void swap(int a,int b){int temp;temp=a;a=b;b=temp;}int main(){int i,n;int a[N];cout<<"请输入排列数据总个数：";cin>>n;cout<<"请输入数据：";for(i=0;i<n;i++){cin>>a[i];}cout<<"该数据的全排列："<<endl;Perm(a,n,0);return 0;}《算法设计与分析》实验报告实验二递归与分治策略应用提高学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期一、实验目的1、深入理解递归的概念和分治法的基本思想2、正确使用递归与分治策略设计相应的问题的算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。

实验01熟悉环境和递归算法
[实验目的]
1.熟悉Java上机环境;
2.基本掌握递归算法的原理方法.
[预习要求]
1.认真阅读算法设计教材,了解递归算法原理;
2.设计用递归算法求解阶乘函数、Ackerman函数、排列问题、整数划分问题的递归程序. [实验题]
1.将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，
k≥1。

正整数n的这种表示称为正整数n的划分。

求正整数n的不同划分个数。

2.设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。

3.Hanoi塔问题
设a,b,c是3个塔座。

开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。

各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的圆盘移到塔座b上，并仍按同样顺序叠置。

在移动圆盘时应遵守以下移动规则：
规则1：每次只能移动1个圆盘；
规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。

[实验步骤]
1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止;
2.应用设计的算法和程序求解问题;
3.将程序整理成功能模块存盘备用.
[实验报告要求]
1.阐述实验目的和实验内容;
2.阐述求解问题的算法原理;（算法流程图和算法描述）
3.提交实验程序的功能模块;
4.记录最终测试数据和测试结果。

[思考与练习]
思考题：如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到d，移动规则不变，求移动步数最小的方案。

实验一：分治与递归【实验目的】深入理解分治法算法思想，并采用分治法进行程序设计。

【实验性质】验证性实验。

【实验内容与要求】设有n=2k个运动员要进行网球循环赛。

现要设计一个满足以下要求的比赛日程表：⑴每个选手必须与其他n-1个选手各赛一次；⑵每个选手一天只能赛一次；⑶循环赛一共进行n-1天。

按此要求可将比赛日程表设计－成有n行和n-l列的一个表。

在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。

用分治法编写为该循环赛设计一张比赛日程表的算法并运行实现、对复杂度进行分析。

算法思想：按分治策略，我们可以将所有选手对分为两组，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。

递归地用这种一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。

这时只要让这2个选手进行比赛就可以了。

下图所列出的正方形表是4个选手的比赛日程表。

其中左上角与左下角的两小块分别为选手1至选手2和选手3至选手4第1天的比赛日程。

据此，将左上角小块中的所有数字按其相对位置抄到右下角，将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手2和选手3至选手4在后2天的比赛日程。

这种安排是符合要求的。

程安排表。

#include<stdio.h>#include<conio.h>#define x 16int a[x][x];void gamecal(int k,int m);void main(){int i,j,m;// int a[x][x]={0};printf("请输入参赛人数(2^x)：");scanf_s("%d",&m);gamecal(1,m);printf("d:");for(i=1;i<m;i++)printf("%d ",i);printf("\n");for(i=0;i<m;i++){for(j=0;j<m;j++)printf("%d ",a[i][j]);printf("\n");}}void gamecal(int k,int m){int i,j;if(m==2){a[k-1][0]=k;a[k][0]=k+1;}else{gamecal(k,m/2);gamecal(k+m/2,m/2);}for(i=k-1;i<k-1+m/2;i++){for(j=m/2;j<m;j++)a[i][j]=a[i+m/2][j-m/2];}for(i=k-1+m/2;i<k-1+m;i++){for(j=m/2;j<m;j++)a[i][j]=a[i-m/2][j-m/2];}}。

递归算法实验报告篇一：递归算法的设计和实现的实验报告班级学号姓名实验组别试验日期室温报告日期成绩报告内容：（目的和要求、原理、步骤、数据、计算、小结等）实验名称：递归算法的设计和应用实验目的：1. 掌握递归算法的实现。

2. 实现递归算法的应用。

实验环境（硬/软件要求）：Windows XX, Visual C++ 6.0实验内容：用递归算法实现前n个自然数的累加和与平均数【C语言源程序】#includeint Digui(int n)//设计递归算法功能为求前n个整数的和//{if(n==0)return 0;if(n==1)return 1;else return Digui(n-1)+n;}int main(){int n;printf("请输入n的值：\n");scanf("%d",&n);printf("计算结果为：\n%d\n",Digui(n));printf("这n个数的平均数是：\n%f\n",(float)Digui(n)/n);}篇二：数据结构- 递归算法实验报告实验报告实验五递归算法实验目的：1.熟悉递归算法的实现过程及实现机理；2.熟练并掌握递归算法的设计方法；3.了解递归算法到非递归算法的转换。

实验原理：高级程序语言函数调用原理；递归算法的设计方法。

实验内容：6-14 折半查找问题。

折半查找问题的描述见6.1节，折半查找问题的递归算法见例6-2。

要求：（1）设计折半查找问题的循环结构算法；（2）设计一个查找成功的例子和一个查找不成功的例子，并设计测试主程序；（3）设计一个包含10000个数据元素的查找成功的例子，然后分别调用循环结构的查找算法和递归结构的查找算法，并测试出两种算法在计算机上的实际运行时间。

实验结果：（1）折半查找问题的循环结构算法程序为：int Csearch(int test[],int x,int low,int high) {int i;for( i=0;i {if(x==test[i]) return i;else if(x>test[i])low=i+1;else high=i-1;}if(i>=high) return -1;}（2）①查找成功的例子：#includeint Csearch(int test[],int x,int low,int high) {int i;for( i=0;i {if(x==test[i]) return i;else if(x>test[i])low=i+1;else high=i-1;}if(i>=high) return -1;}int main(){int a[10]={1,2,3,4,5,6,7,8,9,10};int x=6,flag ;int low=0,high=10;flag=Csearch(a,x,0,10);if(flag==-1) printf("searching is failed!\n"); else printf("searching is success!\n") ;printf("This program is made by 10273206\n"); }运行结果为：②查找失败的例子为：#includeint Csearch(int test[],int x,int low,int high) {int i;for( i=0;i {if(x==test[i]) return i;else if(x>test[i])low=i+1;else high=i-1;}if(i>=high) return -1;}int main(){int a[10]={1,2,3,4,5,6,7,8,9,10};int x=11,flag ;int low=0,high=10;flag=Csearch(a,x,0,10);if(flag==-1) printf("searching is failed!\n"); else printf("searching is success!\n") ;printf("This program is made by 10273206\n"); }运行结果为：（3）程序为：#include#includeint Bsearch(int a[],int x,int low,int high) {int mid;if(low>high) return -1;mid=(low+high)/2;if(x==a[mid]) return mid;else if(x Bsearch(a,x,low,mid-1);elseBsearch(a,x,mid+1,high);}int Csearch(int test[],int x,int low,int high) {int i;for( i=0;i {if(x==test[i]) return i;else if(x>test[i])low=i+1;else high=i-1;}if(i>=high) return -1;}int main(){time_t start,end;double dif;int Bsearch(int a[],int x,int low,int high);int Csearch(int test[],int x,int low,int high);int a[10000],x,y,i,bn,flag;int low=0,high=10000,mid=0;printf("please enter number:\n");scanf("%ld",&x);for( i=0;i a[i]=i+1;time(&start);bn=Bsearch(a,x,0,10000);if(bn==-1) printf("%d is not in a !\n",x);else printf("%d is in a,suffix is %d\n",x,bn);time(&end);dif=difftime(end,start);printf("di gui method use time is:%f seconds\n",dif);time(&start);flag=Csearch(a,x,0,10000);if(flag==-1) printf("%ld is not in a !\n",x);else printf("%d is in a,suffix is %d\n",x,flag);time(&end);dif=difftime(end,start);printf("xun huan method use time is :%f seconds\n",dif);printf("This program is made by 10273206\n");}运行结果为：总结与思考通过实验我初步了解了递归算法到非递归算法的转换，递归算法在数据结构存储中用处很大。

实验一循环与递归一、实验目的进一步理解循环与递归程序设计的基本思想，充分利用基本的机械化操作设计高质量的算法。

二、实验要求1、上机前的准备工作根据实验内容中所给题目，利用所学循环与递归的基本设计思想设计算法并编写好上机程序，以提高上机效率；2、独立上机，输入、调试所编程序；3、上机结束后，写出实验报告。

4、上机时间：2学时三、实验内容1、核反应堆中有α和β两种粒子，每秒钟内一个α粒子可以反应产生3个β粒子，而一个β粒子可以反应产生1个α粒子和2个β粒子。

若在t=0时刻的反应堆中只有一个α粒子，求在t时刻的反应堆中α粒子和β粒子数。

#include <iostream>using namespace std;int X(int n);int Y(int n){if(n==1) return 3;return 3*X(n-1)+2*Y(n-1);}int X(int n){if(n==1) return 0;return Y(n-1);}void main(){int t;cout<<"请输入t的值：";cin>>t;cout<<"粒子的个数依次为："<<X(t)<<","<<Y(t)<<endl;}运行结果：2、求这样的两位数据：五位数=3*四位数，9个数字各不相同#include <iostream>using namespace std;int main(){long x, y1, y2;int p[10],i,t,k;for (x=3334;x<=9999; x++){for(i=0; i<=9; i=i+1)p[i]=0;y1=3*x ;k=0;y2=10000*y1+x;while(y2>=0){t=y2 % 10;if(p[t]==1)break;y2=y2/10;p[t]++;k++;}if(k==9)cout<<"四位数："<<x<<","<<"五位数："<< y1<<endl;}}运行结果：3、A、B、C、D、E五人为某次竞赛的前五名，他们在比赛前猜名次：A说：B得第三名，C得第五名B说：D得第二名，E得第四名C说：B得第一名，E得第四名D说：C得第一名，B得第二名E说：D得第二名，A得第三名结果每个人都猜对了一半，实际名次是什么？#include <iostream>using namespace std;void main( ){int a,b,c,d,e;for( a=1;a<=5;a++)for( b=1;b<=5;b++)if (a!=b)for( c=1;c<=5;c++)if (c!=a&&c!=b)for( d=1;d<=5;d++)if (d!=a && d!=b && d!=c ){e=15-a-b-c-d;if (e!=a&&e!=b&& e!=c&&e!=d)if(((c==5)+(b==3))==1&&((d==2)+(e==4))==1&& ((b==1)+(e==4))==1&& ((c==1)+(b==2))==1&& ((d==2)+(a==3))==1)cout<< "a,b,c,d,e="<<a<<b<<c<<d<<e<<endl;}}运行结果：4、从下列题中任选其一：1）国王分财产。

递归算法实验报告篇一：递归算法的设计和实现的实验报告班级学号姓名实验组别试验日期室温报告日期成绩报告内容：（目的和要求、原理、步骤、数据、计算、小结等）实验名称：递归算法的设计和应用实验目的：1. 掌握递归算法的实现。

2. 实现递归算法的应用。

实验环境（硬/软件要求）：Windows XX, Visual C++ 6.0实验内容：用递归算法实现前n个自然数的累加和与平均数【C语言源程序】#includeint Digui(int n)//设计递归算法功能为求前n个整数的和//{if(n==0)return 0;if(n==1)return 1;else return Digui(n-1)+n;}int main(){int n;printf("请输入n的值：\n");scanf("%d",&n);printf("计算结果为：\n%d\n",Digui(n));printf("这n个数的平均数是：\n%f\n",(float)Digui(n)/n);}篇二：数据结构- 递归算法实验报告实验报告实验五递归算法实验目的：1.熟悉递归算法的实现过程及实现机理；2.熟练并掌握递归算法的设计方法；3.了解递归算法到非递归算法的转换。

实验原理：高级程序语言函数调用原理；递归算法的设计方法。

实验内容：6-14 折半查找问题。

折半查找问题的描述见6.1节，折半查找问题的递归算法见例6-2。

要求：（1）设计折半查找问题的循环结构算法；（2）设计一个查找成功的例子和一个查找不成功的例子，并设计测试主程序；（3）设计一个包含10000个数据元素的查找成功的例子，然后分别调用循环结构的查找算法和递归结构的查找算法，并测试出两种算法在计算机上的实际运行时间。

实验结果：（1）折半查找问题的循环结构算法程序为：int Csearch(int test[],int x,int low,int high) {int i;for( i=0;i {if(x==test[i]) return i;else if(x>test[i])low=i+1;else high=i-1;}if(i>=high) return -1;}（2）①查找成功的例子：#includeint Csearch(int test[],int x,int low,int high) {int i;for( i=0;i {if(x==test[i]) return i;else if(x>test[i])low=i+1;else high=i-1;}if(i>=high) return -1;}int main(){int a[10]={1,2,3,4,5,6,7,8,9,10};int x=6,flag ;int low=0,high=10;flag=Csearch(a,x,0,10);if(flag==-1) printf("searching is failed!\n"); else printf("searching is success!\n") ;printf("This program is made by 10273206\n"); }运行结果为：②查找失败的例子为：#includeint Csearch(int test[],int x,int low,int high) {int i;for( i=0;i {if(x==test[i]) return i;else if(x>test[i])low=i+1;else high=i-1;}if(i>=high) return -1;}int main(){int a[10]={1,2,3,4,5,6,7,8,9,10};int x=11,flag ;int low=0,high=10;flag=Csearch(a,x,0,10);if(flag==-1) printf("searching is failed!\n"); else printf("searching is success!\n") ;printf("This program is made by 10273206\n"); }运行结果为：（3）程序为：#include#includeint Bsearch(int a[],int x,int low,int high) {int mid;if(low>high) return -1;mid=(low+high)/2;if(x==a[mid]) return mid;else if(x Bsearch(a,x,low,mid-1);elseBsearch(a,x,mid+1,high);}int Csearch(int test[],int x,int low,int high) {int i;for( i=0;i {if(x==test[i]) return i;else if(x>test[i])low=i+1;else high=i-1;}if(i>=high) return -1;}int main(){time_t start,end;double dif;int Bsearch(int a[],int x,int low,int high);int Csearch(int test[],int x,int low,int high);int a[10000],x,y,i,bn,flag;int low=0,high=10000,mid=0;printf("please enter number:\n");scanf("%ld",&x);for( i=0;i a[i]=i+1;time(&start);bn=Bsearch(a,x,0,10000);if(bn==-1) printf("%d is not in a !\n",x);else printf("%d is in a,suffix is %d\n",x,bn);time(&end);dif=difftime(end,start);printf("di gui method use time is:%f seconds\n",dif);time(&start);flag=Csearch(a,x,0,10000);if(flag==-1) printf("%ld is not in a !\n",x);else printf("%d is in a,suffix is %d\n",x,flag);time(&end);dif=difftime(end,start);printf("xun huan method use time is :%f seconds\n",dif);printf("This program is made by 10273206\n");}运行结果为：总结与思考通过实验我初步了解了递归算法到非递归算法的转换，递归算法在数据结构存储中用处很大。

递归算法的实验报告引言递归算法是计算机科学中一种重要的算法思想，通过将问题分解为更小的子问题并逐步解决，从而实现问题的求解。

本实验旨在探讨递归算法的原理，并通过具体例子来说明递归算法的应用。

算法原理1.递归定义：递归算法通过将问题分解为规模更小的子问题来解决。

通常，递归算法会有一个或多个基准情况，当问题的规模达到基准情况时，递归调用将停止。

2.递归调用：在递归算法中，函数会调用自身来解决规模更小的子问题。

通过递归调用，问题的规模逐步缩小，直到达到基准情况。

3.递归终止条件：递归算法必须定义一个或多个递归终止条件，当满足这些条件时，递归调用将停止。

实验步骤为了更好地理解递归算法的应用，我们选取了斐波那契数列作为示例，并通过递归算法计算斐波那契数列的第n项。

1.确定递归终止条件：斐波那契数列的第0项和第1项为预定义的基准情况，所以递归终止条件为n=0或n=1。

2.实现递归算法：创建一个递归函数fibonacci(n)，用于计算斐波那契数列的第n项。

3.处理递归调用：在递归函数中，当n大于1时，调用fibonacci(n-1)和fibonacci(n-2)来计算第n-1项和第n-2项，并将它们相加得到第n项的值。

4.返回计算结果：将计算得到的结果返回给调用者。

实验结果通过上述步骤，我们成功实现了递归算法来计算斐波那契数列的第n项。

以下是一些示例结果：•当n=0时，第0项为0。

•当n=1时，第1项为1。

•当n=2时，第2项为1。

•当n=3时，第3项为2。

•当n=4时，第4项为3。

我们还可以通过增大n的值来计算更多项的斐波那契数列。

实验总结通过本次实验，我们深入了解了递归算法的原理和应用。

递归算法通过将问题分解为更小的子问题，从而解决复杂的计算任务。

然而，递归算法也存在一些缺点，如效率较低和可能出现栈溢出的风险。

因此，在实际应用中需要谨慎使用递归算法，并针对具体问题选择合适的算法思想。

希望通过本次实验，读者对递归算法有了更深入的理解，并能够灵活运用递归算法解决实际问题。

一、实验背景递归算法是计算机科学中一种重要的算法设计方法，它通过将复杂问题分解为若干个规模更小的相同问题来求解。

递归算法在处理某些问题时具有简洁、直观和高效的优点。

本实验旨在通过实践和探索，深入理解递归算法的设计与实现，并分析其优缺点。

二、实验目的1. 理解递归算法的基本概念和原理。

2. 掌握递归算法的设计方法。

3. 分析递归算法的优缺点。

4. 通过具体实例，实践递归算法的编程实现。

三、实验内容本实验选择了两个具有代表性的递归算法进行实践：汉诺塔问题和斐波那契数列问题。

1. 汉诺塔问题汉诺塔问题是一个经典的递归问题，描述了三个柱子和n个大小不同的盘子，初始时盘子按从小到大的顺序放在第一个柱子上，目标是将所有盘子移动到第三个柱子上，每次只能移动一个盘子，且在移动过程中，大盘子不能放在小盘子上面。

实验步骤：（1）定义递归函数`move(n, source, target, auxiliary)`，其中n表示盘子数量，source表示起始柱子，target表示目标柱子，auxiliary表示辅助柱子。

（2）当n=1时，直接将盘子从source移动到target。

（3）当n>1时，首先将前n-1个盘子从source移动到auxiliary，然后将第n个盘子从source移动到target，最后将前n-1个盘子从auxiliary移动到target。

代码实现：```pythondef move(n, source, target, auxiliary):if n == 1:print(f"Move disk 1 from {source} to {target}")returnmove(n-1, source, auxiliary, target)print(f"Move disk {n} from {source} to {target}")move(n-1, auxiliary, target, source)```2. 斐波那契数列问题斐波那契数列是一个著名的数列，其中每个数都是前两个数的和。

软件英才网软件行业驰名招聘网站一步一步写算法（之循环和递归）其实编程的朋友知道，不管学什么语言，循环和递归是两个必须学习的内容。

当然，如果循环还好理解一点，那么递归却没有那么简单。

我们曾经对递归讳莫如深，但是我想告诉大家的是，递归其实没有那么可怕。

所谓的递归就是函数自己调用自己而已，循环本质上也是一种递归。

1）求和递归函数我们可以举一个循环的例子，前面我们说过，如果编写一个1到n的求和函数怎么写呢，你可能会这么写：1int calculate(int m)2{3int count = 0;4if(m <0)5return -1;67for(int index = 0; index <= m; index++)8 count += index;910return count;11}12int calculate(int m)13{14if(m == 0)15return 0;16else17return calculate(m -1) + m;18}大家看着两段代码有什么不同？（1）第一段代码从0，开始计算，从0到m逐步计算；第二段代码是从10开始计算，逐步到0之后这回，这样同样可以达到计算的效果（2）第一段代码不需要重复的压栈操作，第二段需要重复的函数操作，当然这也是递归的本质（3）第一段代码比较长，第二段代码较短软件英才网软件行业驰名招聘网站2）查找递归函数大家可能说，这些代码有些特殊。

如果是查找类的函数，有没有可能修改成递归函数呢？19int find(int array[], int length, int value)20{21int index = 0;22if(NULL == array || 0 == length)23return -1;2425for(; index < length; index++)26 {27if(value == array[index])28return index;29 }3031return -1;32}大家可能说，这样的代码可能修改成这样的代码：33int _find(int index, int array[], int length, int value)34{35if(index == length)36return -1;3738if(value == array[index])39return index;4041return _find(index + 1, array, length, value);42}4344int find(int array[], int length, int value)45{46if(NULL == array || length == 0)47return -1;4849return _find(0, array, length, value);50}3）指针变量遍历结构指针是我们喜欢的遍历结构，试想如果有下面定义的数据软件英才网软件行业驰名招聘网站结构：51typedef struct _NODE52{53int data;54struct _NODE* next;55}NODE;56void print(const NODE* pNode)57{58if(NULL == pNode)59return;6061while(pNode){62 printf("%d\n", pNode->data);63 pNode = pNode->next;64 }65}66void print(const NODE* pNode)67{68if(NULL == pNode)69return;70else71 printf("%d\n", pNode->data);7273 print(pNode->next);74}其实，写这么多，就是想和大家分享一下我个人的观点：循环是一种特殊的递归，只有递归和堆栈是等价的。