Распечатать последовательность N-Боначи

55

Это не очень широко известно, но то, что мы называем последовательностью Фибоначчи, АКА

1, 1, 2, 3, 5, 8, 13, 21, 34...

на самом деле называется последовательность Duonacci . Это потому, что для получения следующего числа вы суммируете предыдущие 2 числа. Существует также последовательность Трибоначи ,

1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201...

потому что следующее число является суммой предыдущих 3 чисел. И последовательность Quadronacci

1, 1, 1, 1, 4, 7, 13, 25, 49, 94, 181, 349, 673...

И все любимые, последовательность Пентаначи :

1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129...

И последовательность Гексаначчи, последовательность Септаначчи, последовательность Октоначи и так далее, и так далее, вплоть до последовательности N-Боначи.

Последовательность N-Боначи всегда будет начинаться с N 1 с подряд.

Соревнование

Вы должны написать функцию или программу, которая принимает два числа N и X и печатает первые числа X N-Боначи. N будет целым числом больше 0, и вы можете смело предполагать, что числа N-Bonacci не превысят тип номера по умолчанию на вашем языке. Вывод может быть в любом удобочитаемом формате, и вы можете принять ввод любым разумным способом. (Аргументы командной строки, аргументы функций, STDIN и т. Д.)

Как обычно, это Code-golf, поэтому применяются стандартные лазейки и выигрывает самый короткий ответ в байтах!

Образец ввода-вывода

#n,  x,     output
 3,  8  --> 1, 1, 1, 3, 5, 9, 17, 31
 7,  13 --> 1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193
 1,  20 --> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
 30, 4  --> 1, 1, 1, 1       //Since the first 30 are all 1's
 5,  11 --> 1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129
DJMcMayhem
источник
1
Чувак, у меня была эта идея некоторое время назад, и я не удосужился написать ее.
Морган Трепп
9
Кнопка "Мой голос" == ваш аватар
ETHproductions
Не будет ли 3-боначи 1, 1, 2, 4, 7третьей позицией 0 + 1 + 1? ... и так один с другими?
Зонт
1
@umbrella Нет, трибоначчи начинаются с 3 1 с. Смотрите мои правки, чтобы прояснить этот момент.
DJMcMayhem

Ответы:

24

Boolfuck, 6 байтов

,,[;+]

Вы можете смело предполагать, что числа N-Bonacci не будут превышать тип номера по умолчанию на вашем языке.

Тип номера по умолчанию в Boolfuck немного. Предполагая, что это также распространяется на входные числа N и X, и учитывая, что N> 0, есть только два возможных входа - 10 (который ничего не выводит) и 11 (который выводит 1).

,читает немного в текущую ячейку памяти. N игнорируется, поскольку должно быть 1. Если X равно 0, тело цикла (окруженное []) пропускается. Если X равен 1, он выводится и затем переворачивается на 0, поэтому цикл не повторяется.

user253751
источник
4
Разве нет стандартной лазейки именно так?
Стэн Струм
1
@StanStrum От до или после этого ответа?
user253751
2
Я считаю, что это было раньше, позвольте мне проверить это ... Meta Link ; Первая редакция была 31 января 2016 года в 13:44. Вау, не важно! У меня были два выходных. Хотя, чтобы быть упрямым, последнее изменение для этого было 31 января 2016 года в 16:06. Ооооо, да, в моей книге все хорошо
Стэн Струм
9

Python 2, 79 байт

n,x=input()
i,f=0,[]
while i<x:v=[sum(f[i-n:]),1][i<n];f.append(v);print v;i+=1

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

лямбда
источник
Попробуйте заменить последнюю строку наexec"v=[sum(f[i-n:]),1][i<n];f+=[v];print v;i+=1;"*x
Cyoce
8

Пиф, 13

<Qu+Gs>QGEm1Q

Тестирование

Вводит новую строку, разделенную nпервым.

Объяснение:

<Qu+Gs>QGEm1Q  ##  implicit: Q = eval(input)
  u      Em1Q  ##  read a line of input, and reduce that many times starting with
               ##  Q 1s in a list, with a lambda G,H
               ##  where G is the old value and H is the new one
   +G          ##  append to the old value
     s>QG      ##  the sum of the last Q values of the old value
<Q             ##  discard the last Q values of this list
FryAmTheEggman
источник
1
Вау, это было быстро Я едва успел закрыть свой браузер, прежде чем вы уже опубликовали это!
DJMcMayhem
5

Haskell, 56 байт

g l=sum l:g(sum l:init l)
n#x|i<-1<$[1..n]=take x$i++g i

Пример использования: 3 # 8-> [1,1,1,3,5,9,17,31].

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

i<-1<$[1..n]           -- bind i to n copies of 1
take x                 -- take the first x elements of
       i++g i          -- the list starting with i followed by (g i), which is
sum l:                 -- the sum of it's argument followed by
      g(sum l:init l)  -- a recursive call to itself with the the first element
                       -- of the argument list replaced by the sum
Ними
источник
Разве это не должно быть tail lвместо init l?
гордый haskeller
@proudhaskeller: это не имеет значения. мы сохраняем последние nэлементы в списке. Нет разницы между удалением с конца и добавлением вперед и наоборот, то есть удалением с фронта и добавлением в конец, потому что первоначальный список состоит только из 1s.
Ними
О, я понял. Это отличный способ заменить ++[]на :!
гордый haskeller
@proudhaskeller: да, именно так!
Ними
5

Python 2, 55 байт

def f(x,n):l=[1]*n;exec"print l[0];l=l[1:]+[sum(l)];"*x

Отслеживает длинное nокно последовательности в списке l, обновляемое путем добавления суммы и удаления первого элемента. Печатает первый элемент каждой итерации для xитераций.

Другой подход хранения всех элементов и суммирования последних nзначений дал одинаковую длину (55).

def f(x,n):l=[1]*n;exec"l+=sum(l[-n:]),;"*x;print l[:x]
XNOR
источник
5

Javascript ES6 / ES2015, 107 97 85 80 байт

Спасибо @ user81655, @Neil и @ETHproductions за сохранение некоторых байтов


(i,n)=>eval("for(l=Array(i).fill(1);n-->i;)l.push(eval(l.slice(-i).join`+`));l")

попробуйте это онлайн


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

console.log(f(3,  8))// 1, 1, 1, 3, 5, 9, 17, 31
console.log(f(7,  13))// 1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193
console.log(f(5,  11))// 1, 1, 1, 1, 1, 5, 9, 17, 33, 65, 129
gabrielperales
источник
1
Приятно. Пара советов по игре в гольф: forвсегда лучше, чем while, x.split('')-> [...x], ~~a-> +a, n-=1-> n--, если вы заключаете все тело функции в то, что evalвам не нужно писать return. Кроме того, даже короче, чем [...'1'.repeat(i)]есть, Array(i).fill(1)и вы можете удалить ~~из aи b. И вы можете удалить f=.
user81655
2
Это то , что это выглядит как мои советы (85 байт): (i,n)=>eval("for(l=Array(i).fill(1);n-->i;)l.push(l.slice(-i).reduce((a,b)=>a+b));l"). Я изменил порядок операторов, объединил n--в n-iи удалил lиз аргументов, чтобы сохранить несколько дополнительных байтов.
user81655 30.01.16
1
@ user81655 Я не получаю evalэкономию; (i,n)=>{for(l=Array(i).fill(1);n-->i;)l.push(l.slice(-i).reduce((a,b)=>a+b));return l}по-прежнему 85 байтов.
Нил
@Neil Для меня это выглядит как 86 байт ...
user81655 30.01.16
3
l.slice(-i).reduce((a,b)=>a+b)=>eval(l.slice(-i).join`+`)
ETHproductions
4

ES6, 66 байт

(i,n)=>[...Array(n)].map((_,j,a)=>a[j]=j<i?1:j-i?s+=s-a[j+~i]:s=i)

К сожалению map, не позволит вам получить доступ к массиву результатов в обратном вызове.

Нил
источник
1
Сохраните байт, используя параметры.
Лохматый
4

Желе, 12 байт

ḣ³S;
b1Ç⁴¡Uḣ

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

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

b1Ç⁴¡Uḣ  Main link. Left input: n. Right input: x.

b1       Convert n to base 1.
    ¡    Call...
  Ç        the helper link...
   ⁴       x times.
     U   Reverse the resulting array.
      ḣ  Take its first x elements.


ḣ³S;     Helper link. Argument: A (list)

ḣ³       Take the first n elements of A.
  S      Compute their sum.
   ;     Prepend the sum to A.
Деннис
источник
3

C ++ 11, 360 байт

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

#include<vector>
#include<numeric>
#include<iostream>
using namespace std;typedef vector<int>v;void p(v& i) {for(auto&v:i)cout<<v<<" ";cout<<endl;}v b(int s,int n){v r(n<s?n:s,1);r.reserve(n);for(auto i=r.begin();r.size()<n;i++){r.push_back(accumulate(i,i+s,0));}return r;}int main(int c, char** a){if(c<3)return 1;v s=b(atoi(a[1]),atoi(a[2]));p(s);return 0;}

Я оставлю это как понятное объяснение кода выше.

#include <vector>
#include <numeric>
#include <iostream>

using namespace std;
typedef vector<int> vi;

void p(const vi& in) {
    for (auto& v : in )
        cout << v << " ";
    cout << endl;
}

vi bonacci(int se, int n) {
    vi s(n < se? n : se, 1);
    s.reserve(n);
    for (auto it = s.begin(); s.size() < n; it++){
        s.push_back(accumulate(it, it + se, 0));
    }
    return s;
}

int main (int c, char** v) {
    if (c < 3) return 1;
    vi s = bonacci(atoi(v[1]), atoi(v[2]));
    p(s);
    return 0;
}
hetepeperfan
источник
Добро пожаловать в Программирование головоломок и Code Golf. Это хороший ответ, однако я заметил, что у вас много пробелов, а имена переменных и функций длиннее 1 символа. На самом деле это хорошая читабельная версия вашего кода, но вы должны добавить версию для гольфа. Когда ты это сделаешь, я дам тебе голос, но пока я не буду играть в гольф, я не буду.
wizzwizz4
@ wizzwizz4 Привет, добавил вышеприведенную версию кода для игры в гольф. Я оставил код без присмотра, чтобы люди увидели, как я это сделал. Кроме того, мне нравится читать функцию bonacci, которая возвращает vi, который по-прежнему звучит как вибоначи. Я чувствую, что не должен делать основную функцию короче, потому что стандарт обязывает использовать int main (int, char **) в качестве точки входа в программу. Кроме того, я полагаю, что все переменные имеют длину не более 1 символа, и все несущественные пробелы удаляются.
hetepeperfan
3
Это не кодекс - «соблюдайте стандарты». Это код-гольф . Мы манипулируем и пользуемся нашими языками. Если есть переменные ints, удалите int. Если какие-либо функции вызываются foo, вызывайте их f. Быть жестоким; игнорировать стандарт и использовать компилятор. Вот как ты играешь в гольф.
wizzwizz4
Каламбуры и хороший код принадлежит в ungolfed коде только . Но не стесняйтесь держать их там; на самом деле, это рекомендуется. Но будьте очень, очень значимы для компилятора, когда вы играете в гольф свой код. Получите как можно меньше, несмотря ни на что . (О, и вот +1, я обещал!)
wizzwizz4
@ wizzwizz4 Действительно ли удаление "int"? Я думал, подразумевается, что int не будет работать.
DJMcMayhem
3

Haskell , 47 байтов

q(h:t)=h:q(t++[h+sum t])
n?x=take x$q$1<$[1..n]

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

<$ возможно, был введен в Prelude после публикации этого вызова.


Haskell , 53 байта

n%i|i>n=sum$map(n%)[i-n..i-1]|0<1=1
n?x=map(n%)[1..x]

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

Определяет двоичную функцию ?, используемую как 3?8 == [1,1,1,3,5,9,17,31].

Вспомогательная функция %рекурсивно находит iэлемент nпоследовательности -bonacci путем суммирования предыдущих nзначений. Затем функция ?табулирует первые xзначения %.

XNOR
источник
Старый ответ, а вы имеете в виду «вспомогательная функция %»?
Конор О'Брайен
Смена охранников превратится i<=nв i>n.
Орджан Йохансен
@ ØrjanJohansen Я тоже это заметил при редактировании, хотя оглядываться назад на весь метод кажется плохим, так что я мог бы просто переделать весь гольф.
xnor
2

APL, 21

{⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1}

Это функция, которая принимает n в качестве левого аргумента и x в качестве правого аргумента.

Объяснение:

{⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1}
                   ⍺/1  ⍝ begin state: X ones    
                  +     ⍝ identity function (to separate it from the ⍵)
    ⍺{         }⍣⍵     ⍝ apply this function N times to it with X as left argument
      ⍵,               ⍝ result of the previous iteration, followed by...
        +/              ⍝ the sum of
          ⍺↑            ⍝ the first X of
            ⌽          ⍝ the reverse of
             ⍵         ⍝ the previous iteration
 ⍵↑                    ⍝ take the first X numbers of the result

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

      ↑⍕¨ {⍵↑⍺{⍵,+/⍺↑⌽⍵}⍣⍵+⍺/1} /¨ (3 8)(7 13)(1 20)(30 4)(5 11)
 1 1 1 3 5 9 17 31                       
 1 1 1 1 1 1 1 7 13 25 49 97 193         
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
 1 1 1 1                                 
 1 1 1 1 1 5 9 17 33 65 129              
Мэринус
источник
2

Python 3, 59

Сохранено 20 байтов благодаря FryAmTheEggman.

Не очень хорошее решение, но пока оно будет работать.

def r(n,x):f=[1]*n;exec('f+=[sum(f[-n:])];'*x);return f[:x]

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

assert r(3, 8) == [1, 1, 1, 3, 5, 9, 17, 31]
assert r(7, 13) == [1, 1, 1, 1, 1, 1, 1, 7, 13, 25, 49, 97, 193]
assert r(30, 4) == [1, 1, 1, 1]
Морган Трепп
источник
2

Java, 82 + 58 = 140 байт

Функция для нахождения i- го числа n -bonacci ( 82 байта ):

int f(int i,int n){if(i<=n)return 1;int s=0,q=0;while(q++<n)s+=f(i-q,n);return s;}

Функция для вывода первого числа k n -bonacci ( 58 байт ):

(k,n)->{for(int i=0;i<k;i++){System.out.println(f(i,n));}}
HyperNeutrino
источник
2

Brain-Flak , 144 124 122 байта

-20 байт благодаря нитродену

Это мой первый ответ Brain-Flak, и я уверен, что его можно улучшить. Любая помощь приветствуется.

(([{}]<>)<{({}(()))}{}>)<>{({}[()]<<>({<({}<({}<>)<>>())>[()]}{})({}<><({({}<>)<>}<>)>)<>>)}{}<>{({}<{}>())}{}{({}<>)<>}<>

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

H.PWiz
источник
1

Юлия, 78 байт

f(n,x)=(z=ones(Int,n);while endof(z)<x push!(z,sum(z[end-n+1:end]))end;z[1:x])

Это функция, которая принимает два целых числа и возвращает массив целых чисел. Подход прост: генерируйте массив из единиц длины n, затем увеличивайте массив, добавляя сумму предыдущих nэлементов, пока массив не будет иметь длину x.

Ungolfed:

function f(n, x)
    z = ones(Int, n)
    while endof(z) < x
        push!(z, sum(z[end-n+1:end]))
    end
    return z[1:x]
end
Алекс А.
источник
1

MATL , 22 26 байт

1tiXIX"i:XK"tPI:)sh]K)

Используется текущий выпуск (10.2.1) языка / компилятора.

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

Несколько дополнительных байтов :-( из-за ошибки в Gфункции (вставьте ввод; теперь исправлено для следующего выпуска)

объяснение

1tiXIX"      % input N. Copy to clipboard I. Build row array of N ones
i:XK         % input X. Build row array [1,2,...X]. Copy to clipboard I
"            % for loop: repeat X times. Consumes array [1,2,...X]
  t          % duplicate (initially array of N ones)
  PI:)       % flip array and take first N elements
  sh         % compute sum and append to array
]            % end
K)           % take the first X elements of array. Implicitly display
Луис Мендо
источник
1

Perl 6 , 38 байт

->\N,\X{({@_[*-N..*].sum||1}...*)[^X]} # 38 bytes
-> \N, \X {
  (

    {

      @_[
        *-N .. * # previous N values
      ].sum      # added together

      ||     # if that produces 0 or an error
      1      # return 1

    } ... *  # produce an infinite list of such values

  )[^X]      # return the first X values produced
}

Использование:

# give it a lexical name
my &n-bonacci = >\N,\X{…}

for ( (3,8), (7,13), (1,20), (30,4), (5,11), ) {
  say n-bonacci |@_
}
(1 1 1 3 5 9 17 31)
(1 1 1 1 1 1 1 7 13 25 49 97 193)
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
(1 1 1 1)
(1 1 1 1 1 5 9 17 33 65 129)
Брэд Гилберт b2gills
источник
1

C, 132 байта

Рекурсивный подход короче на пару байтов.

k,n;f(i,s,j){for(j=s=0;j<i&j++<n;)s+=f(i-j);return i<n?1:s;}main(_,v)int**v;{for(n=atoi(v[1]);k++<atoi(v[2]);)printf("%d ",f(k-1));}

Ungolfed

k,n; /* loop index, n */

f(i,s,j) /* recursive function */
{
    for(j=s=0;j<i && j++<n;) /* sum previous n n-bonacci values */
        s+=f(i-j);
    return i<n?1:s; /* return either sum or n, depending on what index we're at */
}

main(_,v) int **v;
{
    for(n=atoi(v[1]);k++<atoi(v[2]);) /* print out n-bonacci numbers */
        printf("%d ", f(k-1));
}
Коул Камерон
источник
1

Шелуха , 9 байт

↑§¡ȯΣ↑_B1

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

Начинается с Base- 1представления N (просто списка из N ) и ¡теоретически суммирует ( Σ) последний ( ↑_) N элементов и добавляет результат в список. Наконец, берет ( ) первые X чисел в этом списке и возвращает их.

Лео
источник
0

Perl 6, 52 ~ 72 47 ~ 67 байт

sub a($n,$x){EVAL("1,"x$n~"+*"x$n~"...*")[^$x]}

Требуется модуль MONKEY-SEE-NO-EVALиз-за следующей ошибки:

=== К сожалению! === Ошибка при компиляции -e
EVAL - очень опасная функция !!! (используйте MONKEY-SEE-NO-EVAL для переопределения,
но только если вы ОЧЕНЬ уверены, что ваши данные не содержат инъекционных атак)
при -e: 1

$ perl6 -MMONKEY-SEE-NO-EVAL -e'a(3,8).say;sub a($n,$x){EVAL("1,"x$n~"+*"x$n~"...*")[^$x]}'
(1 1 1 3 5 9 17 31)
andlrc
источник
Кто-нибудь знает, как отключить строгий режим и т. Д.?
andlrc
Я думаю, что если вы используете версию Perl 6, выпущенную до Рождества 2015 года, то это не обеспечит реализацию monkey-see-no-eval.
Бэтмен
0

Jq 1,5 , 67 байт

def C:if length>X then.[:X]else.+=[.[-N:]|add]|C end;[range(N)|1]|C

Предполагается, что входные данные предоставлены N и X, например

def N: 5;
def X: 11;

расширенный

def C:                        # . is current array
    if length>X               # stop when array is as long as X
    then .[:X]                # return first X elements
    else .+=[.[-N:]|add] | C  # recursively add sum of last N elements to array
    end
;
  [range(N)|1]                # initial state
| C

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

jq170727
источник
0

J, 31 байт

]{.(],[:+/[{.])^:(-@[`]`(1#~[))

Ungolfed:

] {. (] , [: +/ [ {. ])^:(-@[`]`(1 #~ [))

объяснение

Веселые времена с глаголом силы в форме герунды :

(-@[`]`(1 #~ [)) NB. gerund pre-processing

Разбивка в деталях:

  • ] {. ...Возьмите первые <right arg>элементы из всего этого материала справа, который делает работу ...
  • <left> ^: <right>Примените глагол <left>несколько <right>раз ... где <right>указано средним герундием в (-@[] (1 #~ [), т. ]е. правый аргумент передан в саму функцию. Так что же <left>? ...
  • (] , [: +/ [ {. ])Левый аргумент всей этой фразы сначала трансформируется первым герундом, т -@[. Е. Это означает, что левый аргумент этой фразы является отрицательным аргументом левого аргумента для всей функции. Это необходимо для того, чтобы фраза [ {. ]взяла последние элементы из списка возврата, который мы строим. Те тогда суммируются +/. И, наконец, добавляется в тот же список возврата ] ,.
  • Итак, как инициализируется список возврата? Вот что выполняет третья предварительная обработка, выполняемая герундами: (1 #~ [)- повторить 1 раз «левый аргумент».

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

Ион
источник
0

Mathematica, 59 байт

((f@#=1)&/@Range@#;f@n_:=Tr[f[n-#]&/@Range@#];f/@Range@#2)&

Возможно, вы захотите Clear@fмежду вызовами функций. Аргументы n,x, как и в случае с тестами.

numbermaniac
источник
0

Приборка , 36 байт

{x,n:n^recur(*tile(x,c(1)),sum@c,x)}

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

объяснение

{x,n:n^recur(*tile(x,c(1)),sum@c,x)}
{x,n:                              }   lambda taking parameters `x` and `n`
     n^                                take the first `n` terms of...
       recur(                     )        a recursive function
             *tile(x,c(1)),                whose seed is `x` `1`s
                           sum@c,          taking the sum of each window
                                 x         with a window size of `x`
Конор О'Брайен
источник
0

Japt , 18 байт

@ZsVn)x}gK=Vì1;K¯U

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

Объяснение:

         K=Vì1        :Start with n 1s in an array K
@      }gK            :Extend K to at least x elements by setting each new element to:
      x               : The sum of
 ZsVn                 : The previous n elements
              ;       :Then
               K¯U    :Return the first n elements of K
Камил Дракари
источник