Рекурсивный алгоритм представления Цекендорфа

    Спасибо добрым участникам Хабра, за то, что пригласили писать посты и получать на них фидбек.

    Сегодня я бы хотел осветить тему представления чисел с помощью ряда Фибоначчи и разумеется написать простенькое REST API c использованием Mongo DB алгоритм с помощью языка Ruby, который бы по заданному числу N возвращал его представление.

    Часть 1 : представление Цекендорфа

    Как гласит статья из Википедии :

    Теорема Цекендорфа гласит, что всякое натуральное число можно единственным образом представить в виде суммы одного или нескольких различных чисел Фибоначчи так, чтобы в этом представлении не оказалось двух соседних чисел из последовательности Фибоначчи.


    100 = 89 + 8 + 3.

    Я думаю, понимая что такое числа Фибоначчи, не составит труда понять в чём заключена данная теорема.

    Цели которые должны быть достигнуты :

    • скорость работы

    • максимальная простота кода

    Как язык программирования я буду использовать Ruby, почему? Потому что Ruby - это

    Лучший друг программиста.

    Сначала теоретически нужно найти закономерность по которой и будет написан алгоритм.

    Выписав все числа Фибоначчи которые меньше заданного, на листочек (школа), я обнаружил, что выгодней всего для такой суммы брать самое последнее число, но при условии что оно меньше чем наше искомое число.

    Пример:
    N = 51
    F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.

    Берём число 34, соседнее с ним число (21) можно сразу пропустить, ибо их сумма будет заведомо больше нашего входного числа N, ибо числа Фибоначчи мы ищем пока они не превысят входное, ведь зачем нам числа больше входного.

    Но каким образом лучше всего посчитать сумму, простым перебором мы точно не добьемся первого условия : скорость работы .
    Сложным алгоритмом - откажемся от второго : максимальная простота кода.

    И тогда появилась идея: а что если отнимать от N последнее число в ряду Фибоначчи, и искать новый ряд где эта разница будет лимитом, и рекурсивно продолжать это действия пока разница не станет <= 0.

    Пример
    :
    N = 51
    F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
    ans = [34]

    N = 51 - 34 = 17
    F = 1 , 1 , 2 , 3 , 5 , 8 , 13.
    ans = [34 , 13]

    N = 17 - 13 = 4
    F = 1 , 1 , 2 , 3.
    ans = [34 , 13 , 3]

    N = 4 - 3 = 1
    F = 1
    ans = [34 , 13 , 3, 1]

    Сразу попробую записать в код :

    def le_fib(limit, fib)
      theoretical = fib[fib.count - 1] + fib[fib.count - 2]
      return fib.last if theoretical > limit
    
      fib << theoretical
      le_fib(limit, fib)
    end
    
    def main(target,result)
      temporary = le_fib(target, [1,1])
      result << temporary
      return result if target - temporary <= 0
    
      main(target - temporary, result)
    end
    pp main(gets.to_i,[])
    

    Функция le_fib - рекурсивно ищет ряд Фибоначчи с пределом, на то, что бы следующее число не было больше чем входное число target. Здесь важно, что нас не интересует ряд Фибоначчи целиком, нам важно лишь его окончание.

    Функция main - рекурсивно ищет масcив, числа которого есть числами Фибоначчи, и которые бы в сумме давали нам входное число.

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

    Пример работы для 20 случайных чисел до 1000

    Оценка времени работы в зависимости от величины ряда (входного числа)

    Как видим время работы даже на числах до 10^9 очень позитивное.

    А общий объем кода в 17 строк говорит о том что обе задачи выполнены успешно.

    Статья про интерес, всегда в рукаве нужно иметь пару задач с числами Фибоначчи, иначе какой из тебя программист.

    Комментарии 20

      +2
      Было бы полезно узнать, какие практические применения такого представления для числа?
      Например бинарное представление — это булева логика, и вычисления в ЭВМ.А тут как?
        +1
        Вообще-то тут тоже бинарное представление: 100(в десятичной) записывается как 1000010100, подразумеваем (89)0000(8)0(3)00 — тут вместо еденичек в скобках веса соответствующих разрядов. Отмечу, что ряд фибоначчи тут начинается с 1,2,3,5… — меньшие веса здесь избыточны.
        Когда-то такое представление рассматривали как код, выявляющий ошибки — в представлении числа не может быть двух еденичек подряд. А потом придумали код Хэмминга, код Соломона-Рида, и эту чепуху выбросили.

        ps Если уж автор добрался до статьи в вики, он бы мог её прочитать.
        Для любого заданного натурального числа его цекендорфово представление находится при помощи жадного алгоритма

        Какой перебор, какая рекурсия, какой фибонаЧе?..
          0

          Не всё в этой жизни автор знает…
          Спасибо за отличное разъяснение, самому было интересно!
          Ну рекурсия же выглядит занимательно, разве нет ?)

            0
            Вот в этой статье есть парочка алгоритмов
            C. Heuberger, Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms
            wwwu.aau.at/cheuberg/publications/pdf/minredfibo.pdf
              +2
              Сбавь темп публикаций, нет смысла тащить сюда всякое дважды-два-четыре.
              Рекурсия выглядит уныло, если достаточно простой итерации.
              n, F = 100, [1, 2]
              while F[-1] < n do
                F << F[-2] + F[-1]
              end
              F.reverse.each do |f|
                if f <= n
                  n -= f
                  print f
                  print '+' if n > 0
                end
              end
              
              Извиняюсь за стиль, ruby не мой профиль.
                0

                Ты прав

                  0
                  Дружище, тебе очень нравится рекурсия. Мне тоже. Смотри.
                  Самый-самый классический кейс про рекурсию — DFS, обход дерева в глубину. Фишка в том, что приходтся возвращаться к развилкам, к тем данным, какие ты надыбал, впервые подойдя к развилке, и уходить из этой развилки с этими стартовыми данными в другую ветвь.
                  Это всегда хорошо работает, но не всегда нужно. Представь, что твоё дерево — бамбук. Развилок нет вообще, прёшь вверх до упора, упёрся — спрыгнул. Нет смысла запоминать ситуации на развилках, ведь развилок нет. Вот это-то и значит, что рекурсия тебе избыточна, достаточно итерации.
                  В данном случае отсутствие развилок — это природа жадного алгоритма. Ты откусываешь от n максимально возможное число фибоначчи, на другие не смотришь.
                  С Новым годом.
                    0
                    C Новым Годом и тебе друг
            0
            0

            А тут сложение, где перенос, хоть и происходит сразу в две стороны, но дальше не распространяется.

              0

              В вашем же рекурсивном алгоритме вся рекурсия — хвостовая. Соответственно, она эквивалентна циклам. Ваше решение, фактически — это 2 вложенных цикла. le_fib строит числа фиббоначи до максимального, не больше заданного (одним циклом, с меньих к большим). Main откусывает максимальное число фиббоначи в цикле от заданного.


              Если переписать с циклами, то станет понятно, что ваше решение квадратичное и делает много лишнего! Вместо того, чтобы строить числа фиббоначи с нуля на каждой итерации main, их можно построить только один раз, и дальше пройтись по этому массиву один раз с конца, вычитая текущее число, если оно помещается в target.


              Будет даже короче вашего кода и быстрее в 20 раз для 10^9. Код уже выше привел longclaps.

                0
                Забавно, насколько программисты любят оверинженерить.
                  0

                  Это вы про меня или про себя?

                    0
                    Про программистов в целом :-)
                0
                вот перевел алгоритм на Python:
                def le_fib(limit, fib):
                theoretical = fib[-1] + fib[-2]
                if theoretical > limit:
                return fib[-1]
                fib.append(theoretical)
                return le_fib(limit, fib)

                def main(target,result):
                temporary = le_fib(target, [1,1])
                result.append(temporary)
                if target — temporary <= 0:
                return result
                return main(target — temporary, result)

                i=int(input('Enter i: '))
                print(main(i,[]))
                  0

                  Тег код же есть на хабре! Там даже можно язык выбрать — подсветка будет.

                  0
                  это мой 1й пост на хабре — не подумал про теги…
                  def le_fib(limit, fib):
                  	theoretical = fib[-1] + fib[-2]
                  	if theoretical > limit:
                  		return fib[-1]
                  	fib.append(theoretical)
                  	return le_fib(limit, fib)
                  
                  def main(target,result):
                  	temporary = le_fib(target, [1,1])
                  	result.append(temporary)
                  	if target - temporary <= 0:
                  		return result 
                  	return main(target - temporary, result)
                  
                  i=int(input('Enter i: '))
                  print(main(i,[]))
                  
                    0
                    Отличная работа над ошибками!
                    Это не пост, а коммент — но ты всё равно молодец!
                    Осталось подумать над чужими комментариями — и ты в клубе!
                      0
                      и первым же «постом» ты решил перевести мой тривиальный алгоритм на Python
                      хорош
                      0
                      просто изучаю Python и ищу, где можно лишний раз потренироваться :)

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое