求解一道作业题。。。Python + Recursion

好久不写程序，最近翻看sicp发现伯克利的一个公开课上有这道题。本来以为求到最接近的2**n<=Amount，再partition一下做个recursion就行了，结果老是不对，到了count_change(100)就大相径庭了。。考虑可能是思路问题，求教下各位伙伴！谢谢！

原题：

Once the machines take over, the denomination of every coin will be a power of two: 1-cent, 2-cent, 4-cent, 8-cent, 16-cent, etc. There will be no limit to how much a coin can be worth.

A set of coins makes change for n if the sum of the values of the coins is n. For example, the following sets make change for 7:

    7 1-cent coins
    5 1-cent, 1 2-cent coins
    3 1-cent, 2 2-cent coins
    3 1-cent, 1 4-cent coins
    1 1-cent, 3 2-cent coins
    1 1-cent, 1 2-cent, 1 4-cent coins

Thus, there are 6 ways to make change for 7. Write a function count_change that takes a positive integer n and returns the number of ways to make change for n using these coins of the future:

def count_change(amount):
    """Return the number of ways to make change for amount.

    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """

不求同年同日生，只求热心求解不鄙视。。

代码贴出来看看？动态规划应该可以解决的，划分子类比较蛋疼。话说最后部分是答案吗？如果是的话那我这个程序是对的。我用Java写的，参考的是这个：http://www.algorithmist.com/index.php/Coin_Change

代码如下：

1. public class CountChange {
   
2.         public int countChange(int amount, int dim, int[][] count) {
   
3.                 int q;
   
4.                 //三种base cases
   
5.                 if (amount == 0) return 1;//没钱了，所以就一种solution，就是不用任何硬币
   
6.                 if (amount < 0) return 0;//钱总额小于0，不可能有solution
   
7.                 if (amount >= 0 && dim < 0) return 0;//钱数大于等于0，但维数小于0，也就是没有coinset存在，也不可能有solution
   
8.                
   
9.                 if (count[amount][dim] >= 0) return count[amount][dim];//如果memo里面已经计算过相应情况的组合数目，那么直接返回。
   
10.                
    
11.                 q = countChange(amount, dim - 1, count) + countChange((int)(amount - Math.pow(2, dim)), dim, count);//具体可见链接http://www.algorithmist.com/index.php/Coin_Change，解释有点复杂。这个就是这个问题比较难得递归分类问题
    
12.                 count[amount][dim] = q;
    
13.                 return q;
    
14.         }
    
15.         public int count(int amount) {
    
16.                 int dim = (int)(Math.log(amount) / Math.log(2));//dim表示最大银币面值的指数，也就是2的dim次为最大面值。他也是组成coinset的维数
    
17.                 int[][] count = new int[amount + 1][dim + 1];//设置一个memo，count[i][j]表示总额为i时，利用维数为j的时候一共有多少种组合方式。
    
18.                 for (int i = 0; i <= amount; i++)
    
19.                         for (int j = 0; j <= dim; j++)
    
20.                                 count[i][j] = -1;
    
21.                 return countChange(amount, dim, count);
    
22.         }
    
23.         public static void main(String[] args) {

复制代码

供参考。

不知为何被审核了。。再发一遍吧。。哎。。
利用动态规划可以解决，寻找子集部分比较巧妙，可参考：http://www.algorithmist.com/index.php/Coin_Change

用Java写的代码如下：

1. public class CountChange {
   
2.         public int countChange(int amount, int dim, int[][] count) {
   
3.                 int q;
   
4.                 //三种base cases
   
5.                 if (amount == 0) return 1;//没钱了，所以就一种solution，就是不用任何硬币
   
6.                 if (amount < 0) return 0;//钱总额小于0，不可能有solution
   
7.                 if (amount >= 0 && dim < 0) return 0;//钱数大于等于0，但维数小于0，也就是没有coinset存在，也不可能有solution
   
8.                
   
9.                 if (count[amount][dim] >= 0) return count[amount][dim];//如果memo里面已经计算过相应情况的组合数目，那么直接返回。
   
10.                
    
11.                 q = countChange(amount, dim - 1, count) + countChange((int)(amount - Math.pow(2, dim)), dim, count);//具体可见链接http://www.algorithmist.com/index.php/Coin_Change，解释有点复杂。这个就是这个问题比较难得递归分类问题
    
12.                 count[amount][dim] = q;
    
13.                 return q;
    
14.         }
    
15.         public int count(int amount) {
    
16.                 int dim = (int)(Math.log(amount) / Math.log(2));//dim表示最大银币面值的指数，也就是2的dim次为最大面值。他也是组成coinset的维数
    
17.                 int[][] count = new int[amount + 1][dim + 1];//设置一个memo，count[i][j]表示总额为i时，利用维数为j的时候一共有多少种组合方式。
    
18.                 for (int i = 0; i <= amount; i++)
    
19.                         for (int j = 0; j <= dim; j++)
    
20.                                 count[i][j] = -1;
    
21.                 return countChange(amount, dim, count);
    
22.         }
    
23.         public static void main(String[] args) {
    
24.                 CountChange t = new CountChange();
    
25.                 int c = t.count(20);
    
26.                 System.out.println(c);
    
27.         }
    
28. 
    
29. }
    

复制代码

搞定了，和同学讨论了一下。应该按照等比数列来做recur的partition。。通常相当于step为+1，这个相当于step是×2

1. def count_change(amount):
   
2.     def count_recur(amount, starter):    # Help function; add starting value to args
   
3.         if amount <= 0:                  # to cater for ((amount - starter), starter)
   
4.             return 0
   
5.         elif amount < starter:           # to cater for (amount, starter * 2)
   
6.             return 0
   
7.         elif amount == starter:          # when amount - start decrease to == starter,
   
8.             return 1                     # or starter * 2 increase to == amount, 1 solution for each call
   
9.         else:
   
10.          ''' p1. (at least) a coin worth of the starting/current value is present in the seq;
    
11.              p2: no coin == starting/current value, roll up one level '''
    
12.             return count_recur(amount - starter, starter) + count_recur(amount, starter * 2 )
    
13.     return count_recur(amount, 1)        # start from the lowest coin value

复制代码

这个和同学商量了一下，觉得之前思考有点复杂，之前在找partition的指进入误区，其实这就是个以1开始等比递增的recur，相对于AP series来说，GP出现的少一点。
代码可能在审核

1. def count_change(amount):
   
2.     def count_recur(amount, starter):    # Help function; add starting value to args
   
3.         if amount <= 0:                  # to cater for ((amount - starter), starter)
   
4.             return 0
   
5.         elif amount < starter:           # to cater for (amount, starter * 2)
   
6.             return 0
   
7.         elif amount == starter:          # when amount - start decrease to == starter,
   
8.             return 1                     # or starter * 2 increase to == amount, 1 solution for each call
   
9.         else:
   
10.          ''' p1. (at least) a coin worth of the starting/current value is present in the seq;
    
11.              p2: no coin == starting/current value, roll up one level '''
    
12.             return count_recur(amount - starter, starter) + count_recur(amount, starter * 2 )
    
13.     return count_recur(amount, 1)        # start from the lowest coin value

复制代码