文档介绍：Algorithm Design Techniques Greedy Algorithms Divide and Conquer Dynamic Programming Backtracking Algorithms Randomized Algorithms Greedy Algorithms ?找零钱问题假定有伍角、壹角、伍分、贰分和壹分共五种硬币,在给顾客找硬币时,一般都会尽可能的选用硬币个数最小的方法。例如,当要给某顾客找七角二分钱时,会给他一个伍角, 2个壹角和 1个贰分的硬币。请编写一个程序,输入的是要找给顾客的零钱(以分为单位),输出的是应该找回的各种硬币数目,并保证找回的硬币数最少。#include <> int main() { int change; cout<<" 请输入要找给顾客的零钱(以分为单位) "; cin>>change; cout<<" 找给顾客的五角硬币个数为: "<<change/50<<endl; change=change%50; cout<<" 找给顾客的壹角硬币个数为: "<<change/10<<endl; change=change%10; cout<<" 找给顾客的伍分硬币个数为: "<<change/5<<endl; change=change%5; cout<<" 找给顾客的贰分硬币个数为: "<<change/2<<endl; change=change%2; cout<<" 找给顾客的壹分硬币个数为: "<<change<<endl; return 0; } 活动安排问题设有 n个活动的集合 e={1 ,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动 i都有一个要求使用该资源的起始时间 si和一个结束时间 fi,且 si<fi 。如果选择了活动 i,则它在时间区间[si, fi]内占用资源。若区间[si, fi]与区间[sj, fj]不相交,则称活动 i与活动 j是相容的。也就是说,当 si≥ fi或 sj≥ fj时,活动 i与活动 j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。?各活动的起始时间和结束时间存储于数组 s和f中且按结束时间的非减序: f1≤ f2≤…≤ fn排列。如果所给出的活动未按此序排列,需重排。 template< class type> void greedyselector(int n, type s[ ], type f[ ], bool a[ ] ) { a[ 1 ] = true; int j = 1; for (int i=2;i< =n;i+ + ) { if (s[i]>=f[j]) { a[i] = true; j=i; } else a[i]= false; }}?该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。 1,4,8,11 Divide and Conquer 找出伪币?假定有 16枚硬币,其中包含一个是伪造的硬币, 这枚伪币比真币要轻一些。要求找出这个伪造的硬币。?为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,利用这台仪器,可以知道两组硬币的重量是否相同。找伪币算法?算法 1:两两比较–最多通过 8次比较来判断伪币的存在并找出这一伪币。?算法 2:利用分治法–16枚硬币的问题就被分为两个 8枚硬币( A组和 B组)的问题。通过比较这两组硬币的重量,可以判断伪币是否存在。如果没有伪币,则算法终止。否则,继续在较轻的那组硬币来寻找伪币。直到最后的那个组里只有两个硬币。比较该组中两个硬币的重量,可以立即找到伪币。–最多需要 4次即能找到伪币