MATLAB编程实例-（42）斐波那契数列分解

题目

取自Mathwork平台上的Cody问题42340 - Fibonacci分解。每个正整数都可以唯一地分解为非连续的斐波那契数之和。给定一个正整数n，请返回这些数字。返回向量f = [f1, f2, …]并按从小到大的顺序排列。sum(f)等于n。示例：n=3时的结果为f=[3]

n = 32
f = [3 8 21]

分析

这道题目确实有一定难度。查阅了其他解法后发现，“任何一个正整數都可以表示為若干個互不相鄰的Fibonacci數之和”，這一句話表達了這樣一個事實：在這些互不相鄰的Fibonacci數中، 必然包含与其最接近的一个Fibonacci数值。基於此結論, 接下来我們可以採用遞歸的方法來求解最終結果。

代码

    function f = fib_decomposition(n)
    if n==0
    f = [];
    else
    f = [1 2];
    while f(2)<=n %找到当前数n在斐波那契数列中的位置
        f = [f(2) sum(f)];
    end
    f = [fib_decomposition(n-f(1)) f(1)];%和n相近的数f(1)作为所求的数之一，其它的数再进行递归即可
    end
    end