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; ?} } |