Olkoon S(n) luvut n binaariesityksessä olevien ykkösten lukumäärä. Laske S(1) S(2) ... S(123456). Onnistuuko vaikapa Wolfram Alphalla? Ei oikeastaan väliä, miten summa saadaan laskettua, mutta omat yritykseni ovat kaatuneet huolimattomuusvirheisiin, ja en ole oikeasta tuloksesta varma.
Kombinatorinen probleema
probleemapolle
15296
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 15
Vanhimmat
Tällainen koodinpätkä Octaveen laitettuna (toivottavasti näkyy oikein):
s=0;for i=1:123456;s=s length(find(dec2bin(3)=='1'));end;s
antaa tällaisen lopputuloksen:
s = 246912
Toinen tapa laskea sama tulos on toki tämä:
123456*2 = 246912
Kiitos avusta. Octave ei ollut tuttu, mutta sain ratkaistua probleeman. Tosin koodina tulee olla
s=0;for i=1:123456;s=s length(find(dec2bin(i)=='1'));end;s
eikä kirjoittamasi.
Paljonko sait tulokseksi?
Ups, ai *siksi* se tulos olikin niin yksinkertainen... siis oikea on
s = 1032966
Kaikissa binääriluvuissa, joissa on enintään n merkkiä ("bittiä"), on yhteensä n*2^(n-1) ykköstä. Tämä siksi, että näitä lukuja on 2^n kappaletta (kun nollakin lasketaan mukaan), niissä kaikissa on n merkkiä (etunollat mukaanlukien), ja jokainen merkki on yhtä usein 0 ja 1 (siksi tuo -1 siinä potenssissa).
Niinpä kaikissa binääriluvuissa luvusta 1 lukuun 2^m (ykkönen ja m nollaa) asti on yhteensä m*2^(m-1) 1 ykköstä. (Kaikkien m merkkiä pitkien lukujen ykkösten määrä plus yksi lisää siitä 2^m luvusta, joka sisältää tasan yhden ykkösen).
123456 on 2^17 2^16 2^15 2^14 2^10 2^7 (binäärilukuna siis 11110001001000000). Ykkösten yhteismäärä tästä ja kaikista tätä pienemmistä luvuista saadaan laskettua laskemalla 2^17 ja pienempien lukujen ykkösten määrä plus 2^16 ja pienempien jne, käyden kaikki tuon luvun kakkosen potenssit läpi.
Ykkösiä on siis yhteensä 17*2^16 16*2^15 15*2^14 14*2^13 10*2^9 7*2^6 6 kpl.
Sain vastaukseksi 2004332.
Pari korjausta tähän. Ensinkin:
123456 = 2^16 2^15 2^14 2^13 2^9 2^6
kuten vaikka copypasteamalla Octaveen voi tarkistaa. n-pituisten binäärilukujen kaavasi menee oikein, mutta yhdistetyssä luvussa unohdit laskea mukaan ne päällä olevat ylemmät bitit alempia bittejä käsitellessä. Siispä oikea tulos saadaan näin:
6*2^15 15*2^14 14*2^13 13*2^12 9*2^8 6*2^5 6
2^15 2*2^14 3*2^13 4*2^9 5*2^6
= 1032966
Tuon n-pituisten binäärilukujen tuloksen voi johtaa myös rekursioyhtälöllä näin:
Olkoon n pituisissa binääriluvuissa (2^n kpl) yhteensä f(n) ykkästä. Tällöin kaikki n 1 pituiset saadaan, kun yhdistetään n-pituiset luvut 0-alulla ja vielä samat 1-alulla. Siispä ykkösiä on yhteensä
f(n 1) = 2^n 2 f(n)
Lisäksi tiedetään, että f(1) = 1. Otetaan z-muunnos:
z F(z) = 1 / (1 - 2z^-1) 2 F(z)
josta
F(z) = z^-1 / (1 - 2z^-1)^2
ja edelleen käänteis z-muunnoksella
f(n) = n 2^(n-1)
Tajusin itsekin myöhemmin tehneeni nuo pari virhettä, mutten jaksanut yöllä enää laittaa konetta päälle ja kirjoitella korjausta (ja ehkä herättää ja suututtaa tuota parempaa puoliskoa).
Algoritminahan tämä tapa on paljon tehokkaampi kuin tuo ylempänä ketjussa esitetty "brute force" metodi. Vaikkei sillä nykyajan tietokoneilla mitään väliä olekaan ellei laskettavat luvut ole todella isoja.
"Algoritminahan tämä tapa on paljon tehokkaampi kuin tuo ylempänä ketjussa esitetty "brute force" metodi. Vaikkei sillä nykyajan tietokoneilla mitään väliä olekaan ellei laskettavat luvut ole todella isoja."
Niinpä, tämä on O(n) bittien määrän suhteen kun brute force on O(2^n). Esimerkkiksi summa S(1) ... S(10^100) onnistuu vielä ihan hyvin toisin kuin brute-forcella.
Sivumennen sanoen nykyajan ohjelmointityylinä tuntuisi olevan käyttää yleisesti ottaen tuollaisia brute-force-taktiikoita ilman kummenpaa ajattelua (kiire, scrummin sprintti loppuu kohta, asiakas suuttuu, jne). Kehityssykli on toki lyhyt, mutta hidasta softaahan siitä tulee. Ainahan voi tietysti ostaa tehokkaamman tietokoneen, mutta ei se tuohon eksponentiaaliseen kompleksisuuteen taida auttaa...
"Sivumennen sanoen nykyajan ohjelmointityylinä tuntuisi olevan käyttää yleisesti ottaen tuollaisia brute-force-taktiikoita ilman kummenpaa ajattelua"
Tämä on niin totta. Valitettavasti. Itse olen yrittänyt pitää sellaista linjaa, että jos koodi on kertakäyttöistä (yhden ainutkertaisen ongelman ratkaisu), antaa mennä vaan, mutta jos sitä tarvitaan toistekin, parempi tehdä kerralla kunnolla.
vaikkapa luvuissa 1,2,...,1234567890123456789012345678901234567890?
Suurin piirtein 8.001156514440549e 40.
1234567890123456789012345678901234567890 on binäärinä:
1110100000110010010010000001110101110000001101101111110011101110001010110010111100010111111001011011001110001111110000101011010010,
joten siitä tulee:
129*2^128 128*2^127 127*2^126 125*2^124 119*2^118 118*2^117 115*2^114 112*2^111 109*2^108 102*2^101 101*2^100 100*2^99 98*2^97 96*2^95 95*2^94 94*2^93 87*2^86 86*2^85 84*2^83 83*2^82 81*2^80 80*2^79 79*2^78 78*2^77 77*2^76 76*2^75 73*2^72 72*2^71 71*2^70 69*2^68 68*2^67 67*2^66 63*2^62 61*2^60 59*2^58 58*2^57 55*2^54 53*2^52 52*2^51 51*2^50 50*2^49 46*2^45 44*2^43 43*2^42 42*2^41 41*2^40 40*2^39 39*2^38 36*2^35 34*2^33 33*2^32 31*2^30 30*2^29 27*2^26 26*2^25 25*2^24 21*2^20 20*2^19 19*2^18 18*2^17 17*2^16 16*2^15 11*2^10 9*2^8 7*2^6 6*2^5 4*2^3 2^0 2^128 2*2^127 3*2^125 4*2^119 5*2^118 6*2^115 7*2^112 8*2^109 9*2^102 10*2^101 11*2^100 12*2^98 13*2^96 14*2^95 15*2^94 16*2^87 17*2^86 18*2^84 19*2^83 20*2^81 21*2^80 22*2^79 23*2^78 24*2^77 25*2^76 26*2^73 27*2^72 28*2^71 29*2^69 30*2^68 31*2^67 32*2^63 33*2^61 34*2^59 35*2^58 36*2^55 37*2^53 38*2^52 39*2^51 40*2^50 41*2^46 42*2^44 43*2^43 44*2^42 45*2^41 46*2^40 47*2^39 48*2^36 49*2^34 50*2^33 51*2^31 52*2^30 53*2^27 54*2^26 55*2^25 56*2^21 57*2^20 58*2^19 59*2^18 60*2^17 61*2^16 62*2^11 63*2^9 64*2^7 65*2^6 66*2^4 67*2^1 68
Saat itse laskea tuloksen.
Ohhoh, rivit katkesi. Uusi yritys:
1234567890123456789012345678901234567890 on binäärinä:
111010000011001001001000000111010111000
000110110111111001110111000101011001011
110001011111100101101100111000111111000
0101011010010
joten siitä tulee:
129*2^128
128*2^127
127*2^126
125*2^124
119*2^118
118*2^117
115*2^114
112*2^111
109*2^108
102*2^101
101*2^100
100*2^99
98*2^97
96*2^95
95*2^94
94*2^93
87*2^86
86*2^85
84*2^83
83*2^82
81*2^80
80*2^79
79*2^78
78*2^77
77*2^76
76*2^75
73*2^72
72*2^71
71*2^70
69*2^68
68*2^67
67*2^66
63*2^62
61*2^60
59*2^58
58*2^57
55*2^54
53*2^52
52*2^51
51*2^50
50*2^49
46*2^45
44*2^43
43*2^42
42*2^41
41*2^40
40*2^39
39*2^38
36*2^35
34*2^33
33*2^32
31*2^30
30*2^29
27*2^26
26*2^25
25*2^24
21*2^20
20*2^19
19*2^18
18*2^17
17*2^16
16*2^15
11*2^10
9*2^8
7*2^6
6*2^5
4*2^3
2^0
2^128
2*2^127
3*2^125
4*2^119
5*2^118
6*2^115
7*2^112
8*2^109
9*2^102
10*2^101
11*2^100
12*2^98
13*2^96
14*2^95
15*2^94
16*2^87
17*2^86
18*2^84
19*2^83
20*2^81
21*2^80
22*2^79
23*2^78
24*2^77
25*2^76
26*2^73
27*2^72
28*2^71
29*2^69
30*2^68
31*2^67
32*2^63
33*2^61
34*2^59
35*2^58
36*2^55
37*2^53
38*2^52
39*2^51
40*2^50
41*2^46
42*2^44
43*2^43
44*2^42
45*2^41
46*2^40
47*2^39
48*2^36
49*2^34
50*2^33
51*2^31
52*2^30
53*2^27
54*2^26
55*2^25
56*2^21
57*2^20
58*2^19
59*2^18
60*2^17
61*2^16
62*2^11
63*2^9
64*2^7
65*2^6
66*2^4
67*2^1
68
Saat itse laskea tuloksen.
Tuohon muualla tässä ketjussa esittämääni rekursioon perustuva pieni Python-ohjelma:
def f(n):
if n==0:
return 0;
if (n/2)*2==n:
return b(n) f(n-1);
else:
return 2*f((n-1)/2) ((n 1)/2);
def b(n):
m=0;
while n>0:
if (n/2)*2 1==n:
m=m 1;
n=n/2;
return m;
a=input('Kokonaisluku: ')
while a!=0:
print f(a);
a=input('Kokonaisluku: ');
antaa tulokseksi ratkaisun:
f(1234567890123456789012345678901234567890
)=
80011565144405472451914694449473938840267
Olkoon f(n) ykkösbittien kokonaislukumäärää kuvaava funktio.
Alkupään arvoja tarkastelemalla löydetään seuraava luvun n toistuvaan kahdella jakamiseen perustuva rekursio:
1) f(0)=0
2) Kun n on suurempi kuin 0, niin:
jos n on pariton, niin
f(n) = 2*f((n-1)/2) (n 1)/2
muuten
f(n) = S(n) f(n-1),
missä S(n) on luvun n sisältämien ykkösbittien lukumäärä sen binäärilukuesityksessä.
(Siis f(n)=S(0) S(1) ... S(n).)
Tapauksessa n=123456 saadaan:
f(123456)
= f(123455) 6
= 6 (2*f(61727) 61728)
= 61734 2*f(61727)
= 61734 2(2*f(30863) 30864)
= 123462 4*f(30863)
= 123462 4(2*f(15431) 15432)
= 185190 8*f(15431)
= 185190 8(2*f(7715) 7716)
= 246918 16*f(7715)
= 246918 16(2*f(3857) 3858)
= 308646 32*f(3857)
= 308646 32(2*f(1928) 1929)
= 370374 64*f(1928)
= 370374 64(f(1927) 5)
= 370694 64*f(1927)
= 370694 64(2*f(963) 964)
= 432390 128*f(963)
= 432390 128(2*f(481) 482)
= 494086 256*f(481)
= 494086 256(2*f(240) 241)
= 555782 512*f(240)
= 555782 512(f(239) 4)
= 557830 512*f(239)
= 557830 512(2*f(119) 120)
= 619270 1024*f(119)
= 619270 1024(2*f(59) 60)
= 680710 2048*f(59)
= 680710 2048(2*f(29) 30)
= 742150 4096*f(29)
= 742150 4096(2*f(14) 15)
= 803590 8192*f(14)
= 803590 8192(f(13) 3)
= 828166 8192*f(13)
= 828166 8192(2*f(6) 7)
= 885510 16384*f(6)
= 885510 16384(f(5) 2)
= 918278 16384*f(5)
= 918278 16384(2*f(2) 3)
= 967430 32768*f(2)
= 967430 32768(f(1) 1)
= 1000198 32768(2*f(0) 1)
= 1000198 32768(2*0 1)
= 1032966
Tehtävän ratkaiseminen tällä tavalla on siis melko suoraviivaista, mutta käsinlaskennassa tuntuu hiukan työläältä tavalta.
Kuitenkin tällaiset peräkkäiseen kahdella jakamiseen perustuvat ratkaisualgoritmit ovat tietotekniikassa varsin yleisesti käytettyjä. Ne ovat varsin helposti ohjelmoitavia ja tietokonelaskennassa myös tehokkaita, kunhan eivät haaraudu.