一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1283|回复: 4
收起左侧

[智力题] 求解一道作业题。。。Python + Recursion

[复制链接] |试试Instant~ |关注本帖
charlesdickens 发表于 2014-8-30 17:56:30 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
好久不写程序,最近翻看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
    """
 楼主| charlesdickens 发表于 2014-8-30 18:06:07 | 显示全部楼层
不求同年同日生,只求热心求解不鄙视。。
回复 支持 反对

使用道具 举报

ysyyork 发表于 2014-8-30 23:30:43 | 显示全部楼层
本帖最后由 ysyyork 于 2014-8-31 01:41 编辑

代码贴出来看看?动态规划应该可以解决的,划分子类比较蛋疼。话说最后部分是答案吗?如果是的话那我这个程序是对的。我用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) {
复制代码
供参考。


回复 支持 反对

使用道具 举报

ysyyork 发表于 2014-8-31 01:43:10 | 显示全部楼层
不知为何被审核了。。再发一遍吧。。哎。。
利用动态规划可以解决,寻找子集部分比较巧妙,可参考: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. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| charlesdickens 发表于 2014-8-31 16:02:14 | 显示全部楼层
搞定了,和同学讨论了一下。应该按照等比数列来做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
复制代码
回复 支持 反对

使用道具 举报

 楼主| charlesdickens 发表于 2014-8-31 16:11:04 | 显示全部楼层
这个和同学商量了一下,觉得之前思考有点复杂,之前在找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
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 04:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表