问题已关闭。原因:代为完成的个人任务。
提问需要满足:其他人可能遇到相似问题,或问题的解决方法对其他人有所助益。如果通过其他方式解决遇到困难,欢迎提问并说明你的求知过程。

猴子摘香蕉一次可以摘 1 个或 2 个,总共 50 个,问有多少种摘法?

疼逊笔试题,用程序写出来。
关注者
341
被浏览
125340

43 个回答

设n个香蕉的摘法数量为f(n)。

每一个f(n)的摘法的最后一次采摘要么是一个,要么是两个。

所以f(n)=f(n-1)+f(n-2)。

f(1)=1,f(2)=2,所以,题主你看呢?

补充:

我可能没说明白f(n)=f(n-1)+f(n-2)这个式子的来源,评论里有人问。

是这样的,我们把n个香蕉的所有摘法分成两类,第一类是最后一次摘一个的,第二类是最后一次摘两个的。

那第一类有多少个呢?

第一类中的每一种摘法,去掉最后一次摘的一根,都是(n-1)个香蕉的某一种摘法。

也就是说,第一类中的摘法与(n-1)个香蕉的摘法一一对应;再换句话说,就是第一类中的摘法与(n-1)个香蕉的摘法一样多。

同理,第二类中的摘法与(n-2)个香蕉的摘法一样多。

所以f(n)=f(n-1)+f(n-2)。

我说清楚了吗? @源思
发现很多人觉得,咦,BAT面试居然考这么水的题?
我只能回答,太天真了。

这只是这趟校招面试的某个Chapter的第一关,面试官还煞费苦心地把爬楼梯换成猴子摘香蕉,也是醉醉的。

=============================================================
踏入BAT的第一关:写出公式
做人不能太装逼,虽然你可能对这个弱智问题嗤之以鼻,但是你也要先正面回答面试官的问题,不要给人留下“虽然我不会骑自行车,但是我会开飞机”的印象。
所以,首先你得像 @匡世珉那样回答。尽管你可能已经对斐波那契数列的通项公式了如指掌,也请针对题面,简单做一下推导,写出公式来先:
f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)

踏入BAT的第二关:编码实现
问题里很明确说了,要编码实现,而不是用伪代码。所以你要在短时间内在纸上写出一段漂亮的代码来,要点是:漂亮!因为这时候面试官往往没有规定时间和空间复杂度,所以可以随意发挥。
可能是这样的一行装逼流:
int fun1(int n) {
    return n > 1 ? f(n-1) + f(n-2) : 1;
}
也可能是这样勤俭节约内存的:
int fun2(int n) {
    int a1 = 1, a2 = 1, t;
    for (int i=1; i<n; i++) {
        t = a1 + a2;
        a1 = a2;
        a2 = t;
    }
    return n > 1 ? t : 1;
}
还有这样花式开数组的:
int fun3(int n) {
    int *f=(int *)malloc(sizeof(int)*n);
    f[0] = f[1] = 1;
    for (int i=2; i<n; i++)
        f[i] = f[i-1] + f[i-2];
    int result = f[n-1];
    free(f);
    return result;
}

踏入BAT的第三关:考察计算机和数学的基本知识
这块完全由面试官自由发挥,我想到的数学知识有:
1、求通项公式(比如待定系数法、特征方程法);
2、求斐波那契数列的前n项和;
3、一些相关的应用,比如杨辉三角;
4、给出一个斐波那契数列的变种,或者是考察广义的斐波那契数列。
计算机知识又有:
1、计算机实现递归的原理;
2、很好,你知道递归是通过栈实现的,那么栈在内存中具体是如何实现;
3、评估下你给出代码的时间和空间复杂度;
4、考察语法,比如C++中int、long int、long long的区别;
(如果你知道C99和C++11在这里的区别那是极好的)

踏入BAT的第四关:高级进阶
当面试官听你滔滔不绝地扯了一大堆东西之后,往往会默默地抛出一句话:“还有更好的方法吗?”那么恭喜你,基本上这关你的完成度已经达到90%,剩下的发挥就是展现你异于常人的环节。(插播广告:往往有过OI/ACM等相关竞赛经历的选手在这里就有明显的优势)
你要是搞过竞赛,我想你根本不需要思考就会答出可以利用矩阵乘法的特性将时间复杂度优化到O(logN)。
在线性代数中,斐波那契数列通项公式被表述成以下形式:
所以优化问题就转变为:如何快速地求出这个矩阵的n次方?
(1)利用二分的思想:假设要求矩阵的n次方为A(n),设i=n/2,若n%2==1,则 A(n)=A(i)*A(i)*A(1),若n%2==0,则A(n)=A(i)*A(i);
(2)利用二进制思想:将N拆为二进制数,譬如13=(1101)2,那么 A^13= A^8 * A^4 * A^1。这个方法在求快速幂模的时候经常用。

踏入BAT的第五关:变态面试官,不把你问垮不死心
基本走到第四关就差不多了,如果这个面试官比较变态,可能会让你把上述O(logN)算法实现一下……(我也是听说过面试有要求手写平衡树Treap的orz)
代码比较长,我就不贴了,相信有求学精神的你一定会自己去探索的。
=================================================================

这才是这道题本来的面目,如果觉得还不过瘾的话,去把这题灭了吧,n的范围最大达10^9,当然了题目本身也不完全是斐波那契数列,需要有一定的推导能力。
祭出大杭电OJ的传送门:Problem - 2855

以上。
希望对即将准备踏入BAT的童鞋有帮助。

利益相关:
1、曾OI/ACM弱弱,省金,regional银;
2、曾通过阿里算法校招面试,现担任某创业公司算法工程师;
3、曾担任某创业公司的算法岗位校招面试官。
为什么?