《第6章过程封装--函数》.ppt

解法1　－－分治法 如果我们可以用一个硬币找零，这就是最小的。 否则，对于每个可能的值i，我们可以独立计算找i分钱零钱和K-i分钱需要的最小硬币数。然后选择这个和最小的i。 怎样找出63分钱零钱 找出1分钱零钱和62分钱零钱分别需要的硬币数是1和4。因此，63分钱需要使用五个硬币。 找出2分钱和61分钱分别需要2和4个硬币，一共是六个硬币。 我们继续尝试所有的可能性。我们看到一个21分和42分的分解，它可以分别用一个和两个硬币来找开，因此，这个找零问题就可以用三个硬币解决。 我们需要尝试的最后一种分解是31分和32分。我们可以用两个硬币找出31分零钱，用三个硬币找出32分零钱，一共是五个硬币。 因此最小值是三个硬币。 int coin(int k) { int i, tmp, int coinNum = k; if （能用一个硬币找零） return 1; for (i=1; ik; ++i) if ((tmp = coin(i) + coin(k-i)) coinNum) 　　　　coinNum = tmp; return coinNum; } 上述解法分析 此算法的效率很低 事实上63分钱找零的问题是不会在一个合理的时间内解决的。就如Finbonacci 函数一样 解法2 通过指定其中的一个硬币来递归地简化问题。 例如，对于63分钱，我们可以给出以下找零的办法。 一个1分的硬币加上递归地分派62分钱 一个5分的硬币加上递归地分派58分钱 一个10分的硬币加上递归地分派53分钱 一个21分的硬币加上递归地分派42分钱 一个25分的硬币加上递归地分派38分钱 该算法的问题仍然是效率问题 动态规划解 效率低下主要是由于重复计算造成的。因此，可把已有子问题的答案存放起来，当再次遇到此子问题时就不用重复计算了。 在本例中，我们用coinsUsed[i]代表了找i分零钱所需的最小硬币数。 算法思想 先找出一分钱的找零方法，把最小硬币数存入coinUsed[1] 依次找出2分钱、3分钱…的找零方法，知道到达要找零的钱为止： 对每个要找的零钱i，可以把i分解成某个coins[j]和 i - coins[j]， 所需硬币数为coinUsed[i-coins[j]]+1。对所有的j，取最小的coinUsed[i-coins[j]]+1作为i元钱找零的的答案。 函数原型 Void makechange( int coins[], int differentCoins, int maxChange, int coinUsed [] ) Coins存放所有不同的硬币值，不同的硬币个数为differentCoins。 maxChange为要找的零钱数 void makechange( int coins[ ], int differentCoins, int maxChange, int coinUsed[] ) { coinUsed[0] = 0; for (int cents = 1; cents = maxChange; cents++) { int minCoins = cents; //都用1分找零，硬币数最大 for (int j = 1; j differentCoins; j++) //尝试所有硬币 { if (coins[j] cents) continue; //coin[j]硬币不可用 if (coinUsed[ cents - coins[j] ] + 1 minCoins) //分解成coins[i]和cents-coins[j] minCoins = coinUsed[ cents - coins[j] ] + 1; //用此硬币 } coinUsed[cents] = minCoins; } } 总结 函数可以将一段完成独立功能的程序封装起来。通过函数名就可执行这一段功能。使用函数可以将程序模块化 C++的程序是由一组函数组成。每个程序必须有一个名为main的函数，它对应于一般的程序设计语言中主程序 函数也可以调用自己，这样的函数称为递归函数 基于递归的算法 计算机网络讲义 *