歐拉項目＃201

Question

我一直試圖解決Problem 201一段時間了，但我不能想出這樣的大集合的解決方案。考慮到可能的可達金額不超過300,000，我嘗試了一種隨機算法，但它只適用於計算時間較長的較小集合。然後，我嘗試了一種動態編程方法，但沒有取得任何成功。

我已經放棄了，但我很好奇如何有效地解決這個問題。

Answer 1

SP AH AH AH AH！

我想給了我是如何處理這個問題，一對夫婦的提示（和表明它在一般的方式如何適應處理這一問題）

提示1：制定（或只寫代碼）一遞歸以下功能

布爾existsRepresentation（INT數，INT maximalIntegerToSquare，INT numberOfSquares）

其中如果參數號具有表示作爲numberOfSquares的總和 該函數返回true形式的二次項的x^2，其中最大的x是最大的alIntegerToSquare。因此

existsRepresentation（5,2,2），因爲5 = 2^2 + 1^2但 existsRepresentation（5,2,3）爲假，因爲沒有不同的x，y和z < = 2，則返回true使得5 = X^2 + Y^2 + Z^2

HINT 2：制定（或寫代碼）功能

布爾existsUniqueRepresentation（INT數，INT maximalIntegerToSquare，INT numberOfSquares）

遞歸

其中如果參數號碼具有UNIQUE表示形式作爲n的總和 ，則函數返回true umberOfSquares格式x^2的二次項，其中x的最大值小於或等於maximalIntegerToSquare（遞歸應該包含函數 existsUniqueRepresentation和函數existsRepresentation來自HINT 1 ，參數值較小）。因此，

existsUniqueRepresentation（5,2,2）返回true，因爲5 = 2^2 + 1^2並且沒有其他表示5作爲兩個不同平方和x^2 + y^2 x < y （作爲想要的最大y = 2，否則）

existsUniqueRepresentation（5,2,3）是錯誤的，因爲沒有5的表示（因此沒有唯一表示）爲3的平方和3個不同數目小於或大於等於2（沒有X，Y，Z爲其中1 < = X <ý<ž< = 2 ..）

existsUniqueRepresentation（89,8,3）和existsUniqu eRepresentation（89,9,3）是錯誤的，因爲 89 = 8^2 + 4^2 + 3^2和89 = 7^2 + 6^2 + 2^2。 （），或existsUniqueRepresentation（）（實際上這在教科書中被稱爲「memoization」），動態編程（動態編程），動態編程編程指的是一種組織緩存值的方式，以便在不進行遞歸調用的情況下進行計算，但重點始終是將解決方案緩存到子問題）。

所以一般的做法是：將問題制定爲遞歸..然後緩存所有移動的東西！ （你的電腦上有足夠內存的所有東西，就是..）

它可以工作（在這裏以及許多其他問題）！