《算法设计与分析》实验三-实验报告电子版.docVIP

学 号 1421050102 《算法设计与分析》 实验报告三 学生姓名 Cherish 专业、班级 指导教师 唐国峰 成绩 计算机与信息工程学院软件工程系 2017 年 4 月 11 日 实验三：贪心算法运用练习 一、实验目的 本次实验是针对贪心算法运用的算法设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。 二、实验步骤与要求 1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容； 3．实验结束后，用统一的实验报告模板编写实验报告。 4．提交说明： （1）电子版提交说明： a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验三_学号_姓名”， 如“《算法设计与分析》实验三张三”。 b 压缩包内为一个“《算法设计与分析》实验三_学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明： a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号 字。 c 行间距：单倍行距。 （3）提交截止时间：2017年4月25日16:00。 实验项目 1．传统的找零钱问题的算法及程序实现（基于人民币）。 2．特殊的0-1背包问题的求解：本次求解的0-1背包问题的特点为每种物品各有M件，已知每个物品的单位价值，求使得所获价值最大的装包方案。 3．设有n个正整数，将它们连接成一排，组成一个最大的多位整数。例如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。 对每个数依次进行10^n的取整，直到某一n值取整结果为0，则返回对10^(n-1)取整的结果， 4．均分纸牌问题：有N堆纸牌，编号分别为1，2，…，n。每堆上有若干张,但纸牌总数必为n的倍数.可以在任一堆上取若干张纸牌,然后移动。移牌的规则为：在编号为1上取的纸牌，只能移到编号为2的堆上；在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如：n=4，4堆纸牌分别为：① 9 ② 8 ③ 17 ④ 6 移动三次可以达到目的：从③取4张牌放到④ 再从③区3张放到②然后从②去1张放到①。 5．数列极差问题：在黑板上写了N个正整数做成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。编程任务：对于给定的数列，编程计算出极差M。 先排序 最大值是由最小的往上叠加剩下的最后一个 最小值是由最大的往下叠加剩下的最后一个 四、实验过程 （一）题目一：传统的找零钱问题的算法及程序实现（基于人民币）。 题目分析 贪心算法是做出在当前看来是最好的选择，并不从整体最优上加以考虑。而本题找零钱也是整体最优的。 算法构造 零钱既有整型又有浮点型对于赋值过于麻烦，先将它们统一乘10，都为整型。内部处理也将找的零钱乘10倍，用10倍后找的零钱的分别对10倍后的不同面额取整，记得不同面额应找的数目。 算法实现 //程序在Visual Studio 2010环境下编写；#includestdio.h #includestdlib.h float in;//收顾客钱数 float consume;//顾客消费钱数 float outmoney;//应找顾客钱数 void out(int n) { int a[7]={500,200,100,50,10,5,1};//将市面上常用零钱面额统一扩大10倍 int b[7];//用于存储找的零钱各面值的个数 for(int i=0;i7;i++) { int j=a[i]; if(n/j0) continue; else b[i]=n/j; n=n-(n/j)*j; } printf(50元\t20元\t10元\t5元\t1元\t5角\t1角\n); for(int i=0;i7;i++) { printf(%d个\t,b[i]); } printf(\n); } void main() { printf(请输入顾客给的钱数：\n); scanf_s(%f,in); printf(请输入顾客消