โปรแกรม C++ สำหรับทฤษฎี Zeckendorf

ที่นี่เราจะดูวิธีตรวจสอบว่าผลรวมที่กำหนดสามารถหาได้จากการบวกเลขฟีโบนัชชีที่ไม่ติดกันหรือไม่ ถ้าใช่ ตัวเลขคืออะไร ตัวอย่างเช่น ถ้าค่าผลรวมคือ 10 นี่คือผลรวมของ 8 และ 2 ทั้ง 8 และ 2 เป็นพจน์ฟีโบนัชชีและไม่ได้อยู่ติดกัน มาดูอัลกอริทึมเพื่อเข้าใจแนวคิด

อัลกอริทึม

nonNeighbourFibo(sum)

Begin
    while sum > 0, do
        fibo := greatest Fibonacci term but not greater than sum
        print fibo
        sum := sum - fibo
    done
End

ตัวอย่าง

#include<iostream>
using namespace std;

int fibonacci(int n) {
    if (n == 0 || n == 1)
        return n;
    // get the greatest Fibonacci Number smaller than n.
    int prev = 0, curr = 1, next = 1;
    while (next <= n) {
        prev = curr;
        curr = next;
        next = prev + curr;
    }
    return curr;
}

void nonNeighbourFibo(int sum) {
    while (sum > 0) {
        int fibo = fibonacci(sum);
        cout << fibo << " ";
        sum = sum - fibo;
    }
}

int main() {
    int sum = 120;
    cout << "Sum is same as Non-adjacent Fibonacci terms: ";
    nonNeighbourFibo(sum);
}

ผลลัพธ์

Sum is same as Non-adjacent Fibonacci terms: 89 21 8 2