必威体育Betway必威体育官网
当前位置:首页 > IT技术

猴子摘桃

时间:2019-08-10 16:11:04来源:IT技术作者:seo实验室小编阅读:58次「手机版」
 

猴子摘桃

猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾就多吃了一个。第二天早上又将剩下的桃子吃了一半,还是不过瘾又多

吃了一个。以后每天都吃前一天剩下的一半再加一个。到第10天刚好剩一个。问猴子第一天摘了多少个桃子?

源:http://www.cnblogs.com/huangxincheng/archive/2012/08/08/2628022.html

设第十天为,则第九天还剩(2*x + 1),那么第九天吃了数量是比剩的还多一个,则第九天吃了(2*x  + 1 + 1),继续按着这样推导下去则有:

第10天   第9天  .......第1天

x1   2(x1 + 1) 2(x9 + 1)

则采用递归的算法如下:

int functionThree(int day)
{
    int total = 0;
    if (day == 1)
    {
        total = 1;
    }
    else
    {
        total = 2 * (functionThree(day-1) + 1);
    }
    return total;
}
正如原作者所说,递归是一个不断压栈的过程,可以直接采用一个for循环,代码如下:
int functionFour(int day)
{
    int total = 1;
    for (int i=0; i<day-1; i++)
    {
        total = 2*(total + 1);
    }
    return total;
}

递推算法可能不得不提到Hanoi塔的问题,是一个比较经典的递推。

                                A        BC

递推的过程如下:

1)一个和尚把n-1个盘子借助C,从A移动到B;

2)另外的一个和尚把最大大盘子从A移动到C;

3)再来一个和尚把刚才的n-1个盘子借助A,从B移动到C;

所以不管有多少个盘子,都可以分为上面的3步,只是这样和尚一个一个的分任务。所以代码如下:

void move(char a,char b)
{
    printf("%c---->%c\n",a,b);
}
void hanoi(int n,char a,char b,char c)
{
    if (n == 1)
    {
        move(a,c);
    }
    else
    {
        hanoi(n-1,a,b,c);
        move('A','C');
        hanoi(n-1,b,a,c);
    }
}

相关阅读

王定标:YouTube是月亮 国内web2.0是猴子

“猴子难摘月亮” “看到视频共享网站YouTube的成功,很多国内web 2.0网站的心态一下子高了。”大旗网董事长王定标如此评价现在的w

分享到:

栏目导航

推荐阅读

热门阅读