C#之猴子吃桃儿问题的解法——猴子吐桃儿-阿里云开发者社区

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

2015-11-23 1591

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 猴子第一天摘了许多个桃子，先吃了所有桃子的一半，后又吃了一个；第二天又吃了剩下桃子的一半，后又吃了一个……第十天，剩1个桃子。问：猴子第一天摘了多少个桃子？首先对“猴子吃桃”的过程进行正向推导，设：猴子第一天摘了N个桃子，第n天剩Ln个桃子。

猴子第一天摘了许多个桃子，先吃了所有桃子的一半，后又吃了一个；第二天又吃了剩下桃子的一半，后又吃了一个……第十天，剩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;
            }
        }
    }
}