Рубрики

Кодирование Фибоначчи

Математика

Кодирование Фибоначчи кодирует целое число в двоичное число с использованием представления числа Фибоначчи. Идея основана на теореме Цекендорфа, которая гласит, что каждое положительное целое число может быть записано однозначно в виде суммы различных несмежных чисел Фибоначчи (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, …… ..).

Кодовое слово Фибоначчи для конкретного целого числа — это в точности целочисленное представление Цекендорфа с обратным порядком его цифр и добавлением дополнительной «1» в конце. Дополнительная 1 добавляется для обозначения конца кода (обратите внимание, что код никогда не содержит двух последовательных единиц в соответствии с теоремой Цекендорфа . Представление использует числа Фибоначчи, начинающиеся с 1 (2-го числа Фибоначчи). Таким образом, используемые числа Фибоначчи 1, 2 , 3, 5, 8, 13, 21, 34, 55, 89, 141, …….

Учитывая число n, выведите его код Фибоначчи.

Примеры:

Input: n = 1
Output: 11
1 is first Fibonacci number in this representation
and an extra 1 is appended at the end.

Input:  n = 11
Output: 001011
11 is sum of 8 and 3.  The last 1 represents extra 1
that is always added. A 1 before it represents 8. The
third 1 (from beginning) represents 3.

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.
Следующий алгоритм принимает целое число в качестве входных данных и генерирует строку, в которой хранится кодировка Фибоначчи.

Найти наибольшее число Фибоначчи f, меньшее или равное n. Скажи, что это я номер в серии Фибоначчи. Длина кодового слова для n будет i + 3 символа (один для дополнительного 1 добавляется в конце, один, потому что я индекс, и один для '/ 0'). Предполагая, что ряд Фибоначчи хранится:

  • Пусть f будет наибольшим числом Фибоначчи, меньшим или равным n, с добавлением «1» в двоичной строке. Это указывает на использование f в представлении для n. Вычтите f из n: n = n — f
  • Иначе, если f больше n, добавьте «0» к двоичной строке.
  • Перейти к числу Фибоначчи чуть меньше, чем f.
  • Повторяйте до нулевого остатка (n = 0)
  • Добавьте дополнительную '1' к двоичной строке. Мы получаем кодировку, в которой две последовательные единицы указывают на конец числа (и начало следующей).

    • Ниже приведена реализация вышеуказанного алгоритма.

    C ++

    / * C-программа для кодирования Фибоначчи натурального числа n * /

      
    #include<stdio.h>
    #include<stdlib.h>

      
    // Для ограничения наибольшего числа Фибоначчи, которое будет использоваться
    #define N 30 

      
    / * Массив для хранения чисел Фибоначчи. фиб [я] идет

       хранить (i + 2) 'число Фибоначчи * /

    int fib[N];

      
    // Сохраняет значения в fib и возвращает индекс наибольшего
    // число Фибоначчи меньше n.

    int largestFiboLessOrEqual(int n)

    {

        fib[0] = 1;  // Fib [0] сохраняет второе число Фибоначчи

        fib[1] = 2;  // Fib [1] сохраняет 3-й номер Фибоначчи

      

        // Продолжаем генерировать оставшиеся числа, пока ранее

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

        int i;

        for (i=2; fib[i-1]<=n; i++)

            fib[i] = fib[i-1] + fib[i-2];

      

        // Возвращаем индекс наибольшего числа Фибоначчи

        // меньше или равно n. Обратите внимание, что выше

        // цикл остановился, когда fib [i-1] стал больше.

        return (i-2);

    }

      
    / * Возвращает указатель на строку символов, которая соответствует

       код для n * /

    char* fibonacciEncoding(int n)

    {

        int index = largestFiboLessOrEqual(n);

      

        // выделяем память для кодового слова

        char *codeword = (char*)malloc(sizeof(char)*(index+3));

      

        // индекс наибольшего Фибоначчи f <= n

        int i = index;

      

        while (n)

        {

            // Отметим использование Фибоначчи f (1 бит)

            codeword[i] = '1';

      

            // вычитаем f из n

            n = n - fib[i];

      

            // Перейти к Фибоначчи чуть меньше чем f

            i = i - 1;

      

            // Пометить все Фибоначчи> n как неиспользуемые (0 бит),

            // прогресс в обратном направлении

            while (i>=0 && fib[i]>n)

            {

                codeword[i] = '0';

                i = i - 1;

            }

        }

      

        // дополнительный бит 1

        codeword[index+1] = '1';

        codeword[index+2] = '\0';

      

        // возвращаем указатель на кодовое слово

        return codeword;

    }

      
    / * функция драйвера * /

    int main()

    {

        int n = 143;

        printf("Fibonacci code word for %d is %s\n", n, fibonacciEncoding(n));

        return 0;

    }

    python3

    # Python3 программа для кодирования Фибоначчи
    # положительного целого числа n

      
    # Ограничить на самый большой
    # Число Фибоначчи, которое будет использоваться

    N = 30

      
    # Массив для хранения чисел Фибоначчи.
    # fib [i] собирается хранить
    # (i + 2) -ое число Фибоначчи

    fib = [0 for i in range(N)]

      
    # Сохраняет значения в fib и возвращает индекс
    # наибольшее число Фибоначчи меньше n.

    def largestFiboLessOrEqual(n):

        fib[0] = 1 # Фиб [0] хранит 2-й номер Фибоначчи

        fib[1] = 2 # Фиб [1] хранит 3-й номер Фибоначчи

      

        # Продолжайте генерировать оставшиеся номера, пока

        # ранее сгенерированное число меньше

        i = 2

      

        while fib[i - 1] <= n:

            fib[i] = fib[i - 1] + fib[i - 2]

            i += 1

      

        # Возвращает индекс наибольшего числа Фибоначчи

        # меньше или равно n. Обратите внимание, что выше

        Цикл # остановился, когда fib [i-1] стал больше.

        return (i - 2)

      
    # Возвращает указатель на строку символов, которая
    # соответствует коду для n

    def fibonacciEncoding(n):

        index = largestFiboLessOrEqual(n)

      

        # выделить память для кодового слова

        codeword = ['a' for i in range(index + 2)]

      

        # Индекс наибольшего Фибоначчи f <= n

        i = index

      

        while (n):

              

            # Отметить использование Фибоначчи f (1 бит)

            codeword[i] = '1'

      

            # Вычтите f из n

            n = n - fib[i]

      

            # Перейти к Фибоначчи чуть меньше, чем F

            i = i - 1

      

            # Отметить все числа Фибоначчи> n как неиспользуемые (0 бит),

            # прогресс в обратном направлении

            while (i >= 0 and fib[i] > n):

                codeword[i] = '0'

                i = i - 1

      

        # дополнительный бит 1

        codeword[index + 1] = '1'

      

        # вернуть указатель на кодовое слово

        return "".join(codeword)

      
    Код водителя

    n = 143

    print("Fibonacci code word for", n,

             "is", fibonacciEncoding(n))

               
    # Этот код предоставлен Мохитом Кумаром


    Выход:

Fibonacci code word for 143 is 01010101011

иллюстрация

Область применения:
Обработка и сжатие данных — представление данных (которые могут быть текстом, изображением, видео…) таким образом, чтобы пространство, необходимое для хранения или передачи данных, было меньше размера входных данных. Статистические методы используют коды переменной длины, причем более короткие коды назначаются символам или группе символов, которые имеют более высокую вероятность появления. Если коды должны использоваться по шумному каналу связи, их устойчивость к вставке битов, удалению и к переворотам битов имеет большое значение.
Подробнее о приложении читайте здесь .

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

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

Кодирование Фибоначчи

0.00 (0%) 0 votes