確定N是否爲斐波那契，如果沒有找到最大的斐波那奇數小於N

-3

如何確定給定的數字N是否爲斐波納契數，如果該數不是斐波那契數，我如何確定最大的斐波那奇數字小於N？確定N是否爲斐波那契，如果沒有找到最大的斐波那奇數小於N

我通過生成限制N的一系列斐波納契數找到了解決方案。

有沒有更好的方法在Python中做到這一點？

傢伙考慮下投票，我接受了這裏提供的解決方案。我不認爲這是值得的，因爲我發佈了我需要的東西，並從你們那裏得到了解決方案。

謝謝。

來源

2012-08-09 sam

這功課嗎？ – 2012-08-09 07:49:53

這不是關於如何在Python（或任何其他編程語言）中執行此操作，而是關於正確的算法的問題。 – 2012-08-09 07:51:22

nop，我想到了這個問題並試圖獲得解決方案。我用傳統的方式做了這件事，即用限制N_生成一系列斐波納契數。我需要一些優化或更好的方式在PYTHON中做同樣的事情。 – sam 2012-08-09 07:52:45

一些整數N是否是斐波那契數的簡單測試如下：

N is a Fibonacci number iff either (5 * n^2 + 4) or (5 * n^2 - 4) is a square number.

看到這裏巧妙的證明（頁417）：http://www.fq.math.ca/Scanned/10-4/advanced10-4.pdf

如果事實證明N是不是斐波那契數字，那麼最簡單的方法就是繼續嘗試使用較小的數字，直到找到一個數字，儘管對於較大的N這可能需要很長時間。

來源

2012-08-09 08:02:56

下面是一個通用算法：天真的方法是用遞歸來解決它 - 但就運行時複雜性而言，它根本沒有用處。創建一個新的數組，我們稱之爲FibArr。將1,1插入到數組中。然後，數組中第i個索引的值爲fibArr [i-1] + fibArr [i-2]（i> = 3）在每次迭代中檢查插入到fibArr == N中的新值。如果爲true，則返回。否則，檢查插入值是否大於N. 如果爲true，假定現在fibArr具有k個值，則返回（k-1）值。否則，繼續迭代:)

*使用python更容易做到 - 但請注意，在python中沒有數組，但列表。 python更容易，因爲你不必設置列表長度，就像在java中一樣。

來源

2012-08-09 07:56:39 Itamar

確定N是否爲斐波那契，如果沒有找到最大的斐波那奇數小於N

回答

相關問題