Чергова сила Послідовність Фібоначчі

Dennis 08/19/2017. 12 answers, 2.084 views
code-golf math sequence array-manipulation fibonacci

Визначення

Чергова сила Послідовність Фібоначчі формується наступним чином.

  1. Почніть з порожньої послідовності і встановіть n до 1 .

  2. Обчислити f n , n й неотрицательный номер Фібоначчі , з повтореннями.
    0 - перший, 1 - другий і третій, 2 - четвертий. Всі інші отримані шляхом підсумовування двох попередніх чисел у послідовності, так що 3 = 1 + 2 є п'ятим, 5 = 2 + 3 є шостим і т. Д.

  3. Якщо n непарний, змініть знак f n .

  4. Додайте до послідовності 2n-1 копії f n .

  5. Приріст n і повернутися до кроку 2.

Це перші сотні термінів послідовності APF.

0  1  1 -1 -1 -1 -1  2  2  2  2  2  2  2  2 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3
-3 -3 -3 -3 -3 -3  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
 5  5  5  5  5  5  5  5  5  5  5  5  5 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
-8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 

Завдання

Напишіть повну програму або функцію, яка приймає позитивне ціле число n як вхідний, і друкує або повертає n й термін послідовності APF.

Якщо ви віддаєте перевагу індексування на основі 0, ви можете також взяти неотрицательное ціле число n і роздрукувати або повернути номер APF за індексом n .

Це ; може найкоротший код у байтах виграти!

Тестові випадки (на основі 1)

1 ->    0
    2 ->    1
    3 ->    1
    4 ->   -1
    7 ->   -1
    8 ->    2
  100 ->   -8
  250 ->   13
  500 ->  -21
 1000 ->   34
11111 ->  233
22222 -> -377
33333 ->  610 

Тестові випадки (на основі 0)

0 ->    0
    1 ->    1
    2 ->    1
    3 ->   -1
    6 ->   -1
    7 ->    2
   99 ->   -8
  249 ->   13
  499 ->  -21
  999 ->   34
11110 ->  233
22221 -> -377
33332 ->  610 
4 Comments
Okx 01/31/2017
Чи існують обмеження для n ?
2 Dennis♦ 01/31/2017
Поки ваш алгоритм працює для довільно великих значень n , ви можете припустити, що він вписується у ваш тип даних.
1 Mindwin 02/01/2017
Чи має цей номер OEIS?
Dennis♦ 02/01/2017
@Міндвін це не так.

12 Answers


Jonathan Allan 01/31/2017.

Желе , 5 байт

BLCÆḞ 

Try it online!

Як?

Продовжуючи серію Фібоначчі знову в негативні індекси так, що все ще зберігається відношення f(i) = f(i-2) + f(i-1) :

i   ...   -8  -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   4   5 ...
f(i)  ...  -21  13  -8   5  -3   2  -1   1   0   1   1   2   3   5   8 ... 

Повертаючись назад з i=0 числа - це ті, що нам потрібно повторити 2n-1 разів, а вбудований Jelly's Fibonacci, ÆḞ , обчислить їх.

Ми можемо знайти -i (позитивне число), що нам потрібно, беручи b-довжину n і віднімаючи 1 .

Оскільки ми хочемо, щоб i (негативне число), ми можемо замість цього виконати 1-bitLength а Jelly має атом для 1-x , C , монада доповнення.

BLCÆḞ - Main link: n               e.g.  500
B     - convert n to a binary list      [1,1,1,1,1,0,1,0,0]
 L    - get the length                   9
  C   - complement                      -8
   ÆḞ - Fibonacci                       -21 
3 comments
miles 01/31/2017
Я знав, що був коротший шлях, але не так багато, думав, що це буде 7 байтів з способом видалення µ та
Jonathan Allan 01/31/2017
Ваше повторюване заперечення було розумним, хоча я дивився на мінус-сили, що додає кілька байтів, доки я не згадував про негативні значення Фібоначчі і намагався підключити їх до монади Желі.
4 ETHproductions 01/31/2017
Чесно кажучи, я здивований, Jelly не має єдиного байта, щоб отримати двійкову довжину числа ...

xnor 01/31/2017.

Python 2 , 30 bytes

 f=lambda n:n<1or f(n/4)-f(n/2) 

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

Один індексований.

Послідовність відчувала себе як головоломка, те, що Денніс створив, маючи короткий шлях для його вираження. Потужність з двох повторень передбачає рекурсию біт-зміщення (розділ на половину на 2). Рекурсія Фібоначчі з черговим знаком f(n)=f(n-2)-f(n-1) може бути пристосована до бітшифт замість декрементації. Базовий випадок прекрасно працює, тому що всі воронки до n=0 .


martin 02/01/2017.

Mathematica, 43 36 24 байт

Fibonacci@-Floor@Log2@#& 

7 байтів збережено завдяки @GregMartin, а ще 12 завдяки @JungHwanMin.

2 comments
1 Greg Martin 01/31/2017
Ви можете зберегти кілька байтів за допомогою Floor@Log2@# , а також писати Fibonacci[t=...] (і видалити пробіли в останньому експоненті).
1 JungHwan Min 02/01/2017
-12 байтів: Fibonacci@-Floor@Log2@#& - Fibonacci можуть приймати негативні аргументи (піклується про знак для вас).

Luis Mendo 02/01/2017.

MATL , 19 17 16 11 байт

lOiB"yy-]x& 

Вхід 1 базується.

Спробуйте онлайн! Або перевірити всі тестові випадки .

Як це працює

Для введення n на основі 1, нехай m - число цифр у бінарному розширенні n . n -й термін у вихідній послідовності є m - m терміном у послідовності Фібоначчі, можливо, з його зміною.

Одна ідея полягає в ітерації m раз, щоб обчислити умови послідовності Фібоначчі. Це легко з використанням for each циклу масиву двійкових цифр. Якщо послідовність Фібоначчі була паралізована 0 , тоді як 1 як завжди, повторення m разів призведе до складання m+2 термінів у стекі, тому дві перші номери слід було б видалити. Замість цього ми перенаправляємо з 1 , потім 0 . Таким чином, наступні згенеровані терміни - 1 , 1 , 2 , ... і потрібна лише one делегація.

Знак може бути вирішено за допомогою іншого циклу, щоб змінити знак m разів. Але це дорого. Краще інтегрувати два цикли, що робиться просто шляхом subtracting а не додавання в ітерацію Фібоначчі.

l       % Push 1
O       % Push 0
iB      % Input converted to binary array
"       % For each
  yy    %   Duplicate top two elements
  -     %   Subtract. This computes the new Fibonacci term with the sign changes
]       % End
x       % Delete top number
&       % Specify that implicit display should take only one input
        % Implicitly display the top of the stack 

ETHproductions 04/13/2017.

JavaScript (ES6), 33 байти

f=(n,p=1,c=0)=>n?-f(n>>1,c,p+c):p 

1-індексований.

Відповідь порту xnor буде 23:

f=n=>n<1||f(n/4)-f(n/2) 

ovs 02/18/2017.

Python 2 , 83 82 79 bytes

 def f(n,a=0,b=1):
 l=bin(n)[2:]
 for _ in l:a,b=b,a+b
 return a*-(len(l)%2or-1) 

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

1 comments
TuukkaX 01/31/2017
Пробіл не вимагається при or -1 .

miles 01/31/2017.

Желе , 9 байт

BLµ’ÆḞN⁸¡ 

Використовує єдину індексацію.

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

Пояснення

Цей метод працює, якщо ваша функція Фібоначчі підтримує невід'ємні аргументи.

BLµ’ÆḞN⁸¡  Input: integer n
B          Binary digits of n
 L         Length. len(bin(2)) = floor(log2(n)))
  µ        Start new monadic chain on x = len(bin(2))
   ’       Decrement
    ÆḞ     Get Fibonacci(x-1)
       ⁸¡  Repeat x times on that
      N      Negate.
           Return Fibonacci(x-1) if x is even else -Fibonacci(x-1) 

ETHproductions 01/31/2017.

Japt , 6 байт

Mg1-¢l 

Перевірте його в Інтернеті!

Як це працює

Як згадувалося в інших відповідях, n й член в ряді з черговим знаком Фібоначчі такий самий, як -n й член в регулярній серії. n можна знайти, беручи бітовий вхідний сигнал і вираховуючи його; заперечуючи це результати в 1 мінус біт-довжини.

Mg1-¢l
    ¢l  // Calculate the length of the input in binary.
  1-    // Subtract this from 1.
Mg      // Get the Fibonacci number at this index. 

Emigna 04/13/2017.

05AB1E , 11 10 байт

Використовує індексування на основі 1

05AB1E з Фібоначчі повертає кількість позитивних чисел менше, ніж n , що означає, що ми повинні генерувати більше, ніж необхідно, отримати правильний за індексом, а потім обчислити знак. Тому я сумніваюся, що будь-який метод, що базується на цьому, буде коротшим, ніж обчислення чисел ітераційно.

Використовує усвідомлення того, що ми можемо ініціалізувати стек з 1, 0 назад, щоб розглянути ситуацію, коли n=1 як описано у відповідь на MATL-відповіді Луїса Мендо .

XÎbgG‚D«`- 

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

Explanation

X             # push 1
 Î            # push 0 and input
  b           # convert input to binary
   g          # get length of binary number
    G         # for N in [1...len(bin(input))-1] do:
     ‚        # pair the top 2 elements of the stack in a list
      D       # duplicate the list 
       «      # concatenate the 2 lists together
        `     # split into separate elements on the stack
         -    # subtract the top 2 elements 

smls 01/31/2017.

Perl 6 , 53 bytes

 {flat(((0,1,*+*...*)Z*|<-1 1>xx*)Zxx(1,2,4...*))[$_]} 

Пряме впровадження послідовності, як це було описано.
На основі нуля.


Dennis 04/13/2017.

Юлія 0.5 , 19 байт

 !n=n<1||!(n/=4)-!2n 

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

Як це працює

Це використовує ту саму формулу, що і відповідь Python @ xnor . Відношення рецидивів
g(n) = g(n-2) + g(n-1) генерує негативні терміни послідовності Фібоначчі, які дорівнюють позитивним членам з чергуючими знаками. З будь-якого місця в 2 к- повторюванні одного і того ж номера ми можемо обрати будь-яке повторення попереднього циклу з номерами 2 k-1 і пробігом 2 k-2 номерів перед ними, розділивши індекс на 2 і 4 .

Замість прямого

 f(n)=n<1||f(n÷4)-f(n÷2) # 25 bytes 

ми можемо перевизначити оператора в наших цілях. Крім того, f буде працювати так само добре, як і плаваючі, так що ми отримуємо

 !n=n<1||!(n/4)-!(n/2)   # 21 bytes 

Нарешті, якщо ми оновлюємо n з поділом на 4 , wwe може написати n/2 як 2n і виключити пару parens, що призведе до визначення 19-байтових функцій у цьому відповіді.


miles 02/05/2017.

J 18 байт

(%>:-*:)t.@<:@#@#: 

Використовує єдину індексацію. Вводить ціле число n > 0 і обчислює floor(log2(n)) , знайшовши довжину його двійкового подання, а потім декременти, значення яких оцінюються за одиницю. Потім він знаходить floor(log2(n))-1 th коефіцієнта генеруючої функції x / (1 + x - x 2 ), яка є gf для негативних індексованих значень Фібоначчі.

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

Пояснення

(%>:-*:)t.@<:@#@#:  Input: integer n
                #:  Binary
              #@    Length
           <:@      Decrement
(      )            The generating function x/(1+x-x^2)
  >:                  Increment x
     *:               Square x
    -                 Subtract
 %                    Divide x by previous
        t.          Get series coefficient at the index given by previous value 

Related questions

Hot questions

Language

Popular Tags