Задний план

Большинство из вас знает, что такое число Фибоначчи . Некоторые из вас могут знать, что все положительные целые числа могут быть представлены в виде суммы одного или нескольких различных чисел Фибоначчи, согласно теореме Цекендорфа . Если число членов в оптимальном представлении Цекендорфа целого числа nсамо является числом Фибоначчи, мы будем называть n«тайно» Фибоначчи.

Например:

139 = 89 + 34 + 13 + 3
This is a total of 4 integers. Since 4 is not a Fibonacci number, 139 is not secretly Fibonacci

140 = 89 + 34 + 13 + 3 + 1
This is a total of 5 integers. Since 5 is a Fibonacci number, 140 is secretly Fibonacci

Заметки

• Оптимальное представление Цекендорфа можно найти с помощью жадного алгоритма. Просто возьмите наибольшее число Фибоначчи <= n и вычтите его из n, пока не достигнете 0
• Все числа Фибоначчи могут быть представлены как сумма 1 числа Фибоначчи (самого себя). Поскольку 1 - это число Фибоначчи, все числа Фибоначчи также являются тайными числами Фибоначчи.

Вызов

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

вход

Вы можете принять участие в любом разумном формате. Вы можете предположить, что ввод будет одним положительным целым числом.

Выход

Выведите один из двух разных результатов для того, является ли ввод тайно Фибоначчи. Примеры включают в себя True/ False, 1/ 0и т. Д.

счет

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

Тестовые случаи

Truthy (secretly Fibonacci)
1
2
4
50
140
300099

Falsey (NOT secretly Fibonacci)
33
53
54
139
118808

JavaScript (Node.js) , 54 байта

x=>g(g(x))<2;g=(x,i=1,j=1)=>j>x?x&&g(x-i)+1:g(x,j,i+j)

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

Python 2 , 77 байт

def f(n):z=[bin(x).count('1')for x in range(n*n+1)if x&2*x<1];print z[z[n]]<2

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

Это использует теорему о том, что два описания OEIS A003714 эквивалентны:

$n = F(i_1) + F(i_2) + \dots + F(i_k)$$n$$n$$a(n) = 2^{i_1} + 2^{i_2} + \dots + 2^{i_k}$$1$«S.

z$n$

Тогда остается проверить , если z[n]это число Фибоначчи, то есть z[z[n]] == 1.

^{$n^2+1$}

Желе , 15 байт

‘ÆḞ€fRṪạµƬL’Ɗ⁺Ị

Монадическая ссылка, принимающая неотрицательное целое число, которое возвращает 1«Тайно по Фибоначчи» и в 0противном случае.

Попробуйте онлайн! (слишком неэффективно для больших тестовых случаев)

Как?

‘ÆḞ€fRṪạµƬL’Ɗ⁺Ị - Link: integer, I
        µƬ      - perform the monadic link to the left as a function of the current I,
                - collecting up all the inputs until the results are no longer unique:
‘               -   increment I -> I+1
 ÆḞ€            -   nth Fibonacci number for €ach n in [1,I+1]
     R          -   range from 1 to I
    f           -   filter discard (discard Fibonacci numbers not in the range, i.e. > I)
      Ṫ         -   tail (get the largest)
       ạ        -   absolute difference with I
                - This gives us a list from I decreasing by Fibonacci numbers to 0
                - e.g. for 88 we get [88,33,12,4,1,0]
                -      because (88-33)+(33-12)+(12-4)+(4-1)+(1-0)=55+21+8+3+1=88 
          L     - length (the number of Fibonacci numbers required plus one)
           ’    - decrement (the number of Fibonacci numbers required)
            Ɗ   - treat the last three links (which is everything to the left) as a monad:
             ⁺  - ...and repeat it
                - i.e. get the number of Fibonacci numbers required for the number of
                -      Fibonacci numbers required to represent I.
                -      This is 1 if I is Secretly Fibonacci, and greater if not)
              Ị - insignificant? (is the absolute value of that <= 1?)

R , 83 байта

function(n){T=1:0
while(n>T)T=c(T[1]+T[2],T)
while(n){n=n-T[T<=n][1]
F=F+1}
F%in%T}

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

C # (.NET Core) , 124 115 98 байт

a=>{int n=0,b,c;for(;a>0;a-=b,n++)for(b=c=1;c<=a;b=c-b)c+=b;for(b=c=1;c<n;c+=b)b=c-b;return c==n;}

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

-3 байта: изменено в цикле цикла на (благодаря Оливье Грегуару )
-6 байтов: переключено на использование переменных, инициализированных b и c вне циклов (благодаря Кевину Круйссену )
-17 байтов: изменено условие во втором цикле для перемещения, если вне цикла и объединить с возвращаемыми, повторно использованными переменными b и c в последнем цикле (спасибо разнагул )

Ungolfed:

a => {
    int n = 0, b, c;                        // initialize variables

    for(; a > 0; a -= b, n++)               // increase n until a is 0
        for(b = c = 1; c <= a; b = c - b)   // set b and c to 1 for each a; set second largest Fibonacci number until largest Fibonacci number reaches a
            c += b;                         // set largest Fibonacci number of current sequence

    for(b = c = 1; c < n; c += b)           // while e is less than or equal to n, continue incrementing largest (e) Fibonacci number in the sequence
        b = c - b;                          // increment second-largest (d) Fibonacci number

    return c == n;                          // if c equals n, a is a secret Fibonacci number
}

Perl 6 , 58 байт

{(1,&[+]...*>$_)∋($_,{$^n-(1,&[+]...^*>$n).tail}...0)-1}

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

1, &[+] ... * > $_ это просто последовательность Фибоначчи, остановленная в удобном бесконечном месте (входное число).

$_, { $^n - (1, &[+] ...^ * > $n).tail } ... 0представляет собой последовательность чисел, начиная с входного номера, и каждый последующий элемент получается путем вычитания наибольшего числа Фибоначчи, меньшего или равного предыдущему элементу из предыдущего элемента. Последовательность заканчивается, когда 0достигается. Например, если $_есть 140, то эта последовательность есть 140, 51, 17, 4, 1, 0.

Вычитание одного из этой последовательности рассматривает его как число, его длину, а разность - это число чисел Фибоначчи, которые, сложенные вместе, дают входное число. Затем этот номер проверяется на членство в первой последовательности Фибоначчи.

Perl 6 , 48 байт

{4>($_,{$_,{$_-(1,&[+]...*>$_)[*-2]}...^0}...1)}

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

Преобразует входные данные в список представления Zeckendorf несколько раз, пока он не достигнет одного числа, а затем проверяет, была ли длина последовательности меньше 4.

Функция Ценкендорфа в середине в основном основана на ответе Шона с парой улучшений.

Объяснение:

{4>($_,{$_,{$_-(1,&[+]...*>$_)[*-2]}...^0}...1)}
{                                              } # Anonymous code block
                                          ...     # Define a sequence:
    $_  # That starts at the input
      ,{                                 }  # Each element is defined by:
                                   ... # Another sequence that:
        $_,   # Starts at the previous element
            $_-   # The previous element minus
                1,&[+]...*     # The Fibonacci sequence
                          >$_  # Ending when it is larger than the previous element
               (             )[*-2]  # The second from last element
          {                        }...^0  # Run until 0, discarding the last element
         # This returns the length of the Zeckendorf Representation
                                         ...1  # Run this until it is length 1
 4>(                                         )  # Return true if the length of the sequence is smaller than 4

Например, последовательность для 2is 2 1с 2уже является числом Фибоначчи. Последовательность для 140is 140 5 1, и так как 5 является числом Фибоначчи, это возвращает true. Последовательность для 33is 33 4 2 1, и поскольку 4она не является числом Фибоначчи, последовательность имеет длину 4.

05AB1E , 14 байтов

ΔDÅFθ-¼}¾ÅF¾<å

Попробуйте онлайн . Нет набора тестов для всех тестовых случаев, потому что counter_variableневозможно сбросить до 0 .. Я проверил все вручную, и они верны.

Объяснение:

Δ      }          # Loop until the top of the stack no longer changes
 D                #  Duplicate the top of the stack
                  #  (implicitly the input in the first iteration)
  ÅF              #  Get a list of all Fibonacci numbers lower than this number
    θ             #  Get the last item (largest one)
     -            #  Subtract it from the number
      ¼           #  Increase the counter_variable by 1 every iteration
        ¾         # After the loop, push the counter_variable
         ÅF       # Get all Fibonacci numbers below this counter_variable
           ¾<     # Push the counter_variable again, and subtract 1
             å    # Check if this value is in the list of Fibonacci numbers
                  # (and output implicitly)

ПРИМЕЧАНИЕ. Это counter_variableбудет 5для ввода 139и 6для ввода 140, потому что для того, чтобы Δ-loop проверить стек остался прежним, он, конечно, делает дополнительную итерацию.

Haskell , 64 байта

s=(<2).r.r
f=1:scanl(+)1f
r 0=0
r z=1+r(z-last(takeWhile(<=z)f))

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

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

.+
$*
M`((?>\2?)(\1|\G.))*..|.
.+
$*
^(((?>\3?)(\2|^.))*.)?.$

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

.+
$*

Преобразовать в одинарный.

M`((?>\2?)(\1|\G.))*..|.

Подсчитайте количество необходимых чисел Фибоначчи.

Первое чередование касается чисел Фибоначчи, которые не меньше 2. На первом проходе \2еще не существует, но, к счастью, это необязательно, поэтому нам не нужно сопоставлять его. \1тоже не существует, но, к счастью, у нас есть альтернатива, \G.которая соответствует одному символу в начале матча. Оба \2и \1поэтому принимают значение 1.

На последующих проходах, \2существует, поэтому мы пытаемся сопоставить его. На этот раз, если произойдет \1сбой, произойдет сбой (так как он больше, чем \2), но, если это удастся, (?>)предотвращает возврат, поэтому, если \2совпадения \1не совпадают , мы не пытаемся просто \1. ( \G1всегда терпит неудачу, так как мы продвинулись после начала патча.) Наконец, \2принимает предыдущее значение, \1а while \1принимает сумму двух значений.

Поэтому мы сопоставляем столько чисел Фибоначчи, сколько можем, добавляя их по ходу. Так как частичные суммы последовательности 1, 2, 3, 5..., 0, 1, 3, 6, 11...т.е. на 2 меньше, чем числа Фибоначчи, мы заканчиваем сопоставлением 2 в конце.

Это, очевидно, не соответствует самому 1, так что чередование обрабатывает этот случай.

.+
$*

Преобразовать в одинарный.

^(((?>\3?)(\2|^.))*.)?.$

Проверьте, является ли это число Фибоначчи. В нем используется та же идея, что и в первом тесте, но он использует ^вместо, \Gи мы также должны точно соответствовать, поэтому он использует необязательный захват вместо чередования, так как это лучше для гольфа (но это увеличивает числа захватов на 1).

Сетчатка , 35 байт

.+
*
2}C`((?>\2?)(\1|\G.))*..|.
^1$

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

.+
*

Преобразовать в одинарный.

C`((?>\2?)(\1|\G.))*..|.

Подсчитайте количество необходимых чисел Фибоначчи. (Зацикливание как преобразования, так и счета экономит целый байт, прежде всего, получая счет в унарном порядке.)

2}

Выполните предыдущие шаги в общей сложности дважды. Это берет количество чисел Фибоначчи, необходимое для суммирования к числу чисел Фибоначчи.

^1$

Если число было тайно Фибоначчи, то результат равен 1.

Python 2 , 146 137 байт

lambda a:len(g(len(g(a))))<2
f=lambda n:n<3or f(n-2)+f(n-1)
def g(a,n=1):j=f(n-1);return[j]if a-j<1else[j]+g(a-j)if a-f(n)<0else g(a,n+1)

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

f () - рекурсивная функция, которая возвращает значение n-го числа Фибоначчи. Взято из этого ответа .

g () - рекурсивная функция, которая возвращает представление Цекендорфа данного числа в виде списка целых чисел.

Поскольку все числа Фибоначчи будут иметь возвращаемую длину одного элемента из g (), h () проверяет, является ли длина g () из g (n) == 1.

РЕДАКТИРОВАТЬ: Сохранено 9 байтов благодаря Nedla2004 . Я постоянно забываю, что лямбды не всегда являются лучшим решением ...