[精品]猴子吃桃问题
[转] 猴子吃桃问题的一种解答
来源:RobinWen的专栏 作者:我为C狂 等级:精品
发布于2006-01-30 22:25 被读4786次 【字体:大 中 小】
【问题描述】
一只猴子在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
【问题
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
】
这个题目比较好的解决方法是用递归。
我们定义一个递归
函数
excel方差函数excelsd函数已知函数 2 f x m x mx m 2 1 4 2拉格朗日函数pdf函数公式下载
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
#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 ) ;
}
![[精品]猴子吃桃问题](https://swf.iask.com/VL5xwpjimqy.svg?ssig=TCyw6%2BxmAO&Expires=1721164872&KID=sina,ishare&range=0-4879)
浙公网安备 33021202002483