PE[31] 小学 5 年级数学题（答对者 + 代码 = 加 1 技术分）

FreddyMusic

人民币是中国的流通货币。它由如下面额货币组成：

1 分，2 分，5分，1角，2角，5角，1元，2元

如果要组成 2元钱 可以是

2元钱 = 1个*1 元 + 1个*5角 + 2个*2角 + 1个*5分 + 1个*2分+ 3个*1分

你可以使用以上任意货币面额组成 2 元钱，问共有多少种方式？

waynebuaa

73682
该代码是求出了所有解然后再Length的：

1. FrobeniusSolve[{1, 2, 5, 10, 20, 50, 100, 200}, 200] // Length

复制代码

FreddyMusic

代码很帅，就是运行时间长了点。

能缩短运行时间的还有加分。

joehappy

真的好难！手算我是算不出来，现在的孩子真不得了！

chyanog

真是巧合啊，今天在数学研发网论坛里见到类似的题目（http://bbs.emath.ac.cn/thread-2317-1-1.html）,效率还可以，

1. 
   
2. IntegerPartitions[200, All, {1, 2, 5, 10, 20, 50, 100, 200}] //
   
3.   Length // Timing
   

复制代码

{0.14, 73682}

lin2009

C语言版本的程序：得数73682

#include < stdio.h >
int main(void)
{
  int x[] = {1,2,5,10,20,50,100,200};
  
  int t = 200;  // t is total;
  int k = 0 ;
  for (int n0 = 0; n0 <= t/x[0]; n0 ++ )
    {
      for (int n1 = 0; n1 <= ( t - n0*x[0])/x[1]; n1 ++ )
        {
          for (int n2 = 0; n2 <= ( t - n0*x[0] - n1*x[1])/x[2]; n2 ++ )
            {
              for (int n3 = 0; n3 <= ( t - n0*x[0] - n1*x[1] - n2*x[2])/x[3]; n3 ++ )
                {
                  for (int n4 = 0; n4 <= ( t - n0*x[0] - n1*x[1] - n2*x[2] - n3*x[3])/x[4]; n4 ++ )
                    {
                      for (int n5 = 0; n5 <= ( t - n0*x[0] - n1*x[1] - n2*x[2] - n3*x[3] - n4*x[4])/x[5]; n5 ++ )
                        {
                          for (int n6 = 0; n6 <= ( t - n0*x[0] - n1*x[1] - n2*x[2] - n3*x[3] - n4*x[4] - n5*x[5])/x[6]; n6 ++ )
                            {
                              for (int n7 = 0; n7 <= ( t - n0*x[0] - n1*x[1] - n2*x[2] - n3*x[3] - n4*x[4] - n5*x[5] - n6*x[6])/x[7]; n7 ++ )
                                {
                                  int  s = n0*x[0] + n1*x[1] + n2*x[2] + n3*x[3] + n4*x[4] + n5*x[5] + n6*x[6] + n7*x[7] ;
                                  if (s == 200 )
                                    {
                                    //printf("%d %d %d %d %d %d %d %d \n",n0,n1,n2,n3,n4,n5,n6,n7);
                                      k ++ ;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
  printf("\n\t总个数为  %d\n\n",k);
  return 0;
}

jimogsh

5# chyanog 确实比2楼的方法要快

guocong89

闲极无聊，做点老题练练手
用标准的动态规划实现，代码稍微复杂，但是实现更加底层

1. Block[
   
2.   {money, cnt, i, j, k},
   
3.   money = {1, 2, 5, 10, 20, 50, 100, 200};
   
4.   cnt = Table[0, {200}, {8}];
   
5.   Table[cnt[[1, i]] = 1, {i, 8}];
   
6.   For[i = 2, i < 201, i++,
   
7.    For[j = 1, j < 9, j++,
   
8.     cnt[[i, j]] = 0;
   
9.     For[k = 1, k <= j, k++,
   
10.      If[money[[k]] < i, cnt[[i, j]] += cnt[[i - money[[k]], k]],
    
11.       If[money[[k]] == i, cnt[[i, j]]++]]]]];
    
12.   cnt[[200, 8]]
    
13.   ] // Timing

复制代码

运行结果 {0.055991, 73682}

chyanog

还有一个快速的方法，用生成函数

1. Coefficient[Series[Product[  1/(1 - x^i), {i, {1, 2, 5, 10, 20, 50, 100, 200}}], {x, 0, 200}],  x^200]

复制代码

miniwhale

chyanog 发表于 2013-4-27 23:16
还有一个快速的方法，用生成函数

用生成函数？不懂，也没有google到。
能详细说一下或是给个相关链接学习吗？

miniwhale

miniwhale 发表于 2013-4-29 22:49
用生成函数？不懂，也没有google到。
能详细说一下或是给个相关链接学习吗？ ...

多谢，我也找到一个英文的，正在看，谢谢！
http://www.math.upenn.edu/~wilf/gfologyLinked2.pdf

流殇、浅忆

长见识了，开心，哈哈。。。。。