人民币问题

kexin_xiao

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

Cielo

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

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

金眼睛

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

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

金眼睛

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

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

bbshanwei

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

zxl0714

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

pilyfe

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

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

金眼睛

<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 编辑 ]

zxl0714

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

金眼睛

<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>