欧拉第31题！求思路！！

sinner

在英国，货币是由英镑，便士p构成的。一共有八种钱币在流通：

1p, 2p, 5p, 10p, 20p, 50p, 1 (100p) 和 2 (200p).
要构造2可以用如下方法：

1*1 + 1*50p + 2*20p + 1*5p + 1*2p + 3*1p
允许使用任意数目的钱币，一共有多少种构造2的方法？

以上就是题目，求思路！！

                               
登录/注册后可看大图

该贴已经同步到 sinner的微博

微博评论

哇呀～深奥到～[晕]

                               
登录/注册后可看大图

来自 Yukilulu 的新浪微博

仰望天上的光

最土的办法，递归：
设数组int index[8]={1,2,5,10,20,50,100,200};表示每种钱币的面值大小。
函数int f( int*index, int begin, int end, int total );返回用index[begin...end]这么多种钱币表示总数为total的钱有集中表示方法，得到递归公式：
f( index, begin, end, total ) =   f( index, begin, end, total-index[begin] ) + f( index, begin+1, end, total );//意思是如果取一个index[begin]的话，表示方法数目等于
         //f( index, begin, end, total-index   [begin] )；
         //不取index[begin]的话，表示方法数目等于 f( index, begin+1, end, total );
在加上递归结束条件：
begin>end,f=0;
total<=0,f=0

知道怎么递归了吧？

微博评论

回复@Yukilulu:呢D题，的确唔简单！

                               
登录/注册后可看大图

来自 私竇_TCY-咏 的新浪微博

sinner

仰望天上的光 发表于 2012-2-3 10:27

                               
登录/注册后可看大图

最土的办法，递归：
设数组int index[8]={1,2,5,10,20,50,100,200};表示每种钱币的面值大小。
函数int f( ...

小弟不才，还是不懂，begin end total分表代表什么？

仰望天上的光

函数int f( int*index, int begin, int end, int total );返回用index[begin...end]这么多种钱币表示总数为total的钱有几种表示方法
如begin=0,end=7,total=200，则f(index,0,7,200)的返回值就是“用数组index下标为0到7的8种硬币表示总数为200的钱，用几种表示方法”

sinner

仰望天上的光 发表于 2012-2-3 22:59

                               
登录/注册后可看大图

函数int f( int*index, int begin, int end, int total );返回用index这么多种钱币表示总数为total的钱有几 ...

我这样做对吗？

1. #include <stdio.h>
   
2. main()
   
3. {
   
4.         int i[]={1,2,5,10,20,50,100,200};
   
5.         int x;
   
6.         x=f(i,0,7,200);
   
7.         printf("%d",x);
   
8.         system("pause");
   
9. 
   
10. }
    
11. int f(int i[],int begin,int end,int total)
    
12. {
    
13.         int x1;
    
14.         if(total==0)
    
15.                 return 1;
    
16.         if(total<0||begin>end)
    
17.                 return 0;
    
18.         x1=f(i,begin,end,total-i[begin])+f(i,begin+1,end,total);
    
19.         return x1;
    
20. }

复制代码

仰望天上的光

正确

wangyexin

母函数应该可以解

JX机械

仰望天上的光 发表于 2012-2-3 10:27

                               
登录/注册后可看大图

最土的办法，递归：
设数组int index[8]={1,2,5,10,20,50,100,200};表示每种钱币的面值大小。
函数int f( ...

这个递归公式是怎么得到的？