Zadanie

Znajdź zestaw liczb w taki sposób, że reprezentacja binarna zawiera dwa lub więcej przebiegów 1oddzielonych co najmniej jednym 0.

Na przykład liczby o długości 4 bitów:

 0 0000        (no ones)
 1 0001        (only one run)
 2 0010        (only one run)
 3 0011        (only one run)
 4 0100        (only one run)
 5 0101 Valid
 6 0110        (only one run)
 7 0111        (only one run)
 8 1000        (only one run)
 9 1001 Valid
10 1010 Valid
11 1011 Valid
12 1100        (only one run)
13 1101 Valid
14 1110        (only one run)
15 1111        (only one run)

Wkład

Liczba całkowita dostarczona do aplikacji za pośrednictwem niektórych danych wejściowych z zakresu 3 .. 32. Jest to maksymalna liczba bitów do zliczenia.

Dane wejściowe nwskazują, że liczby muszą zostać zbadane.0 .. 2n-1

Wydajność

Ograniczona (do wyboru) lista wszystkich liczb spełniających kryteria. Liczby należy przedstawić w kolejności numerycznej. Dopuszczalny jest dodatkowy ogranicznik końcowy. []Dopuszczalne są również załączniki struktury danych (np. I podobne).

Przykład

Input: 3
Output: 5

Input: 4
Output: 5, 9, 10, 11, 13

Input: 5
Output: 5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29

To jest golf golfowy - wygrywa odpowiedź z najmniejszą ilością bajtów.

Pyth, 12 bajtów

f<2r.BT8U^2Q

Wypróbuj online.

Pomysł

Binarna reprezentacja dowolnej liczby dodatniej zawsze zaczyna się od ciągu 1 s, po którym ewentualnie następują inne przemienne przebiegi od 0 do 1 s. Jeśli istnieją co najmniej trzy oddzielne przebiegi, dwa z nich są gwarantowane przez 1 s.

Kod

              (implicit) Store the evaluated input in Q.
         ^2Q  Calculate 2**Q.
f       U     Filter; for each T in [0, ..., 2**Q-1]:
    .BT         Compute T's binary representation.
   r   8        Perform run-length encoding.
                This returns a list of character/run-length pairs.
 <2             Discard the trailing two pairs.
                This returns a non-empty array if there are more than 2 runs.
              Keep T if the array was truthy (non-empty).

Python, 48

lambda n:[i for i in range(2**n)if'01'in bin(i)]

Bardzo się nad tym zastanawiałem. Musimy tylko sprawdzić, czy zawiera to rozszerzenie binarne '01'.

Aby były dwa biegi jednego, ten po prawej musi być poprzedzony znakiem 0. Jeśli jest tylko jeden bieg, nie będzie żadnych wiodących 0, więc tak się nie stanie.

Stara odpowiedź:

lambda n:[i for i in range(2**n)if len(set(bin(i).split('0')))>2]

Reprezentacja binarna Pythona działa tutaj bardzo dobrze. Liczba binarna jest zapisana jak bin(9)=='0b10110'. Podział na '0'wyniki w postaci listy

• Puste ciągi znaków po lewej stronie inicjału 0, między dowolnymi dwoma kolejnymi 0i po prawej stronie dowolnego finału0
• Litera, bpo której następuje jeden lub więcej wiodących
• Ciągi 1, które nie prowadzą

Dwie pierwsze kategorie zawsze istnieją, ale ostatnia istnieje tylko wtedy, gdy istnieje taka 1seria, która nie zawiera wiodącej '1', a więc tylko wtedy, gdy jest więcej niż jedna seria 1. Wystarczy więc sprawdzić, czy lista zawiera więcej niż 2odrębne elementy.

Python 3.5 zapisuje 2 znaki poprzez rozpakowanie {*_}zamiast set(_).

Ruby, 44 40 38 znaków

^{przekreślone 44 jest nadal regularne 44; (}

->n{(0..2**n).select{|x|/01/=~'%b'%x}}

Anonimowa funkcja (właściwie proc), która przyjmuje liczbę całkowitą i zwraca tablicę.

Używa wyrażenia regularnego /10+1/: a 1, co najmniej jeden 0, a następnie inny 1. @histocrat wskazuje, że jeśli 01jest gdziekolwiek w ciągu, musi być 1gdzieś przed nim.

Julia, 43 41 bajtów

n->filter(i->ismatch(r"01",bin(i)),1:2^n)

Tworzy to nienazwaną funkcję, która akceptuje liczbę całkowitą i zwraca tablicę. Wykorzystuje sztuczkę wyrażenia regularnego histokratów (stosowaną w odpowiedzi Doorknob), gdzie 01będzie pasować tylko, jeśli jest poprzedzająca 1.

Nie golfowany:

function f(n::Int)
    # Take the integers from 1 to 2^n and filter them down to
    # only those such that the binary representation of the integer
    # matches the regex /01/.
    filter(i -> ismatch(r"01", bin(i)), 1:2^n)
end

Matlab, 79 68 64 59

Chodzi o interpretację liczby binarnej jako tablicy zer i jedynek, a następnie obliczenie bezwzględnej różnicy między każdą parą sąsiadów. Jeśli mamy dwa lub więcej razy różnicę 1, to oczywiście mamy ciąg dwóch lub więcej. Zauważ, że działa to tylko wtedy, gdy reprezentujemy liczbę binarną bez zer wiodących.

@(n)find(arrayfun(@(k)sum(~~diff(dec2bin(k)+0))>1,1:2^n-1))

Stare wersje:

k=1:2^input('')-1;k(arrayfun(@(k)sum(~~diff(dec2bin(k)+0))>1,k))

for k=1:2^input('')-1;if sum(~~diff(dec2bin(k)+0))>1;disp(k);end;end

for k=1:2^input('')-1;if sum(~~conv(dec2bin(k)+0,[-1,1],'v'))>1;disp(k);end;end

JavaScript (ES7), 89 85 72 69 62 bajtów

Święta krowa, tworzenie zakresów w JS nie jest łatwe. Być może byłby krótszy z rzeczywistą forpętlą. Nie, skłamałem; to właściwie trochę dłużej. No cóż. Chyba będę musiał zadowolić się zapisanymi 27 bajtami. (7 dzięki Mwr247!)

x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]

Działa poprawnie w najnowszych wersjach Firefox, ale prawdopodobnie nie w żadnej innej przeglądarce. Wypróbuj to:

<!--                               Try the test suite below!                              --><strong id="bytecount" style="display:inline; font-size:32px; font-family:Helvetica"></strong><strong id="bytediff" style="display:inline; margin-left:10px; font-size:32px; font-family:Helvetica; color:lightgray"></strong><br><br><pre style="margin:0">Code:</pre><textarea id="textbox" style="margin-top:5px; margin-bottom:5px"></textarea><br><pre style="margin:0">Input:</pre><textarea id="inputbox" style="margin-top:5px; margin-bottom:5px">5</textarea><br><button id="testbtn">Test!</button><button id="resetbtn">Reset</button><br><p><strong id="origheader" style="font-family:Helvetica; display:none">Original Code Output:</strong><p><div id="origoutput" style="margin-left:15px"></div><p><strong id="newheader" style="font-family:Helvetica; display:none">New Code Output:</strong><p><div id="newoutput" style="margin-left:15px"></div><script type="text/javascript" id="golfsnippet">var bytecount=document.getElementById("bytecount");var bytediff=document.getElementById("bytediff");var textbox=document.getElementById("textbox");var inputbox=document.getElementById("inputbox");var testbtn=document.getElementById("testbtn");var resetbtn=document.getElementById("resetbtn");var origheader=document.getElementById("origheader");var newheader=document.getElementById("newheader");var origoutput=document.getElementById("origoutput");var newoutput=document.getElementById("newoutput");textbox.style.width=inputbox.style.width=window.innerWidth-50+"px";var _originalCode="x=>[for(a of Array(1<<x).keys())if(/01/.test(a.toString(2)))a]";function getOriginalCode(){if(_originalCode!=null)return _originalCode;var allScripts=document.getElementsByTagName("script");for(var i=0;i<allScripts.length;i++){var script=allScripts[i];if(script.id!="golfsnippet"){originalCode=script.textContent.trim();return originalCode}}}function getNewCode(){return textbox.value.trim()}function getInput(){try{var inputText=inputbox.value.trim();var input=eval("["+inputText+"]");return input}catch(e){return null}}function setTextbox(s){textbox.value=s;onTextboxChange()}function setOutput(output,s){output.innerHTML=s}function addOutput(output,data){output.innerHTML+='<pre style="background-color:'+(data.type=="err"?"lightcoral":"lightgray")+'">'+escape(data.content)+"</pre>"}function getByteCount(s){return(new Blob([s],{encoding:"UTF-8",type:"text/plain;charset=UTF-8"})).size}function onTextboxChange(){var newLength=getByteCount(getNewCode());var oldLength=getByteCount(getOriginalCode());bytecount.innerHTML=newLength+" bytes";var diff=newLength-oldLength;if(diff>0){bytediff.innerHTML="(+"+diff+")";bytediff.style.color="lightcoral"}else if(diff<0){bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgreen"}else{bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgray"}}function onTestBtn(evt){origheader.style.display="inline";newheader.style.display="inline";setOutput(newoutput,"");setOutput(origoutput,"");var input=getInput();if(input===null){addOutput(origoutput,{type:"err",content:"Input is malformed. Using no input."});addOutput(newoutput,{type:"err",content:"Input is malformed. Using no input."});input=[]}doInterpret(getNewCode(),input,function(data){addOutput(newoutput,data)});doInterpret(getOriginalCode(),input,function(data){addOutput(origoutput,data)});evt.stopPropagation();return false}function onResetBtn(evt){setTextbox(getOriginalCode());origheader.style.display="none";newheader.style.display="none";setOutput(origoutput,"");setOutput(newoutput,"")}function escape(s){return s.toString().replace(/&/g,"&amp;").replace(/</g,"&lt;").replace(/>/g,"&gt;")}window.alert=function(){};window.prompt=function(){};function doInterpret(code,input,cb){var workerCode=interpret.toString()+";function stdout(s){ self.postMessage( {'type': 'out', 'content': s} ); }"+" function stderr(s){ self.postMessage( {'type': 'err', 'content': s} ); }"+" function kill(){ self.close(); }"+" self.addEventListener('message', function(msg){ interpret(msg.data.code, msg.data.input); });";var interpreter=new Worker(URL.createObjectURL(new Blob([workerCode])));interpreter.addEventListener("message",function(msg){cb(msg.data)});interpreter.postMessage({"code":code,"input":input});setTimeout(function(){interpreter.terminate()},1E4)}setTimeout(function(){getOriginalCode();textbox.addEventListener("input",onTextboxChange);testbtn.addEventListener("click",onTestBtn);resetbtn.addEventListener("click",onResetBtn);setTextbox(getOriginalCode())},100);function interpret(code,input){window={};alert=function(s){stdout(s)};window.alert=alert;console.log=alert;prompt=function(s){if(input.length<1)stderr("not enough input");else{var nextInput=input[0];input=input.slice(1);return nextInput.toString()}};window.prompt=prompt;(function(){try{var evalResult=eval(code);if(typeof evalResult=="function"){var callResult=evalResult.apply(this,input);if(typeof callResult!="undefined")stdout(callResult)}}catch(e){stderr(e.message)}})()};</script>

^{(Fragment pochodzi z tej strony )}

Sugestie mile widziane!

Haskell, 68 61 53 bajtów

Ulepszenie od Damiena

g x|x`mod`4==1=x>4|2>1=g$x`div`2
a x=filter g[1..2^x]

Historia:

To naprawia błąd (Zamienione == i = i kwadrat zamiast potęgi dwóch). I zamień true na 2> 1, a false na 1> 2. Również dzięki wskazaniu, że 2 ^ x zawsze kończy się niepowodzeniem. Dzięki Thomas Kwa i nimi

g x|x<5=1>2|x`mod`4==1=2>1|2>1=g$x`div`2
a x=filter g[1..2^x]

Pierwotnie

g x|x<5=False|x`mod`4=1==True|2>1=g$x`div`2
a x=filter g[1..(x^2-1)]

Jeśli to musi być pełny program,

g x|x<5=False|x`mod`4==1=True|2>1=g$x`div`2
main=interact$show.a
a x=filter g[1..2^(read x)]

APL, 34 27 bajtów

{0~⍨{⍵×2<+/2≢/⍵⊤⍨⍵/2}¨⍳2*⍵}

Tworzy to nienazwaną funkcję monadyczną, która akceptuje liczbę całkowitą po prawej stronie i zwraca tablicę.

Wyjaśnienie:

                     }¨⍳2*⍵}  ⍝ For each integer from 1 to 2^input...
              ⍵⊤⍨⍵/2         ⍝ Get the binary representation as a vector
           2≢/                ⍝ Pairwise non-match, yielding a boolean vector
       2<+/                   ⍝ Check whether the number of trues is >2
     ⍵×                       ⍝ Yield the integer if so, otherwise 0
{0~⍨{                         ⍝ Remove the zeros from the resulting array

Zaoszczędź 7 bajtów dzięki Dennisowi!

R 55 55 bajtów

(z pewną pomocą @ Alex.A)

cat(grep("10+1",R.utils::intToBin(1:2^scan())))

R nie ma wbudowanej funkcji do wyświetlania konwertowanych liczb w wygodny sposób, więc używam R.utils::intToBindo tego, podczas gdy cała reszta to po prostu zgłoś lokalizację dopasowanego wyrażenia regularnego i drukuj do STDOUT, oddzielając je przestrzeń.

CJam, 14

2qi#{2b2,#)},p

3 bajty krótsze dzięki Dennisowi. Wypróbuj online

JavaScript (ES6), 69 68 67 62 bajtów

a=>[...Array(1<<a).keys()].filter(i=>/01/.test(i.toString(2)))

Dzisiaj odkryłem nowy, krótszy sposób dynamicznego wypełniania tablic bez użycia wypełnienia lub mapy. Wykonanie x=>[...Array(x).keys()]spowoduje zwrócenie tablicy z zakresu od 0 do x. Jeśli chcesz zdefiniować własny zakres / wartości, użyj x=>[...Array(x)].map((a,i)=>i), ponieważ jest to tylko kilka bajtów dłużej.

Java, 214 165 155 154 148 141 110 110 bajtów

To przesłanie wykorzystuje fakt, że binarna reprezentacja ciągu liczbowego w Javie nigdy nie ma wiodącego zera. Jeśli ciąg „01” pojawia się w binarnej reprezentacji liczby, musi to oznaczać drugie wystąpienie liczby „1”.

Gra w golfa:

String f(int l){String r="";for(long i=5;i<1L<<l;++i)if(Long.toString(i,2).contains("01"))r+=i+", ";return r;}

Nie golfowany:

public class NumbersWithMultipleRunsOfOnes {

  public static void main(String[] a) {
    // @formatter:off
    String[][] testData = new String[][] {
      { "3", "5" },
      { "4", "5, 9, 10, 11, 13" },
      { "5", "5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29" }
    };
    // @formatter:on

    for (String[] data : testData) {
      System.out.println("Input: " + data[0]);
      System.out.println("Expected: " + data[1]);
      System.out.print("Actual:   ");
      System.out.println(new NumbersWithMultipleRunsOfOnes().f(Integer.parseInt(data[0])));
      System.out.println();
    }
  }

  // Begin golf
  String f(int l) {
    String r = "";
    for (long i = 5; i < 1L << l; ++i)
      if (Long.toString(i, 2).contains("01")) r += i + ", ";
    return r;
  }
  // End golf
}

Dane wyjściowe programu (pamiętaj, że dopuszczalne są końcowe ograniczniki):

Input: 3
Expected: 5
Actual:   5, 

Input: 4
Expected: 5, 9, 10, 11, 13
Actual:   5, 9, 10, 11, 13, 

Input: 5
Expected: 5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29
Actual:   5, 9, 10, 11, 13, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 

C (gcc) , 111 99 bajtów

long i,x;main(a,b)char**b;{for(;++i<1L<<atol(b[1]);x>>ffsl(~x)-1&&printf("%ld,",i))x=i>>ffsl(i)-1;}

Wypróbuj online!

Ogolono 12 bajtów dzięki @ceilingcat!

Nie golfowany:

int main(int a, char **b) {
  for(long i = 0, x = 0; ++i < (1LL << atol(b[1])); ) {
    x = i >> (ffsl(i) - 1);
    if (x >> (ffsl(~x) - 1))
      printf("%ld,", i);
  }
}

Funkcja ffsl () daje indeks pierwszego bitu, który jest ustawiony na długą liczbę całkowitą. Więc zapętlamy od i = 1do 2 ^ liczba_bitów. Stawiamy xna iprzesunięty w prawo, aż usunęliśmy wszystkie kolejne bity zerowe w najmniej znaczącym końca. Następnie przesuwamy się w xprawo, dopóki nie usuniemy wszystkich kolejnych 1 bitów na najmniej znaczącym końcu. Jeśli wynik jest wciąż niezerowy, znaleźliśmy dopasowanie.

JavaScript (ES6) 76

f=n=>Array(1<<n).fill().map((_,x)=>/01/.test(x.toString(2))?x+',':'').join``

//TEST
for(i=1;i<16;i++)O.innerHTML+=i+' -> '+f(i)+'\n'

<pre id=O></pre>

K5, 19 bajtów

Działa to zgodnie z podobnymi zasadami jak rozwiązanie Dennisa, ale z mniejszą liczbą wbudowanych do skorzystania.

{&2<+/'~0=':'+!x#2}

Najpierw wygeneruj serię binarnych x-krotek ( +!x#2), a następnie dla każdej krotki znajdź każdy punkt, w którym cyfra nie pasuje do poprzedniego, jeśli w tym celu traktujemy -1-szy element listy jako 0 ~0=':'. Nasze rozwiązania polegają na tym, że dwa są mniejsze niż suma każdego przebiegu. ( &2<+/').

Pokazanie każdego kroku pośredniego jest wyraźniejsze:

  4#2
2 2 2 2

  !4#2
(0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1)

  +!4#2
(0 0 0 0
 0 0 0 1
 0 0 1 0
 0 0 1 1
 0 1 0 0
 0 1 0 1
 0 1 1 0
 0 1 1 1
 1 0 0 0
 1 0 0 1
 1 0 1 0
 1 0 1 1
 1 1 0 0
 1 1 0 1
 1 1 1 0
 1 1 1 1)

  ~0=':'+!4#2
(0 0 0 0
 0 0 0 1
 0 0 1 1
 0 0 1 0
 0 1 1 0
 0 1 1 1
 0 1 0 1
 0 1 0 0
 1 1 0 0
 1 1 0 1
 1 1 1 1
 1 1 1 0
 1 0 1 0
 1 0 1 1
 1 0 0 1
 1 0 0 0)

  +/'~0=':'+!4#2
0 1 2 1 2 3 2 1 2 3 4 3 2 3 2 1

  2<+/'~0=':'+!4#2
0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0

  &2<+/'~0=':'+!4#2
5 9 10 11 13

A wszystko razem:

  {&2<+/'~0=':'+!x#2}'3 4 5 
(,5
 5 9 10 11 13
 5 9 10 11 13 17 18 19 20 21 22 23 25 26 27 29)

Pip, 13 + 1 = 14 bajtów

Pobiera dane z wiersza poleceń i używa -sflagi do spacji między liczbami wyjściowymi.

01NTB_FI,2**a

Całkiem proste: buduj range(2**a)i filtruj lambda _: "01" in toBinary(_). Byłem bardzo zadowolony z 01samodzielnego wymyślania tego pomysłu. Nie są potrzebne żadne cudzysłowy, 01ponieważ skanuje się je jako literał liczbowy (liczby i ciągi znaków są tego samego typu w Pipie).

Julia, 40 bajtów

n->filter(i->count_ones(i$i>>1)>2,1:2^n)

Wykorzystuje to nieco inne podejście do innego rozwiązania Julii - zamiast wyszukiwać ciąg „01” w ciągu bitowym, używa pewnej matematyki do ustalenia, czy liczba spełnia warunek.

i$i>>1będą miały tylko te miejsca, w których cyfra zmienia się od zera do jednego lub od jednego do zera. W związku z tym muszą istnieć co najmniej trzy, iaby przełączać się między zerem a wystarczającą liczbą razy. count_onesznajduje liczbę, a następnie filterusuwa te, które nie mają wystarczającej liczby.

C ++, 197 188 141 bajtów

Uwaga: zostało to napisane i przetestowane przy użyciu MSVC ++ 2013. Wygląda na to, że #includeing <iostream>zawiera wszystkie niezbędne nagłówki C, aby to zadziałało. Wygląda również na to, że kod nie jest już tak naprawdę C ++, ale kompilacja przy użyciu C ++ pozwala na tę sztuczkę nagłówka, która zmniejsza rozmiar kodu w porównaniu z dołączeniem większej liczby nagłówków C.

Używanie printfzamiast coutoszczędza również kilka bajtów.

Gra w golfa:

#include<iostream>
int main(int a,char**b){char c[34];for(long i=5;i<1L<<atol(b[1]);++i){_ltoa(i,c,2);if(strstr(c,"01"))printf("%ld\n",i);}}

Nie golfowany:

#include <iostream>
int main(int a, char **b) {
  char c[34];
  for (long i = 5; i < 1L << atol(b[1]); ++i) {
    _ltoa(i, c, 2);
    if (strstr(c, "01"))
      printf("%ld\n", i);
  }
}

Perl 5, 55 53 49 47 41 bajtów

sprintf("%b",$_)=~/01/&&say for 0..2**<>

54 52 48 46 40 bajtów plus jeden na -Eflagę zamiast -e.

Dzięki xnor za podpowiedź na temat używania /01/zamiast /10+1/, co pozwoliło zaoszczędzić dwa bajty.

Dzięki Dennisowi za radę, której należy użyć <>zamiast$ARGV[0] , co pozwoliło zaoszczędzić sześć bajtów.

C, 84 81 bajtów

long i,j,k;main(){for(scanf("%ld",&j);++i<1L<<j;k&k+1&&printf("%ld ",i))k=i|i-1;}

Jest to oparte na komentarzach, które wypowiedziałem na temat innej odpowiedzi C na to pytanie dotyczące możliwości korzystania z prostych operatorów bitowych. Działa poprzez przełączenie wszystkich końcowych 0 bitów na 1 w instrukcji i | (i-1). Następnie przełącza wszystkie końcowe 1 bity na 0 za pomocą k & (k + 1). Doprowadzi to do zera, jeśli jest tylko jeden ciąg jednych, a niezerowego w przeciwnym razie. Przyjmuję założenie, że długi jest 64-bitowy, ale mógłbym to poprawić kosztem trzech bajtów, używając zamiast tego int64_t.

Bez golfa

long i,j,k;
main()
{
    for(scanf("%ld",&j);++i<1L<<j;)
    {
        k=i|(i-1);
        if((k&(k+1)) == 0)
            printf("%d ",i);
    }
}

Pyth, 20 17 16 bajtów

f:.BT"10+1"ZU^2Q

Demo na żywo.

Python 2.7, 89 bajtów

print[i for i in range(1,2**input())if[n[:1]for n in bin(i)[2:].split("0")].count("1")-1]

Myślę, że można to trochę pograć w golfa.

TI-BASIC, 34 32 30 bajtów

Do kalkulatora serii TI-83 + / 84 +.

For(X,5,e^(Ans
If log(sum(2=int(4fPart(X/2^randIntNoRep(1,Ans
Disp X
End

Aby liczba zawierała dwa przebiegi 1s, musi zawierać dwa 10s, gdy przyczepimy końcowe zero do reprezentacji binarnej.

Zamiast generować reprezentację binarną i sprawdzać, a 10, bity matematycznie testujemy parami, używając reszty o wartości 4 ( int(4fPart(), co da, 2gdzie jest 10. Ponieważ nie dbamy o porządek, randIntNoRep(jest to najkrótszy sposób na wygenerowanie listy wykładników.

Używamy log(do sprawdzania liczby przebiegów:

• Jeśli są co najmniej 2 przebiegi, to log(jest dodatni, a liczba jest wyświetlana.

• Jeśli jest jeden przebieg, to log(jest 0, a numer nie jest wyświetlany.

• Jeśli nie ma żadnych uruchomień (co najpierw dzieje się przy X = 2 ^ Ans), następnie log(zgłasza ERR: DOMAIN, zatrzymując dane wyjściowe dokładnie we właściwym punkcie.

Używamy e^(Ansjako argumentu końcowego For(pętli - zawsze jest większy niż 2^Ans, ale e^(jest to pojedynczy token, więc jest o jeden bajt krótszy.

Wejście / wyjście dla N = 4:

4:prgmRUNSONES
               5
               9
              10
              11
              13

Następnie kalkulator zgłasza błąd; ekran błędu wygląda następująco:

ERR:DOMAIN
1:Quit
2:Goto

Po naciśnięciu przycisku 1 ponownie pojawia się ekran główny:

4:prgmRUNSONES
               5
               9
              10
              11
              13
           Error

Kalkulatory TI przechowują wszystkie liczby w liczbie zmiennoprzecinkowej BCD z 14 cyframi dokładności, a nie liczbami całkowitymi lub binarnymi. Dlatego podziały przez potęgi dwóch większych niż 2^14mogą nie być dokładne. Chociaż zweryfikowałem, że najtrudniejsze liczby 3*2^30-1i 2^32-1są obsługiwane poprawnie, nie wykluczyłem możliwości zaokrąglania błędów. Byłbym jednak zaskoczony, gdyby wystąpiły błędy w danych wejściowych.

• to nie bije odpowiedzi Flawr, ale nie mogłem się oprzeć urokowi pytania

Matlab(90)(70)

j=input('');for l=2:j-1,a=1;for k=l:-1:2,a=a+2^k;a:a+2^(k-1)-2,end,end

wykonanie

4

ans =

5

ans =

9    10    11

ans =

13

zasada

• Szereg liczb jest wynikiem wynikającego z tego paska 1, co oznacza, że ​​f (n, l) = 2 ^ l + 2 ^ (l + 1) + .... 2 ^ n

Dowolna liczba pobrana z przedziału] f (n, l), f (n, l) + 2 ^ (l-1) [gdzie l> 1 weryfikuje ten warunek, więc wynik jest wynikiem negacji tej serii w warunki n.

x = 1

x = x + 1 = 01,

x = x + 2 ^ 0 = 11,

x = x + 1 = 001,

x = x + 2 ^ 1 = 011,

x = x + 2 ^ 0 = 111,

x = x + 1 = 0001,

x = x + 2 ^ 2 = 0011,

x = x + 2 ^ 1 = 0111,

x = x + 2 ^ 0 = 0111,

x = x + 1 = 1111...

x + 1, x = x + 2 ^ n, x = x + 2 ^ (n-1) ... x = x + 2 ^ 0

Mój program drukuje zakres między każdą z dwóch linii (jeśli istnieje)

Edycja: niestety nie czyni to więcej golfa, ale chciałem dodać inne podejście do realizacji tego pomysłu

po okresie zmagań udało mi się znaleźć matematyczną reprezentację tej serii:

2 ^ l (0 + 1 + 2 ^ 1 + ... 2 ^ k) z l + k <n

= 2 ^ l (2 ^ k-1)

wynik = 90

@(n)setdiff(0:2^n-1,arrayfun(@(x)2^mod(x,(n+1)-fix(x/(n+1)))*(2^fix(x/(n+1))-1),0:(n+1)^2))

C, 103 102 bajtów

long i,x;main(int a,char**b){for(;++i<1L<<atoi(b[1]);)for(x=i;x>4&&(x%4!=1||!printf("%ld,",i));x/=2);}

Rozszerzanie (właściwie kurczenie się) wpisu G.Sliepen, korzystając z uwagi xnor na 01wzorzec w reprezentacji binarnej, ale używając tylko standardowych funkcji i nieco przewracając się.

Wersja bez golfa:

long i, x;
main(int a, char**b) {
    for (; ++i < 1L << atoi(b[1]);) {
        for (x = i; x > 4 && (x % 4 != 1 || !printf("%ld,", i)); x /= 2)
            ;
    }
}

Wewnętrzna pętla skanuje iwzór binarny 01, iteracyjnie przesuwając xw prawo, o ile ma jeszcze 3 bity. printfzwraca liczbę wydrukowanych znaków, a więc nigdy 0, więc test pętli wewnętrznej kończy się niepowodzeniem po printf, unikając potrzeby breakwyrażenia.

C ++, 129 128 bajtów

Dostosowując ten sam pomysł, wariant C ++ jest tutaj:

#include<iostream>
long i,x;int main(int a,char**b){for(;++i<1L<<atoi(b[1]);)for(x=i;x>4&&(x%4!=1||!(std::cout<<i<<','));x/=2);}

Technicznie rzecz biorąc, należy dokonać aby zapewnić 64 bitową operację i obliczyć września za dodatkową opłatą 5 bajtów, ale nowoczesne platformy mają 64-bitowych ints.ilong long2^32

JavaScript ES6, 60 bajtów

Kod

n=>[...Array(1<<n).keys()].filter(g=x=>x>4?x%4==1|g(x>>1):0)

Wypróbuj online!

Wyjaśnienie

[...Array(1<<n).keys()]                                          Create an array of numbers from 0 to 2^n-1
                       .filter(                                  Find the numbers which meet criteria
                               g=x=>x>4?                  :0     If x is less than or equal to four return zero (false/invalid)
                                        x>4?x%4==1|              If the binary pattern ends with 01 return one (true/valid)
                                                   g(x>>1)       Otherwise bitshift right by one and try again

C (rodzaj - kompiluje z ostrzeżeniami w GCC) - 103

Nie używa to żadnych funkcji bibliotecznych z wyjątkiem printf. Patrząc na to, widać, że nie dołożono żadnych starań, aby był on zgodny ze standardami lub unikał UB.

x,c;main(n,v){n--;for(;c<1<<n;c++)for(v=0;v<32;v++)if(c&1<<v){if(x&&x<v&&printf("%d ",c))break;x=v+1;}}

Aby był zgodny, musisz zrobić wiele rzeczy, takich jak stdio.h, co byłoby sprzeczne z duchem zmniejszania go do minimum.

Jeśli ktoś ma sugestie dotyczące skrócenia, daj mi znać.

PowerShell, 80 bajtów

while([Math]::Pow(2,$args[0])-gt$n++){$n|?{[Convert]::ToString($n,2)-match"01"}}

Python, 44 bajty

Okej, to prawdopodobnie może być krótsze, ale to mój pierwszy codegolf:

x=1
while True:
    if '01' in bin(x):
        print(x)
    x+=1

Pomyśl, że to odpowiada na pytanie, proszę nie głosować, jeśli nie, po prostu opublikuj poniżej, co jest nie tak.

kolejna inna odpowiedź Matlaba na dobry wynik.

Matlab 60(57)

@(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

wykonanie

>> @(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

ans =

@(n)find(mod(log2(bitcmp(1:2^n,fix(log2(1:2^n)+1))+1),1))

>> ans(5)

ans =

 5     9    10    11    13    17    18    19    20    21    22    23    25    26    27    29

• Chodzi o to, aby zbierać liczby x, gdzie binarna reprezentacja - (x) +1 nie zawiera tylko jednego wystąpienia1

przykład:

0000111jest odrzucany, ponieważ ~ x = 1111, ~ x + 1 = 00001zawiera jedną cyfrę = 1

0100111jest akceptowane, ponieważ ~ x = 1011, ~ x + 1 = 0111zawiera wiele 1