Re: [問題] Google Code Jam 2008, Round 1A - C
令 x = 3 + √5 y = 3 - √5
易知 x+y = 6 xy = 4 (這是 y 選這個值的原因之一)
那麼 x^2 + y^2 = (x+y)^2 - 2xy = 36 - 8 = 28
x^3 + y^3 = (x+y)(x^2+y^2) - xy(x+y) = 6(28) - 4(6) = 144
x^4 + y^4 = (x+y)(x^3+y^3) - xy(x^2+y^2) = 6(144) - 4(28) = 752
等等
一般來說我們有 x^n + y^n = (x^(n-1) + y^(n-1))(x+y) - (x^(n-2)+y^(n-2))(xy)
若令 A_n = x^n + y^n 則我們就有
A_0 = 2 A_1 = 6 A_n = 6A_(n-1) - 4A_(n-2) 這樣的遞迴式
而所求的 floor(x^n) 即為 (A_n) - 1
(這是由於 0 < y < 1 所以 0 < y^n < 1, 這是 y 選這個值的原因之二)
由於有這樣的遞迴式的關係 一定時間之後必然會發生循環
最最粗略的估計 觀察到除了前兩項外後面的所有項都是四的倍數
(A_2 = 28, 因此 A_3 之後全部都是四的倍數)
因此前兩項的末三位到後來至多只會有 250^2 = 62500 種組合
於是在 62500 項後必定存在循環
基本上這樣就足夠寫出一個不慢的程式了
而且實際上如你所發現的 其實一百項之後就循環了 XD
--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.230.62
→
03/08 10:39, , 1F
03/08 10:39, 1F
推
03/08 13:28, , 2F
03/08 13:28, 2F
→
03/08 13:29, , 3F
03/08 13:29, 3F
→
03/08 13:30, , 4F
03/08 13:30, 4F
→
03/08 13:30, , 5F
03/08 13:30, 5F
推
03/08 13:49, , 6F
03/08 13:49, 6F
推
03/08 13:57, , 7F
03/08 13:57, 7F
→
03/08 14:02, , 8F
03/08 14:02, 8F
→
03/08 19:33, , 9F
03/08 19:33, 9F
討論串 (同標題文章)