人民币问题

pilyfe

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

nhlijiaming

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

nhlijiaming

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

bimilbenhao

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

金眼睛

<P>

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

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

zxl0714

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

金眼睛

<P>

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

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

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

pilyfe

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

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

zxl0714

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

bbshanwei

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