Преобразование числа из представления Цекендорфа в десятичное

18

О представительствах Цекендорфа / Базисные числа Фибоначчи

Это система счисления, которая использует числа Фибоначчи в качестве своей базы. Числа состоят из 0 и 1, и каждый 1 означает, что число содержит соответствующее число Фибоначчи, а 0 означает, что это не так.

Например, давайте преобразуем все натуральные числа <= 10 в основную Фибоначчи.

  • 1 станет 1, потому что это сумма 1, которая является числом Фибоначчи,

  • 2 станет 10, потому что это сумма 2, которая является числом Фибоначчи, и ей не нужно 1, потому что мы уже достигли желаемой суммы.

  • 3 станет 100, потому что это сумма 3, которая является числом Фибоначчи, и ей не нужно 2 или 1, потому что мы уже достигли желаемой суммы.

  • 4 станет 101, потому что это сумма [3,1], оба из которых являются числами Фибоначчи.
  • 5 станет 1000, потому что это сумма 5, которая является числом Фибоначчи, и нам не нужны никакие другие числа.
  • 6 станет 1001, потому что это сумма чисел Фибоначчи 5 и 1.
  • 7 станет 1010, потому что это сумма чисел Фибоначчи 5 и 2.
  • 8 станет 10000, потому что это число Фибоначчи.
  • 9 станет 10001, потому что это сумма чисел Фибоначчи 8 и 1.
  • 10 станет 10010, потому что это сумма чисел Фибоначчи 8 и 2.

Давайте преобразуем случайное число Базового числа Фибоначчи, 10101001010, в десятичное: сначала запишем соответствующие числа Фибоначчи. Затем мы вычисляем сумму чисел до 1.

 1   0   1   0   1   0   0   1   0   1   0
 144 89  55  34  21  13  8   5   3   2   1  -> 144+55+21+5+2 = 227.

Узнайте больше о базовых числах Фибоначчи: ссылка , он также имеет инструмент, который преобразует обычные целые числа в базовые числа Фибоначчи. Вы можете поэкспериментировать с этим.

Теперь вопрос:

Ваша задача - взять число в представлении Zeckendorf и вывести его десятичное значение.

Ввод - это строка, которая содержит только 0 и 1 (хотя вы можете принимать входные данные любым удобным для вас способом).

Выведите одно число в десятичном виде.

Тестовые случаи: (в формате input-> output)

 1001 -> 6
 100101000 -> 73
 1000000000 -> 89
 1001000000100100010 -> 8432
 1010000010001000100001010000 -> 723452

Это код-гольф, поэтому выигрывает самый короткий ответ в байтах.

Примечание. Входные данные не будут содержать начальных 0 или последовательных 1.

Печенье мельницы
источник
Можем ли мы принять входные данные в виде списка битов?
Wheat Wizard
Мол, взять входной кодированный ascii, а затем преобразовать его в двоичный или что-то в этом роде?
Печенье мельницы
4
Можем ли мы принять ввод в LSB-первом порядке ?
Мего
1
Подмножество codegolf.stackexchange.com/questions/54287/… , обратное к codegolf.stackexchange.com/questions/2677/… .
user202729
1
@Mego Да, вы можете
Печенье Ветряная мельница

Ответы:

19

Такси , 1987 г. 1927 байт

-60 байтов из-за осознания того, что разрывы строк являются необязательными.

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to Chop Suey.Go to Chop Suey:n 1 r 1 l 4 r 1 l.[B]Switch to plan C if no one is waiting.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 3 l.Pickup a passenger going to Narrow Path Park.Pickup a passenger going to Sunny Skies Park.Go to Zoom Zoom:n.Go to Sunny Skies Park:w 2 l.Go to Narrow Path Park:n 1 r 1 r 1 l 1 r.Go to Chop Suey:e 1 r 1 l 1 r.Switch to plan B.[C]1 is waiting at Starchild Numerology.1 is waiting at Starchild Numerology.Go to Starchild Numerology:n 1 l 3 l 3 l 2 r.Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Go to Cyclone:w 1 r 4 l.[D]Pickup a passenger going to Addition Alley.Pickup a passenger going to Cyclone.Go to Addition Alley:n 2 r 1 r.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Multiplication Station.Go to Zoom Zoom:n.Go to Narrow Path Park:w 1 l 1 l 1 r.Switch to plan E if no one is waiting.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:e 1 r.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:n 1 r 2 l.Pickup a passenger going to Joyless Park.Go to Joyless Park:n 2 l 1 r 1 r.Go to Addition Alley:w 1 r 2 l 1 l.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l.Pickup a passenger going to Addition Alley.Switch to plan D.[E]Go to Addition Alley:w 1 l 1 r 1 l.Pickup a passenger going to Riverview Bridge.Go to Riverview Bridge:n 1 r.Go to Joyless Park:e 1 r 2 l.Pickup a passenger going to Addition Alley.[F]Switch to plan G if no one is waiting.Pickup a passenger going to Addition Alley.Go to Fueler Up:w 1 l.Go to Addition Alley:n 3 l 1 l.Pickup a passenger going to Addition Alley.Go to Joyless Park:n 1 r 1 r 2 l.Switch to plan F.[G]Go to Addition Alley:w 1 r 2 l 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:n 1 r 1 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.

Попробуйте онлайн!

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

JosiahRyanW
источник
Joyless Parkкажется хорошим местом для посещения
aloisdg говорит восстановить Monica
Ну, это меньше символов, чем Sunny Skies Park.
JosiahRyanW
11

Perl 6 , 28 23 байта

{[+] (1,2,*+*...*)Z*$_}

Попробуйте онлайн!

Анонимный кодовый блок, который принимает список 1s и 0s в порядке LSB и возвращает число.

Объяснение:

{                     }   # Anonymous codeblock
 [+]                      # The sum of
     (1,2,*+*...*)        # The infinite Fibonacci sequence starting from 1,2
                  Z*      # Zip multiplied by
                    $_    # The input list in LSB form
Джо Кинг
источник
7

Желе , 5 байт

T‘ÆḞS

Монадическая ссылка, принимающая список в форме с прямым порядком байтов (т.е. от LSB слева до MSB справа).

Попробуйте онлайн!

Джонатан Аллан
источник
Ницца, я был альтернативный 6-byter: J‘ÆḞḋṚ.
г-н Xcoder
4

Haskell , 38 байт

f=1:scanl(+)2f
sum.zipWith(*)f.reverse

Попробуйте онлайн!

Вводит в виде списка 1 и 0.

объяснение


f=1:scanl(+)2f

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

sum.zipWith(*)f.reverse

Принимает входной список, reverseумножает каждую запись на соответствующую запись f, затем sumвыводит результаты.

Haskell , 30 байт

f=1:scanl(+)2f
sum.zipWith(*)f

Попробуйте онлайн!

Если сначала мы введем вход с младшим битом, то он нам не нужен, reverseпоэтому мы можем сохранить 8 байтов.

Мастер пшеницы
источник
4

Python 2 , 43 байта

a=b=0
for x in input():b+=a+x;a=b-a
print b

Попробуйте онлайн!

Принимает ввод в виде списка. Обновление является более короткой версией a,b=b+x,a+b+x, которая похожа на обновление Фибоначчи, a,b=b,a+bесли вы игнорируете x.


Python 2 , 45 байт

f=lambda n,a=1,b=1:n and n%10*b+f(n/10,b,a+b)

Попробуйте онлайн!

Принимает ввод в виде десятичных чисел.

XNOR
источник
3

Pyth, 13 байт

Большая часть этого (8 байт) просто генерирует числа Фибоначчи.

s*V_m=+Z|~YZ1

Попробуйте это с этим набором тестов!

Объяснение:

s*V_m=+Z|~YZ1QQ     Autofill variables
    m=+Z|~YZ1Q      Generate the first length(input) Fibonacci numbers as follows:
       Z             Start with Z=0
         ~YZ         And Y=[] (update it to Y=Z, return old Y)
        |   1        if Y is [], then replace with 1
      +              Sum Z and Y
     =               Replace Z with sum
    m                Repeat process
             Q       once for each element of the input
   _                Reverse the order of the Fibonacci numbers
 *V                 Vectorize multiplication
s                   Sum
Стивен Х.
источник
3

J , 24 14 байт

#.~2+&%&1~#-#\

Попробуйте онлайн!

Гольф до 24-байтовой версии, которая использует смешанную базу для Фибоначчи.

Как это устроено

#.~2+&%&1~#-#\  Example input: y=1 0 0 1 0
          #-#\  Length minus 1-based indices; 4 3 2 1 0
   2     ~      Starting from 2, run the following (4,3,2,1,0) times:
    +&%&1         Given y, compute 1 + 1 / y
                The result is 13/8 8/5 5/3 3/2 2
#.~             Mixed base conversion of y into base above; 2+8=10

J , 21 байт

1#.|.*[:+/@(!~#-])\#\

Попробуйте онлайн!

Уточненная версия 25-байтового решения Галена Иванова .

Используется диагональная сумма треугольника Паскаля, которая эквивалентна сумме биномиальных коэффициентов:

FNзнак равноΣязнак равно0NN-яСя

Как это устроено

1#.|.*[:+/@(!~#-])\#\
                       Example input: 1 0 0 1 0
                   #\  Generate 1-based index; 1 2 3 4 5
      [:          \    For each prefix of above... (ex. 1 2 3)
              #-]        Subtract each element from the length (ex. 2 1 0)
           (!~   )       Compute binomial coefficient (ex. 3C0 + 2C1 + 1C2)
        +/@              Sum
                       The result is Fibonacci numbers; 1 2 3 5 8
   |.*                 Multiply with mirrored self; 0 2 0 0 8
1#.                    Sum; 10

J , 24 байта

3 :'y#.~|.(1+%)^:(<#y)2'

Попробуйте онлайн!

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

Как это устроено

y#.~|.(1+%)^:(<#y)2  Explicit verb, input: y = Fibonacci digit array, n = length of y
      (1+%)          x -> 1 + 1/x
           ^:(<#y)2  Apply the above 0..n-1 times to 2
                     The result looks like 2/1, 3/2, 5/3, 8/5, 13/8, ...
    |.               Reverse
                     Now, if it is fed into #. on the left, the digit values become
                     ...(8/5 * 5/3 * 3/2 * 2/1), (5/3 * 3/2 * 2/1), (3/2 * 2/1), 2/1, 1
                     which is ... 8 5 3 2 1 (Yes, it's Fibonacci.)
y#.~                 Convert y to a number using Fibonacci base

альтернативы

J , 27 байт

}.@(+#{.3#{.)^:(<:@#)@(,&0)

Попробуйте онлайн!

Идея:

 1  0  0  1  0  1
-1 +1 +1
------------------
    1  1  1  0  1
   -1 +1 +1
------------------
       2  2  0  1
      -2 +2 +2
------------------
          4  2  1
         -4 +4 +4
------------------
             6  5
            -6 +6 +6 <- Add an imaginary digit that has value 1
---------------------
               11  6
              -11+11
---------------------
                  17 <- the answer

J , 30 байт

0.5<.@+(%:5)%~(-:>:%:5)#.,&0 0

Попробуйте онлайн!

На это ушло больше всего усилий. Использует выражение закрытой формы с трюком с округлением. В выражении 0-е и 1-е значения равны 0 и 1 соответственно, поэтому фактическая разрядность должна начинаться с 2.

0.5<.@+(%:5)%~(-:>:%:5)#.,&0 0  Tacit verb.
                         ,&0 0  Add two zeroes at the end
              (-:>:%:5)#.       Convert to a number using base phi (golden ratio)
       (%:5)%~                  Divide by sqrt(5)
0.5<.@+                         Round to nearest integer

Хотя ошибка ( ((1-sqrt(5))/2)^nусловия) может накапливаться, она никогда не превышает 0,5, поэтому трюк с округлением работает до бесконечности. Математически:

Максимум(|еррор|)знак равно15Σ1(1-52)2Nзнак равно15Σ0(1-52)Nзнак равно5-125<12

фонтанчик для питья
источник
Отличное решение! Я рад видеть явный глагол, бьющий молчаливое решение.
Гален Иванов
Я пытаюсь найти более короткое молчаливое решение, но безуспешно. 25 байт на данный момент . Я использую треугольник Паскаля.
Гален Иванов
@GalenIvanov Пересматривая вызов через год, я получил новое, супер короткое молчаливое решение :)
Bubbler
Замечательно! Я посмотрю на это более подробно в ближайшее время.
Гален Иванов
2

MathGolf , 8 6 байт

{î)f*+

Попробуйте онлайн!

объяснение

{        Start block (foreach in this case)
 î)      Push loop index (1-based) and increment by 1
   f     Get fibonacci number of that index
    *    Multiply with the array value (0 or 1)
     +   Add top two elements of stack. This implicitly pops the loop index the first iteration, which makes the addition become 0+a, where a is the top of the stack.

Благодаря JoKing сохранен 1 байт, а при заказе LSB - еще один байт.

maxb
источник
LSB заказ действительно разрешен. также -1 байт
Джо Кинг,
@JoKing Конечно, я даже реализовал неявное дополнение только на прошлой неделе ... Приятное прикосновение, теперь MathGolf находится на первом месте!
Максб
2

05AB1E , 11 9 8 байт

vyiNÌÅfO

Попробуйте онлайн!

Объяснение:

v             : For each character in input string (implicit) in LSB order
  yi          : If the current character is truthy (1)
    NÌ        : Add 2 to the current index
       ÅfO    : Add the fibonacci of this number to the stack
  • -2 байта : Спасибо @KevinCruijssen за указание на небольшие способы сократить этот код!
  • -1 байт : Спасибо @JonathanAllan за указание порядка LSB для ввода!
Арнав Борбора
источник
1
Вы можете удалить Θ. 1правда в 05AB1E уже. :) Также 2+можно Ì.
Кевин Круйссен
1
Мы можем принять входные данные в форме Little-endian (т.е. в обратном порядке), что должно сохранить байт (или два?).
Джонатан Аллан
1

C (gcc) , 63 байта

Принимает входные данные в виде массива 1's' и 0's' вместе с длиной массива. Это решение представляет собой довольно прямую обратную петлю.

f(_,l,a,b,t)int*_;{a=b=1;for(t=0;l--;b=(a+=b)-b)t+=a*_[l];_=t;}

Попробуйте онлайн!


источник
0

Сетчатка 0.8.2 , 23 байта

0?
;
+`1;(1*);
;1$1;1
1

Попробуйте онлайн! Ссылка включает в себя более быстрые тестовые случаи. Объяснение:

0?
;

Вставьте разделители везде и удалите все нули. Например, 1001становится ;1;;;1;.

+`1;(1*);
;1$1;1

Повторно заменяйте каждое 1на a 1в каждом из следующих двух мест, так как сумма их значений равна значению оригинала 1. 1Поэтому они мигрируют и накапливаются, пока не достигнут последних двух мест, которые (благодаря недавно добавленному разделителю) теперь оба имеют значение1 .

1

Посчитай 1с.

Нил
источник
0

На самом деле 8 байтов

;r⌐@░♂FΣ

Попробуйте онлайн!

Ввод принимается как список битов в порядке младшего бита.

Объяснение:

;r⌐@░♂FΣ
;r        range(0, len(input))
  ⌐       add 2 to every element in range (range(2, len(input)+2))
   @░     filter: take values in range that correspond to 1s in input
     ♂F   Fibonacci number at index of each element in list (Actually uses the F(0)=F(1)=1 definition, which is why we needed to add 2 earlier)
       Σ  sum
Mego
источник
0

Powershell, 68 байт

param($s)$b=1
$s[$s.Length..0]|%{$a,$b=$b,($a+$b)
$x+=($_-48)*$b}
$x

Тестовый скрипт:

$f = {
param($s)$b=1
$s[$s.Length..0]|%{$a,$b=$b,($a+$b)
$x+=($_-48)*$b}
$x
}

@(
    ,("1001", 6)
    ,("100101000", 73)
    ,("1000000000", 89)
    ,("1001000000100100010", 8432)
    ,("1010000010001000100001010000", 723452)
) | % {
    $s,$e = $_
    $r = &$f $s
    "$($r-eq$e): $r"
}

Выход:

True: 6
True: 73
True: 89
True: 8432
True: 723452
Mazzy
источник
0

Java (OpenJDK 8) , 65 байт

Довольно мал для ответа на Java, я доволен этим. Принимает ввод в виде LSB-первого упорядоченного массива целых.

d->{int s=0,f=1,h=1;for(int i:d){s+=i>0?f:0;f=h+(h=f);}return s;}

Попробуйте онлайн!

Ungolfed

d->{                        // Lambda function that takes array of ints
    int s=0,f=1,h=1;        // Initialise sum and fibonacci vars
    for(int i:d){           // Loop through each input integer
        s+=i>0?f:0;         // If it's 1 add current fibonacci number to sum
        f=h+(h=f);          // Increase fibonacci number 
    }return s;              // return sum
}
Люк Стивенс
источник
0

Z80Golf , 34 байта

00000000: dde1 f1b7 2819 fe30 2812 4504 aff5 3cf5  ....(..0(.E...<.
00000010: d1f1 82d5 f510 f9c1 f17c 8067 2c18 e3dd  .........|.g,...
00000020: e5c9                                     ..

Пример с вводом 1001 - Попробуйте онлайн!

Пример с вводом 100101000-Попробуйте онлайн!

Монтаж:

zeck:		; input=push on stack in MSB order (eg top is LSB) output=reg h
pop ix		; save return addr in ix
f:
pop af		; get next digit
or a
jr z, return	; if current digit==0, return
cp 0x30
jr z, skip	; if current digit=='0' (e.g. not '1'), skip loop
ld b, l		; find fib of counter
fib:
	inc b	; 1-indexing for func to work
	xor a	; set a to 0 (1st fibo num)
	push af
	inc a	; set a to 1 (2nd fibo num)
	push af
	fib_loop:
		pop de
		pop af
		add d
		push de
		push af
		djnz fib_loop
pop bc		; get the fibo num just calculated
pop af		; pop just to reset stack frame
ld a, h
add b		; add current fibo number to sum
ld h, a
skip:
inc l		; increment counter reg
jr f		; repeat loop
return:
push ix		; push the return addr to ret to it
ret
Logern
источник