cuiyi's blog（崔毅 crazycy）

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

应该是：
public class T {
public int t(int n){
if (n == 0) {
return 1;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else if (n == 3) {
return 4;
} else {
return 2 * t(n-1) - t(n-4);
}
}
}

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

增开7群,号码 30440732
8群 30756649
9群 30178567
10群 28694497

我们的qq群:15096318 学习程序的都可以来

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

@katlao

对；呵呵；这个地方是记错了；上交的卷子是这样写的；

觉得还应该能继续推导的；当时在考场上没有推导出来；因为都与t(3)有2的幂方关系

另外，我觉得另外的思路上正向做，并且存储每一个数字；

我现在思考的是倒向是否有办法存储呢？

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

@123bingbing

我曾经加入了47个群；呵呵，现在只留了4个，拒绝新的群了。

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

最优的算法是推导出递推公式的，但是那个要用到矩阵，有一些技巧来推，我当时也没有推出来。次优的一个方案是对中间的结果进行缓存，dp阿，O(n)的复杂度，而不是O(3^n)
----------------------------------------------------
int buffer[n+1]

buffer[0] = 1; buffer[1] = 1; buffer[2] = 2;

for(int i = 3; i<=n; i++)
buffer[i] = buffer[i - 1] + buffer[i - 2] + buffer[i - 3];

return buffer[n];

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

我把楼上的作了一下修改，也不知道是改好了，还是改差了，呵呵
就是把计算的结果存储到数组中值最小的元素当中，因为它对以后的计算已经没有用处了
虽然节省了空间，但是不知道速度会不会明显变慢

public static int t1( int n ){
if( n==0 ){
return 1;
}else if( n== 1 ){
return 1;
}else if( n==2 ){
return 2;
}else{
int[] b= new int[3];
b[0] = 1;
b[1] = 1;
b[2] = 2;
for( int i = 3; i < n+1; i++ ){
b[i%3] = b[i%3] + b[(i+1)%3] + b[(i+2)%3];
}
return b[n%3];
}

# 我的  回复  更多评论   

#!/usr/bin/python
x=[1,1,2]
def T(n):
if n > len(x)-1:
x.append(T(n-1)+T(n-2)+T(n-3))
return x[n]

import sys
print T(int(sys.argv[1]))

$ python test.py 100
180396380815100901214157639

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

重贴，不到1秒
[code]
#!/usr/bin/python
x=[1,1,2]
def T(n):
if n > len(x)-1:
x.append(T(n-1)+T(n-2)+T(n-3))
return x[n]

import sys
print T(int(sys.argv[1]))
[/code]

$ python test.py 1000
2758842807766486252615892411656158645133100149652696210351601845036392978912293462801016485671033253921841350537004356434253826361707295202024537559785200706502368152965047761644352316799391470273906561574500883480570560512982435681502330814068718832813973880527601

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

@马嘉楠
不错！

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

是不是还得考虑溢出的情况？

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

#!/usr/bin/python

import sys
import datetime

def T(n):
if n == 0:
return 1
elif n == 1:
return 1
elif n == 2:
return 2
else:
i = 3
a = 1
b = 1
c = 2
while i <= n:
d = a + b + c

if i == n:
return d
else:
i = i + 1
a = b
b = c
c = d

t_start = datetime.datetime.today()

print T(int(sys.argv[1]))

t_end = datetime.datetime.today()

print t_end - t_start


当n=100000时执行时间为5.86秒

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

都乱了，大家可以到http://bbs.btant.com/viewthread.php?tid=80&extra=page%3D1

copy代码

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

@Gasbarroni

哦 题目中声明了不需考虑溢出

呵呵

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

崔崔强啊，到google面试了？

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

“发现mm还是超级可怕滴，眼睁睁看着一个骗局”，恩，建议你闭上眼过日子：）不然一睁眼就是怕怕了~

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

程序在运行中由于数据值过大，会导致溢出,所以在程序中计算时间的准确性值得怀疑.

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

给出此问题的一种“记忆”解法(java解法)
//n的值到了80应该要超出Long型的范围了
static long[] knownT=new long[100];
public static long t(n)
{ long t;
if (knownT[n]!=0) return knownT[n];
if(n<0) return 0;
else if(n==0) return (knownT[n]=1);
else if(n==1) return (knownT[n]=1);
else if(n==2) return (knownT[n]=2);
else if(n>=3) t=t(n-1)+t(n-2)+t(n-3);
return (knownT[n]=t);

}
数据再大一些，只有使用BigInteger了。



BigInteger

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

不好意思

long t＝0;

要不然，会出现编译错误

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

@wes109

乱了，乱了
重新来过，哈哈

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

#!/usr/bin/python
x=[1,1,2]
def T(n):
if n < 3:
return x[n]
else:
for i in xrange(n-2):
x.append(sum(x))
x.pop(0)
return x[-1]

import sys
print T(int(sys.argv[1]))

time t.py 150000

real 0m9.860s
user 0m9.553s
sys 0m0.016s

# re: google笔试的败笔（大家来仁者见仁哦）  回复  更多评论   

int T(int n)
{
int i, temp, a[3] = {1, 1, 2};

for (i = 3; i <= n; ++i)
{
temp = a[0] + a[1] + a[2];
a[0] = a[1];
a[1] = a[2];
a[2] = temp;
}

return a[2];
}

# re: google笔试的败笔（大家来仁者见仁哦）[未登录]  回复  更多评论   

int T(int n){
int a=0,b=2,c=1,d=1;
for(int i=3; i<n; i++){
a = b+c+d;
d=c;c=b;b=a;
}
return a;
}

# re: google笔试的败笔（大家来仁者见仁哦）[未登录]  回复  更多评论   

晕 大家难道就没有 发现 递归 运算最大的问题是重复计算嘛？