算法分析与设计实验报告

掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。 1. 【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算其时间复杂度。 2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       1839  2008-11-26 20:30  算法分析实验\01背包 回溯.txt

     文件      26112  2008-11-12 22:11  算法分析实验\《算法分析与设计》 实验指导书.doc

     文件      75776  2010-04-26 14:24  算法分析实验\算法实验一.doc

     文件      98304  2010-04-26 14:25  算法分析实验\算法实验二.doc

     文件      59392  2008-11-25 21:22  算法分析实验\贪心算法.doc

     文件      12998  2008-11-25 21:00  算法分析实验\贪心算法.txt

     目录          0  2010-04-26 14:25  算法分析实验

----------- ---------  ---------- -----  ----

               274421                    7