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

Пусть F _n будет n-м числом Фибоначчи, где

F ₁ = 1,
F ₂ = 2 и
для всех k > 2 F _k = F _{k - 1} + F _{k - 2} .

Представление Цекендорфа Z ( n ) неотрицательного целого числа n представляет собой набор натуральных чисел, таких что

п = Σ _{я ∈ Z , ( п )} Р _я   и
∀ _{я ∈ Z , ( п )} я + 1 ∉ Z ( п ).

(в прозе: представление Цекендорфа числа n представляет собой набор натуральных чисел, таких, что числа Фибоначчи для этих индексов суммируют до n, и никакие два соседних целых числа не являются частью этого набора)

Примечательно, что представление Zeckendorf является уникальным. Вот несколько примеров для представлений Zeckendorf:

Z (0) = ∅ (пустое множество)
Z (1) = {1}
Z (2) = {2}
Z (3) = {3} ({1, 2} не является представлением Цекендорфа 3)
Z (10) = {5, 2}
Z (100) = {3, 5, 10}

В этой задаче представления Цекендорфа кодируются как наборы битов, где младший значащий бит представляет собой, если он 1является частью набора, и т. Д. Можно предположить, что представления Цекендорфа как входных, так и выходных данных укладываются в 31 бит.

Ваша задача - вычислить Z ( n + m ) с учетом Z ( n ) и Z ( m ). Решение с наименьшей длиной в октетах выигрывает.

Справочную реализацию, написанную на ANSI C, можно найти здесь . Он также может быть использован для генерации представлений Цекендорфа или вычисления числа из его представления Цекендорфа.

Вот несколько пар примеров ввода и вывода, где первые два столбца содержат входные данные, а третий столбец содержит выходные данные:

73865           9077257         9478805
139808          287648018       287965250
34              279004309       279004425
139940          68437025        69241105
272794768       1051152         273846948
16405           78284865        83888256
9576577         4718601         19013770
269128740       591914          270574722
8410276         2768969         11184785
16384           340             16724

K (нгн / к) , 45 43 42 41 байт

{2/<':(+/F@&+/'|2\x){y!x}\|F:64(+':1,)/0}

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

Алгоритм Бубблера

{ } функция с аргументом x

64( )/0 сделать 64 раза, используя 0 в качестве начального значения:

• 1, подготовить 1

• +': добавить каждый предыдущий (оставить первый элемент без изменений)

F:назначить Fдля "последовательности Фибоначчи"

| обеспечить регресс

(.. ){y!x}\.., начиная со значения слева, вычисляет кумулятивные остатки (слева направо) для списка справа. значение слева представляет собой простую сумму входных данных без представления Цекендорфа:

• 2\xдвоичное кодирование входов. это будет матрица размером 2 бит на 2

• | обеспечить регресс

• +/' суммировать каждый

• &где 1с? - список показателей. если есть любые 2, соответствующий индекс повторяется дважды.

• F@ индексация массива в F

• +/ сумма

<': меньше, чем каждый предыдущий (первым результатом всегда будет фальси)

2/ двоичное декодирование

CJam, 76 74 70 63 59 байт

2q~{32{2\#I&},}fI+32_,*{WUer$Kf-[UU]/[-2X]*2,/2a*Kf+}fKf#1b

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

идея

Мы начнем с определения небольшого варианта последовательности в вопросе:

G _-2 = 0
G _-1 = 1
G _k = G _k-1 + G _k-2 всякий раз, когда k является неотрицательным целым числом

Таким образом, бит 0 (младший бит) из входных битовых массивов или выход соответствует числу Фибоначчи G ₀ и, в общем, бит к к G _к .

Теперь мы заменим каждый установленный бит в Z (n) и Z (m) на индекс, который он кодирует.

Например, вход 532 ₁₀ = 1000010100 ₂ преобразуется в [2 4 9] .

Это дает два массива целых чисел, которые мы можем объединить в один.

Например, если n = m = 100 , результат будет A: = [2 4 9 2 4 9] .

Если мы заменим каждое k в A на G _k и добавим результаты, мы получим n + m = 200 , поэтому A - это способ разложения 200 на числа Фибоначчи, но, конечно, не тот, что из теоремы Цекендорфа.

Помня, что G _k + G _{k + 1} = G _{k + 2} и G _k + G _k = G _k + G _k-1 + G _k-2 = G _{k + 1} + G _k-2 , мы можем заменить последовательные и дублированные индексы другими (а именно ((k, k + 1) на k + 2 и (k, k) на (k + 1, k - 2) ), повторяя эти замены снова и снова, пока не будет достигнуто представление Цекендорфа. ¹

Особый случай должен быть взят для результирующих отрицательных индексов. Поскольку G _-2 = 0 , индекс -2 можно просто игнорировать. Кроме того, G _-1 = 0 = G ₀ , поэтому любой результирующий -1 должен быть заменен на 0 .

Для нашего примера A мы получаем следующие (отсортированные) представления, последним из которых является представление Цекендорфа.

[2 2 4 4 9 9] → [0 3 4 4 9 9] → [0 5 4 9 9] → [0 6 9 9] → [0 6 7 10] → [0 8 10]

Наконец, мы конвертируем обратно из массива целых в битовый массив.

Код

2             e# Push a 2 we'll need later.
q~            e# Read and evaluate the input.
{             e# For each integer I in the input:
  32{         e#   Filter [0 ... 31]; for each J:
    2\#       e#     Compute 2**J.
    I&        e#     Compute its logical AND with I.
  },          e#   Keep J if the result in truthy (non-zero).
}fI           e#
+             e# Concatenate the resulting arrays.
32_,*         e# Repeat [0 ... 31] 32 times.
{             e# For each K:
  WUer        e#   Replace -1's with 0's.
  $           e#   Sort.
  Kf-         e#   Subtract K from each element.
  [UU]/[-2X]* e#   Replace subarrays [0 0] with [-2 1].
  2,/2a*      e#   Replace subarrays [0 1] with [2].
  Kf+         e#   Add K to each element.
}fK           e#
f#            e# Replace each K with 2**K.
1b            e# Cast all to integer (discards 2**-2) and sum.

¹ _{Реализация пытается заменить 32 раза и не проверяет, было ли фактически достигнуто представление Цекендорфа. У меня нет формального доказательства того, что этого достаточно, но я проверил все возможные суммы 15-битных представлений (чьи представления сумм требуют до 17 бит), и для всех них было достаточно 6 повторений. В любом случае увеличение числа повторений до 99 возможно без увеличения числа байтов, но это снизит производительность.}

APL (Dyalog Extended) , 39 байт

⊥1↓⍧|/⌽(+/g[⍸⌽+/⊤⎕]),↑,\⌽g←(2+/,)⍣38⍨⍳2

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

Изменен в полную программу, принимающую один аргумент длины 2, а также изменил генератор Фибоначчи. Спасибо @ngn за множество идей.

Использует ⎕IO←0так, что ⍳2оценивает 0 1.

Генератор Фибоначчи (новый)

Обратите внимание, что последние два числа являются неточными, но это не меняет вывод программы.

(2+/,)⍣38⍨⍳2
→ 0 1 ((2+/,)⍣38) 0 1

Step 1
0 1 (2+/,) 0 1
→ 2+/ 0 1 0 1
→ (0+1) (1+0) (0+1) ⍝ 2+/ evaluates sums for moving window of length 2
→ 1 1 1

Step 2
0 1 (2+/,) 1 1 1
→ 2+/ 0 1 1 1 1
→ 1 2 2 2

Step 3
0 1 (2+/,) 1 2 2 2
→ 2+/ 0 1 1 2 2 2
→ 1 2 3 4 4

Цекендорф в равнине

⍸⌽+/⊤⎕
     ⎕  ⍝ Take input from stdin, must be an array of 2 numbers
    ⊤   ⍝ Convert each number to base 2; each number is mapped to a column
  +/    ⍝ Sum in row direction; add up the counts at each digit position
 ⌽      ⍝ Reverse
⍸       ⍝ Convert each number n at index i to n copies of i

APL (Dyalog Extended) , 47 байт

g←1↓(1,+\⍤,)⍣20⍨1
{⊥1↓⍧|/⌽⍵,↑,\⌽g}+⍥{+/g[⍸⌽⊤⍵]}

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

Изменена часть 1 предыдущего ответа для повторного использования чисел Фибоначчи. Кроме того, удалите дубликат 1, чтобы сохранить несколько байтов в других местах.

Часть 1 (новая)

{+/g[⍸⌽⊤⍵]}
       ⊤⍵    ⍝ Argument to binary digits
     ⍸⌽      ⍝ Reverse and convert to indices of ones
   g[    ]   ⍝ Index into the Fibonacci array of 1,2,3,5,...
 +/          ⍝ Sum

APL (Dyalog Extended) , 52 байта

{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣20⍨1}+⍥({+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤)

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

Как это работает

Нет сложного алгоритма для добавления в Zeckendorf, потому что APL не известен работой с отдельными элементами в массиве. Вместо этого я решил преобразовать два входных значения из Цекендорфа в простые целые числа, добавить их и преобразовать обратно.

Часть 1: Zeckendorf для простого целого числа

{+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤  ⍝ Zeckendorf to plain integer
                ⊤  ⍝ Convert the input to array of binary digits (X)
{    (  ≢⊤⍵)  }    ⍝ Take the length L of the binary digits and
      ⌽⍳           ⍝   generate 1,2..L backwards, so L..2,1
{+∘÷⍣(     )⍨1}    ⍝ Apply "Inverse and add 1" L..2,1 times to 1
                   ⍝ The result looks like ..8÷5 5÷3 3÷2 2 (Y)
               ⊥   ⍝ Mixed base conversion of X into base Y

Base |             Digit value
-------------------------------
13÷8 | (8÷5)×(5÷3)×(3÷2)×2 = 8
 8÷5 |       (5÷3)×(3÷2)×2 = 5
 5÷3 |             (3÷2)×2 = 3
 3÷2 |                   2 = 2
 2÷1 |                   1 = 1

Часть 2: Добавьте два простых целых числа

+⍥z2i  ⍝ Given left and right arguments,
       ⍝   apply z2i to each of them and add the two

Часть 3: Преобразование суммы обратно в Цекендорф

«Можно предположить, что представления Цекендорфа как входных, так и выходных данных помещаются в 31 бит», было довольно удобно.

{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣20⍨1}  ⍝ Convert plain integer N to Zeckendorf
                 (1,+\⍤,)⍣20⍨1   ⍝ First 41 Fibonacci numbers starting with two 1's
                ⌽                ⍝ Reverse
             ↑,\                 ⍝ Matrix of prefixes, filling empty spaces with 0's
          ⌽⍵,                    ⍝ Prepend N to each row and reverse horizontally
        |/                       ⍝ Reduce by | (residue) on each row (see below)
       ⍧                         ⍝ Nub sieve; 1 at first appearance of each number, 0 otherwise
  1↓¯1↓                          ⍝ Remove first and last item
 ⊥                               ⍝ Convert from binary digits to integer

Генератор Фибоначчи

(1,+\⍤,)⍣20⍨1
→ 1 ((1,+\⍤,)⍣20) 1  ⍝ Expand ⍨
→ Apply 1 (1,+\⍤,) x 20 times to 1

First iteration
1(1,+\⍤,)1
→ 1,+\1,1  ⍝ Expand the train
→ 1,1 2    ⍝ +\ is cumulative sum
→ 1 1 2    ⍝ First three Fibonacci numbers

Second iteration
1(1,+\⍤,)1 1 2
→ 1,+\1,1 1 2  ⍝ Expand the train
→ 1 1 2 3 5    ⍝ First five Fibonacci numbers

⍣20  ⍝ ... Repeat 20 times

Это следует из свойства чисел Фибоначчи: если Фибоначчи определяется как

тогда

Итак, накопленная сумма $1,F_0, \cdots, F_n$ (Массив Фибоначчи с добавлением 1) становится $F_1, \cdots, F_{n+2}$, Затем я снова добавляю 1, чтобы получить обычный массив Фибоначчи, начинающийся с индекса 0.

Цифры Фибоначчи в Цекендорф

Input: 7, Fibonacci: 1 1 2 3 5 8 13

Matrix
0 0 0 0 0 0 13 7
0 0 0 0 0 8 13 7
0 0 0 0 5 8 13 7
0 0 0 3 5 8 13 7
0 0 2 3 5 8 13 7
0 1 2 3 5 8 13 7
1 1 2 3 5 8 13 7

Reduction by residue (|/)
- Right side always binds first.
- x|y is equivalent to y%x in other languages.
- 0|y is defined as y, so leading zeros are ignored.
- So we're effectively doing cumulative scan from the right.
0 0 0 0 0 0 13 7 → 13|7 = 7
0 0 0 0 0 8 13 7 →  8|7 = 7
0 0 0 0 5 8 13 7 →  5|7 = 2
0 0 0 3 5 8 13 7 →  3|2 = 2
0 0 2 3 5 8 13 7 →  2|2 = 0
0 1 2 3 5 8 13 7 →  1|0 = 0
1 1 2 3 5 8 13 7 →  1|0 = 0
Result: 7 7 2 2 0 0 0

Nub sieve (⍧): 1 0 1 0 1 0 0
1's in the middle are produced when divisor ≤ dividend
(so it contributes to a Zeckendorf digit).
But the first 1 and last 0 are meaningless.

Drop first and last (1↓¯1↓): 0 1 0 1 0
Finally, we apply base 2 to integer (⊥) to match the output format.

Хаскелл, 325 396 байтов

РЕДАКТИРОВАТЬ: новая версия:

s f[]=[]
s f l=f l
x((a:b):(c:d):(e:r))=x(b:d:(a:e):r)
x(a:b:((c:d:e):r))=x((c:a):b:e:((d:s head r):s tail r))
x[]=[]
x(a:r)=a:x r
w l|x l/=l=w.x$l|True=l
l=length
t n x=take n$repeat x
j 0=[]
j n=t(mod(n)2)1:j(div(n)2)
i n=[[],[]]++j n++t(32-(l$j n))[]
u[]=0
u(a:r)=2*u r+l a
o(_:a:r)=u r+l a
z a b=o$w$zipWith(++)(i a)(i b)

z делает работу

ES6, 130 байт

(n,m)=>{for(a={},s=0,i=x=y=1;i<<1;i+=i,z=y,y=x,x+=z)s+=((n&i)+(m&i))/i*(a[i]=x);for(r=0;i;i>>>=1)s>=a[i]?(s-=a[i],r|=i):0;return r}

Первоначально я пытался вычислить сумму на месте (по сути, в соответствии с реализацией CJam), но у меня не хватало временных значений, поэтому я просто преобразовал числа в реальные целые числа и обратно.

(Да, я могу, вероятно, сохранить байт, используя eval.)

Рубин , 85 73 65 байт

->*a{r=(0..2*a.sum).select{|r|r^r*2==r*3};r[a.sum{|w|r.index w}]}

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

Как?

Сначала получите верхнюю границу для закодированной суммы: (a + b) * 2 в порядке.

Теперь отфильтруйте все числа не-Зеккендорфа из (0..limit).

У нас есть справочная таблица, отсюда вниз по склону.

Python 3, 207 байт

def s(n):
 p=1
 while n>=2*p:
  p*=2
 return n if n<=p else s(n+p//2)if n>=3*p/2 else s(m)if (m:=s(n-p)+p)!= n else n
a=lambda n,m:(b:=n&m)>-1 and s(a(a(a(s((n|m)-b%4),b//4*2),b//4),b%4*2+b%4//2))if m else n

Попробуйте онлайн! (Проверьте все контрольные примеры)

объяснение

Эта программа напрямую управляет двоичными переводами представлений Цекендорфа. Функция a(n,m)выполняет основные вычисления и s(n)является вспомогательной функцией, которая избавляет от соседних чисел, содержащихся в представлении Цекендорфа.

Давайте начнем с функции s(n)(расширенной для ясности):

def s(n): 
    p=1                  #This finds the highest digit of the binary form of n.
    while n>=2*p:
        p*=2
    if n<=p:             #If n is a power of two (i.e, our number is already a Fibonnaci number)...
        return n         #Then return it normally.  This also works for zero. (A)
    if n>=3*p/2:         #If n's first digit is followed by a 1 (i.e, it starts with 11X)
        return s(n+p//2) #Then replace that with 100X (B)
    m = s(n-p)+p         #Otherwise, apply s to the rest of the number (C)
    if m==n:             #If this is out final result, we're done! (D)
        return n
    return s(m)          #Otherwise, reapply it. (E)

Например, число 107 ( 1101011в двоичном виде, представляющее 1 + 2 + 5 + 13 + 21 = 42), подвергается следующему процессу:

1+2+5+13+21 [1101011] -> 1+2+5+34 [10001011] (B)
1+2+5+34 [10001011] (C)
 1+2+5 [1011] (C)
  1+2 [11] -> 3 [100] (B)
 ->3+5 [1100] (A/E)
 (E):  3+5 [1100] -> 8 [10000] (B)
->8+34 [10010000] (A/E)
(E): 8+34 [10010000] (C)
->8+34 [10010000] (A/E)

Попробуйте онлайн! (с подробным выводом)

Вот расширенная версия a(n,m):

def a(n,m):
    if m==0:
        return n
    b=n&m
    t=s((n|m)-b%4)              #(A)
    t=a(t,b//4*2)               #(B)
    t=a(t,b//4)                 #(C)
    return s(a(t,b%4*2+b%4//2)) #(D)

Эта функция преобразует два представления Цекендорфа в четыре двоичных числа, которые легче объединить. Линия (A) - это побитовое ИЛИ двух двоичных представлений Цекендорфа - они соответствуют одной копии каждого числа Фибоначчи в любой группе. (B) и (C) - побитовое И двух чисел, сдвинутых вправо 1 и 2 раза соответственно. Мы знаем, что когда соответствующие числа Фибоначчи для (B) и (C) складываются вместе, они будут эквивалентны поразрядному И нашего nи mпотому что F (n) = F (n-1) + F (n-2) ,

Например, предположим, что у нас есть двоичные числа n = 101001 (что соответствует 1 + 5 + 13) и m = 110110 (2 + 3 + 8 + 13). Тогда мы будем иметь (A) = 111111 (1 + 2 + 3 + 5 + 8 + 13), который преобразуется в 1010100 (3 + 8 + 21) по нашей функции s, (B) = 10000 (8) и ( С) = 1000 (5). Мы можем проверить, что (1 + 5 + 13) + (2 + 3 + 8 + 13) = (3 + 8 + 21) + (8) + (5) = 45. Этот процесс повторяется с ((3 + 8 + 21) + (8)) + (5) = ((3 + 8 + 21) + (5) + (3)) + (5) и т. Д.

Единственная сложность этой системы в том, что она не работает для чисел Фибоначчи 1 и 2, поскольку они не подчиняются свойству F(n)=F(n-1)+F(n-2)(это самые младшие два числа)! Из-за этого, когда 1 или 2 содержится в обоих nи m, они удаляются из A, B и C, их сумма помещается в D под свойством 1 + 1 = 2 и 2 + 2 = 1 + 3. Например, если мы добавим 1 + 3 (101) + 1 + 3 + 5 (1101), мы получим:

(А): 3 + 5 (1100) = 8 (10000)

(В): 2 (10)

(С): 1 (1)

(D): 2 (10)

Обратите внимание, что 3 и 5 были помещены в A, дубликат 3 был разделен на 2 + 1 в B и C, а дубликаты 1 были удалены из A, B и C, добавлены вместе и помещены в D. Аналогично, если мы сложив 2 + 3 (110) + 2 + 3 + 5 (1110), получим:

(А): 3 + 5 (1100) = 8 (10000)

(В): 2 (10)

(С): 1 (1)

(D): 1 + 3 (101)

Попробуйте онлайн! (с подробным выводом)

Wolfram Language (Mathematica) , 218 байтов

Fold[#+##&,Total@PadLeft@IntegerDigits[#,2]//.{{p=n_/;n>1,r=y___}:>{0,n,y},{q=x___,i_,p,j_,k_,r}:>{x,i+1,n-2,j,k+1,y},{q,i_,p,j_}:>{x,i+1,n-2,j+1},{q,i_,p}:>{x,i+1,n-2},{1,1,r}:>{1,0,0,y},{q,i_,1,1,r}:>{x,i+1,0,0,y}}]&

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

Просто сопоставление с образцом.

Ungolfed:

FromDigits[Total@PadLeft@IntegerDigits[#, 2] //.
   {{n_ /; n > 1, y___} :> {0, n, y},
    {x___, i_, n_ /; n > 1, j_, k_, y___} :> {x, i + 1, n - 2, j, k + 1, y},
    {x___, i_, n_ /; n > 1, j_} :> {x, i + 1, n - 2, j + 1},
    {x___, i_, n_ /; n > 1} :> {x, i + 1, n - 2},
    {1, 1, y___} :> {1, 0, 0, y},
    {x___, i_, 1, 1, y___} :> {x, i + 1, 0, 0, y}}, 2] &