cuiyi's blog（崔毅 crazycy）

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

應(yīng)該是：
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筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

增開7群,號碼 30440732
8群 30756649
9群 30178567
10群 28694497

我們的qq群:15096318 學(xué)習(xí)程序的都可以來

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

@katlao

對；呵呵；這個地方是記錯了；上交的卷子是這樣寫的；

覺得還應(yīng)該能繼續(xù)推導(dǎo)的；當(dāng)時在考場上沒有推導(dǎo)出來；因為都與t(3)有2的冪方關(guān)系

另外，我覺得另外的思路上正向做，并且存儲每一個數(shù)字；

我現(xiàn)在思考的是倒向是否有辦法存儲呢？

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

@123bingbing

我曾經(jīng)加入了47個群；呵呵，現(xiàn)在只留了4個，拒絕新的群了。

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

最優(yōu)的算法是推導(dǎo)出遞推公式的，但是那個要用到矩陣，有一些技巧來推，我當(dāng)時也沒有推出來。次優(yōu)的一個方案是對中間的結(jié)果進行緩存，dp阿，O(n)的復(fù)雜度，而不是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筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

我把樓上的作了一下修改，也不知道是改好了，還是改差了，呵呵
就是把計算的結(jié)果存儲到數(shù)組中值最小的元素當(dāng)中，因為它對以后的計算已經(jīng)沒有用處了
雖然節(jié)省了空間，但是不知道速度會不會明顯變慢

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

# 我的  回復(fù)  更多評論   

#!/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筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

重貼，不到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筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

@馬嘉楠
不錯！

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

是不是還得考慮溢出的情況？

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

#!/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


當(dāng)n=100000時執(zhí)行時間為5.86秒

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

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

copy代碼

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

@Gasbarroni

哦 題目中聲明了不需考慮溢出

呵呵

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

崔崔強啊，到google面試了？

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

“發(fā)現(xiàn)mm還是超級可怕滴，眼睜睜看著一個騙局”，恩，建議你閉上眼過日子：）不然一睜眼就是怕怕了~

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

程序在運行中由于數(shù)據(jù)值過大，會導(dǎo)致溢出,所以在程序中計算時間的準(zhǔn)確性值得懷疑.

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

給出此問題的一種“記憶”解法(java解法)
//n的值到了80應(yīng)該要超出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);

}
數(shù)據(jù)再大一些，只有使用BigInteger了。



BigInteger

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

不好意思

long t＝0;

要不然，會出現(xiàn)編譯錯誤

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

@wes109

亂了，亂了
重新來過，哈哈

# re: google筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

#!/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筆試的敗筆（大家來仁者見仁哦）  回復(fù)  更多評論   

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筆試的敗筆（大家來仁者見仁哦）[未登錄]  回復(fù)  更多評論   

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筆試的敗筆（大家來仁者見仁哦）[未登錄]  回復(fù)  更多評論   

暈 大家難道就沒有 發(fā)現(xiàn) 遞歸 運算最大的問題是重復(fù)計算嘛？