Google的编程习题

Python/PHP/Perl 开发与设计
hsy541
帖子: 65
注册时间: 2007-04-03 10:06
送出感谢: 0
接收感谢: 0

#16

帖子 hsy541 » 2007-04-13 10:25

显然看过MIT的算法导论,但是这个方法是unstable的
sandorf 写了:还有更好的方法,楼上的方法都是O(n)时间的,可以用矩阵相乘写出O(log(n))时间的

代码: 全选

| 7 4 2 |   | 1 1 0 |^(n-4)  | T(n)   T(n-1) T(n-2) |
| 4 2 1 | * | 1 0 1 |      = | T(n-1) T(n-2) T(n-3) |
| 2 1 1 |   | 1 0 0 |        | T(n-2) T(n-3) T(n-4) |
其中乘方可以用log(n)时间实现

代码: 全选

def mul(A,B):
    n = len(A)
    C = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            C[i][j] = sum([A[i][k]*B[k][j] for k in range(n)])
    return C

def power(A, n):
    if n == 1:
        return A
    tmp = power(A, n/2)
    
    if n%2:
        return mul(mul(tmp,tmp),A)
    else:
        return mul(tmp,tmp)
            
def T2(n):
    if n == 0: return 1
    if n == 1: return 1
    if n == 2: return 2
    if n == 3: return 4
    if n == 4: return 7
    init = [[7,4,2],[4,2,1],[2,1,1]]
    unit = [[1,1,0],[1,0,1],[1,0,0]]
    return mul(init, power(unit,n-4))[0][0]
同二楼的简单比较一下:

代码: 全选

from time import time
def test(n):
    start = time()
    # linear
    a = T(n)
    end = time()
    print 'linear:\t', end - start

    #log
    start = time()
    b = T2(n)
    end = time()
    print 'log:\t', end - start
在n>800时候更快:

代码: 全选

>>> test(10)
linear: 1.81198120117e-05
log:    0.000334024429321
>>> test(100)
linear: 0.0001380443573
log:    0.000746011734009
>>> test(1000)
linear: 0.0025589466095
log:    0.00187397003174
>>> test(10000)
linear: 0.158092975616
log:    0.0290448665619
>>> test(100000)
linear: 5.38085889816
log:    0.533372163773
>>> 
头像
stlxv
论坛版主
帖子: 8273
注册时间: 2006-05-03 0:39
来自: المريخ
送出感谢: 0
接收感谢: 1 次

Re: Google的编程习题

#17

帖子 stlxv » 2007-04-16 1:18

oneleaf 写了: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) {
}
可以用最熟悉的语言写

代码: 全选

function T(n:integer):integer;
var t0,t1,t2,i,t:integer;
begin
if (n=1) or (n=0) then begin result:=1; exit; end;
if n=2 then begin result:=2; exit; end;
t0:=1;
t1:=1;
t2:=2;
for i:=3 to n do begin
    t:=t0+t1+t2;
    t0:=t1;
    t1:=t2;
    t2:=t;
end;
result:=t;
end;
PHP是最好的语言!不服来战!
头像
stlxv
论坛版主
帖子: 8273
注册时间: 2006-05-03 0:39
来自: المريخ
送出感谢: 0
接收感谢: 1 次

#18

帖子 stlxv » 2007-04-16 1:26

再来一个:

代码: 全选

T[n_]:=[
    If[n<=1, Result:=1,
        If[n==2, Result:=2,
            t0:=1;
            t1:=1;
            t2:=1;
            For[i=3,i<=n,i++,
                Result:=t0+t1+t2;
                t0:=t1;
                t1:=t2;
                t2:=Result
            ]
        ]
    ];
    Result
]
PHP是最好的语言!不服来战!
dilemma
帖子: 1
注册时间: 2006-11-18 21:56
送出感谢: 0
接收感谢: 0

#19

帖子 dilemma » 2007-05-06 15:20

其实就是个递归算法,应该就是二楼的了
sandorf
帖子: 16
注册时间: 2006-12-21 18:05
送出感谢: 0
接收感谢: 0

#20

帖子 sandorf » 2007-07-02 21:26

呵呵,是的,他那个是用2阶矩阵算fibonacci数列,这里正好可以扩展一下
这个unstable这里指什么?使用Python,而不是C,还存在这个问题吗?
hsy541 写了:显然看过MIT的算法导论,但是这个方法是unstable的
sandorf 写了:还有更好的方法,楼上的方法都是O(n)时间的,可以用矩阵相乘写出O(log(n))时间的

代码: 全选

| 7 4 2 |   | 1 1 0 |^(n-4)  | T(n)   T(n-1) T(n-2) |
| 4 2 1 | * | 1 0 1 |      = | T(n-1) T(n-2) T(n-3) |
| 2 1 1 |   | 1 0 0 |        | T(n-2) T(n-3) T(n-4) |
其中乘方可以用log(n)时间实现

代码: 全选

def mul(A,B):
    n = len(A)
    C = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            C[i][j] = sum([A[i][k]*B[k][j] for k in range(n)])
    return C

def power(A, n):
    if n == 1:
        return A
    tmp = power(A, n/2)
    
    if n%2:
        return mul(mul(tmp,tmp),A)
    else:
        return mul(tmp,tmp)
            
def T2(n):
    if n == 0: return 1
    if n == 1: return 1
    if n == 2: return 2
    if n == 3: return 4
    if n == 4: return 7
    init = [[7,4,2],[4,2,1],[2,1,1]]
    unit = [[1,1,0],[1,0,1],[1,0,0]]
    return mul(init, power(unit,n-4))[0][0]
同二楼的简单比较一下:

代码: 全选

from time import time
def test(n):
    start = time()
    # linear
    a = T(n)
    end = time()
    print 'linear:\t', end - start

    #log
    start = time()
    b = T2(n)
    end = time()
    print 'log:\t', end - start
在n>800时候更快:

代码: 全选

>>> test(10)
linear: 1.81198120117e-05
log:    0.000334024429321
>>> test(100)
linear: 0.0001380443573
log:    0.000746011734009
>>> test(1000)
linear: 0.0025589466095
log:    0.00187397003174
>>> test(10000)
linear: 0.158092975616
log:    0.0290448665619
>>> test(100000)
linear: 5.38085889816
log:    0.533372163773
>>> 
头像
wcb552101315
帖子: 66
注册时间: 2007-06-29 22:38
送出感谢: 0
接收感谢: 0
联系:

#21

帖子 wcb552101315 » 2007-07-09 17:38

学习了
生命是琉璃瓶里的冰冻玫瑰,而我,是她坟前燃起的一柱香
yymailb
帖子: 240
注册时间: 2007-03-16 1:38
送出感谢: 0
接收感谢: 0

#22

帖子 yymailb » 2007-07-10 0:25

学到一半, 先睡了, 把链接扔在这里,明天继续看
http://www.math.gatech.edu/~ecroot/recu ... notes2.pdf
cendy_0925
帖子: 21
注册时间: 2007-06-20 14:41
送出感谢: 0
接收感谢: 0

我这里出错,为什么啊?

#23

帖子 cendy_0925 » 2007-08-02 1:55

File "/home/ubuntu/cx/Tn.py", line 15, in
print T(int(sys.argv[1]))
IndexError: list index out of range
Saiy
帖子: 24
注册时间: 2007-04-29 14:47
送出感谢: 0
接收感谢: 0

简单!!!!!!

#24

帖子 Saiy » 2007-08-04 16:35

def T(n):
....if n==0 or n==1:
...............return 1
....elif n==2:
................return 2
....else:
................return T(n-1)+T(n-2)+T(n-3)
n=input()
print T(n)
头像
lvjinhua
帖子: 436
注册时间: 2006-02-23 14:46
来自: 上海
送出感谢: 0
接收感谢: 1 次
联系:

在 Dive into python 中有过如下类似的方法

#25

帖子 lvjinhua » 2007-08-11 23:40

代码: 全选

m={0:1,1:1,2:2} # global
def T(n):
    if n in m.keys():
        return m[n]
    else:
        m[n] = T(n-1) + T(n-2) + T(n-3)
        return m[n]

#Test it
T(100)
T(4)
====
dubuntu-6.06-livecd-i386正式版正式完工!
====
*支持LiveCD硬盘启动
*Linux 2.6.15-23-686
*永中Office 2007
*LumaQQ+OpenQ+cycloneQQ
**N 多的编程及调试工具**
头像
ct
帖子: 2201
注册时间: 2005-04-06 21:15
来自: 安徽黄山
送出感谢: 0
接收感谢: 0
联系:

#26

帖子 ct » 2007-08-15 21:25

大学是睡过去的,这就是差距. :shock:
Leekeen
帖子: 23
注册时间: 2007-03-22 16:31
送出感谢: 0
接收感谢: 0

#27

帖子 Leekeen » 2007-08-24 17:11

楼主的第一种法子很好哦!
就是不知道为什么运行不出来。
情况同23楼。
牡丹花下死,做鬼也风流。
yuri
帖子: 10
注册时间: 2005-05-20 14:09
送出感谢: 0
接收感谢: 0

#28

帖子 yuri » 2007-09-09 21:33

我连题目都看不明白.
robert870119
帖子: 768
注册时间: 2007-03-05 20:45
送出感谢: 0
接收感谢: 0

#29

帖子 robert870119 » 2007-10-01 9:05

[quote="stlxv"][/quote]


只能看懂MM的代码 :oops: :oops:
honggou027
帖子: 6
注册时间: 2006-08-13 19:15
送出感谢: 0
接收感谢: 0

#30

帖子 honggou027 » 2007-11-02 14:50

看二楼的算法是比较的简单!!!!!!!
回复

回到 “Python/Php/Perl”