我試圖解決上面的問題，但我被卡住了。我想這一切都取決于非質數的因式分解。這個數字可能非常大10^15。
我試圖做的是將 x 和所有 Fibonacci 數分解到大約 155 次（這是超過 10^30 的那個，這意味著我不能將它的因子包含在我的 x 的因子中），然后就像在正常分解中，我從最高的斐波那契數回圈到最低的數，并檢查我的 x 是否具有第 i 個斐波那契數的所有因數。如果是，那么我將 x 除以它。當我到達 i=1（我遍歷了所有斐波那契因子表）時，我只是檢查我的 x 是否等于 1。如果是，那么我的答案是 YES，否則就是 NO。
這個解決方案不起作用，因為有時它以排除進一步除法的方式劃分 x，所以我試圖將它分成兩個回圈 - 第一個回圈只能將 x 除以至少有一個不屬于的數字的斐波那契數到斐波那契數列，第二個可以除以每個數字。
我從這個網站上提取了因式斐波那契數： http : //www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
這是一個破壞第一個想法的例子：
x=2^10 × 3^5 × 5^2 × 7 × 11 × 17 × 23 × 47 × 89 × 1103
我將它除以： 48th number, 12th, 11th, 10th 之后我無法擺脫 17 所以我的答案是否定的，但應該是是除以：48th, 11th, 10th, 9th, 10th, 6th ，第 5 個，第 3*4 個。
我的第二個想法有點奇怪，所以這就是我寫它的原因。我的解決方案是否正確？或者也許還有另一個可以確定這個數字是否可以寫成斐波那契數的乘積？（請注意，x 可能非常大）
uj5u.com熱心網友回復：
不依賴斐波那契數的任何特殊屬性，您可以將其歸類為硬幣找零問題，其中可用的硬幣是斐波那契數，并且必須通過乘法而不是加法來實作目標。
一個解決方案是使用遞回演算法結合記憶化來避免重復解決相同的子問題（動態規劃原理）。
這是 JavaScript 中的演示實作，它運行您在問題中提到的問題的演算法：
// Preprocessing: collect all Fibonacci numbers with 15 digits or less:
let fib = [];
let a = 1, b = 2;
while (b < 1e16) {
fib.push(b);
[a, b] = [b, a b];
}
fib.reverse(); // Put greatest Fib numbers first
let memo = new Map(); // For memoization
function solve(n, start=0) {
if (n === 1) return true;
let result = memo.get(n);
if (result === undefined) { // Not in map:
let i;
for (i = start; i < fib.length; i ) {
if (n % fib[i] == 0) {
// Try solving problem after division by this factor:
if (solve(n / fib[i], i)) break;
}
}
result = i < fib.length;
memo.set(n, result);
}
return result;
}
// Example input from question:
n = 2**10 * 3**5 * 5**2 * 7 * 11 * 17 * 23 * 47 * 89 * 1103
console.log(n, solve(n)); // 864126051784934400 trueuj5u.com熱心網友回復：
你的第一個想法幾乎是正確的：一個微小的修改使它起作用。根據卡邁克爾定理，除了 1、8 和 144 之外的每個斐波那契數都有一個質數除數，它不能整除任何更小的斐波那契數。因為 8 和 144 都可以寫成斐波那契數本身的乘積，所以我們在尋找除數時可以忽略它們。
// Given: integer N
F <- [2, 3, 5, 8, 13...] // All Fibonacci numbers x, 1 < x <= N
F.reverse() // put in decreasing order
for x in F:
if x == 8 or x == 144: continue
while N % x == 0:
N = N / x
return (N == 1)
忽略8和144，這作業，因為如果f是最大的斐波那契數劃分N，那么f有一個素因子p沒有更早Fibonacci數了，所以我們要劃分p出N許多倍，可能的，如果它要寫成產品斐波那契數列。
事實上，在替換 (8 with 2^3) 和 (144 with 2^4 * 3^2or 8 * 2 * 3^2)的同構之前，這個因式分解必須是唯一的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/335898.html
上一篇：如何將陣列劃分為總和最小的子陣列
下一篇：R-向前推進1直到達到另一個1