Rozważ następującą sekwencję numerów:

$0, \frac{1}{2}, \frac{1}{4}, \frac{3}{4}, \frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{7}{8}, \frac{1}{16}, \frac{3}{16}, \frac{5}{16}, \frac{7}{16}, \frac{9}{16}, \frac{11}{16}, \frac{13}{16}, \frac{15}{16}, \frac{1}{32}, \frac{3}{32}, \frac{5}{32}, \dots$

Wymienia wszystkie ułamki binarne w przedziale jednostkowym .$[0, 1)$

(Aby ułatwić to wyzwanie, pierwszy element jest opcjonalny: Możesz go pominąć i rozważyć, że sekwencja zaczyna się od 1/2).

Zadanie

Napisz program (pełny program lub funkcję), który ...

Wybierz jedno z tych zachowań:

• Wejście n, wyjście n-ty element sekwencji (indeksowane 0 lub indeksowane 1);
• Wprowadź n, wyślij pierwsze n elementów sekwencji;
• Nic nie wpisuj, wypisz nieskończoną sekwencję liczb, którą możesz brać jeden po drugim;

Reguła

• Twój program powinien co najmniej wspierać pierwsze 1000 pozycji;
• Możesz wybrać wyświetlanie liczb dziesiętnych lub ułamków (wbudowane, pary całkowite, łańcuchy) według własnego uznania;
  • Wejście / Wyjście jako cyfry binarne nie jest dozwolone w tym pytaniu;
• To jest golf-golf , wygrywanie najkrótszych kodów;
• Standardowe luki zabronione.

Przypadki testowe

input output
1     1/2     0.5
2     1/4     0.25
3     3/4     0.75
4     1/8     0.125
10    5/16    0.3125
100   73/128  0.5703125
511   511/512 0.998046875
512   1/1024  0.0009765625

Przykłady te oparte są na sekwencji z indeksowaniem 0, w tym z wiodącym 0. Konieczne będzie dostosowanie danych wejściowych w celu dopasowania rozwiązania.

Czytaj więcej

• OEIS A006257
  • Problem z Józefem Flawiuszem: . (Poprzednio M2216)$a_{2n} = 2a_n-1, a_{2n+1} = 2a_n+1$
  • 0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, ...
• OEIS A062383
  • n > 0 a n = 2 ⌊ l o g 2 n + 1 ⌋ a n = 2 a ⌊ $a_0 = 1$ : dla , lub .$n>0$$a_n = 2^{\lfloor log_2n+1 \rfloor}$$a_n = 2a_{\lfloor \frac{n}{2} \rfloor}$
  • 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, ...

• A006257 (n) / A062383 (n) = (0, 0,1, 0,01, 0,11, 0,001, ...) wylicza wszystkie ułamki binarne w przedziale jednostkowym [0, 1). - Fredrik Johansson, 14 sierpnia 2006 r

Haskell , 25 bajtów

pred.until(<2)(/2).(+0.5)

Wypróbuj online!

Generuje dziesiętne, zindeksowane bez początkowego terminu zerowego.

Dodaje 0,5 do danych wejściowych, następnie zmniejsza o połowę, aż wyniki będą niższe niż 2, a następnie odejmuje 1. Użycie wyrażenia bezcelowego oszczędza 1 bajt

f n=until(<2)(/2)(n+0.5)-1

Java 10, 68 64 bajtów

Najpierw spróbuj golfa code!

Opcja 1: znajdź n- ty element (1-indeksowany)

-4 bajty dzięki @Kevin Cruijssen

n->{int x=0;for(;n>>++x!=1;);return((~(1<<x)&n)*2.+1)/(1<<x+1);}

Jest to anonimowa metoda, która znajduje n- ty składnik, usuwając najbardziej znaczący bit z n , podwajając go i dodając jeden, a następnie dzieląc przez następną najwyższą potęgę 2.

Wypróbuj online!

Przewodnik po kodzie:

n->{                      // builds anonymous function with input n
int x=0;                  // stores floor of log(n) (base 2) for most significant digit
for(;n>>++x!=1;);         // calculates floor of log(n) by counting right shifts until 1
return((~(1<<x)&n)        // removes most significant digit of n
*2.+1)                     // multiplies 2 and adds 1 to get the odd numerator
/(1<<x+1);}               // divides by the next highest power of 2 and returns`

Dokonuje edycji, jeśli konieczne jest wydrukowanie końcowej wartości zamiast jej zwracania.

MathGolf , 5 4 bajtów

╫\╨]

Wypróbuj online!

Jak by to wyglądało, gdy operator działa poprawnie

╫\)╨]   (")" adds 1 to TOS, making rounding behave as expected)

Wypróbuj online!

Wyjaśnienie

╫     Left-rotate all bits in input
 \    Swap top two elements on stack, pushing the input to the top
  ╨   Round up to nearest power of 2
   ]  Wrap in array (just for pretty printing)

Inspirację czerpałem z tego pytania, aby rozwiązać problem. Myślę, że moje „własne” rozwiązanie miało około 10-12 bajtów.

Zamierzałem, aby zaokrąglenie w górę do najbliższej potęgi 2 zwróciło samą liczbę, jeśli była to liczba dwa, ale z powodu błędu zaokrągla ona do następnej potęgi dwóch (np. 4 -> 8 zamiast 4 -> 4 ). To trzeba będzie naprawić później, ale teraz oszczędza mi to jeden bajt.

Java 10, 89 85 70 69 68 bajtów

v->{for(float j,t=2;;t*=2)for(j=1;j<t;j+=2)System.out.println(j/t);}

Port odpowiedzi 05AB1E @Emigma , więc wypisuje również dziesiętne w nieskończoność.
-15 bajtów dzięki @Arnauld .

Wypróbuj online.

Wyjaśnienie:

v->{                      // Method with empty unused parameter and no return-type
  for(float j,t=2;;       //  Loop `t` from 2 upwards indefinitely,
                   t*=2)  //  doubling `t` after every iteration
    for(j=1;j<t;          //   Inner loop `j` in the range [1, `t`),
                j+=2)     //   in steps of 2 (so only the odd numbers)
      System.out.println( //    Print with trailing new-line:
        j/t);}            //     `j` divided by `t`

Perl 6 , 19 bajtów

{($_+.5)/2**.msb-1}

Wypróbuj online!

Python 3 , 33 bajty

lambda n:(8*n+4)/2**len(bin(n))-1

Wypróbuj online!

Generuje dziesiętne, zindeksowane bez początkowego terminu zerowego.

Java (JDK 10) , 30 bajtów

n->(n+.5)/n.highestOneBit(n)-1

Wypróbuj online!

Zwraca ^nty element w sekwencji.

Ta odpowiedź jest pierwotnie następstwem golfa odpowiedzi Java firmy TCFP . Ostatecznie golfy nie wyglądały już jak oryginalne odpowiedzi (choć zastosowana matematyka jest taka sama), więc postanowiłem opublikować golfa jako osobną odpowiedź zamiast po prostu komentować odpowiedź TCFP. Jeśli więc podoba ci się ta odpowiedź, idź głosować odpowiedź TCFP ! ;-)

Pośrednie pola golfowe to:

n->{int x=0;for(;n>>++x!=1;);return((~(1<<x)&n)*2.+1)/(1<<x+1);} // 64 bytes (TCFP's answer when I started golfing)
n->{int x=0;for(;n>>++x!=1;);x=1<<x;return((~x&n)*2.+1)/x/2;}    // 61 bytes
n->{int x=n.highestOneBit(n);return((~x&n)*2.+1)/x/2;}           // 54 bytes
n->{int x=n.highestOneBit(n);return((~x&n)+.5)/x;}               // 50 bytes
n->((n&~(n=n.highestOneBit(n)))+.5)/n                            // 37 bytes
n->(n-(n=n.highestOneBit(n))+.5)/n                               // 34 bytes
n->(n+.5)/n.highestOneBit(n)-1                                   // 30 bytes, current score

05AB1E , 11 8 bajtów

Zaoszczędził 3 bajty dzięki Kevin Cruijssen .

∞oDÅÉs/˜

Wypróbuj online!

Wyjaśnienie

∞         # start an infinite list [1...
 o        # calculate 2**N
  D       # duplicate
   ÅÉ     # get a list of odd numbers up to 2**N
     s/   # divide each by 2**N
       ˜  # flatten

Galaretka , 9 bajtów

Bṙ1Ḅ,æċ2$

Wypróbuj online!

PowerShell , 40 bajtów

for($i=2;;$i*=2){1..$i|?{$_%2}|%{$_/$i}}

Wypróbuj online!

Zwraca nieskończoną sekwencję jako wartości dziesiętne. Biorąc pod uwagę ograniczenia językowe, w końcu wystąpią problemy z precyzją, ale z łatwością poradzi sobie z pierwszymi 1000 wpisami.

Zaczyna od ustawienia $i=2, a następnie wchodzi w forpętlę. Przy każdej iteracji konstruujemy zakres 1..$ii wyciągamy wartości nieparzyste za pomocą |?{$_%2}. Są one wprowadzane do ich własnej wewnętrznej pętli, gdzie dzielimy każdą z nich, aby uzyskać liczbę dziesiętną |%{$_/$i}. Zostają one pozostawione w potoku i wyprowadzane, gdy potok jest opróżniany po każdej foriteracji. Każdą iterację zwiększamy $i, $i*=2aby uzyskać kolejną rundę.

Haskell, 35 32 bajtów

Edycja: -3 bajty dzięki @ Delfad0r.

[(y,2^x)|x<-[1..],y<-[1,3..2^x]]

To nieskończona lista par liczb całkowitych.

Wypróbuj online!

Haskell , 40 bajtów

s=(1,2):[(i*2+u,j*2)|(i,j)<-s,u<-[-1,1]]

Wypróbuj online!

Nieskończona sekwencja jako pary liczb całkowitych (zaczynając od (1,2)).

Trochę dłużej niż odpowiedź @ nimi , ale podejście jest zupełnie inne, więc i tak zdecydowałem się opublikować.

To rozwiązanie opiera się na poniższej obserwacji.

• $\frac{i}{j}$$\left\{\frac{2i-1}{2j},\frac{2i+1}{2j}\right\}$ $$\left\{\left\{\frac{1}{4},\frac{3}{4}\right\},\left\{\frac{1}{8},\frac{3}{8}\right\},\left\{\frac{5}{8},\frac{7}{8}\right\},\left\{\frac{1}{16},\frac{3}{16}\right\},\ldots\right\}$$
• $$\left\{\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{3}{8},\frac{5}{8},\frac{7}{8},\frac{1}{16},\frac{3}{16},\ldots\right\}$$
• $\frac{1}{2}$ $$\left\{\frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{3}{8},\frac{5}{8},\frac{7}{8},\frac{1}{16},\frac{3}{16},\ldots\right\}$$

Zauważ, jak wróciłeś do sekwencji, którą zacząłeś!

Rozwiązanie wykorzystuje ten fakt (wraz z lenistwem Haskella) do obliczenia sekwencji s.

Python 2 - 68 66 bajtów

-2 bajty dzięki Kevinowi

from math import*
def g(n):a=2**floor(log(n,2));print(n-a)*2+1,2*a

Wypróbuj online!

Python 3 , 53 51 bajtów

• Zaoszczędzono dwa bajty dzięki mypetlion ; ponowne użycie parametrów domyślnych do zresetowania n.

def f(m=2,n=1):n<m and print(n/m)&f(m,2+n)or f(m+m)

Wypróbuj online!

R , 42 bajty

function(n)c(y<-2^(log2(n)%/%1)*2,2*n-y+1)

Wypróbuj online!

Denominator,Numerator$\begin{equation}N = 2*\left(n-2^{\lfloor \log_2(n)\rfloor}\right)+1\end{equation}$$\begin{equation}D = 2^{\lfloor \log_2(n)\rfloor+1}\end{equation}$

Rakieta , 92 91 bajtów

(define(f k(m 2)(n 1))(if(> k 0)(if(=(+ n 1)m)(f(- k 1)(+ m m))(f(- k 1)m(+ n 2)))(/ n m)))

Wypróbuj online!

• Oszczędność bajtu dzięki Giuseppe - usuwanie zbędnych białych znaków.

MATL , 8 bajtów

BnWGEy-Q

Wypróbuj online!

Zwraca licznik, a następnie mianownik. Używa tej samej metody, co moja odpowiedź R. Jednak jest ona nieco bardziej wydajna.

Objaśnienie, z wejściem 5:

           # implicit input 5
B          # convert to array of bits
           # STACK: [[1 0 1]]
n          # length (place of Most Significant Bit)
           # STACK: [3]
W          # elementwise raise 2^x
           # STACK: [8]
G          # paste input
           # STACK: [8, 5]
E          # double
           # STACK: [8, 10]
y          # copy from below
           # STACK: [8, 10, 8]
-          # subtract
           # STACK: [8, 2]
Q          # increment
           # STACK: [8, 3]
           # implicit end of program, display stack contents

Język programowania Szekspira , 426 bajtów

,.Ajax,.Ford,.Act I:.Scene I:.[Exeunt][Enter Ajax and Ford]Ajax:You be the sum ofyou a cat.Ford:You cat.Scene V:.Ford:Is twice you nicer I?If solet usScene X.You be twice you.Let usScene V.Scene X:.Ford:Remember twice you.You be the sum oftwice the remainder of the quotient betweenI you a cat.Open heart.You big big big big big cat.Speak thy.Recall.Open heart.You be twice the sum ofa cat a big big cat.Speak thy.Let usAct I.

Wypróbuj online!

Generuje sekwencję nieskończenie, ponieważ obie liczby są oddzielone spacją, a każdy element jest oddzielony znakiem nowej linii.

Python 2 , 44 bajty

def f(n):m=2**len(bin(n))/4;return 2*n-m+1,m

Wypróbuj online!

Funkcja zwraca krotkę (licznik, mianownik). Wejście 0 nie jest obsługiwane (było opcjonalne).

Excel 48 28 bajtów

Zaoszczędzono 20 bajtów (!) Dzięki tsh

=(A1+0.5)/2^INT(LOG(A1,2))-1

= MOD (A1 + 0,5,2 ^ (INT (LOG (A1,2)))) / 2 ^ INT (LOG (A1,2))

Przyjmuje wartość w A1, dane wyjściowe są dziesiętne. Jeśli chcesz, aby dane wyjściowe były ułamkowe, możesz utworzyć niestandardowy format dla komórki wyjściowej jako „0 / ### 0” i wyświetli się jako ułamek.

Objaśnienie: Trudne do wyjaśnienia, ponieważ zastosowano skrót, aby dostać się do tej formuły. Zasadniczo licznik jest nieco przesunięty w lewo od wejścia, a mianownik jest następną siłą o 2 wyższą niż wprowadzona liczba.

Pierwotnie zacząłem od wbudowanych funkcji Excela dla BITLSHIFT i BITRSHIFT, ale przesuną one całe 48 bitów, co nie jest tym, czego chcesz. Funkcje DEC2BIN (i BIN2DEC) mają limit od -512 do 511 (10 bitów), więc to nie zadziała. Zamiast tego musiałem odbudować liczbę z modułem oryginalnej liczby, następnie dwa razy, a następnie dodać 1 (ponieważ lewa cyfra zawsze będzie miała wartość 1 przed zmianą).

=MOD(A1                        Use MOD for finding what the right digits are
       +0.5                    this will later add the left "1" to the right digits
           ,2^INT(LOG(A1,2)))) Take Log base 2 number of digits on the right
                               this creates the numerator divided by 2 (explained later)
/ 2^INT(LOG(A1,2))             The denominator should be 2^ (Log2 + 1) but instead of 
                               adding a 1 here, we cause the numerator to be divided by 2 instead
                               This gives us a fraction.  In the numerator, we also added .5
                               instead of 1 so that we wouldn't need to divide it in both the
                               numerator and denominator
Then tsh showed how I could take the int/log out of the mod and remove it from numerator/denominator. 

Przykłady:

C ++, 97 75 71 bajtów

-26 bajtów dzięki tsh, ceilingcat, Zacharý

float f(int i){float d=2,n=1;while(--i)n=d-n==1?d*=2,1:n+2;return n/d;}

Kod testowy:

std::cout << "1\t:\t" << f(1) << '\n';
std::cout << "2\t:\t" << f(2) << '\n';
std::cout << "3\t:\t" << f(3) << '\n';
std::cout << "4\t:\t" << f(4) << '\n';
std::cout << "10\t:\t" << f(10) << '\n';
std::cout << "100\t:\t" << f(100) << '\n';
std::cout << "511\t:\t" << f(511) << '\n';
std::cout << "512\t:\t" << f(512) << '\n';

C (gcc) , 63 bajty

Brak danych wejściowych, drukuje nieskończoną sekwencję:

f(i,j){for(i=1,j=2;;i+=2,i>j&&(j*=2,i=1))printf("%d/%d ",i,j);}

Wypróbuj online!

JavaScript (ES6), 44 bajty

$n$

f=(n,p=q=1)=>n?f(n-1,p<q-2?p+2:!!(q*=2)):p/q

Wypróbuj online!

Rubin , 42 bajty

1.step{|i|(1..x=2**i).step(2){|j|p [j,x]}}

Wypróbuj online!

Wyświetla nieskończone pary liczb całkowitych, zaczynając od 1/2.

JavaScript (Node.js) , 30 bajtów

f=(n,d=.5)=>d>n?n/d:f(n-d,d*2)

$\frac{1}{2}$

Ruby , 31 bajtów

->x{(2r*x+1)/2**x.bit_length-1}

Wypróbuj online!

> <> , 19 18 bajtów

Używając pomysłu xnora , naprawionego przez Jo Kinga, -1 bajt przez lepsze wykorzystanie kopii lustrzanych i kolejnych -2 bajtów przez Jo Kinga, ponieważ !był zbędny i ;nie jest wymagany.

2*1+\1-n
2:,2/?(

Wypróbuj online!

Wolfram Language (Mathematica) , 22 bajty

2^Mod[Log2[2#+1],1]-1&

Wypróbuj online!

APL (Dyalog Unicode) , 15 bajtów

1-⍨.5∘+÷2*∘⌊2⍟⊢

Wypróbuj online!

Anonimowy przedrostek lambda.

Dzięki Adámowi za 4 bajty i kwakowi Krowy za 2 bajty.

W jaki sposób:

1-⍨.5∘+÷2*∘⌊2⍟⊢ ⍝ Anonymous lambda, argument ⍵ → 10
            2⍟⊢ ⍝ Log (⍟) of ⍵ in base 2. 2⍟10 → 3.32192809489...
           ⌊     ⍝ Floor. ⌊3.32192809489... → 3
        2*∘      ⍝ Take that power of 2. 2³ → 8
       ÷         ⍝ Use that as denominator
   .5∘+          ⍝ ⍵ + 0.5 → 10.5. Using that as numerator: 10.5÷8 → 1.3125
1-⍨              ⍝ Swap the arguments (⍨), then subtract. 1-⍨1.3125 → 1.3125-1 → 0.3125

C # (.NET Core) , 69 bajtów

a=>{int b=1,c=2;while(a-->1){b+=2;if(b>c){b=1;c*=2;}}return b+"/"+c;}

Wypróbuj online!

Nie golfowany:

a=> {
    int b = 1, c = 2;   // initialize numerator (b) and denominator (c)
    while (a-- > 1)     // while a decrements to 1
    {
        b += 2;         // add 2 to b
        if (b > c)      // if b is greater than c:
        {
            b = 1;      // reset numerator to 1
            c *= 2;     // double denominator
        }
    }
    return b + "/" + c; // return fraction as string
}