• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

C#之猴子吃桃儿问题的解法——猴子吐桃儿

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

猴子第一天摘了许多个桃子,先吃了所有桃子的一半,后又吃了一个;第二天又吃了剩下桃子的一半,后又吃了一个……第十天,剩1个桃子。问:猴子第一天摘了多少个桃子?

首先对“猴子吃桃”的过程进行正向推导,设:猴子第一天摘了N个桃子,第n天剩Ln个桃子。则——

L1 = N/2 - 1

L2 = L1/2 - 1/2 - 1

L3 = L2/2 - 1/2^2 - 1

......

Ln = L(n-1)/2 - 1;

然后对“猴子吐桃”的过程进行逆向推导,因为Ln = L(n-1)/2 - 1,所以L(n-1) = 2Ln + 2。即——

从某一天剩余的桃子量我们可以逆推出上一天的桃子量。可以想象猴子把当天吃的桃子吐了出来(先吐出一个,再吐出目前桃子数2倍的桃子),就是上一天吃剩下的桃子量。

由于我们已经知道了第10天猴子吃完桃后剩余桃子数为1,这样就可以把“第10天”和“1个桃”作为两个参数传入一个“猴子吐桃”的函数中,让猴子把吃的桃儿都吐出来,一直吐到第1天,并返回第一天猴子摘的桃子数:

using System;

namespace MonkeyEatPeaches
{
    class Program
    {
        static void Main(string[] args)
        {
            int left = 1;
            int days = 10;
            Console.WriteLine(MonkeyVomitPeaches(days, left));
            Console.ReadKey();
        }

        private static int MonkeyVomitPeaches(int days, int left)
        {
            if (days > 1)
            {
                left = (left + 1) * 2;
                days--;
                return MonkeyVomitPeaches(days, left);
            }
            else
            {
                return (left + 1) * 2;
            }
        }
    }
}

结果得出:

答:第一天猴子摘了3070个桃子。

其实这个递归法就相当于一个for循环,所以时间复杂度为O(n)。

可以进一步研究一下递归算法的时间复杂度


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
关于C#winform怎么调用webapi来获取到json数据发布时间:2022-07-10
下一篇:
C#操作Excel开发报表系列整理发布时间:2022-07-10
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap