魔方吧·中文魔方俱乐部

标题: 人民币问题 [打印本页]

作者: pilyfe 时间: 2008-6-2 11:58:47 标题: 人民币问题

我国现行货币面值为：1分、2分、5分、1角、2角、5角、1元、2元、5元、10元、20元、50元、100元。
问题是：每一张面值的人民币用比他小的面值人民币组成，共有多少种组法？
比如：2分有1种组法、5分有3种、1角有10种......
这该如何计算其他面值？

作者: 魔鱼儿 时间: 2008-6-2 12:20:39

应该是相同数字面值的钱随单位的变化会成几何倍数的增加吧，100元的组合可能就太多了/

不管了，先占沙发。

作者: kexin_xiao 时间: 2008-6-2 12:36:11

抢个板凳，问一下，这个研究有什么意义吗？呵呵

作者: nhlijiaming 时间: 2008-6-2 12:56:55

如果是编程，这就设计一个动态规划的完全背包问题 假设i元有n种取法，对于每个i ，就等于 i-面值的取法总和 假设把面值数放在money[j]中，有k种面额， t表示 i元有t种取法 动态规划状态方程是： t【 i 】=t[i-money[j]]+t { 0<=i , 0<j<k } 开始时t[0]=0 例题：金银岛(coin) 打得好辛苦 ..   这里不能用中括号括住 i  ，很无奈～

[ 本帖最后由 nhlijiaming 于 2008-6-2 13:26 编辑 ]

作者: nhlijiaming 时间: 2008-6-2 12:59:41

例题找不到了，我记得 usaco Chapter 2 有一道题是类似的

[ 本帖最后由 nhlijiaming 于 2008-6-2 13:20 编辑 ]

作者: nhlijiaming 时间: 2008-6-2 13:22:59

终于找到了希望没有灌水嫌疑。。怕不够位置 USACO Section 2.3 Money Systems The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure. The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others. Write a program to compute how many ways to construct a given amount of money using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal). PROGRAM NAME: money INPUT FORMAT The number of coins in the system is V (1 <= V <= 25). The amount money to construct is N (1 <= N <= 10,000). Line 1: Two integers, V and N Lines 2..: V integers that represent the available coins (no particular number of integers per line) SAMPLE INPUT (file money.in) 3 10 1 2 5 OUTPUT FORMAT A single line containing the total number of ways to construct N money units using V coins. SAMPLE OUTPUT (file money.out) 10 Money Systems 货币系统 译 by timgreen 母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。 [In their own rebellious way],，他们对货币的数值感到好奇。 传统地，一个货币系统是由1,5,10,20 或 25,50, 和 100的单位面值组成的。 母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。 举例来说, 使用一个货币系统 {1,2,5,10,...}产生 18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。 写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。 保证总数将会适合long long (C/C++) 和 Int64 (Free Pascal)。 PROGRAM NAME: money INPUT FORMAT 货币系统中货币的种类数目是 V 。 (1<= V<=25) 要构造的数量钱是 N 。 (1<= N<=10,000) 第 1 行: 二整数， V 和 N 第 2 ..V+1行：可用的货币 V 个整数　(每行一个　每行没有其它的数)。 SAMPLE INPUT (file money.in) 3 10 1 2 5 OUTPUT FORMAT 单独的一行包含那个可能的构造的方案数。 SAMPLE OUTPUT (file money.out) 10

作者: gozichen 时间: 2008-6-2 14:42:01

真是一样米养百样人啊，太费脑了

作者: whitetiger 时间: 2008-6-2 15:09:04

比较简单的问题“一个数字用比它小的数字之和表示有多少种情况”已经很折腾人了，这个更麻烦。等着看结论吧！

作者: 丙丙 时间: 2008-6-2 15:18:49

RMB通常没有这么复杂，花完就没了

作者: 黑索金 时间: 2008-6-2 15:30:02

那啥我智商66 晕菜啊！

作者: kexin_xiao 时间: 2008-6-2 15:50:32

又是编程，太夸张了吧，没有必要吧

作者: Cielo 时间: 2008-6-2 22:32:32

原帖由 whitetiger 于 2008-6-2 15:09 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=146141&ptid=9371" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
比较简单的问题“一个数字用比它小的数字之和表示有多少种情况”已经很折腾人了，这个更麻烦。等着看结论吧！

这个就是整数分拆问题吧，不知道整数分拆问题有没有一个表达式的解啊？

作者: 金眼睛 时间: 2008-6-3 11:52:04

根据楼下的方法和程序，再给出几个结果，供有其他思路的朋友检验之用，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/loveliness.gif" border=0 smilieid="28"> 
 
2分、5分、1角、2角、5角、1元、   2元
1       3       10     40     450   4562    73681
 
五元 —  (6295435-1)
十元  —  (327631322-1)
二十元 —  (28311903609-1)
五十元 —  (23303034594533-1)
一百元 —  (7089628318292844-1)(估计值)
 
方法是通用的，N元都可以算，比如：三十元 —  490867960201

[ 本帖最后由金眼睛于 2008-6-4 21:38 编辑 ]

作者: 金眼睛 时间: 2008-6-3 13:27:34

想到一个思路：基础是一个同级相换的方法数序列，也就是X分换1分，2分，5分的方法数，如下
 
序列一：
单位：分          0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20   ...
换分的方法数   1  1  2  2  3  4  5  6  7  8  10  11  13  14  16  18  20  22  24  26  29   ...
 
这个序列也适用于角，同级即可。然后，在10的倍数的位置，取差一级相换的方法数序列。
 
序列二：
单位：角          0 1   2    3   4    5     6    7      8     9     10   11    12   13    14     15     16     17     18     19      20  ...
换分的方法数   1-10-29-58-97-146-205-274-353-442-541-650-769-898-1037-1186-1345-1514-1693-1882-2081  ...
 
我是编程算的序列，速度还行。看了一下曲线，非常类似e指数曲线，只是不知道有什么规律没有？<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/mad.gif" border=0 smilieid="11"> 
 
由于元和角分的情况不同，大于等于10元方法数会增加，元换元的方法数形成了新的序列。
 
序列三：
单位：元          0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20   ...
换元的方法数   1  1  2  2  3  4  5  6  7  8  11  12  15  16  19  22  25  28  31  34  41   ...
 
我这里的方法数包括了自身换自身，比如1元换1元也算做一种方法，这样有利于编程和理解，如果想得到小面值的组合种数，只需要减去1即可。
 
M元方法数=M元换元数*0元角分方法数+(M-1)元换元数*1元角分方法数+ ... +0元换元数*M元角分方法数
 
N元角分方法数=10*N角换角分方法数=10*N角换角方法数*0角换分方法数+(10*N-1)角换角方法数*1角换分方法数+ ... +0角换角方法数*10*N角换分方法数
 
 
比如算2元的方法数
 
2元方法数=2元换元数*0元角分方法数+1元换元数*1元角分方法数+0元换元数*2元角分方法数
                =2元换元数*0元角分方法数+1元换元数*(10角换角数+9角换角数*1角换分数+ ... +1角换角数*19角换分数+20角换分数)+0元换元数*(20角换角数+19角换角数*1角换分数+ ... +1角换角数*19角换分数+20角换分数)
                =2+1*(10+8*10+ ... +1*442+541)+1*(29+26*10+ ... +1*1882+2081)    (注：根据颜色对应序列1~3中的数)
                =73682(种)
 
程序如下，有时候程序更易于理解，Yuan为多少元，Tong为同级序列，Lin为临级序列，YY为元换元方法数序列：
Yuan=2; Method=0; for i=0:Yuan     Method=Method+YY(i+1)*sum(Tong(1 :Yuan-i)*10+1).*Lin((Yuan-i)*10+1:-1:1)); end
可以看出无论是元换角还是角换分都要一元一角地向后退，这样就不会遗漏任何情况了，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/loveliness.gif" border=0 smilieid="28"> 

[ 本帖最后由金眼睛于 2008-6-4 17:58 编辑 ]

作者: bbshanwei 时间: 2008-6-3 18:27:54

还有玩RMB的。太费脑子了，不想了。一个头两个大了。

作者: zxl0714 时间: 2008-6-3 18:38:03

这个是拆分数问题，编程即可，用母函数来解。当然也可以用动态规划，不过现在都是用母函数。如果是可以有任意面值的钱，那么拆分数估计式，哪本组合数学的书上应该都有，不过误差仍然很大。

作者: pilyfe 时间: 2008-6-4 14:54:13

13#真是厉害，思路很好，佩服！
用普通方法人工计算最多到1元就已经很麻烦了，而且很容易出错。
14#是不是应该还有一个序列，就是十元。
 

[ 本帖最后由 pilyfe 于 2008-6-4 14:59 编辑 ]

作者: 金眼睛 时间: 2008-6-4 17:57:25

原帖由 pilyfe 于 2008-6-4 14:54 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=147770&ptid=9371" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 13#真是厉害，思路很好，佩服！用普通方法人工计算最多到1元就已经很麻烦了，而且很容易出错。 14#是不是应该还有一个序列，就是十元。

是啊，不光是人工计算，就算编程也得采用技巧，这动辄上万上亿的，我的这台破电脑算了一小时都快冒烟了，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> 
 
10元，元，角，分，都是单位，100元换元数一定等于1元换角分数，序列三也是衍生出来的。计算式的本质是嵌套结构，高级序列的基础是序列一，引入高级序列只是为了方便理解和计算而已。所以引不引入10元的序列都可以。

[ 本帖最后由金眼睛于 2008-6-4 21:35 编辑 ]

作者: zxl0714 时间: 2008-6-4 18:39:26

楼上的算法有问题吧。。。。结果就算有几百亿也应该0.001秒就跑出来。。。

作者: 金眼睛 时间: 2008-6-4 20:29:18

原帖由 zxl0714 于 2008-6-4 18:39 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=147957&ptid=9371" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 楼上的算法有问题吧。。。。结果就算有几百亿也应该0.001秒就跑出来。。。

序列的计算也需要时间的，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12">

作者: bimilbenhao 时间: 2008-6-7 14:31:54

好难啊... 可计算这样的认为没啥用..

作者: nhlijiaming 时间: 2008-6-7 14:54:35

动态规划的时间复杂度是O（n^2），最多就10000元 ...........

作者: nhlijiaming 时间: 2008-6-7 14:55:36

计算1亿元，不使用高精度情况下需要1万秒去运行....

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)