[转] 猴子吃桃问题的一种解答

 

【问题描述】

    一只猴子在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 ) ;
    }