云南开放大学算法设计与分析第七章 贪心算法法

习题-7
1.猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘多少个桃子。请按算法的分析步骤设计并求解。

2.数组中有n个数据，要将它们顺序循环向前移k位，即后面的元素向前(左)移k位，前面的元素则循环向后移k位，例：0、1、2、3、4、5循环移2位后为： 2、3、4、5、0、1。考虑到n会很大，不允许用2*n及以上个空间来完成此题。
要求给出：(1) 计算模型并证明；(2)算法设计与描述；(3)算法分析；(4)算法实现与测试。
3.设a和b两个数将为大数，求a*b的值。
要求给出：(1) 计算模型；(2)算法设计与描述；(3)算法分析；(4)算法实现与测试。
4. 有n个底面为长方形的物品需要租用库房存放。如果每个物品都必须放在地面上，且所有物品的底面宽度都等于库房的宽度，那么第i个物品占用库房面积大小只需要用它的底面长度li来表示，i=1,2,…,n。设库房总长度是L，且i=1nli>L。如果要求放入库房的物品个数最多，请选择一个算法设计技术完成此任务。要求：简述该算法的设计思想，证明算法的正确性，并估计算法最坏情况下的时间复杂度。
5. 假设零钱系统的币值是{1,v,v2,…,vn}, v>1,且每个钱币的重量都等于1。设计一个最坏情况下时间复杂度最低的算法，使得对任何钱数x，该算法得到的零钱个数最少。简述算法的主要设计思想，证明它的正确性，并给出最坏情况下的时间复杂度分析。