《算法分析与设计》实验指导书
《算法分析与设计》课程是计算机专业的一门必修课程。
开设算法分析与设计实验，目的就是为了使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。
《算法分析与设计》课程实验的目的：是为了使学生在课程学习的同时，通过实验环境中的实际操作，对部分算法的具体应用有一个初步的了解，使学生加深了解和更好地掌握《算法分析与设计》课程教学大纲要求的内容。
《算法分析与设计》课程实验的注意事项：在《算法分析与设计》的课程实验过程中，要求学生做到：
(1)预习实验指导书有关部分，认真做好实验内容的准备，就实验可能出
现的情况提前作出思考和分析。
(2)认真书写实验报告。
实验报告包括实验目的和要求，实验情况及其分
析。
(3)遵守机房纪律，服从辅导教师指挥，爱护实验设备。
(4)实验课程不迟到。
如有事不能出席，所缺实验一般不补。
《算法分析与设计》课程实验的验收：实验的验收将分为两个部分。
第一部分是上机操作，包括检查程序运行和即时提问。
第二部分是提交电子的实验报告。
实验一算法实现一
一、实验目的与要求
熟悉C/C++语言的集成开发环境；
通过本实验加深对分治法、贪心算法的理解。
二、实验内容:
掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。
三、实验题
1. 【伪造硬币问题】给你一个装有n个硬币的袋子。
n个硬币中有一个是伪造的。
你的
任务是找出这个伪造的硬币。
为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。
试用分治法的思想写出解决问题的算法，并计算其时间复杂度。
2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。
售
货员希望用数目最少的硬币找给小孩。
假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。
给出一种找零钱的贪心算法。
a)实验步骤
理解算法思想和问题要求；
编程实现题目要求；
上机输入和调试自己所编的程序；
验证分析实验结果；
整理出实验报告。
四、实验程序
五、实验结果
六、实验分析
1本实验运用分治算法。
可将硬币分成N堆来进行实验
若分成两堆算法思想如下
步骤一、令x等于n.
步骤二、若x为偶数，
则将袋子中的硬币一分为二，即各x/2个放仪器上比较两组硬币的重量,那组较轻伪造的硬币就在该组。
若n等于2,则结束，因为已经找出伪造硬币。
否则，令n=n/2，执行步骤一。
否则，
取出一个硬币后，再把剩下的x-1个硬币进行分组，每组(x-1)/2个硬币；并放在仪器上比较两组的重量，若两组一样重，则刚才拿出来的硬币为伪造的；否则，伪造的硬币在较轻的那一组。
若n等于2,则结束，因为已经找出伪造硬币。
否则，令n=(x-1)/2，执行步骤一。
时间复杂度。
因为以上算法应用的是二分法的思想，每次比较排除1/2的真硬币。
所以其时间复杂度为O(n)。
分成三堆思想
/*总体思想：将所有的硬币分成三堆，通过比较三堆的质量找出与其他两组不同的一组，伪造的硬币一定在这一组中。
写程序时还须注意硬币号
所以一共有三种可能性：
1.硬币刚好能分成三堆，即硬币的数目能被3整除。
这样只需要比较哪堆硬币质量和其他的两组质量不一样，不一样的那组是有伪造硬币的那组。
2.硬币的数目被3整除余1。
再将这一种情况分成两种情况考虑：
a.三组硬币质量相等，则剩下的硬币是伪造的。
b.三组硬币质量不等，则情况与1一致。
3.硬币数目被3整除余2。
也将这一种情况分成两种情况考虑：
a.三组硬币质量相等，则伪造的硬币一定在剩下的两个硬币当中。
从三组硬币中任意取出一个与剩下的两个硬币比较质量，则质量与其他两个不相等的硬币是伪造的。
b.三组硬币质量不等，则情况与1一致。
*/
实验程序如下
#include <iostream>
#include <>
using namespace std;
void findTheCoin(int a[], int n ,int num);
2M
找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。
售货员希望用数目最少的硬币找给小孩。
假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。
给出一种找零钱的贪心算法。
对于给定的数额，用面值25、10、5、2、1的硬币找零，要求所用硬币总数最少。
实现，算法如下：
#include <iostream>
#include <>
using namespace std;
int main()
{
int a,b25,b10,b5,b2,b1;
cout <<"请输入要找的零钱:"<<endl;
cin>>a;
b25=(a/25);
b10=(a%25)/10;
b5=(a%25)%10/5;
b2=(a%25)%10%5/2;
b1=(a%25)%10%5%2;
cout<<"需要以下几枚零钱:"<<endl;
if(b25!=0)
cout<<"25分的"<<b25<<"枚"<<endl;
if(b10!=0)
cout<<"10分的"<<b10<<"枚"<<endl;
if(b5!=0)
cout<<"5分的"<<b5<<"枚"<<endl;
if(b2!=0)
cout<<"2fende"<<b2<<"mei"<<endl;
if(b1!=0)
cout <<"1分的"<<b1<<"枚"<< endl;
return(0);
}
实验二算法实现二一、实验目的与要求
熟悉C/C++语言的集成开发环境；
通过本实验加深对贪心算法、动态规划和回溯算法的理解。
二、实验内容:
掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。
三、实验题
1."0-1"背包问题的贪心算法
2."0-1"背包问题的动态规划算法
3."0-1"背包问题的回溯算法
四、实验步骤
理解算法思想和问题要求；
编程实现题目要求；
上机输入和调试自己所编的程序；
验证分析实验结果；
整理出实验报告。
五、实验程序
六、实验结果
七、实验分析。