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

(Следующее объяснение последовательности для этого вызова предполагает, что символы в последовательности являются 0и 1.)

Рекурсивное определение последовательности Туэ-Морса таково , что

T_0 = 0
T_2n = T_n
T_2n+1 = 1 - T_n

Более прямое определение является то , что последовательность из , 0чтобы 2**m-1и 2**m to 2**(m+1)-1бинарные комплементы. Так 0следует 1, 01следует 10, 0110следует 1001, и, пропустив вперед немного, 0110100110010110следует 1001011001101001.

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

Примеры

>>> tm_01(20)
01101001100101101001
>>> tm_ab(42)
abbabaabbaababbabaababbaabbabaabbaababbaab
>>> tm_paren(37)
())()(())(()())()(()())(())()(())(()(
>>> tm_space_star(12)
 ** *  **  *
>>> tm_01(0)
                # to show that this is a valid input

правила

• На входе будет любое неотрицательное целое число. Вы можете предположить, что все входные данные действительны.

• Выходными данными должны быть первые nэлементы последовательности Туэ-Морса с использованием любых удобных символов. Если вам нравится, вы также можете добавить разделитель. В моих примерах у меня нет. Примечание. Это правило разрешает списки (например, списки Python), так как ,это допустимый разделитель, и я не против начальных или конечных символов, таких как [и ]в выходных данных.

• Это код гольф, поэтому выигрывает наименьшее количество байтов.

Как всегда, если проблема неясна, пожалуйста, дайте мне знать. Удачи и хорошего гольфа!

Каталог

var QUESTION_ID=65549;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='<h1>'+c.body.replace(OVERRIDE_REG,'')+'</h1>'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery('<a>'+lang+'</a>').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}

body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table>

Pyth, 6 байт

xMjR2Q

Попробуйте онлайн: демонстрация

Основано на решении @ThomasKwa и вариации @FryAmTheEggman.

Он использует следующий формуляр: i-м цифра в последовательности Туэ-Морса: xor(digits of i in base 2).

Объяснение:

xMjR2Q   implicit: Q = input number
  jR2Q   convert each number in [0, 1, ..., Q-1] to its binary digits
xM       xor each binary list

CJam, 17 9 байтов

ri{2b:^}/

или

ri,2fb::^

Проверьте это здесь.

объяснение

Это использует альтернативное определение, данное в Википедии, основанное на четности числа 1s в двоичном представлении n.

ri   e# Read input and convert to integer n.
{    e# For each i from 0 to n-1...
  2b e#   Convert i to base 2.
  :^ e#   Fold XOR over the bits to compute the parity of the number of 1s.
}/

Альтернативные виды использования решений , ,чтобы превратить в nявном виде в диапазон [0 ... n-1]перед использованием операторов инфиксных для вычисления двоичных представлений и XOR без необходимости блока.

Бонусные Решения

Вот некоторые решения, основанные на других определениях. Если есть два решения, более короткое из них очень быстро взорвет память (потому что предварительное вычисление генерирует 2^nбиты перед усечением n).

Как L-система с 0 --> 01и 1 --> 10:

ri_2mL2,\{2,aA+f=s:~}*<
ri_2,\{2,aA+f=s:~}*<

Отрицая и добавляя предыдущую часть:

ri_2mL2,\{_:!+}*<
ri_2,\{_:!+}*<

Используя рекуррентное отношение, данное в задаче, используйте divmodXOR для различения двух рекурсивных определений:

ri{Ta{2md\j^}j}/

(Хотя, конечно, это рекуррентное отношение - это просто другой способ выразить последовательность Туэ-Морса как четность 1 бита в двоичном представлении n.)

Дьялог АПЛ, 8 7 байт

≠⌿⍴∘2⊤⍳

Это монадическая последовательность, которая ожидает начало индекса 0 ( ⎕IO←0). Эквивалентная функция , не поезд {≠⌿(⍵⍴2)⊤⍳⍵}.

Объяснение:

      ⍳      List of numbers from 0 to (input-1)
  ⍴∘2        (input) copies of 2
     ⊤       Convert all the elements in ⍳ to base 2 to (input) digits
≠⌿           Reduce over the first axis by not-equal

Выход - разделенный пробелами список 0и 1. Попробуй это здесь .

Mathematica, 35 21 байт

Mathematica имеет встроенную последовательность Туэ-Морса!

Array[ThueMorse,#,0]&

Оригинальный ответ:

#&@@@DigitCount[Range@#-1,2]~Mod~2&

LabVIEW, 15 примитивов LabVIEW

сейчас как супер модный гиф с зондом

J, 12 11 байт

@ MartinBüttner сохранил байт.

~:/@#:"0@i.

Это монадическая (то есть унарная) функция, используемая следующим образом:

   f =: ~:/@#:"0@i.
   f 10
0 1 1 0 1 0 0 1 1 0

объяснение

Я использую альтернативное определение, что T _n - это четность числа 1-бит в двоичном представлении n.

~:/@#:"0@i.  Input is n.
~:/          Output is XOR folded over
   @#:       the binary representations of
      "0     each element of
        @i.  integers from 0 to n-1.

Pyth, 11 10 байт

m%ssM.Bd2Q

Выходы в виде списка в стиле Python.

Japt , 29 11 байт

Uo ®¤¬r@X^Y

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

Выводится напрямую как массив, который сохраняет около 4 байтов.

Неуправляемый и объяснение

Uo ®   ¤  ¬ r@  X^Y
Uo mZ{Zs2 q rXY{X^Y}}
        // Implicit: U = input number
Uo      // Create an array of integers in the range `[0, U)`. 
mZ{Zs2  // Map each item Z in this range to Z.toString(2),
q rXY{  //  split into chars, and reduced by
X^Y}}   //   XORing.
        //  This returns (number of 1s in the binary string) % 2.
        // Implicit: output last expression

Редактировать: теперь вы можете использовать следующий 8-байтовый код (недействительно; функция опубликована после этого вызова):

Uo ®¤¬r^

Haskell, 39 36 35 байт

take<*>(iterate([id,(1-)]<*>)[0]!!)

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

Как это работает: начните с [0]и примените время x ++ invert x-функции n. Возьмите первые nэлементы из полученного списка. Благодаря лени Хаскелла на nсамом деле рассчитываются только первые элементы. Примечание: первый <*>находится в контексте функции, второй - в контексте списка.

С GHC v8.4 (который не был доступен во время испытания) есть 34-байтовое решение:

take<*>(iterate(id<>map(1-))[0]!!)

Изменить: -3 соотв. -4 байта благодаря @Laikoni. -1 байт благодаря @ Örjan Johansen.

Haskell, 54 байта

Менее компактный, чем решение nimi, но я не хотел отказывать вам в этой части функциональной путаницы в коде. Работает на любую пару объектов; например, вы можете заменить (f 0.f 1)на(f 'A'.f 'B') .

На основании определения, что первые 2 ⁿ цифр следуют той же последовательности цифр в обратном порядке. Что мы делаем, это строим два списка бок о бок; один для последовательности, один для обратной. Мы постоянно добавляем все более длинные части одного списка в другой.

Реализация состоит из трех определений:

t=(f 0.f 1)t
f c=flip take.(c:).g 1
g n l=l n++g(n+n)l

Функция tпринимает любое число и возвращает последовательность Туэ-Морса этой длины. Две другие функции являются помощниками.

• Функция fпредставляет собой любой список; f 0для последовательности, f 1для обратного.
• Функция gзаботится о добавлении все более длинных повторений одного списка в другой.

Скрипка: http://goo.gl/wjk9S0

Пари / ГП , 33 байта

n->[sumdigits(x,2)%2|x<-[0..n-1]]

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

Бурлеск, 21 байт

{0}{J)n!_+}400E!jri.+

Примеры:

blsq ) "20"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1}
blsq ) "42"{0}{J)n!_+}400E!jri.+
{0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1}

Объяснение:

{0}      -- setup
{J)n!_+} -- duplicate, map invert, concatenate
400E!    -- do 400 times (this will eventually run
            out of memory).
jri.+    -- take n elements

Без jri.+части вам не хватит памяти (потому что она вычислит последовательность Морзе с невероятно большим числом длины ). Но так как Бурлеск ленив, просто попросить первый n-элемент будет работать в любом случае.

K5, 27 13 байт

{x#((log x)%log 2){x,~x}/0}

Вычислить последовательность довольно просто, проблема состоит в том, чтобы избежать слишком большого количества вычислений. Мы можем признать, что простое расширение последовательности дает нам последовательность строк, которые являются последовательными степенями длины два. Взяв логарифмическую базу 2 для ввода и округления, мы получим достаточно для работы, а затем мы можем сократить ее до соответствующего размера:

  {x#((log x)%log 2){x,~x}/0}'(20 42 37 12 0)
(0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1
 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0
 0 1 1 0 1 0 0 1 1 0 0 1
 ())

Редактировать:

Решение на основе четности:

~=/'(64#2)\'!

В бою:

  ~=/'(64#2)\'!20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

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

Октава, 33 31 байт

Сохранено 2 байта благодаря Томасу Ква.

@(n)mod(sum(dec2bin(0:n-1)'),2)

Perl 5, 62 49 байт

Да, не лучший язык для этого, но мне все еще нравится, как он вышел. Требуется 5.14+ для /rи say.

sub{$_=0;$_.=y/01/10/r while$_[0]>length;say substr$_,0,$_[0]}

Используя определение четности, требуется 5.12+ для say:

sub{say map{sprintf("%b",$_)=~y/1//%2}0..$_[0]-1}

Пролог (SWI), 115 байт

Код:

N*X:-N>1,R is N//2,R*Y,X is(N mod 2)xor Y;X=N.
p(N):-M is N-1,findall(E,between(0,M,E),L),maplist(*,L,K),write(K).

Разъяснение:

N*X:-                                 % Calculate Thue-Morse number at index N
     N>1,                             % Input is bigger than 1
     R is N//2,R*Y,X is(N mod 2)xor Y % Thue-Morse digit at index N is binary digits of N xor'ed
     ;X=N.                            % OR set X to N (end of recursion)
p(N):-
      M is N-1,                       % Get index of Nth number
      findall(E,between(0,M,E),L),    % Make a list of number 0->N-1
      maplist(*,L,K),                 % Map * on list L producing K
      write(K).                       % Print K

Пример:

p(20).
[0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1]

Попробуйте онлайн здесь

Сетчатка , 70 69 байт

Используя определение как L-систему с начальным словом 0и продукцией 0 --> 01и 1 --> 10.

^
0;
(T`d`ab`^(.)+;(?!(?<-1>.)+$)
a
01
)`b
10
!`^(?=.*;(.)+)(?<-1>.)+

Ввод принимается в одинарном .

Вы можете запустить код из одного файла с помощью -s флагом. Или просто попробуйте онлайн.

объяснение

^
0;

Зависит 0;от ввода, где 0находится начальное слово и ;является просто разделителем.

(T`d`ab`^(.)+;(?!(?<-1>.)+$)

(Указывает на то, что это начало цикла (который повторяется до тех пор , пока цикл прекращает изменение строки). Эта стадия сама превращается 0и 1в aи bсоответственно (потому что dрасширяется до 0-9). Это происходит до тех пор, пока текущее слово (длина которого измеряется с помощью (.)+короче, чем входное значение (т. Е. До тех пор, пока мы не можем прочитать конец строки, сопоставив столько 1s, сколько мы имеем в слове).

a
01

Заменить a( заменить 0) на 01.

)`b
10

Заменить b( заменить 1) на 10. Это также конец цикла. Цикл завершается, когда условие на этапе транслитерации не выполняется, потому что тогда все 0s и1 s останутся неизменными, а на двух других этапах ничего не будет найдено.

!`^(?=.*;(.)+)(?<-1>.)+

Последний шаг - обрезать слово до длины ввода. На этот раз мы измеряем длину ввода с (.)+предвкушением. Затем мы сопоставляем столько символов в начале строки.

Руби, 33

->n{n.times{|i|p ("%b"%i).sum%2}}

Звоните так:

f=->n{n.times{|i|p ("%b"%i).sum%2}}
f[16]

Использует тот факт, что четность двоичных чисел образует последовательность thue-morse.

Символ разделителя - перевод строки. Преобразует числоi в двоичную строку, затем вычисляет сумму всех кодов ASCII по модулю 2.

Если символ новой строки не является допустимым разделителем, следующий не имеет разделителя для дополнительных 2 байтов:

->n{n.times{|i|$><<("%b"%i).sum%2}}

MATL , 9 байт

Этот язык был разработан после испытания .

Подход 1: 13 байтов

Это создает последовательность путем объединения отрицательных копий блоков увеличивающегося размера.

itBFw"t~h]w:)

пример

>> matl itBFw"t~h]w:)
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

объяснение

i           % input number, say "N"
tB          % duplicate and convert to binary. Produces a vector
F           % initialize sequence to "false"
w           % swap to bring vector to top
"           % for loop. There will be at least log2(N) iterations
  t~h       % duplicate, negate, concatenate
]           % end for
w           % swap
:)          % index with vector 1, 2, ..., N

Подход 2: 9 байт

Это использует тот же подход, что и ответ Алефальфы .

i:1-B!s2\

пример

>> matl i:1-B!s2\
> 20
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1

объяснение

i           % input "N" 
:1-         % create vector 0, 1, ..., N-1
B           % convert to binary
!           % tranpose
s           % sum
2\          % modulo 2

C 88 83 байта

Рассчитывает паритет для каждой отдельной позиции.

i,j;main(int c,char**a){for(;i<atoi(a[1]);putchar(c))for(c=48,j=i++;j;j&=j-1)c^=1;}

Скрипка: http://goo.gl/znxmOk

Желе , 4 байта

ḶB§Ḃ

Обратите внимание, что этот вызов старше, чем желе.

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

Как это работает

ḶB§Ḃ  Main link. Argument: n (integer)

Ḷ     Unlength; yield [0, ..., n-1].
 B    Compute the binary representation of each integer in the range.
  §   Take the sum of each binary representation.
   Ḃ  Take the LSB of each sum.

Матлаб, 42

Я использую тот факт, что это то же самое, что и начало, 0а затем повторение шага добавления дополнения к текущей серии, nраз.

t=0;for k=1:input('');t=[t;~t];end;disp(t)

𝔼𝕊𝕄𝕚𝕟, 11 символов / 23 байта (неконкурентные)

Ⓐïⓜ_ⓑⓢĊ⇀$^_

Try it here (Firefox only).

Круги сильны с этим.

Баш, 71 66 байт

На основании определения, что первые 2 ⁿ цифр следуют той же последовательности цифр в обратном порядке.

x=0;y=1;while((${#x}<$1));do z=$x;x=$x$y;y=$y$z;done;echo ${x::$1}

$1 В качестве параметра указывается желаемое количество цифр.

Скрипка: http://goo.gl/RkDZIC

Пакетный, 115 + 2 = 117 байт

На основании ответа Bash.

@echo off
set x=0
set y=1
set z=0
:a
set x=!x!!y!
set y=!y!!z!
set z=!x:~0,%1!
if !z!==!x! goto a
echo !z!

Нуждается в дополнительном /Vвызове, чтобы разрешить использование !s.

ES6, 53 байта

f=(i,x="0",y=1)=>x.length<i?f(i,x+y,y+x):x.slice(0,i)

Рекурсия казалась проще, чем цикл.

Par , 8 байт

✶u[Σ_✶¨^

Объяснение:

✶          parse implicit input number
 u         range [0..n-1]
  [        map:
   Σ           convert to binary
    _✶         get digit list
      ¨^       fold with xor

Выводит что-то вроде:

(0 1 1 0 1 0 0 1)

Математика ++ , 86 байт

Использует 0.0\nдля 0 и 1.0\nдля 1

?>n
3*!!(n-m)>$
m>a
0>k
6+6*!a>$
9-2*!(a%2)>$
a/2>a
5>$
(a-1)/2>a
!k>k
5>$
k
m+1>m
2>$

Arcyóu , 50 55 байт

Мне пришлось добавить 5 байт, чтобы заставить его работать правильно :(

(f i(_(#(l)))(r b^(@(> i 0)(pg 0(% i 2)(: i(#/ i 2))))0

Пояснение (с псевдокодом Pythonesque вдоль стороны:

(f i (_ (# (l)))       ; For i in range(int(input())):
  (r b^                ; Reduce with binary xor
    (@ (> i 0)         ; While i > 0:
      (pg 0            ; Return first of its arguments
        (% i 2)        ; i mod 2
        (: i (#/ i 2)) ; i //= 2
      )
    )
    0                  ; Default reduce argument of 0 for the first bit in the sequence

Common Lisp , 50 байт

(lambda(n)(dotimes(i n)(princ(mod(logcount i)2))))

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