Raku: 解 Fibonacci Sum

作者:   發佈於:

Fibonacci 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