[问题描述]

    一只猴子在X天中一共吃了Y个桃子。已知这只猴子每天最多吃10个桃子，最少可以不吃桃子。问一共有多少种不同的吃法。

    例如：X=3，Y=4时（即3天吃4个桃子）一共有下面列出的15种不同吃法

 1         :0   0   4  
        2         :0   1   3  
        3         :0   2   2  
        4         :0   3   1  
        5         :0   4   0  
        6         :1   0   3  
        7         :1   1   2  
        8         :1   2   1  
        9         :1   3   0  
        10        :2   0   2  
        11        :2   1   1  
        12        :2   2   0  
        13        :3   0   1  
        14        :3   1   0  
        15        :4   0   0

    [问题分析]

    这个题目比较好的解决方法是用递归。

    我们定义一个递归函数eat（ x， y ）表示在x天之内吃y个桃子。那么具体定义为：1、如果x=0且y=0，表示当前已经搜索到的是一种可行的解法，需要把该解法输出。

    2、如果x>0且y>0，表示还没有搜索完，那么就要按下面的方法继续递归：

for ( i = 0 ; i <= 10 ; i++ )                eat( x-1, y-i ) ;

    这里的i相当于是该天吃桃子数量的探索值。但是由于可以在后面的几天里面一个桃子也不吃（见上面的5、9、12、14、15这几种情况），也就是说只要没有到最后一天（x=0），就需要继续向下搜索，所以x>0且y>0的条件是不完备的，应该是x>0且y>=0.

    3、其它情况（如x<0或y<0，x=0且y>0等）为非法情况或表明当前解不成立，故要返回。

    由此可以写出eat函数的伪代码：

void eat( int x, int y )         {             if ( x > 0 && y >= 0 )                 for ( i = 0 ; i <= 10 ; i++ )                     eat( x-1, y-i ) ;             else if ( x == 0 && y == 0 )                 输出当前解;             return ;         }

    [程序代码]

    根据上述思路，我们可以比较容易地写出下面的程序。不过，这里有几个地方经过了修改：1、为了便于结果的输出，所以使用了一个全局整型数组arr来存放当前解。

    2、为了便于对arr数组的下标进行管理，给eat函数增加一个参数idx，标识出当前的空余位置（把探索的解i放在该位置）。

    3、虽然每天最多吃10个桃子，但是如果当前情况下不够10个桃子，那么在进行for（ i = 0 ； i <= 10 ； i++ ）这个循环时，有些i值就是不必要的。所以程序设立了一个i_end变量，如果当前情况下剩余的桃子总数y多于10个，那么i_end取10；如果少于10个，那么就让i_end等于y.这样可以减少不必要的循环与递归。

#include <stdio.h>     #define DAY  3     #define PEACH   4     int arr[DAY] ;     long int times ;     FILE *fp ;     void eat( int day, int peach, int idx )     {         if ( day > 0 && peach >= 0 )         {             int i, i_end ;             i_end = ( (peach<10) ? (peach) : (10) ) ;             for ( i = 0 ; i <= i_end ; i++ )             {                 arr[idx] = i ;                 eat( day-1, peach-i, idx+1 ) ;             }             return ;         }         else if ( day == 0 && peach == 0 )         {             int i ;             times++ ;             fprintf( fp, "%-10ld:", times ) ;             for ( i = 0 ; i < DAY ; i++ )                 fprintf( fp, "%-3d ", arr[i] ) ;             fprintf( fp, "\n" ) ;             return ;         }         else             return ;     }     int main( void )     {         int day, peach ;         day = DAY ;         peach = PEACH ;         times = 0 ;         fp = fopen( "monkey.txt", "w" ) ; /* 打开用于保存结果的文件 */         eat( day, peach, 0 ) ;         fclose( fp ) ;                                  /* 关闭文件 */         return( 0 ) ;     }

原文链接: http://c.chinaitlab.com/cc/examp...