Raku: 解 Fibonacci Sum
作者：gugod 發佈於： #rakuFibonacci Sum 是個從 Perl Weekly Challenge 那裡看來的題目。輸入為整數 $N，目標為找出所有總和為 $N 之費波納契數集合，且集合內數字不重複。
目前已知所有正整數 $N 都至少對應到一組解。此為齊肯多夫定理。其實齊肯多夫定理內所提到的表示式比這題目限制更強一些，比方說不能使用相鄰的費波納契數，但總之，「對所有正整數 N 都至少有一組解」這個陳述依然成立。
費波納契數，就是在費波納契數列裡出現的數字。基本上就只有第一個 1 有重複一次，後面出現的數字就全無重複了。因此，稍為改一下定義，讓頭兩個數字為 (1,2) 就可生出毫無重複數字的費波納契數無限集合。
my @fib = 1, 2, { $^a + $^b } ... *;
既然 $N 與 @fib 內容都是正整數，那麼計算總和時，若用了比 $N 更大的 @fib[$i]，就不可能得到 $N。因此比 $N 還大的部分就可以不必計算出來。換言之，取 @fib 前方 k 個就可以了：
my @subfib = @fib[0 ... @fib.first({ $^fib > $n }, :k)-1];
剩下的部份就是寫個暴力法把所有組合找出來：
sumsearch($n, @subfib);
其中這 sumsearch 就是本題核心的通解，其目的就是要找出所有總和為 $n 的 @subfib 的子集合。
考慮到這題目的特殊性，或許可以用 DP 解，但總之先做個直接了當的遞迴解：
sub sumsearch (Int $n, @nums) {
my @solutions = [];
if $n == 0 {
@solutions.push([]);
return @solutions;
}
if @nums.elems == 0 || $n < 0 {
return @solutions;
}
my $firstNum = @nums.pop();
my @s1 = sumsearch($n, @nums);
my @s2 = sumsearch($n - $firstNum, @nums).map({ $_.prepend($firstNum) });
@nums.push($firstNum);
@solutions.append(@s1);
@solutions.append(@s2);
return @solutions;
}
實際上全整合起來之後還頂好玩的。比方說fibsum(8192) 有 81 組解：
# raku fibsum.raku 8192
... subfib = 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
|fibsum(8192)| = 81
8192
= 4181 + 1597 + 987 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 1597 + 987 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 3
= 4181 + 1597 + 987 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 2 + 1
= 4181 + 1597 + 987 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 3
= 4181 + 1597 + 987 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 8
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 3
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 2 + 1
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 3
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 34 + 21 + 8
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 55 + 5 + 2 + 1
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 55 + 5 + 3
= 4181 + 1597 + 987 + 610 + 377 + 233 + 144 + 55 + 8
= 4181 + 2584 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 2584 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 3
= 4181 + 2584 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 2 + 1
= 4181 + 2584 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 3
= 4181 + 2584 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 8
= 4181 + 2584 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 2584 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 3
= 4181 + 2584 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 2 + 1
= 4181 + 2584 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 3
= 4181 + 2584 + 610 + 377 + 233 + 144 + 34 + 21 + 8
= 4181 + 2584 + 610 + 377 + 233 + 144 + 55 + 5 + 2 + 1
= 4181 + 2584 + 610 + 377 + 233 + 144 + 55 + 5 + 3
= 4181 + 2584 + 610 + 377 + 233 + 144 + 55 + 8
= 4181 + 2584 + 987 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 2584 + 987 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 3
= 4181 + 2584 + 987 + 233 + 89 + 55 + 34 + 21 + 5 + 2 + 1
= 4181 + 2584 + 987 + 233 + 89 + 55 + 34 + 21 + 5 + 3
= 4181 + 2584 + 987 + 233 + 89 + 55 + 34 + 21 + 8
= 4181 + 2584 + 987 + 233 + 144 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 2584 + 987 + 233 + 144 + 34 + 13 + 8 + 5 + 3
= 4181 + 2584 + 987 + 233 + 144 + 34 + 21 + 5 + 2 + 1
= 4181 + 2584 + 987 + 233 + 144 + 34 + 21 + 5 + 3
= 4181 + 2584 + 987 + 233 + 144 + 34 + 21 + 8
= 4181 + 2584 + 987 + 233 + 144 + 55 + 5 + 2 + 1
= 4181 + 2584 + 987 + 233 + 144 + 55 + 5 + 3
= 4181 + 2584 + 987 + 233 + 144 + 55 + 8
= 4181 + 2584 + 987 + 377 + 34 + 13 + 8 + 5 + 2 + 1
= 4181 + 2584 + 987 + 377 + 34 + 13 + 8 + 5 + 3
= 4181 + 2584 + 987 + 377 + 34 + 21 + 5 + 2 + 1
= 4181 + 2584 + 987 + 377 + 34 + 21 + 5 + 3
= 4181 + 2584 + 987 + 377 + 34 + 21 + 8
= 4181 + 2584 + 987 + 377 + 55 + 5 + 2 + 1
= 4181 + 2584 + 987 + 377 + 55 + 5 + 3
= 4181 + 2584 + 987 + 377 + 55 + 8
= 6765 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 2 + 1
= 6765 + 610 + 377 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 3
= 6765 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 2 + 1
= 6765 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 5 + 3
= 6765 + 610 + 377 + 233 + 89 + 55 + 34 + 21 + 8
= 6765 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 2 + 1
= 6765 + 610 + 377 + 233 + 144 + 34 + 13 + 8 + 5 + 3
= 6765 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 2 + 1
= 6765 + 610 + 377 + 233 + 144 + 34 + 21 + 5 + 3
= 6765 + 610 + 377 + 233 + 144 + 34 + 21 + 8
= 6765 + 610 + 377 + 233 + 144 + 55 + 5 + 2 + 1
= 6765 + 610 + 377 + 233 + 144 + 55 + 5 + 3
= 6765 + 610 + 377 + 233 + 144 + 55 + 8
= 6765 + 987 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 2 + 1
= 6765 + 987 + 233 + 89 + 55 + 34 + 13 + 8 + 5 + 3
= 6765 + 987 + 233 + 89 + 55 + 34 + 21 + 5 + 2 + 1
= 6765 + 987 + 233 + 89 + 55 + 34 + 21 + 5 + 3
= 6765 + 987 + 233 + 89 + 55 + 34 + 21 + 8
= 6765 + 987 + 233 + 144 + 34 + 13 + 8 + 5 + 2 + 1
= 6765 + 987 + 233 + 144 + 34 + 13 + 8 + 5 + 3
= 6765 + 987 + 233 + 144 + 34 + 21 + 5 + 2 + 1
= 6765 + 987 + 233 + 144 + 34 + 21 + 5 + 3
= 6765 + 987 + 233 + 144 + 34 + 21 + 8
= 6765 + 987 + 233 + 144 + 55 + 5 + 2 + 1
= 6765 + 987 + 233 + 144 + 55 + 5 + 3
= 6765 + 987 + 233 + 144 + 55 + 8
= 6765 + 987 + 377 + 34 + 13 + 8 + 5 + 2 + 1
= 6765 + 987 + 377 + 34 + 13 + 8 + 5 + 3
= 6765 + 987 + 377 + 34 + 21 + 5 + 2 + 1
= 6765 + 987 + 377 + 34 + 21 + 5 + 3
= 6765 + 987 + 377 + 34 + 21 + 8
= 6765 + 987 + 377 + 55 + 5 + 2 + 1
= 6765 + 987 + 377 + 55 + 5 + 3
= 6765 + 987 + 377 + 55 + 8
我對哪些數字只有一組解有點好奇，所以試著找了一下：
# for n in {1..8192}; raku fibsum.raku $n | grep fibsum | grep '= 1$'
|fibsum(1)| = 1
|fibsum(2)| = 1
|fibsum(4)| = 1
|fibsum(7)| = 1
|fibsum(12)| = 1
|fibsum(20)| = 1
|fibsum(33)| = 1
|fibsum(54)| = 1
|fibsum(88)| = 1
|fibsum(143)| = 1
|fibsum(232)| = 1
|fibsum(376)| = 1
|fibsum(609)| = 1
|fibsum(986)| = 1
|fibsum(1596)| = 1
^C
顯然，此為目的的話，這個暴力搜尋演算法真是又慢、能耗又高。以後再參考這裡的解說用 DP 重做一次看看。
前述程式碼源碼全文在此： fibsum.raku