Pertimbangkan urutan nomor berikut:

$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$

Ini menghitung semua fraksi biner dalam interval satuan .$[0, 1)$

(Untuk membuat tantangan ini lebih mudah, elemen pertama adalah opsional: Anda dapat melewati dan mempertimbangkan urutan dimulai dengan 1/2.)

Tugas

Tulis program (selesaikan program atau fungsi) yang ...

Pilih salah satu dari perilaku ini:

• Input n, output elemen n dari urutan (0-diindeks atau 1-diindeks);
• Input n, output pertama n elemen urutan;
• Masukkan apa-apa, output urutan nomor tak terbatas yang dapat Anda ambil dari satu per satu;

Aturan

• Program Anda setidaknya harus mendukung 1000 item pertama;
• Anda dapat memilih untuk menghasilkan desimal, atau fraksi (bawaan, bilangan bulat integer, string) sesuka Anda;
  • Input / Output sebagai digit biner tidak diperbolehkan dalam pertanyaan ini;
• Ini adalah kode-golf , kode terpendek menang;
• Celah standar tidak diijinkan.

Testcases

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

Contoh-contoh ini didasarkan pada urutan 0-diindeks dengan 0 terkemuka disertakan. Anda perlu menyesuaikan input untuk menyesuaikan solusi Anda.

Baca lebih lajut

• OEIS A006257
  • Masalah Josephus: $a_{2n} = 2a_n-1, a_{2n+1} = 2a_n+1$ . (Sebelumnya M2216)
  • 0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, ...
• OEIS A062383
  • : untuk n > 0 , a n = 2 ⌊ l o g 2 n + 1 ⌋ atau a n = 2 a ⌊ $a_0 = 1$$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, ...) menghitung semua fraksi biner dalam interval satuan [0, 1). - Fredrik Johansson, 14 Agustus 2006

Haskell , 25 byte

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

Cobalah online!

Output desimal, satu-diindeks tanpa istilah nol awal.

Menambahkan 0,5 ke input, lalu membagi dua hingga hasilnya di bawah 2, lalu kurangi 1. Menggunakan ekspresi pointfree menghemat 1 byte lebih dari

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

Java 10, 68 64 byte

Coba pertama kali di golf kode!

Opsi 1: temukan n elemen ke- (1-diindeks)

-4 byte terima kasih kepada @Kevin Cruijssen

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

Ini adalah metode anonim yang menemukan istilah ke- n dengan menghapus bit paling signifikan dari n , menggandakannya dan menambahkannya, kemudian membaginya dengan kekuatan tertinggi berikutnya 2.

Cobalah online!

Panduan kode:

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`

Akan mengedit jika perlu untuk mencetak nilai akhir alih-alih mengembalikannya.

MathGolf , 5 4 byte

╫\╨]

Cobalah online!

Bagaimana kelihatannya dengan operator yang bekerja dengan benar

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

Cobalah online!

Penjelasan

╫     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)

Saya mengambil inspirasi dari pertanyaan ini untuk menyelesaikan masalah, saya kira solusi "sendiri" sekitar 10-12 byte.

Saya bermaksud untuk putaran ke kekuatan terdekat 2 untuk mengembalikan nomor itu sendiri jika nomor dua, tetapi karena kesalahan itu putaran ke kekuatan dua berikutnya (misalnya 4 -> 8 bukannya 4 -> 4 ). Ini harus diperbaiki nanti, tetapi sekarang menghemat satu byte.

Java 10, 89 85 70 69 68 bytes

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

Port of @Emigma's 05AB1E answer, so outputs decimals indefinitely as well.
-15 bytes thanks to @Arnauld.

Try it online.

Explanation:

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 bytes

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

Try it online!

Python 3, 33 bytes

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

Try it online!

Outputs decimals, one-indexed without the initial zero term.

Java (JDK 10), 30 bytes

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

Try it online!

Returns the n^th item in the sequence.

This answer is originally a succession of golfs of TCFP's Java answer. In the end, the golfs didn't look like the original answer anymore (though the math used is the same) so I decided to post the golfs as a separate answer instead of simply commenting on the TCFP's answer. So if you like this answer, go upvote TCFP's answer as well! ;-)

Intermediate golfs were:

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 bytes

Saved 3 bytes thanks to Kevin Cruijssen.

∞oDÅÉs/˜

Try it online!

Explanation

∞         # 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

Jelly, 9 bytes

Bṙ1Ḅ,æċ2$

Try it online!

PowerShell, 40 bytes

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

Try it online!

Outputs the infinite sequence as decimal values. Given language limitations, will eventually run into precision problems, but easily handles the first 1000 entries.

Starts by setting $i=2, then enters a for loop. Each iteration, we construct a range from 1..$i and pull out the odd values with |?{$_%2}. Those are fed into their own inner loop, where we divide each to get the decimal |%{$_/$i}. Those are left on the pipeline and output when the pipeline is flushed after every for iteration. Each iteration we're simply incrementing $i by $i*=2 to get the next go-round.

Haskell, 35 32 bytes

Edit: -3 bytes thanks to @Delfad0r.

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

This is an infinite list of integer pairs.

Try it online!

Haskell, 40 bytes

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

Try it online!

Infinite sequence as pairs of integers (starting from (1,2)).

Quite a bit longer than @nimi's answer, but the approach is completely different, so I decided to post it anyway.

This solution is based on the following observation.

Consider the infinite sequence

• Replace every number $\frac{i}{j}$ in the sequence with the list $\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\}$$
• Join all the lists into a single sequence: $$\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\}$$
• Add $\frac{1}{2}$ at the beginning of the sequence: $$\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\}$$

Notice how you get back to the sequence you started with!

The solution exploits this fact (together with Haskell's laziness) to compute the sequence s.

Python 2 - 68 66 bytes

-2 bytes thanks to Kevin

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

Try it Online!

Python 3, 53 51 bytes

• Saved two bytes thanks to mypetlion; reusing default parameters to reset n.

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

Try it online!

R, 42 bytes

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

Try it online!

Returns a pair Denominator,Numerator. Uses the formula $\begin{equation}N = 2*\left(n-2^{\lfloor \log_2(n)\rfloor}\right)+1\end{equation}$ from the Josephus sequence and $\begin{equation}D = 2^{\lfloor \log_2(n)\rfloor+1}\end{equation}$ from the other sequence. Happily we are able to re-use the denominator as the two formulas have quite a lot in common!

Racket, 92 91 bytes

(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)))

Try it online!

• Saved a byte thanks to Giuseppe -- removing superfluous whitespace.

MATL, 8 bytes

BnWGEy-Q

Try it online!

Returns Numerator, then Denominator. Uses the same method as my R answer, although it's a bit more efficient.

Explanation, with input 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

Shakespeare Programming Language, 426 bytes

,.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.

Try it online!

Outputs the sequence infinitely as both numbers separated by a space, with each item being separated by a newline.

Python 2, 44 bytes

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

Try it online!

Function returns a tuple of (numerator, denominator). An input of 0 is not handled (it was optional).

Excel 48 28 Bytes

Saved 20 bytes (!) thanks to tsh

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

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

Assumes value in A1, output is in decimal. If you want the output to be in fraction, you can create a custom format for the output cell as "0/###0" and it will show it as fraction.

Explanation: Difficult to explain, since there is a shortcut taken to get to this formula. Basically the numerator is a bit shift left of the input, and the denominator is the next power of 2 higher than the number input.

I originally started with Excel built in functions for BITLSHIFT and BITRSHIFT, but they will shift the entire 48 bits which is not what you want. The functions DEC2BIN (and BIN2DEC) have a limit of -512 to 511 (10 bits) so this wouldn't work. Instead I had to rebuild the number with a modulus of the original number, then times two, then add 1 (since the left digit would always be 1 before a shift).

=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. 

Examples:

C++, 97 75 71 bytes

-26 bytes thanks to 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;}

Testing code :

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 bytes

No input, prints infinite sequence:

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

Try it online!

JavaScript (ES6), 44 bytes

Returns the $n$-th term, 1-indexed.

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

Try it online!

Ruby, 42 bytes

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

Try it online!

Prints integer pairs infinitely, starting from 1/2.

JavaScript (Node.js), 30 bytes

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

Try it online! 0-indexed. Started out as a port of my Batch answer but I was able to calculate in multiples of $\frac{1}{2}$ which saved several bytes.

Ruby, 31 bytes

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

Try it online!

><>, 19 18 bytes

Using xnor's idea, fixed by Jo King, -1 byte by making better use of the mirrors and another -2 bytes by Jo King because the ! was superfluous and ; is not required.

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

Try it online!

Wolfram Language (Mathematica), 22 bytes

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

Try it online!

APL (Dyalog Unicode), 15 bytes

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

Try it online!

Anonymous prefix lambda.

Thanks to Adám for 4 bytes and to Cows quack for 2 bytes.

How:

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 bytes

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

Try it online!

Ungolfed:

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
}