Gegeben seien zwei beliebig genaue dezimale Zahlen 0 ≤ x < y ≤ 1, berechnen die kürzeste (in Ziffern) binäre Zahl b so dass x ≤ b < y .

Geben Sie die Binärziffern von b nach dem Binärpunkt als Array oder als Zeichenfolge aus Nullen und Einsen aus. Beachten Sie, dass das leere Array 0,0 bedeutet, da nachgestellte Nullen gelöscht werden. Dies stellt auch sicher, dass es für jeden Bereich eine eindeutige richtige Antwort gibt.

Wenn Sie mit binären Bruchzahlen nicht vertraut sind, funktionieren sie genau wie Dezimalzahlen:

Base 10   0.625 = 0.6 + 0.02 + 0.005 = 6 x 10^-1  +  2 x 10^-2  +  5 x 10^-3
Base  2   0.101 = 0.1 + 0.00 + 0.001 = 1 x  2^-1  +  0 x  2^-2  +  1 x  2^-3
                                          |             |             |
                                          v             v             v
Base 10                        0.625 =   0.5      +     0       +   0.125

Integrierte Funktionen, die dieses Problem trivialisieren, sind nicht zulässig.

Beispiele:

0.0, 1.0 -> ""
0.1, 1.0 -> "1"
0.5, 0.6 -> "1"
0.4, 0.5 -> "0111"

Der kürzeste Code gewinnt.

CJam, 46

q'.-_,:M;S/{3a.+M'0e]~GM#*AM(#/(2b}/_@.=0#)<2>

Probieren Sie es online aus

Erläuterung:

Die allgemeine Idee ist: multiplizieren beide Zahlen um 10 ^{einige groß genug Exponent} ganze Zahlen zu erhalten, mehrfach wieder um 2 einen ^{weiteren großen genug Exponenten} zu „make room“ für Binärzahlen in integer Form, integer-divide zurück um 10 ^{der erste Exponent} , verringern die Zahlen (um zum Fall "x <b ≤ y" zu gelangen) und konvertieren Sie die Ergebnisse in Basis 2. Suchen Sie die erste andere Ziffer (sie ist 0 in der ersten Zahl und 1 in der zweiten Zahl) und drucken Sie alle Ziffern aus von der zweiten Nummer bis einschließlich dieser.

Bevor ich mit den Multiplikationen beginne, addiere ich 3 zu den ganzzahligen Teilen, um sicherzustellen, dass die Ergebnisse nach dem Dekrementieren die gleiche Anzahl von Binärziffern (ohne führende Nullen) haben. Am Ende überspringe ich die ersten 2 Binärziffern, um dies zu kompensieren.

q          read the input as a string
'.-        remove the dots
_,         duplicate and get the string length
:M;        store in M and pop; M-1 will be the first exponent
S/         split by space
{…}/       for each number (in string form)
  3a.+     add 3 to the first digit (vectorized-add [3] to the string)
  M'0e]    pad to the right with '0's up to length M
            this is like multiplying the decimal number with 10^(M-1)
            but done as a string operation
  ~        evaluate the result as an integer
  GM#*     multiply by 16^M (G=16) = 2^(4*M) -- 4*M is the second exponent
  AM(#/    divide by 10^(M-1) (A=10)
  (2b      decrement and convert to base 2 (array of digits)
_          duplicate the 2nd array
@          bring the first array to the top
.=         vectorized-compare the arrays (digit by digit)
0#         find the position of the first 0 (meaning digits are not equal)
)<         increment and slice the other copy of the 2nd array before that position
2>         discard the first 2 digits

Ruby, 138 132 Bytes

->x,y{d,*a=->{a.map.with_index{|n,i|n/BigDecimal.new(2)**(i+1)}.inject(:+)||0};[a+=[1],a[-1]=d[]>=y ?0:1]while d[]<x;a}

13 Bytes für das -rbigdecimalFlag hinzugefügt . Erwartet die Eingabe als zwei BigDecimals.

Probelauf:

irb(main):029:0> f=->x,y{d,*a=->{a.map.with_index{|n,i|n/BigDecimal.new(2)**(i+1)}.inject(:+)||0};[a+=[1],a[-1]=d[]>=y ?0:1]while d[]<x;a}
=> #<Proc:0x00000001053a10@(irb):29 (lambda)>
irb(main):030:0> f[BigDecimal.new('0.98983459823945792125172638374187268447126843298479182647'),BigDecimal.new('0.98983459823945792125172638374187268447126843298479182648')]
=> [1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1]

Erläuterung:

->x,y{
d,*a=   # sets d to the following, and a to [] with fancy splat operator
->{     # lambda...
 a.map.with_index{|n,i|       # map over a with indices
  n/BigDecimal.new(2)**(i+1)  # this will return:
                              #  - 0 [ /2**(i+1) ] if n is 0
                              #  - 1   /2**(i+1)   if n is 1
 }.inject(:+)                 # sum
 ||0                          # inject returns nil on empty array; replace with 0
};      # this lambda turns `[0, 1, 1]' into `BigDecimal(0b0.011)'
[       # `[...]while x' is a fancy/golfy way to say `while x;...;end'
 a+=[1],            # add a digit 1 to the array
 a[-1]=d[]>=y ?0:1  # replace it with 0 if we exceeded upper bound
]while d[]<x;       # do this while(below the lower bound)
a       # return the array of digits
}

Mathematica, 72 Bytes

IntegerDigits[#2[[-1,-1]],2,Log2@#]&@@Reap[1//.a_/;Sow@⌈a#⌉>=a#2:>2a]&

Erläuterung

Die Methode besteht darin, den kleinsten 2^nFormmultiplikator zu finden, der die Lücke zwischen zwei Eingangszahlen vergrößert, so dass er eine ganze Zahl enthält.

Zum Beispiel 16*{0.4,0.5} = {6.4,8.}enthält 7, so lautet die Antwort 7/16.

Testfall

%[0.4,0.5]
(* {0,1,1,1} *)

JavaScript (ES6), 144 Byte

f=(x,y,b='',d=s=>s.replace(/\d/g,(n,i)=>(i&&n*2%10)+(s[i+1+!i]>4)).replace(/[.0]+$/,''),n=d(x),m=d(y))=>n?n>'1'||(m||2)<='1'?f(n,m,b+n[0]):b+1:b

Nimmt die Eingabe im Formular an 0.<digits>(oder 1.<zeros>ist akzeptabel für y). dist eine Funktion, die den Dezimalteil einer Zahl nimmt und verdoppelt und dann nachgestellte Nullen abschneidet. Die führende Ziffer muss vorhanden sein, wird jedoch ignoriert. Praktischerweise d("0.0")ist es leer, und dies wird daher als Test verwendet, um festzustellen, ob xes sich um einen exakten binären Bruch handelt. in diesem Fall bhält bereits das Ergebnis. Andernfalls gibt es einen etwas komplizierten Test, um festzustellen, ob das Suffix a 1to bzur Unterscheidung zwischen xund dient y; wenn ja, wird das zurückgegeben. Andernfalls wird das MSB von xan das Ergebnis angehängt und die Funktion ruft sich rekursiv auf, um das nächste Bit zu verarbeiten.

Wenn wir stattdessen wünschen, dass x < b ≤ ydie Funktion viel einfacher ist, so etwas (ungetestet):

f=(x,y,b='',d=s=>s.replace(/\d/g,(n,i)=>(i&&n*2%10)+(s[i+1+!i]>4)),n=d(x),m=d(y))=>n>='1'||m<'1'?f(n,m,b+n[0]):b+1