Google笔试的败笔
Google笔试的败笔
1 超级失败的1：说8点开始，考试时间100分钟 ，怎么算都是9：10交卷；9点一到匆匆交卷了，晚上躺床上才发现错也；2 超级失败的2：把自个的生日又记错了；3 怕怕的发现：发现mm还是超级可怕滴，眼睁睁看着一个骗局，哎，也得谨慎些以防上当受骗啊；题目如下：T( 0 ) = 1; T(1)=1;T(2)=2;T(n)=T(n-1)+T(n-2)+T(n-3); 用最优方式求T(n);int?T(int?n)?{}可以用最熟悉的语言写在考场的第一个做法?1 public? class?T? {?2 ? public? int?t( int?n) {?3 ?? if?(n? ==? 0 )? {?4??? return? 1;?5 ??}? else? if?(n? ==? 1 )? {?6??? return? 1;?7 ??}? else? if?(n? ==? 2 )? {?8??? return? 2;?9 ??}? else? {10??? return?t(n - 1 )? +?t(n - 2 )? +?t(n - 3 );11??}?12?} 13 } 当时发现时间够用，进行了公式推理，但未得出规律的真谛每个都与T(3)可以直接发生关系，关系是2的幂次方，但最终没有得出公式遂改进如下：?1 public? class?T? {?2 ? public? int?t( int?n) {?3 ?? if?(n? ==? 0 )? {?4??? return? 1;?5 ??}? else? if?(n? ==? 1 )? {?6??? return? 1;?7 ??}? else? if?(n? ==? 2 )? {?8??? return? 2;?9 ??}? else? {10??? return? 2? *?t(n - 1 )? -?t(n - 3 );11??}?12?} 13 } 晚上躺床上，怎么可能这样直接呢？突然想到最起码的一点就是重复数的计算，应该进行保存；如果正向逐个求然后保存，可行；如果倒向如何保存，尚未想好大家来仁者见仁一下哦（有更好的思路的请指点）public class T {?Map values = new HashMap();??public int t(int n){??int result = 0;??if (n == 0) {??? result = 1;??} else if (n == 1) {???result = 1;??} else if (n == 2) {???result = 2;??} else {???result =? 2 * t(n-1) - t(n-3);??} ??return result;?}}相关推荐：
