Рубрики

Теорема Цекендорфа (Непредметное представление Фибоначчи)

Теорема Цекендорфа гласит, что каждое положительное каждое положительное целое число может быть записано однозначно в виде суммы различных несмежных чисел Фибоначчи. Два числа Фибоначчи являются соседями, если они идут один за другим в последовательности Фибоначчи (0, 1, 1, 2, 3, 5, ..). Например, 3 и 5 являются соседями, а 2 и 5 — нет.

По заданному числу найдите представление числа в виде суммы непоследовательных чисел Фибоначчи.

Примеры:

Input:  n = 10
Output: 8 2
8 and 2 are two non-consecutive Fibonacci Numbers
and sum of them is 10.

Input:  n = 30
Output: 21 8 1
21, 8 and 1 are non-consecutive Fibonacci Numbers
and sum of them is 30.

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Идея состоит в том, чтобы использовать алгоритм жадности .

1) Let n be input number

2) While n >= 0
     a) Find the greatest Fibonacci Number smaller than n.
        Let this number be 'f'.  Print 'f'
     b) n = n - f 

C / C ++

// C ++ программа для теоремы Цекендорфа. Находит представление
// из n как сумма несмежных чисел Фибоначчи.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает наибольшее число Фибоначчи меньше
// или равно n.

int nearestSmallerEqFib(int n)

{

    // Угловые шкафы

    if (n == 0 || n == 1)

        return n;

  

    // Находим наибольшее число Фибоначчи меньше

    // чем п.

    int f1 = 0, f2 = 1, f3 = 1;

    while (f3 <= n) {

        f1 = f2;

        f2 = f3;

        f3 = f1 + f2;

    }

    return f2;

}

  
// Печатает представление Фибоначчи от n, используя
// жадный алгоритм

void printFibRepresntation(int n)

{

    while (n > 0) {

        // Найти число Фибоначчи с меньшими числами

        // чем или равно n

        int f = nearestSmallerEqFib(n);

  

        // Распечатать найденное число Фибоначчи

        cout << f << " ";

  

        // Уменьшаем n

        n = n - f;

    }

}

  
// Метод драйвера для тестирования

int main()

{

    int n = 30;

    cout << "Non-neighbouring Fibonacci Representation of "

         << n << " is \n";

    printFibRepresntation(n);

    return 0;

}

Джава

// Java-программа для теоремы Цекендорфа. Находит
// представление n в виде суммы не соседних
// Числа Фибоначчи.

class GFG {

    public static int nearestSmallerEqFib(int n)

    {

        // Угловые шкафы

        if (n == 0 || n == 1)

            return n;

  

        // Находим наибольшее число Фибоначчи меньше

        // чем п.

        int f1 = 0, f2 = 1, f3 = 1;

        while (f3 <= n) {

            f1 = f2;

            f2 = f3;

            f3 = f1 + f2;

        }

        return f2;

    }

  

    // Печатает представление Фибоначчи от n, используя

    // жадный алгоритм

    public static void printFibRepresntation(int n)

    {

        while (n > 0) {

            // Найти число Фибоначчи с меньшими числами

            // чем или равно n

            int f = nearestSmallerEqFib(n);

  

            // Распечатать найденное число Фибоначчи

            System.out.print(f + " ");

  

            // Уменьшаем n

            n = n - f;

        }

    }

  

    // Метод драйвера для тестирования

    public static void main(String[] args)

    {

        int n = 30;

        System.out.println("Non-neighbouring Fibonacci "

                           + " Representation of " + n + " is");

  

        printFibRepresntation(n);

    }

}

  
// Код предоставлен Мохитом Гупта_OMG

питон

# Программа Python для теоремы Цекендорфа. Находит
# представление n в виде суммы не соседних
Числа Фибоначчи.

  
# Возвращает наибольшее число Фибоначчи меньше
# или равно n.

def nearestSmallerEqFib(n):

      

    # Угловые чехлы

    if (n == 0 or n == 1):

        return n

         

    # Находит наибольшее число Фибоначчи меньше

    # чем n.

    f1, f2, f3 = 0, 1, 1

    while (f3 <= n):

        f1 = f2;

        f2 = f3;

        f3 = f1 + f2;

    return f2;

  

  
# Печатает представление Фибоначчи от n, используя
# жадный алгоритм

def printFibRepresntation(n):

      

    while (n>0):

  

        # Найдите число Фибоначчи, которое меньше

        # чем или равно n

        f = nearestSmallerEqFib(n);

   

        # Распечатать найденное число Фибоначчи

        print f,

   

        # Уменьшить n

        n = n-f

  
# Тест кода водителя над функциями

n = 30

print "Non-neighbouring Fibonacci Representation of", n, "is"

printFibRepresntation(n)

C #

// C # программа для теоремы Цекендорфа.
// Находит представление n как
// сумма несоседних Фибоначчи
// Числа.

using System;

  

class GFG {

    public static int nearestSmallerEqFib(int n)

    {

        // Угловые шкафы

        if (n == 0 || n == 1)

            return n;

  

        // Находим величайшее число Фибоначчи

        // Число меньше n.

        int f1 = 0, f2 = 1, f3 = 1;

        while (f3 <= n) {

            f1 = f2;

            f2 = f3;

            f3 = f1 + f2;

        }

        return f2;

    }

  

    // Печатает представление Фибоначчи

    // из n используя жадный алгоритм

    public static void printFibRepresntation(int n)

    {

        while (n > 0) {

            // Находим врата Фибоначчи

            // Число меньше или равно

            // к п

            int f = nearestSmallerEqFib(n);

  

            // Распечатать найденное число Фибоначчи

            Console.Write(f + " ");

  

            // Уменьшаем n

            n = n - f;

        }

    }

  

    // Метод драйвера

    public static void Main()

    {

        int n = 40;

        Console.WriteLine("Non-neighbouring Fibonacci "

                          + " Representation of " + n + " is");

  

        printFibRepresntation(n);

    }

}

  
// Код предоставлен vt_m

PHP

<?php
// PHP-программа для теоремы Цекендорфа.
// Находит представление n в виде суммы
// несмежных чисел Фибоначчи.

  
// Возвращает наибольшее число Фибоначчи
// Число меньше или равно
// к п.

function nearestSmallerEqFib($n)

{

      

    // Угловые шкафы

    if ($n == 0 || $n==1)

    return $n;

  

    // Находим величайшее число Фибоначчи

    // Число меньше n.

    $f1 = 0; 

    $f2 = 1; 

    $f3 = 1;

    while ($f3 <= $n)

    {

        $f1 = $f2;

        $f2 = $f3;

        $f3 = $f1 + $f2;

    }

    return $f2;

}

  
// Печатает представление Фибоначчи
// из n используя жадный алгоритм

function printFibRepresntation($n)

{

    while ($n > 0)

    {

          

        // Находим врата Фибоначчи

        // Число меньше или

        // равно n

        $f = nearestSmallerEqFib($n);

  

        // Распечатать найденное

        // число Фибоначчи

        echo $f, " ";

  

        // Уменьшаем n

        $n = $n - $f;

    }

}

  

    // Код драйвера

    $n = 30;

    echo "Non-neighbouring Fibonacci Representation of ",

                                            $n, " is \n";

    printFibRepresntation($n);

  
// Этот код предоставлен ajit
?>


Выход:

Non-neighbouring Fibonacci Representation of 30 is 
21 8 1 

Как работает вышеуказанный алгоритм Greedy?
Пусть наибольшее число Фибоначчи, меньшее или равное n, будет fib (i) [i-е число Фибоначчи].

Тогда n — fib (i) будет иметь свое собственное представление в виде суммы несмежных чисел Фибоначчи.

Все, что мы хотим убедиться, это то, что соседних проблем нет. По индукции n-fib (i) не имеет соседней проблемы, тогда единственный способ, которым n может иметь соседнюю проблему, — это если n-fib (i) использует fib (i-1) в своем представлении.

Таким образом, все, что нам нужно доказать, это то, что n-fib (i) не использует fib (i-1) в своем представлении.

Давайте докажем это, используя противоречие. Если n-fib (i) = fib (i-1) + fib (ix) +…, то fib (i) не может быть ближайшим наименьшим числом Фибоначчи к n, поскольку сама fib (i) + fib (i-1) Фиб (я + 1).

Таким образом, если n-fib (i) содержит в своем представлении fib (i-1), то fib (i + 1) будет меньше, чем число fib, чем n, что противоречит нашему предположению, что fib (i) является ближайшим меньшим числом fib к n ,

Может ли это представление быть полезным?
Как бинарное представление. Это может быть альтернативное представление для представления положительных чисел. Одно важное замечание об этом представлении состоит в том, что число 1 в представлении Фибоначчи имеет тенденцию быть намного меньше, чем число 1 в двоичном представлении. Следовательно, если в любом приложении, где хранить 1 стоит дороже, чем хранить 0, имеет смысл использовать представление Фибоначчи.

Эта статья предоставлена Гауравом Саксеной . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Теорема Цекендорфа (Непредметное представление Фибоначчи)

0.00 (0%) 0 votes