计算机一个经典趣味问题,个小猴子边上有100根香蕉,它要走过50米才能到家,每次它最多搬50根香蕉,(多了就被压死了),它每走
1米就要吃掉一根,请问它最多能把多少根香蕉搬到家里。(提示:他可以把香蕉放下往返的走,但是必须保证它每走一米都能有香蕉吃。也可以走到n米时,放下一些香蕉,拿着n根香蕉走回去重新搬50根。)
废话不多说,上代码。
#include "stdlib.h"
#include "stdio.h"
#define TOTAL 100
#define DIST 50
#define MAXPAYLOAD 50
/*
offset 是猴子距离开始的位置
cur_num是猴子当前位置有多少香蕉
n表示从offset处搬n个香蕉继续走
x表示从当前位置决策走多少米停下
*/
int move(int offset, int cur_num, int n, int x)
{
int ret = 0;
int left, step;
if (offset == DIST)/*如果猴子到达终点,返回猴子剩余的香蕉数*/
return cur_num;
if(cur_num == 0)/*如果在当前位置没有了香蕉,表示猴子饿死,错误的决策。。。*/
return -1;
if(cur_num < x)/*如果当前位置的香蕉数小于将要走的距离,错误的决策*/
return -1;
if(n < x)/*猴子从当前位置搬运的香蕉数不足以走x米,错误的决策*/
return -1;
if(cur_num < n)
return -1;
/*计算猴子从当前走x米后,还剩下多少香蕉*/
cur_num n left
S--------offset-----offset+x-----------E
if(cur_num -n < 2*x)/*cur_num -n 表示猴子到达offset+x位置后,还放在offset处的香蕉数*/
/*cur_num-n < 2*x表示猴子不需要返回offset去拿剩余的香蕉*/
{
left = n - x;/*猴子达到offset+x处后,剩余香蕉数*/
}
else/*猴子需要返回offset去拿剩余的香蕉,由于题设我们知道猴子两次肯定能拿完所有的香蕉*/
{
left = cur_num - 3 * x;/*猴子达到offset+x处后,剩余香蕉数*/
}
if(left <= MAXPAYLOAD)/*如果猴子升下的香蕉数比较少了,那就搬起所有香蕉,尽可能往家赶路吧,不需要回头了*/
{
return left - (DIST - (offset + x));
}
/*决策下一次走几米能让剩下的香蕉数最多*/
for(step = 1; step < DIST-offset-x; step ++)
{
int res = move(offset+x, left, left > MAXPAYLOAD ? MAXPAYLOAD: left, step);
if(res <= 0)
continue;
if(res > ret)
{
ret = res;
}
}
return ret;
}
void main()
{
int ret = 0;
int x = 0;
for(x = 1; x < DIST; x ++)
{
int res = move(0, TOTAL, MAXPAYLOAD, x);
if(res <= 0)
continue;
if(res > ret)
{
ret = res;
}
}
printf("ret = %d\n", ret);
}
如果觉得《猴子摘香蕉问题python_猴子搬香蕉问题的C语言解》对你有帮助,请点赞、收藏,并留下你的观点哦!