Начни с

18

Учитывая строго положительное целое число n , выполните следующие действия:

  1. Создайте массив A с n 1 s.
  2. Если A имеет только один элемент, завершите. В противном случае, начиная с первого элемента, замените каждую пару A его суммой, оставив последний элемент как есть, если длина A нечетная, и повторите этот шаг.

Выходные данные должны содержать состояние A после каждого шага в порядке от первого шага до последнего. Использование стандартных лазеек запрещено. Это задача кода-гольфа , поэтому выигрывает решение с наименьшим количеством байтов на каждом языке.

Контрольные примеры

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

Входные данные: 1

[1]

Входные данные: 4

[1, 1, 1, 1]
[2, 2]
[4]

Входные данные: 13

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[2, 2, 2, 2, 2, 2, 1]
[4, 4, 4, 1]
[8, 5]
[13]

Входные данные: 15

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[2, 2, 2, 2, 2, 2, 2, 1]
[4, 4, 4, 3]
[8, 7]
[15]
code-golf arithmetic Эрик Outgolfer
источник
Могу ли я скопировать эту идею вопросов в обратном порядке? Задав число n, выведите пошагово A и так далее, пока не достигнете n 1s?
pixma140
9
@ pixma140 Это было бы по сути той же проблемой, только с обратным выводом. Модификация тривиальна.
Эрик Outgolfer

Ответы:

4

MATL , 10 байт

:g`t2estnq

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

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

:     % Input n (implicit). Range [1 2 ... n]
g     % Convert to logical. Gives [1 1 ... 1]
`     % Do...while
  t   %   Duplicate
  2   %   Push 2
  e   %   Reshape as 2-column matrix, in column-major order, padding with 0 if needed
  s   %   Sum of each column
  t   %   Duplicate
  n   %   Number of elements
  q   %   Subtract 1. This will be used as loop condition
      % End (implicit). If top of the stack is not zero run new iteration
      % Display stack, bottom to top (implicit)
Луис Мендо
источник
4

Python 3 , 57 байт

def f(i,j=1):print(i//j*[j]+[i%j][:i%j]);i>j and f(i,j*2)

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

Python 2 , 51 байт

def f(i,j=1):print i/j*[j]+[i%j][:i%j];i>j>f(i,j*2)

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

Всего -6 байт благодаря tsh

Рекурсивная функция. Для каждого шага он формирует список степеней 2, так что сумма меньше или равна заданному целому числу. Затем он добавляет остаток, если он больше, чем 0.

Jitse
источник
1
Python 3 61 байт: def f(i,j=1):l=i//j*[j]+[i%j][:i%j];print(l);i>j and f(i,j*2); Python 2 55 байт:def f(i,j=1):l=i/j*[j]+[i%j][:i%j];print l;i>j>f(i,j*2)
tsh
@tsh Конечно, спасибо! i>jне работал в моем предыдущем решении, и я забыл попробовать его потом.
Джитс
3

R 65 байт

-1 байт благодаря Джузеппе.

n=scan();while(T<2*n){cat(rep(+T,n%/%T),if(n%%T)n%%T,"\n");T=2*T}

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

%/%%%k=2^in%/%kkn%%k2N-1

Здесь я использую Tвместо k, так как он инициализируется как TRUEпреобразованный в 1. Мне все еще нужно печатать +Tвместо того, Tчтобы избежать вектора TRUEs в выводе.

Робин Райдер
источник
Ударь меня примерно на 5 минут и почти на 60 байтов ... Но Джузеппе прав, последний шаг не выводится.
Sumner18
@ Sumner18 Нужно исправить сейчас.
Робин Райдер
+TкорочеT+0
Джузеппе
@ Giuseppe Спасибо, я знал, что что-то забыл.
Робин Райдер
3

Pyth , 10 байт

.u+McN2m1

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

.u          # Apply until a result is repeated, return all intermediate steps: lambda N,Y:
  +M        # map by + (reduce list on +):
    cN2     # chop N (current value) into chunks of 2, last one is shorter if needed
       m1Q  # map(1, range(Q)) (implicit Q = input)

-1 байт благодаря FryAmTheEggman

ar4093
источник
2

JavaScript, 55 байт

f=(n,t=1,r=n)=>r>t?t+[,f(n,t,r-t)]:n>t?r+`
`+f(n,t+t):r

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

Это в основном гольф-версия следующих кодов:

function f(n) {
  var output = '';
  t = 1;
  for (t = 1; ; t *= 2) {
    for (r = n; r > t; r -= t) {
      output += t + ',';
    }
    output += r;
    if (n <= t) break;
    output += '\n';
  }
  return output;
}
ТТГ
источник
2

Брахилог , 17 байт

;1j₍ẹẉ₂{ġ₂+ᵐ}ⁱ.ẉȮ

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

Как бы ужасно это ни было, я все еще чувствую себя немного умно при использовании .ẉȮ: очевидный способ напечатать что-то, затем проверить, будет ли его длина 1 ẉ₂l1, ẉ₂~gили ẉ₂≡Ȯ, где ≡необходим последний в последнем, потому что ẉ₂объединяет его ввод и вывод до того, как он их напечатает, и Ȯпредварительно ограничен списком длины 1, поэтому объединение завершается неудачно, если входные данные не являются списком длины 1. В конце предиката эту функцию ẉ₂можно обойти, однако используя выходную переменную вместо подписки ẉ: .ẉȮсначала объединяет ее вход с выходной переменной, затем печатает выходную переменную, и только после этого объединяет выходную переменную с Ȯ.

Несвязанная строка
источник
2

Stax , 10 байт

Çë⌐ⁿ┤5π»Å╡

Запустите и отладьте его

Процедура:

  1. Создайте диапазон на основе 0.
  2. Повторно делите пополам каждый элемент, пока все элементы не станут равны нулю.
  3. Рассчитайте длины серий для каждого уникального массива.

Аннотированный источник:

r       main:[0 .. 5] 
{{hmgu  main:[[0 .. 5], [0, 0, 1, 1, 2, 2], [0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 0]] 
m:GJ    main:"1 1 1 1 1 1"
рекурсивный
источник
1

Древесный уголь , 19 байт

ＮθＩＥ↨⊖⊗θ²Ｅ⪪Ｅθ¹Ｘ²κＬλ

Попробуйте онлайн! Ссылка на подробную версию кода. Использует формат вывода Charcoal по умолчанию, который состоит из одного числа в строке, с подрешетками с двойным интервалом друг от друга. Объяснение:

Ｎθ                  Input `n` into a variable
       θ            `n`
      ⊗             Doubled
     ⊖              Decremented
    ↨   ²           Converted to base 2 (i.e. ceil(log2(input)))
   Ｅ                Map
           Ｅθ¹      List of `1`s of length `n`
          ⪪         Split into sublists of length
               ²    Literal `2`
              Ｘ     To power
                κ   Loop index
         Ｅ          Map over each sublist
                 Ｌλ Take the length
  Ｉ                 Cast to string for implicit print
Нил
источник
1

Perl 6 , 38 байт

{1 xx$_,*.rotor(2,:partial)>>.sum...1}

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

Есть некоторый ярлык для частичного ротора, который я сейчас не помню ...

Объяснение:

{                                    }  # Anonymous code block
                                 ...    # Return a sequence
 1 xx$_,            # Starting with a list of 1s with input length
        *           # Where each element is
         .rotor(2,:partial)        # The previous list split into chunks of 2 or less
                           >>.sum  # And each chunk summed
                                    1  # Until the list is length 1
Джо Кинг
источник
1

Haskell , 75 байт

g.pure
g x|x!!0<2=[x]|1>0=(g$(\z->filter(0/=)[-div(-z)2,div z 2])=<<x)++[x]

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

Работает в обратном порядке из списка [n] пока не достигнет списка только из них.

Идя вперед, я мог бы получить 80 байт , используя chunksofот Data.List.Split:

import Data.List.Split
f x=g$1<$[1..x]
g[n]=[[n]]
g x=x:(g$map sum$chunksOf 2 x)

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

Джо Кинг
источник
0

Ом v2 , 8 байт

@Dv·Ω2σΣ

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

Если вывод в научной записи разрешен, в противном случае:

Ом v2 , 9 байт

@Dv·Ω2σΣì

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

Cinaski
источник
Если научные числа обозначений на самом деле являются натуральными типами чисел (например, числами с плавающей запятой) в Оме, то, конечно, это разумно.
Эрик Outgolfer
0

Gaia , 12 байт

ċ)¦⟨:q2/Σ¦⟩ª

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

ċ)¦		| generate array of n 1's (really, generate array of n 0's and increment each)
   ⟨      ⟩ª	| do the following until you get to a fixed point:
    :q		| dup and print with a newline
      2/	| split into groups of 2, with last group possibly being smaller
	Σ¦	| take the sum
Giuseppe
источник