猴子吃桃问题,数学和计算机的十字路口

2014-09-13 白若水 更多博文 » 博客 » GitHub »

原文链接 http://inskyline.com/thinking/2014/09/13/a-thinking-monkeyEatPeach.html
注:以下为加速网络访问所做的原文缓存,经过重新格式化,可能存在格式方面的问题,或偶有遗漏信息,请以原文为准。


据说某一年的小学奥数上出现了一道猴子吃桃子的问题,然后这个题目在计算机世界被发扬光大,好多公司的面试题都有过这样类似的题目。

题目:

猴子第一天摘下若干个桃子,当即吃了一半,还不过瘾,又多吃了一个。第二天早上又将剩下的桃子吃掉一半,又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第十天早上在想吃时,就只剩一个桃子了。求第一天共摘了多少个桃子?

这个题目用程序解决,只需要将问题理顺,用“递推思想”,从后向前推导,第10天是一只,第9天x-(x/2+1)=1,就可以算出为4,根据这种推导就很快转化为一段程序。

代码:

func monkeyEatPeach(day int) {
    // 从后往前推,一次 x/2-1=1
    var x, y int = 1, 0
    // x为累加数,y为当天数目
    for day > 0 {
        y = 2 * (x + 1) //某一天的数目
        x = y
        day--

    }
    println(x)
}

有些问题用数学的方式会很容易,比如说对一堆凌乱的数字排序,直觉就会告诉你怎么排。但用一段程序完成至少知道该用什么方式,比如说对10个数排序,在程序至少得用一个冒泡算法(不过生活中小量的数据也没有必要用计算机解决)。

但如果数据量大就牵扯用什么方式,用什么方式更好,就是算法

“算法”:先通过对一系列数进行某种运算观察规律,然后总结出一个简洁高效的方式,然后将个方式通过转换为让计算程序完成。


例如“猴子吃桃”类似的问题在日常的面试题目中,转换反而简单,如果纯数学方式做则有一定的难度。

就猴子吃桃问题:用纯数学方式推导一下,这个用到“数列”相关知识。

推导如下:

推导

得出这个结果需要一定的数学知识,但是一旦得出这个公式,则将这类问题轻易的解决。

曾经一个数学系的朋友说在数学家眼中世界是N维的。比如说猴子吃桃子问题,一般人会直接用10天推到第一天得到结果,然后会高兴说我解决了这个问题。而数学系的同学则会想,如果是第n天还剩余一个,那总共摘了多少只桃子呢?

我们学了十多年数学,对一些公式和定理也许都忘的差不多了,但是遇到一些问题,至少该用数学思维,看待问题,以及解决问题!