Zeckendorf’s Theorem

Zeckendorf's theorem states that every positive number can split into distinct non consecutive fibonacci numbers. For example.

Input : 32
OutPut : 21 8 3

Input  : 64
OutPut : 55 + 8 + 1

Consecutive elements means in a fibonacci series neighbor element. For example.

0  1  1  2  3  5  8  13  21  34  55  89  144  233  377

Here given the code implementation process.

/*
    C program for
    Zeckendorf’s Theorem
*/
#include <stdio.h>

int fibNumber(int n)
{
    int a = 0;
    int b = 1;
    int c = 1;
    while (c <= n)
    {
        a = b;
        b = c;
        c = a + b;
    }
    // return fibonacci number which 
    // is less than or equal to n
    return b;
}
void combination(int n)
{
    if (n <= 0)
    {
        return;
    }
    int v = 0;
    // Display given number
    printf("\n Given n : %d", n);
    printf("\n Result  :");
    // Display partition of given number n by Fibonacci numbers
    while (n > 0)
    {
        // Find Fibonacci number which is less than or equal to n
        v = fibNumber(n);
        // Display value
        printf(" %d", v);
        // Reduce the value
        n = n - v;
    }
}
int main(int argc, char
    const *argv[])
{
    // Test A
    // num = 64
    // 64 = (55 + 8 + 1)
    combination(64);
    // Test B
    // num = 33
    // 33 = (21 + 8 + 3 + 1)
    combination(33);
    return 0;
}

Output

 Given n : 64
 Result  : 55 8 1
 Given n : 33
 Result  : 21 8 3 1
/*
    Java Program 
    Zeckendorf’s Theorem
*/
public class ZeckendorfTheorem
{
    public int fibNumber(int n)
    {
        int a = 0;
        int b = 1;
        int c = 1;
        while (c <= n)
        {
            a = b;
            b = c;
            c = a + b;
        }
        // return fibonacci number which 
        // is less than or equal to n
        return b;
    }
    public void combination(int n)
    {
        if (n <= 0)
        {
            return;
        }
        int v = 0;
        // Display given number
        System.out.print("\n Given n : " + n);
        System.out.print("\n Result :");
        // Display partition of given number n by Fibonacci numbers
        while (n > 0)
        {
            // Find Fibonacci number which is less than or equal to n
            v = fibNumber(n);
            // Display value
            System.out.print(" " + v);
            // Reduce the value
            n = n - v;
        }
    }
    public static void main(String[] args)
    {
        ZeckendorfTheorem task = new ZeckendorfTheorem();
        // Test A
        // num = 64
        // 64 = (55 + 8 + 1)
        task.combination(64);
        // Test B
        // num = 33
        // 33 = (21 + 8 + 3 + 1)
        task.combination(33);
    }
}

Output

 Given n : 64
 Result : 55 8 1
 Given n : 33
 Result : 21 8 3 1
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program 
    Zeckendorf’s Theorem
*/
class ZeckendorfTheorem
{
    public: int fibNumber(int n)
    {
        int a = 0;
        int b = 1;
        int c = 1;
        while (c <= n)
        {
            a = b;
            b = c;
            c = a + b;
        }
        // return fibonacci number which 
        // is less than or equal to n
        return b;
    }
    void combination(int n)
    {
        if (n <= 0)
        {
            return;
        }
        int v = 0;
        // Display given number
        cout << "\n Given n : " << n;
        cout << "\n Result :";
        // Display partition of given number n by Fibonacci numbers
        while (n > 0)
        {
            // Find Fibonacci number which is less than or equal to n
            v = this->fibNumber(n);
            // Display value
            cout << " " << v;
            // Reduce the value
            n = n - v;
        }
    }
};
int main()
{
    ZeckendorfTheorem *task = new ZeckendorfTheorem();
    // Test A
    // num = 64
    // 64 = (55 + 8 + 1)
    task->combination(64);
    // Test B
    // num = 33
    // 33 = (21 + 8 + 3 + 1)
    task->combination(33);
    return 0;
}

Output

 Given n : 64
 Result : 55 8 1
 Given n : 33
 Result : 21 8 3 1
// Include namespace system
using System;
/*
    Csharp Program 
    Zeckendorf’s Theorem
*/
public class ZeckendorfTheorem
{
    public int fibNumber(int n)
    {
        int a = 0;
        int b = 1;
        int c = 1;
        while (c <= n)
        {
            a = b;
            b = c;
            c = a + b;
        }
        // return fibonacci number which 
        // is less than or equal to n
        return b;
    }
    public void combination(int n)
    {
        if (n <= 0)
        {
            return;
        }
        int v = 0;
        // Display given number
        Console.Write("\n Given n : " + n);
        Console.Write("\n Result :");
        // Display partition of given number n by Fibonacci numbers
        while (n > 0)
        {
            // Find Fibonacci number which is less than or equal to n
            v = this.fibNumber(n);
            // Display value
            Console.Write(" " + v);
            // Reduce the value
            n = n - v;
        }
    }
    public static void Main(String[] args)
    {
        ZeckendorfTheorem task = new ZeckendorfTheorem();
        // Test A
        // num = 64
        // 64 = (55 + 8 + 1)
        task.combination(64);
        // Test B
        // num = 33
        // 33 = (21 + 8 + 3 + 1)
        task.combination(33);
    }
}

Output

 Given n : 64
 Result : 55 8 1
 Given n : 33
 Result : 21 8 3 1
package main
import "fmt"
/*
    Go Program 
    Zeckendorf’s Theorem
*/
type ZeckendorfTheorem struct {}
func getZeckendorfTheorem() * ZeckendorfTheorem {
    var me *ZeckendorfTheorem = &ZeckendorfTheorem {}
    return me
}
func(this ZeckendorfTheorem) fibNumber(n int) int {
    var a int = 0
    var b int = 1
    var c int = 1
    for (c <= n) {
        a = b
        b = c
        c = a + b
    }
    // return fibonacci number which 
    // is less than or equal to n
    return b
}
func(this ZeckendorfTheorem) combination(n int) {
    if n <= 0 {
        return
    }
    var v int = 0
    // Display given number
    fmt.Print("\n Given n : ", n)
    fmt.Print("\n Result :")
    // Display partition of given number n by Fibonacci numbers
    for (n > 0) {
        // Find Fibonacci number which is less than or equal to n
        v = this.fibNumber(n)
        // Display value
        fmt.Print(" ", v)
        // Reduce the value
        n = n - v
    }
}
func main() {
    var task * ZeckendorfTheorem = getZeckendorfTheorem()
    // Test A
    // num = 64
    // 64 = (55 + 8 + 1)
    task.combination(64)
    // Test B
    // num = 33
    // 33 = (21 + 8 + 3 + 1)
    task.combination(33)
}

Output

 Given n : 64
 Result  : 55 8 1
 Given n : 33
 Result  : 21 8 3 1
<?php
/*
    Php Program 
    Zeckendorf’s Theorem
*/
class ZeckendorfTheorem
{
    public  function fibNumber($n)
    {
        $a = 0;
        $b = 1;
        $c = 1;
        while ($c <= $n)
        {
            $a = $b;
            $b = $c;
            $c = $a + $b;
        }
        // return fibonacci number which 
        // is less than or equal to n
        return $b;
    }
    public  function combination($n)
    {
        if ($n <= 0)
        {
            return;
        }
        $v = 0;
        // Display given number
        echo("\n Given n : ".$n);
        echo("\n Result :");
        // Display partition of given number n by Fibonacci numbers
        while ($n > 0)
        {
            // Find Fibonacci number which is less than or equal to n
            $v = $this->fibNumber($n);
            // Display value
            echo(" ".$v);
            // Reduce the value
            $n = $n - $v;
        }
    }
}

function main()
{
    $task = new ZeckendorfTheorem();
    // Test A
    // num = 64
    // 64 = (55 + 8 + 1)
    $task->combination(64);
    // Test B
    // num = 33
    // 33 = (21 + 8 + 3 + 1)
    $task->combination(33);
}
main();

Output

 Given n : 64
 Result : 55 8 1
 Given n : 33
 Result : 21 8 3 1
/*
    Node JS Program 
    Zeckendorf’s Theorem
*/
class ZeckendorfTheorem
{
    fibNumber(n)
    {
        var a = 0;
        var b = 1;
        var c = 1;
        while (c <= n)
        {
            a = b;
            b = c;
            c = a + b;
        }
        // return fibonacci number which 
        // is less than or equal to n
        return b;
    }
    combination(n)
    {
        if (n <= 0)
        {
            return;
        }
        var v = 0;
        // Display given number
        process.stdout.write("\n Given n : " + n);
        process.stdout.write("\n Result :");
        // Display partition of given number n by Fibonacci numbers
        while (n > 0)
        {
            // Find Fibonacci number which is less than or equal to n
            v = this.fibNumber(n);
            // Display value
            process.stdout.write(" " + v);
            // Reduce the value
            n = n - v;
        }
    }
}

function main()
{
    var task = new ZeckendorfTheorem();
    // Test A
    // num = 64
    // 64 = (55 + 8 + 1)
    task.combination(64);
    // Test B
    // num = 33
    // 33 = (21 + 8 + 3 + 1)
    task.combination(33);
}
main();

Output

 Given n : 64
 Result : 55 8 1
 Given n : 33
 Result : 21 8 3 1
#    Python 3 Program 
#    Zeckendorf’s Theorem
class ZeckendorfTheorem :
    def fibNumber(self, n) :
        a = 0
        b = 1
        c = 1
        while (c <= n) :
            a = b
            b = c
            c = a + b
        
        #  return fibonacci number which 
        #  is less than or equal to n
        return b
    
    def combination(self, n) :
        if (n <= 0) :
            return
        
        v = 0
        #  Display given number
        print("\n Given n : ", n, end = "")
        print("\n Result :", end = "")
        #  Display partition of given number n by Fibonacci numbers
        while (n > 0) :
            #  Find Fibonacci number which is less than or equal to n
            v = self.fibNumber(n)
            #  Display value
            print(" ", v, end = "")
            #  Reduce the value
            n = n - v
        
    

def main() :
    task = ZeckendorfTheorem()
    #  Test A
    #  num = 64
    #  64 = (55 + 8 + 1)
    task.combination(64)
    #  Test B
    #  num = 33
    #  33 = (21 + 8 + 3 + 1)
    task.combination(33)

if __name__ == "__main__": main()

Output

 Given n :  64
 Result :  55  8  1
 Given n :  33
 Result :  21  8  3  1
#    Ruby Program 
#    Zeckendorf’s Theorem
class ZeckendorfTheorem 
    def fibNumber(n) 
        a = 0
        b = 1
        c = 1
        while (c <= n) 
            a = b
            b = c
            c = a + b
        end

        #  return fibonacci number which 
        #  is less than or equal to n
        return b
    end

    def combination(n) 
        if (n <= 0) 
            return
        end

        v = 0
        #  Display given number
        print("\n Given n : ", n)
        print("\n Result :")
        #  Display partition of given number n by Fibonacci numbers
        while (n > 0) 
            #  Find Fibonacci number which is less than or equal to n
            v = self.fibNumber(n)
            #  Display value
            print(" ", v)
            #  Reduce the value
            n = n - v
        end

    end

end

def main() 
    task = ZeckendorfTheorem.new()
    #  Test A
    #  num = 64
    #  64 = (55 + 8 + 1)
    task.combination(64)
    #  Test B
    #  num = 33
    #  33 = (21 + 8 + 3 + 1)
    task.combination(33)
end

main()

Output

 Given n : 64
 Result : 55 8 1
 Given n : 33
 Result : 21 8 3 1
/*
    Scala Program 
    Zeckendorf’s Theorem
*/
class ZeckendorfTheorem()
{
    def fibNumber(n: Int): Int = {
        var a: Int = 0;
        var b: Int = 1;
        var c: Int = 1;
        while (c <= n)
        {
            a = b;
            b = c;
            c = a + b;
        }
        // return fibonacci number which 
        // is less than or equal to n
        return b;
    }
    def combination(num: Int): Unit = {
        if (num <= 0)
        {
            return;
        }
        var v: Int = 0;
        var n = num;
        // Display given number
        print("\n Given n : " + n);
        print("\n Result :");
        // Display partition of given number n by Fibonacci numbers
        while (n > 0)
        {
            // Find Fibonacci number which is less than or equal to n
            v = fibNumber(n);
            // Display value
            print(" " + v);
            // Reduce the value
            n = n - v;
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: ZeckendorfTheorem = new ZeckendorfTheorem();
        // Test A
        // num = 64
        // 64 = (55 + 8 + 1)
        task.combination(64);
        // Test B
        // num = 33
        // 33 = (21 + 8 + 3 + 1)
        task.combination(33);
    }
}

Output

 Given n : 64
 Result : 55 8 1
 Given n : 33
 Result : 21 8 3 1
/*
    Swift 4 Program 
    Zeckendorf’s Theorem
*/
class ZeckendorfTheorem
{
    func fibNumber(_ n: Int) -> Int
    {
        var a: Int = 0;
        var b: Int = 1;
        var c: Int = 1;
        while (c <= n)
        {
            a = b;
            b = c;
            c = a + b;
        }
        // return fibonacci number which 
        // is less than or equal to n
        return b;
    }
    func combination(_ num: Int)
    {
        if (num <= 0)
        {
            return;
        }
        var v: Int = 0;
        var n: Int = num;
        // Display given number
        print("\n Given n : ", n, terminator: "");
        print("\n Result  :", terminator: "");
        // Display partition of given number n by Fibonacci numbers
        while (n > 0)
        {
            // Find Fibonacci number which is less than or equal to n
            v = self.fibNumber(n);
            // Display value
            print(" ", v, terminator: "");
            // Reduce the value
            n = n - v;
        }
    }
}
func main()
{
    let task: ZeckendorfTheorem = ZeckendorfTheorem();
    // Test A
    // num = 64
    // 64 = (55 + 8 + 1)
    task.combination(64);
    // Test B
    // num = 33
    // 33 = (21 + 8 + 3 + 1)
    task.combination(33);
}
main();

Output

 Given n :  64
 Result  :  55  8  1
 Given n :  33
 Result  :  21  8  3  1
/*
    Kotlin Program 
    Zeckendorf’s Theorem
*/
class ZeckendorfTheorem
{
    fun fibNumber(n: Int): Int
    {
        var a: Int ;
        var b: Int = 1;
        var c: Int = 1;
        while (c <= n)
        {
            a = b;
            b = c;
            c = a + b;
        }
        // return fibonacci number which 
        // is less than or equal to n
        return b;
    }
    fun combination(num: Int): Unit
    {
        if (num <= 0)
        {
            return;
        }
        var n: Int = num;
        var v: Int ;
        // Display given number
        print("\n Given n : " + n);
        print("\n Result  :");
        // Display partition of given number n by Fibonacci numbers
        while (n > 0)
        {
            // Find Fibonacci number which is less than or equal to n
            v = this.fibNumber(n);
            // Display value
            print(" " + v);
            // Reduce the value
            n = n - v;
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val task: ZeckendorfTheorem = ZeckendorfTheorem();
    // Test A
    // num = 64
    // 64 = (55 + 8 + 1)
    task.combination(64);
    // Test B
    // num = 33
    // 33 = (21 + 8 + 3 + 1)
    task.combination(33);
}

Output

 Given n : 64
 Result  : 55 8 1
 Given n : 33
 Result  : 21 8 3 1


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved