令 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