2 svar
102 visningar
SeriousCephalopod är nöjd med hjälpen!
SeriousCephalopod 1775
Postad: 26 apr 2019 Redigerad: 26 apr 2019

[Kluring] Hitta en binär sträng i en "sorterad" lista av 2^64 strängar (prog)

Drygt ett år sedan postade jag två "hitta ordet i listan"-problem. Här kommer ett nytt liknande problem som jag dock formulerar i sifferspråk.

Introduktion: 

Låt säga att man tagit de binära strängarna av längd 4 och skrivit ut dem i numerisk storleksordning

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

Här är alltså 0101 den 5:e strängen i listan. (Vi räknar från 0!) Av någon anledning vill man istället sortera dem så att talen med minst antal ettor i representationen kommer före de med fler ettor, men att talen med lika många ettor är sorterade i numerisk storleksordning relativt varandra

0000, 0001, 0010, 0100, 1000, 0011, 0101, 0110, 1001, 1010, 1100, 0111, 1011, 1101, 1110, 1111

Här är alltså 0011 det 5:e talet. Låt oss kalla detta "siffersortering". 


Problemet: 

Låt säga att man skulle siffersorterar alla binära strängar av längd 64. Vilken vore då den 10402927437586948002:a strängen som förekommer i listan?

När du har funnit strängen konvertera den till decimalt och presentera det som svaret

n=k=063dk2kn = \sum_{k = 0}^{63} d_k 2^{k}

[Har vi båda gjort rätt så känner du igen talet]


((Notera att 0000000000000000000000000000000000000000000000000000000000000000 är den 0:e strängen och 0000000000000000000000000000000000000000000000000000000000000001 är den 1:a strängen. ))

AlvinB 3030
Postad: 2 dagar sedan

Jag såg att detta var olöst, och så kan vi ju inte ha det, så jag spenderade eftermiddagen med att programmera mig fram till lösningen på detta.

Det enda programmeringsspråket jag är bekant med är Java, vars system för att göra aritmetik med stora tal är ganska krångligt, så jag tänkte att jag kanske skulle ge en förklaring av mitt tillvägagångssätt snarare än att bara visa min kod.

Det första att ta itu med är att klura ut hur många ettor talet innehåller. Jag resonerade mig fram till att det finns nCr(64,0)=1\text{nCr}(64,0)=1 tal med 00 ettor, nCr(64,1)=64\text{nCr}(64,1)=64 tal med 11 etta, o.s.v. (Man kan ju se det som att man väljer ut ett visst antal av 6464 siffror till att vara ettor.). Det betyder att talen med 00 ettor börjar på index 00, talen med 11 etta börjar på index 11, talen med 336565 o.s.v. Med datorhjälp kommer man fram till att talen med 3333 ettor börjar på 1013968410732607107510139684107326071075 och talen med 3434 ettor börjar på 1191677418339161341111916774183391613411. Det 1040292743758694800210402927437586948002:a talet måste därför ha 3333 ettor.

Om man utför subtraktionen 10402927437586948002-10139684107326071075=26324333026087692710402927437586948002-10139684107326071075=263243330260876927 (vårt index minus indexet där talen med 3333 ettor börjar) finner vi att vi söker det 263243330260876927263243330260876927:e talet med 3333 ettor (räkningen börjar på noll). Jag tänker nu att vi gör en ny lista med bara talen med 3333 ettor.

Nästa steg var att klura ut hur många av talen med 3333 ettor som börjar på noll. Då tänkte jag som så att vi fixerar den första nollan, och har därför nCr(63,33)\text{nCr}(63,33) val för övriga siffror, vilket enligt multiplikationsprincipen ger att nCr(63,33)\text{nCr}(63,33) av talen som har 3333 ettor börjar på noll.

0AA...AAnCr(63,33) val0\underbrace{\boxed{\color{transparent}A}\boxed{\color{transparent}A}...\boxed{\color{transparent}A}\boxed{\color{transparent}A}}_{\text{nCr}(63,33)\ \text{val}}

Alltså börjar de nCr(63,33)=860778005594247069\text{nCr}(63,33)=860778005594247069 första talen på 00, och eftersom 263243330260876927<860778005594247069263243330260876927<860778005594247069 är den första siffran i vårt tal noll. Vi kan nu göra ett liknande resonemang för den andra siffran. Man ser att nCr(62,33)\text{nCr}(62,33) av talen som börjar på noll även har noll som andra siffra. Eftersom 263243330260876927<nCr(62,33)263243330260876927<\text{nCr}(62,33) får vi att den andra siffran i vårt tal är noll. Proceduren upprepas, och den enda skillnaden ifall vi skulle få en etta (d.v.s. indexet är större än eller lika med binomialkoefficienten) är att indexet då måste justeras till nästa gång genom att subtrahera binomialkoefficienten (ettorna kommer ju efter nollorna).

Man får då till slut att den binära strängen är:

00101011100110010010110111011111101000100011001001001001110101100010101110011001001011011101111110100010001100100100100111010110

vilket i det decimala systemet blir:

31415926535897932383141592653589793238

men detta mystiska tal känner jag inte igen.

(Dock finns det ett välkänt tal som är ganska precist en 101710^{17}-del så stort :-))

SeriousCephalopod 1775
Postad: 2 dagar sedan Redigerad: 2 dagar sedan

Snyggt jobbat och väl förklarat Alvin. 

Svara Avbryt
Close