+7(904)3314610

Система счисления Фибоначчи, реализация на C++

www.moveinfo.ru

баннер статьи

Дата:

Недалеко от побережья Лигурийского моря, в одном из древних городе средневековой Европпы, что раскинулся на берегах реки Арно, жил выдающийся математик Леонардо Пизанский (около 1170 года, Пиза — около 1250 года, там же), более известный под прозвищем Фибоначчи. Леонардо Пизанский никогда не называл себя Фибоначчи; этот псевдоним был дан ему позднее, предположительно Гийомом Либри (Guglielmo Libri Carucci dalla Sommaja) в 1838 году. Слово Fibonacci — сокращение от двух слов «filius Bonacci», появившихся на обложке «Книги Абака»; они могли означать либо «сын Боначчо», либо, если интерпретировать слово Боначчи как фамилию, «сын Боначчи». Согласно третьей версии, само слово Боначчи нужно понимать как прозвище, означавшее «удачливый». Сам он обычно подписывался Боначчи; иногда он использовал также имя Леонардо Биголло — слово bigollo на тосканском наречии значило «странник», а также «бродяга» [1].

Пиза, в то время, была важным торговым городом и имела сообщение со многими средиземноморскими портами. Отец Леонардо, Гульельмо Боначи, был своего рода таможенником в современной алжирском городе Bejaia, ранее известном как Bugia, от куда во Францию возили восковые свечи. Поэтому восковые свечи на французском языке до сих пор называют «bougies». Так Леонардо вырос в Северной Африке и находился под влиянием мавританской культуры, там же получал образование у арабских учителей, позднее Леонардо путешествовал по берегам Средиземного моря и дальше, он посетил Египет, Сирию, Византию, Сицилию. Фибоначчи встречался со многими купцами и узнал о различных системах счисления и способах выполнения арифметических операций. Вскоре Леонардо понял, многие преимущества «индо-арабской» позиционной системы счисления по сравнению с римской. Труд Леонардо Фибоначчи «Книга абака» способствовал распространению в Европе позиционной системы счисления, более удобной для вычислений, чем римская нотация; в книге были подробно исследованы возможности применения индийских цифр, ранее остававшиеся неясными, и даны примеры решения практических задач, в частности, связанных с торговым делом.

Ряд Фибоначчи образован последовательностью, в которой каждый последующий член равен сумме двух предыдущих, т.е. F(n) = F(n-1) + F(n-2), для каждого целого n > 3, причём F(0) = 0, F(1) = 1, F(2) = 1. Первые члены ряда определяются как: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . Интересным фактом является, что с помощью последовательности образованной рядом Фибоначчи, возможно, записать любое число. Следует отметить, что последовательность, названная в честь Фибоначчи, была известна человечеству за долго до рождения Фибоначчи. Так, например, в Индии данную последовательность использовали в поэзии. Применялась рассматриваемая последовательность в музыке как способ соотношения различных частот, в архитектуре и других видах искусства и инженерной мысли. Последовательность Фибоначчи связана с понятием «золотого сечения» – соотношение двух величин, равное соотношению их суммы к большей из данных величин. Отношение большей части к меньшей в золотом сечении выражается квадратичной иррациональностью φ = (1 + 51/2)/2, где 51/2 – квадратный корень из пяти. Числа последовательности Фибоначчи в нерекурентном виде возможно выразить с помощью выражения: F(n) = [((1 + 51/2)/2) – ((1 – 51/2)/2)]/ (51/2) = (φn – (–φ)– n) / (φ – (–φ)– 1).

Система счисления Фибоначчи, относится к смешанным системам счисления и построена на основе соответствующего ряда, причём отсчёт начинается с третьего элемента (первые два 0 и 1 исключаются), т.е. в данном случае ряд Фибоначчи имеет вид: 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . Единица в соответствующем разряде, в записи числа в системе счисления Фибоначчи, означает, что член ряда Фибоначчи (1, 2, 3, 5, 8, 13, 21, 34, 55, . . .) входит в сумму образующую заданное число ∑[e(n)F(n)]. Например: 101001Ф = 1•13 + 0•8 + 1•5 + 0•3 + 0•2 + 1•1 = 1910, в записи 101001Ф – младший разряд справа, а индекс Ф означает систему счисления Фибоначчи. Для всех чисел (кроме 0, 1 и 2), возможно, найти несколько записей при помощи ряда Фибоначчи. Так, например, десятичное число 2110 = 1000000Ф = 0110000 = 0101100 = 0101011 (младший разряд справа), но правильной будет запись только 1000000Ф, т.к. в системе счисления Фибоначчи, для исключения множества форм для записи одного числа, запрещены варианты записи чисел в которых встречаются две и более подряд идущие единицы. Таким образом, запись вида 10011 необходимо преобразовать в 10100Ф, в соответствии с выражением F(n) = F(n-1) + F(n-2).

Таблица. Числа в различных системах счисления.
Системы счисления
Десятичная, X10 Двоичная, X2 Восьмеричная, X8 Шестнадцатеричная, X16 Фибоначчи (XФ)
0010 000002 008 0016 00000Ф
0110 000012 018 0116 00001Ф
0210 000102 028 0216 00010Ф
0310 000112 038 0316 00100Ф
0410 001002 048 0416 00101Ф
0510 001012 058 0516 01000Ф
0610 001102 068 0616 01001Ф
0710 001112 078 0716 01010 Ф
0810 010002 108 0816 10000Ф
0910 010012 118 0916 10001Ф
1010 010102 128 0A16 10010Ф
1110 010112 138 0B16 10100Ф
1210 011002 148 0C16 10101Ф
1310 011012 158 0D16 100000Ф
1410 011102 168 0E16 100001Ф
1510 011112 178 0F16 100010Ф
1610 100002 208 1016 100100Ф

Свойство запрещения подряд идущих единиц в записи чисел в системе счисления Фибоначчи, позволяет реализовывать на базе системы счисления Фибоначчи различные коды, предназначенные, например, для сжатия битовых серий. Префикс или суффикс из подряд идущих двух единиц (11) может означать конец одного кодового слова и начало нового. В зависимости от выбора направления возрастания в записи числа в системе счисления Фибоначчи, с права на лево (например: 1001010Ф) или с лева направо (0101001Ф), код будет префиксным (например: 11001010) или суффиксным (например: 01010011). В системе счисления Фибоначчи старший бит всегда будет иметь значение единицы (1), т.к. незначащие нули можно отбросить.

Ниже приведён листинг класса выполняющего взаимные преобразования из десятичной в систему счисления Фибоначчи и обратно, чисел в диапазоне 0 . . . 27 777 890 035 28710. Дополнительно класс содержит метод преобразования чисел Фибоначчи в строку.

// файл "mi_fib.h"
/*
Класс взаимного преобразования чисел 
из десятичной системы счисления 
в систему счисления Фибоначчи
*/
// -----------------------------------------------------------------------------
#ifndef mi_fibH
#define mi_fibH
// -----------------------------------------------------------------------------
#include <string>
// пространство имён
using namespace std;
// определение типа uint64 беззнаковый целый 64 бита
// typedef uint_fast64_t uint64;          // C++11 or
// typedef uint64_t uint64;               // C++11 or
// typedef unsigned long long int uint64; // C++   or
// для проверки sizeof(uint64) == 8
typedef unsigned __int64 uint64;
// класс реализации взаимных преобразований систем счисления
// десятичная <=> фибоначчи
class mi_fib {

public:
  //   конструктор
  mi_fib() {
    fib = new uint64[65];
    fib[0] = 1;
    fib[1] = 2;
    for (int i = 2; i < 65; i++) {
      fib[i] = fib[i - 1] + fib[i - 2];
    }
  } ;
  // деструктор
  ~mi_fib() {
    if (fib) {
      delete[]fib;
      fib = 0;
    }
  } ;
  // ---------------------------------------------------------------------------
  // возвращает код числа в системе исчисления Фибоначчи:
  // Fibonacci : (0 1) 1 2 3 5 8 13 21 ...
  // например: (dec)50 = bin(dec)110010 = (fib)164 = bin(fib)10100100
  uint64 IntToFib(uint64 vf) {
    // если больше максимально допустимого генерируем исключительную ситуацию
    if (vf > 27777890035287)
      throw;
    // переменная результата
    uint64 res = 0;
    // если ноль сразу возвращаем результат
    if (vf == 0)
      return (res);
    // формируем число в системе исчисления Фибоначчи
    uint64 fixp = 0x01;
    for (int i = 63; i >= 0; i--) {
      if (vf == fib[i]) {
        res |= (fixp << i);
        break;
      }
      if (vf > fib[i]) {
        vf -= fib[i];
        res |= (fixp << i);
      }
    }
    // выходим
    return (res);
  }
  // ---------------------------------------------------------------------------
  // преоразование из сист. счисления фибоначчи в десятичную
  // возвращает значение uint64 числа в десятичной системе счисления
  uint64 FibToInt(uint64 vi) {
    // переменная результата
    uint64 res = 0;
    uint64 fixp = 0x01;
    for (int i = 0; i <= 63; i++) {
      res += fib[i] * (fixp & (vi >> i));
    }
    return (res);
  }
  // ---------------------------------------------------------------------------
  // функция преобразования числа
  // в системе счисления Фибоначчи в строку (двоичный формат)
  string IntToStrBin(uint64 a) {
    string bstr = "";
    do {
      (a % 2) ? bstr.insert(0, "1") : bstr.insert(0, "0");
      a /= 2;
    } while (a > 0);
    return bstr;
  }
  // ---------------------------------------------------------------------------
private:
  uint64* fib;
} ;
#endif

Ниже приведён пример эксплуатации класса mi_fib.

// пример эксплуатации класса mi_fib
#include <string>
#include <iostream>
#include <stdlib.h>
#include "mi_fib.h"
// ---------------------------------------------------------------------------

#pragma argsused
// пространство имён
using namespace std;

int main() {
  uint64 numb;
  mi_fib fibconv;

  cout << "Введите число ограничивающее вывод таблицы соотвествия:" << endl;
  cin >> numb;

  cout << "Dec\tnumb\tFib" << endl;
  int j = 1000;
  while( j >= 0 ) {
   cout << numb << "\t" <<
    fibconv.IntToFib(numb) << "\t" <<
    fibconv.IntToStrBin(fibconv.IntToFib(numb)) << endl;
    if( !numb ) break;
    numb--;
    j--;
  }

  system("pause"); // пауза перед выходом из консоли (ОС Windows <stdlib.h>)
  return 0;
}
// ---------------------------------------------------------------------------

Литература

  1. Who was Fibonacci?
  2. Воробьёв Н. Н. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).
  3. Кнут Д. Искусство программирования, том 1. Основные алгоритмы.— 3-е изд. — М.: «Вильямс», 2006. — С. 720.