Рекурсивное двоичное описание
Недавно я внес свой первый вклад в OEIS, расширив и добавив b-файл в последовательность A049064 . Последовательность начинается с 0
, а затем следующие значения выводятся из «двоичного описания» последнего элемента.
Например, второй член будет 10
, потому что 0
в первом элементе был один . Третий срок будет 1110
, потому что был один 1
и один 0
. Четвертый будет 11110
. потому что есть три ( 11
в двоичном виде!) 1
и один 0
. Ниже приводится разбивка пятого слагаемого, чтобы прояснить этот процесс:
> 11110
> 1111 0 (split into groups of each number)
> 4*1 1*0 (get count of each number in each group)
> 100*1 1*0 (convert counts to binary)
> 100110 (join each group back together)
И вот пример перехода с 6-го на 7-й семестр:
> 1110010110
> 111 00 1 0 11 0
> 3*1 2*0 1*1 1*0 2*1 1*0
> 11*1 10*0 1*1 1*0 10*1 1*0
> 111100111010110
Вы можете проверить ссылочную программу φ Я сделал для расчета условий.
Твоя работа
Вам необходимо создать программу или функцию, которая принимает число n
через стандартные аргументы ввода или функции и выводит последовательность от 1st
термина к (n+1)th
термину, разделенную новой строкой. Если вы хотите взглянуть на нижние цифры, вы можете обратиться к b-файлу со страницы OEIS. Тем не менее, ваша программа / функция должна поддерживать 0 <= n <= 30
, то есть до 31-го семестра. Это не маленький подвиг, так как δA049064(30)
более 140 000 цифр . Если вы хотите узнать, каким должен быть 31-й срок, я положил его на Пастебина .
Пример ввода / вывода
func(10)
0
10
1110
11110
100110
1110010110
111100111010110
100110011110111010110
1110010110010011011110111010110
1111001110101100111001011010011011110111010110
1001100111101110101100111100111010110111001011010011011110111010110
func(0)
0
func(3)
0
10
1110
11110
Существует только одно правило: никаких стандартных лазеек!
Это код-гольф , поэтому выигрывает самое низкое число байтов.
φ - Gist можно найти здесь , а демонстрация ideone здесь .
δ - Просто на тот случай, если вам интересно, мои оценки по длине сотого семестра оценивают его примерно в 3,28х10 250 символов в длину, что будет достаточно для любого.
[0]\n[1, 0]\n[1, 1, 1, 0]\n...
Ответы:
CJam,
1817 байтовСпасибо @ MartinBüttner за игру в один байт!
Попробуйте онлайн в интерпретаторе CJam .
Как это устроено
источник
Pyth,
1817 байтовПопробуйте онлайн: демонстрация
Спасибо @isaacg за сохранение одного байта.
Объяснение:
При этом используется тот факт, что 0 и 1 в двоичном виде также 0 и 1.
источник
V
вместо.u
:J]0VQjk~JsjR2srJ8
Python 2,
125116110 байтБлагодаря @ Sp3000 и 5 байтам удалось сэкономить 1 байт, удалив избыточный
int
вызов.Старая версия:
Благодаря @ Vioz- сэкономлено много-много байтов!
Оригинальная версия:
источник
Рубин,
807269 байтКак функция:
Назовите это, например, с помощью:
f[6]
источник
->m{l=?0;0.upto(m){puts l;l.gsub!(/1+|0+/){$&.size.to_s(2)+$&[0]}}}
upto
и!
- Спасибо :)Python 2, 102 байта
Каким-то образом сочетание
itertools
длинныхre
иgroupby
возвращаемыхgrouper
объектов означает, что использование регулярных выражений немного короче ...источник
Кобра - 128
источник
Haskell,
136130 байтисточник