主题：【纪事】失败的苹果面试（上） -- landlord
家园 好代码自己会说话 记得我们初学编程的时候，各位同学都在力求找到最优算法，写出最精简的代码，结果就导致有时候很难读懂。后来才渐渐意识到写代码还是简单质朴为好。所谓“重剑无锋，大巧不工”:-)
上面这段代码，我大概会这样写：
int fib(int n)
{
assert(n>0);
int a1=1, a2=1, a3;
if (n == 1) return a1;
if (n == 2) return a2;
for (int i = 3; i <= n; i++)
{
a3=a1+a2;
a1=a2; a2=a3;
}
return a3;
}
编译出的机器代码应该是一样的，但是人读起来就更容易了。数列中相邻3个值的关系表达得很清楚。
家园 兄台做得非常不错，赞一个 细细一想，同事问这道题还是很有道理的。
能用递归做出来的，起码说明思路清晰；能转换成循环的，说明有优化的意识，对于我们这种写企业级软件的，这两点都很重要。
曾经有一位牛人(这人数学一定学得很不错)给出另类答案：
double x = (1 + sqrt(5))/2;
Fib(n) = (x^n - (1-x)^n)/sqrt(5);
这是一个数学上简洁完美的答案，可是在计算机世界里，这是最优解吗？
本帖一共被 1 帖 引用 (帖内工具实现)家园 这个是通项公式 通常我遇到这种问题，都会首先想到通项公式，然后就是查表，最后才是常规方法。
家园 对于公式求解 有rounding的问题，所以最好是要舍入到最接近的那个整数才可以。要判断数学公式求解的优劣，就必须知道库函数x^n是如何实现的。因为库函数可以处理n非整数的情况，所以我估计是用数学里的一些逼近来求近似值，估摸着循环个几十次总是有必要的吧。但是可以用lgn算法，即按照n的二进制表示的位来迭代计算，所以我倾向于这个lgn的算法。如果实在不喜浮点表示的近似，可以用fibonacci迭代的矩阵表示。顺便问一下大牛，哪位知道那些数学函数在计算机里是怎么实现的？比如log，sin这些大概迭代多少次？
家园 这题好像有点简单。 要考递归和循环，可以让写1个比如n个数的全排列之类，让用递归和循环各实现一遍。
这题80%的人做不出来，老外的平均水平也有点汗，不过人家牛的人也真牛，关键是有兴趣，人家的牛人是真热爱写程序，不像中国许多人做IT类工作只是为了工资相对还算比较高，当然中国的基础教育水平还是挺高的。
还有人家的程序牛人四五十岁还在踏踏实实写程序，中国的程序牛人基本30岁就不怎么写程序了，一般都是挂着1个什么总的头衔，干起玩PPT，耍嘴皮子，坑蒙拐骗的勾当了。
家园 循环稍有难度 递归真的是基本人人会做了。不过要求非递归而且不用queue之类来展示存储的我还真没见人问过。可以用alphabetical order来生成下一个，或者用gray code。唉，俺压箱底准备impress下面试官的都毫无保留的告诉大家了。如果你有兴趣，请参看Knuth第四卷关于permutation的那一册。
家园 呃 这哥们记得这个...汗啊...
家园 是九连环那个数列么？ 那玩意儿有啥用啊？
家园 80+15+10= 105
家园 80+15*2/3+10 = 100
家园 那个苹果母牛怎么无缘无故就跳了出来？ 故事没开头？？？
家园 花地主一个，呵呵。 类似事情我也碰到过，有些面试官只会问自己懂的东西，不管你申请的是什么简历。
当年有家公司，我去面试服务端开发，对方老问我mfc的问题，把我都问烦了。
家园 也说说我某次失败的经历 当地的龙头老大E公司招聘,去面试的时候怀里已揣了T公司的聘书,所以有些心不在焉.
考管:你认为现场最需要注意的是什么?
我:XX设备...
之后的问题能听得出很俗套,一出门我就感到最关键的问题上犯了低级错误.对于工程技术人员来说,什么最重要:安全第一!