实例编程：解答猴子吃桃问题

[问题描述]

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

上一篇：C++程序设计最佳实践下一篇：C++风格的文件输入输出流