下载文档原格式
《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：**************姓名：*************班级：*************日期：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、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。
1、硬币面值组合描述使用1角、2角、5角硬币组成n 角钱。
设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。
输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。
输入一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。
输出输出有若干行，每行的形式为：i a b c第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。
样例输入样例输出源代码：#include<stdio.h>#include<stdlib.h>int main(){int t=1;int i,j,k;int n;scanf("%d",&n);int A=n,B=n/2,C=n/5;for(i=0;i<=C;i++){for(j=0;j<=B;j++){for(k=0;k<=A;k++){if(i*5+j*2+k*1==n){printf("%03d%12d%12d%12d\n",t,k,j,i);t++;}}}}getchar();return 0;}2、比赛排名描述5名运动员参加100米赛跑，各自对比赛结果进行了预测：A说：E是第1名。
B说：我是第2名。
C说：A肯定垫底。
D说：C肯定拿不了第1名。
E说：D应该是第1名。
比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。
请编程判断5位选手各是第几名。
输入无输出输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。
样例输入样例输出源代码：#include<stdio.h>int main(){printf("5\n");printf("2\n");printf("1\n");printf("3\n");printf("4\n");return 0;}3、鸡兔同笼描述一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。
动态规划之找最少零钱的硬币问题/* 硬币找零：动态规划算法算法描述：当求解总⾯值为 i 的找零最少硬币数 coinsUsed[ i ] 时，将其分解成求解coinsUsed[ i – cents]和⼀个⾯值为 cents 元的硬币，由于 i – cents < i ，其解coinsUsed[ i – cents] 已经存在，如果⾯值为 cents 的硬币满⾜题意，那么最终解coinsUsed[ i ] 则等于 coinsUsed[ i – cents] 再加上 1（即⾯值为 cents）的这⼀个硬币。
//////////////////////////////////////////////////////////////////////////////////////特定的⾯币值：coins={由⼤到⼩排列的数组}coinused=保存⾯币值为i的纸币找零所需的最⼩硬币数money:需要找零的⾯币coins ----0----1---2--3--4------------|25 21 10 5 1|--------------------------------money=11coinused---0-1-2-3-4-5-6-7-8-9-10-11----|0 1 2 3 4 1 2 3 4 5 1 2|-------------------------------coin---0- 1-2-3-4-5-6-7-8-9-10-11---|0 1 1 1 1 5 1 1 1 1 10 1|-------------------------------*/#include<iostream>using namespace std;//输出每个币值对应的硬币void Print(int *coin,int m){if(m==0)return;else{cout<<coin[m]<<" ";Print(coin,m-coin[m]);}}//找零函数void Find(int money,int *coins,int n){int *coinused=new int[money+1];//保存⾯币的最少零钱数int *coin=new int[money+1];//保存⾯币的各个硬币coin[0]=0;coinused[0]=0;int last=1;for(int cents=1;cents<=money;cents++)//需要找零的⾯币都需从⼩到⼤来计算>>>>>动态规划的⼦问题的解组成问题的解{int mincoins=cents;//每个纸币找零时，最多情况为都是1组成>>>记录最⼩找零数for(int kind=0;kind<n;kind++)//从前向后搜索最先满⾜条件的已知零钱。
动态规划算法——租用游艇问题（一）实验目的：理解动态规划思想，掌握用动态规划设计算法的方法来解决游艇租用问题。
（二）实验内容：长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。
游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。
游艇出租站i到游艇出租站j之间的租金为r（i,j）.设计一个算法，计算出从游艇出租站1到游艇出租站n所需要的最少租金。
（三）实验要求：对于给定的游艇出租站i到游艇出租站j之间的租金为r（i,j），编程计算从游艇出租站1到游艇出租站n所需要的最少租金。
上机调试并测试，记录调试和测试的情况，结合程序进行分析。
（四）实验环境：Vc++编译环境（五）实验主要源代码：（1）用dyna（）函数计算最少租金void dyna(int &n,int f[N][N]){for(int k=2;k<n;k++)for(int i=0;i<n-k;i++){int j=i+k;for(int p=i+1;p<j;p++){int tmp=f[i][p]+f[p][j];if(f[i][j]>tmp)f[i][j]=tmp;}}}（2）在主函数中实现输出结果。
int main(){ifstream fin("050501103in.txt");ofstream fout("050501103out.txt");if (fin.fail()) {cout<<"fin(\"050501103in.txt\")文件出错！请先建立050501103in文本！"<<endl;return 1;}if (fout.fail()) {cout<<"fout(\"050501103out.txt\")文件出错！";return 2;}int f[N][N];int n;int i,j;fin>>n;if(n<=0){ cout<<"请在050501103in文本的第一行中输入游艇出租站的个数："<<endl;cout<<"请在050501103in文本的第二行开始输入n（n-1）/2个站与站之间的租金数："<<endl;}else if(n>N){cout<<"请修改N的值,使N大于n："<<endl;}else {for(i=0;i<n;i++)for(j=0;j<n;j++)if(j>i)fin>>f[i][j];cout<<"请在050501103out文本中看输出结果（从出租站1到n的最少租金）："<<endl;dyna(n,f);fout<<f[0][n-1]<<endl;}}（六）实验结果：050501103in.txt 050501103out.txt3 125 157（七）实验总结：此程序的设计思想：利用dyna（）函数计算最少租金。
贪心算法是一种在每一步选择中都采取当前情况下的局部最优选择，并希望导致结果是全局最优解的算法。
下面是一些贪心算法的题目和解答：1. 旅行商问题(Travelling Salesman Problem)：问题描述：给定一个城市列表和一个距离列表，要求找出一条路径，使得路径上的所有城市都经过，且总距离最短。
贪心算法解法：首先对城市按照距离进行排序，然后从最近的两个城市开始，每次都选择距离当前位置最近的两个城市，直到遍历完所有城市。
由于贪心算法每次选择的都是当前情况下的最优解，因此最终得到的路径总距离是最短的。
2. 背包问题(Knapsack Problem)：问题描述：给定一组物品，每个物品都有自己的重量和价值，要求在不超过背包总重量的情况下，如何选择物品使得背包中物品的总价值最大。
贪心算法解法：按照物品的重量对物品进行排序，然后每次选择重量最小的物品，直到背包已满或无物品可选。
由于贪心算法每次选择的都是当前情况下的最优解，因此最终得到的方案总是可以找到一个大于等于当前最优解的方案。
3. 网格找零问题(Currency Change Problem)：问题描述：给定一组面值不同的硬币，要求用最少的组合方式从一定金额中找零。
贪心算法解法：首先对硬币面值进行排序，然后每次使用当前面值最小的硬币进行组合，直到金额为零或无硬币可选。
贪心算法在此问题中的思路是每次选择最小的硬币进行使用，这样可以保证找零的最小数量。
以上题目和解答只是贪心算法的一部分应用，实际上贪心算法在许多其他领域也有广泛的应用，例如网页布局优化、任务调度、网络流等等。
贪心算法的优势在于其简单易懂、易于实现，但也有其局限性，例如无法处理一些存在冲突的情况或最优解不唯一的问题。
因此在实际应用中需要根据具体问题选择合适的算法。
动态规划基础之硬币问题 动态规划是⼀种算法思想，可以简单解释为将复杂问题分解为许多个⼦问题，在⽆后效性的前提下⼀⼀解决，最后得到原复杂问题的最优解。
1.最少硬币问题 有n种硬币，⾯值为v1,v2,....vn，数量⽆限。
输⼊⾮负整数s，选⽤硬币，使其和为s。
输出最少硬币的组合的数量。
易得其状态转移⽅程为ans[i]=min(ans[i],ans[i-v[j]]+1) (j=1,2...n)其中ans[i]表⽰硬币之和，v[j]表⽰硬币种类，此题本质为背包问题。
2.打印最少硬币的组合 把dp的代码改为：if(ans[i]>ans[i-v[i]]+1){//⽤的硬币变了ans_path[i]=v[i]; //在每个⾦额上记录路径，即某个硬币的⾯值ans[i]=ans[i-v[i]]+1; //递推式} 3.所有硬币组合 有n种硬币，⾯值为v1,v2,....vn，数量⽆限。
输⼊⾮负整数s，选⽤硬币，使其和为s。
输出所有可能的硬币组合的数量。
其状态转移⽅程为dp[i]+=dp[i-v[j]] (j=1,2,3,...n) 例题Coin ChangeTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 34000 Accepted Submission(s): 12212Problem DescriptionSuppose there are 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We want to make changes with these coins for a given amount of money.For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent coin, or two 5-cent coins and one 1-cent coin, or one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So there are four ways of making changes for 11 cents with the above coins. Note that we count that there is one way of making change for zero cent.Write a program to find the total number of different ways of making changes for any amount of money in cents. Your program should be able to handle up to 100 coins.InputThe input file contains any number of lines, each one consisting of a number ( ≤250 ) for the amount of money in cents.OutputFor each input line, output a line containing the number of different ways of making changes with the above 5 types of coins.Sample Input11 26Sample Output4 13 此题与3的区别在于硬币的数量有限，这就需要建⽴第⼆个维度来存储硬币的数量这个状态了。
用改进的贪心算法解决最少硬币问题,暂称之为贪心枚举法.由贪心算法可知尽量用大面值的硬币组合来找钱，可以使使用的硬币最少。
而贪心算法对最少硬币问题的解决总是可以得到最优解很好的近似解。
本算法就是用贪心策略枚举出所有近似最优解，然后从中寻找到问题的最优解寻找近似最优xx例如：9分面值的硬币5枚，8分面值的硬币5枚，2分面值的硬币8枚，要找25分钱。
设要找的钱为m，硬币种类为n，t[i](0<i<=n)为硬币的面值，c[i]为可以使用的各种面值的硬币个数, k[i]为第i种面值的硬币可以使用的最多个数（k[i]=min{m/t[i],c[i]}）(1)将硬币依面值大小排序9 8 2(2)按面值种类划分不同情况有多少种面值就划分多少种情况.每种情况的第一枚硬币面值各不一样,其后对剩余的硬币按面值从大到小排列.划分为三个情况：982，892，298。
对应k[i]为：k[0]=3, k[1]=3 ,k[2]=8得到近似最优解群为9分1枚,8分2枚;9分1枚,8分1枚,2分4枚;9分1枚,2分8枚.算法优化1,在寻找最优组合过程中，有些情况可以不予考虑。
比如上例中2 9 82,在以小面值的硬币为第一个的情况中，在寻找最优组合时，会遇到两种情况：a、使用硬币个数要比以大面值的硬币(如9和8)为第一个的情况大得多。
b、寻找到的组合与前面的情况有重复。
在程序中实现剪枝如果k[i]不比mincount大，则继续用贪心算法寻找近似最优组合。
如上例mincount初始值设为maxint。
k[0]=3 < mincount,则进行贪心选择，并将最好结果放于mincount中mincount=3；k[1]=3 <= mincount=3,进行贪心选择；k[2]=8 > mincount=3,则将其剪枝这样可以有效的减小问题的规模。
该算法的优劣1、对于硬币面值大的情况，执行效率会提高（因为k[i]变小了）。
列举贪心算法求解的经典问题贪心算法是一种常用的求解优化问题的算法，它对问题的求解过程进行优先级排序，每次都选择当前最优的方案，从而得到整体最优的解。
以下是常见的几个贪心算法求解问题。
1.零钱兑换问题：给定一定面额的硬币，求解组成指定数量的钱的最小硬币数。
可以使用贪心算法，每次选择面额最大的硬币进行组合。
2.区间覆盖问题：给定若干条线段和一定长度的区间，求解怎样选择几条线段才能够覆盖整个区间。
可用贪心算法，每次选择覆盖范围最大的线段。
3.背包问题：给定一定限制下的物品和背包容量，求解如何选择物品放入背包中是物品总价值最大。
可用贪心算法，每次选择每个物品单位体积价值最大的物品放入背包中。
4.最小生成树问题：给定一个有n个节点的带权无向图，求解构建一个包含所有节点的最小花费生成树的问题。
可用贪心算法，每次选择当前最小的边加入生成树中。
5. Dijkstra算法：给定一个n个节点的有向图，求解从一个节点到所有节点的最短路径。
可用贪心算法，每次选择当前距离最短的节
点进行扩展。
6. Huffman编码问题：给定一组字符及它们在文本中出现的频率，求解一种编码方式使得编码长度最短。
可用贪心算法，每次选择频率
最小的两个字符进行合并构成一个新的节点。
以上是常见的一些贪心算法求解问题，可以看到它们涉及的问题
领域十分广泛，也是算法竞赛和工程实践中经常使用的算法之一。
贪
心算法虽然看似简单，但需要对问题的模型和贪心策略的设计有深入
的理解，才能够达到最优的解法。
1贪心算法实例贪心算法是一种在每个阶段选择最优解，以期望使最终解也是最优的算法。
它通常不与动态规划相比较，而是作为其一种快速解决方案的方法。
下面我将为你介绍一个贪心算法的实例：最小硬币找零问题。
在现实生活中，我们经常会遇到需要找零的情况，比如给顾客找最少的硬币来凑齐一定金额。
最小硬币找零问题就是通过贪心算法来解决这个问题，即每次找零都找剩下金额中数量最大的硬币。
假设有以下几种硬币：25分、10分、5分和1分。
假设需要找零的金额是41分。
那么贪心算法的实现步骤如下：1.初始化一个空的结果集，用来保存找零的硬币。
2.从最大的硬币开始，即25分硬币。
将41分除以25分硬币，得到商为1和余数为163.将1个25分硬币加入结果集，将16分作为新的待找零金额。
4.接下来选择10分硬币，将16分除以10分硬币，得到商为1和余数为65.将1个10分硬币加入结果集，将6分作为新的待找零金额。
6.再选择5分硬币，将6分除以5分硬币，得到商为1和余数为17.将1个5分硬币加入结果集，将1分作为新的待找零金额。
8.最后选择1分硬币，将1分除以1分硬币，得到商为1和余数为0。
9.将1个1分硬币加入结果集，此时余数为0，找零完毕。
10.返回结果集。
以上就是用贪心算法解决最小硬币找零问题的步骤。
贪心算法的关键是每次选择最优解，即选择剩下金额中数量最大的硬币。
这样就能保证每次找零都尽可能少地使用硬币数量。
然而，贪心算法并不是适用于所有问题的解决方案。
因为它每次只考虑局部最优解，而没有考虑全局最优解。
在一些情况下，使用贪心算法可能得到次优解或者无解。
总结来说，贪心算法是一种简单、高效的算法思想，适用于一些特定的优化问题。
但对于一些复杂的问题，还是需要综合考虑动态规划等其他算法来得到最优解。
