猴子吃桃问题09699

《猴子吃桃问题09699》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实例编程：解答猴子吃桃问题   [问题描述]   一只猴子在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        

2、: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   [问题分析]   这个题目比较

3、好的解决方法是用递归。   我们定义一个递归函数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这几种情况），也就是说只要没有到最后一天（

4、x=0），就需要继续向下搜索，所以x>0且y>0的条件是不完备的，应该是x>0且y>=0.   3、其它情况（如x<0或y<0，x=0且y>0等）为非法情况或表明当前解不成立，故要返回。   由此可以写出eat函数的伪代码： voideat(intx,inty)       {           if(x>0&&y>=0)               for(i=0;i<=10;i++)                   eat(x-1,y-i);           elseif(x==0&&y==0)   

5、            输出当前解;           return;       }   [程序代码]   根据上述思路，我们可以比较容易地写出下面的程序。不过，这里有几个地方经过了修改：1、为了便于结果的输出，所以使用了一个全局整型数组arr来存放当前解。   2、为了便于对arr数组的下标进行管理，给eat函数增加一个参数idx，标识出当前的空余位置（把探索的解i放在该位置）。   3、虽然每天最多吃10个桃子，但是如果当前情况下不够10个桃子，那么在进行for（i=0；i<=10；i++）这个循环时，有些

6、i值就是不必要的。所以程序设立了一个i_end变量，如果当前情况下剩余的桃子总数y多于10个，那么i_end取10；如果少于10个，那么就让i_end等于y.这样可以减少不必要的循环与递归。 #include   #defineDAY 3   #definePEACH  4   intarr[DAY];   longinttimes;   FILE*fp;   voideat(intday,intpeach,intidx)   {       if(day>0&&peach>=0)       {

7、           inti,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;       }       elseif(day==0&&peach==0)       {        

8、   inti;           times++;           fprintf(fp,"%-10ld:",times);           for(i=0;i