Seuraa 
Viestejä45973

Hei,

Otetaan kaksi N:n mittaista bittijonoa, jossa kummassakin on K bittiä ja N>K. Valitaan yksi kaikista mahdollista (N choose K) jonoista ja verrataan sitä kaikkiin jonoihin: jokaiselle jonolle tehdään looginen JA (AND) -operaatio valitun jonon kanssa ja sen jälkeen lasketaan tulosjonon bittien määrä - esim. jono 011 on itsensä (011) kanssa 011&011=011, missä bittien määrä on 2.

Haluaisin laskea tapauksen jakauman, missä jonoissa on aina päällekäisiä ykkösiä eli 2*K>N. On siis selvää, että tapauksia, joissa ei ole päällekäisiä ykkösiä on nolla. Mutta montako tapausta on muissa tapauksissa 1...K? Kun laskiskelin näitä paperilla, niin yksinkertaisilla tapauksilla näytti, että pascal:n kolmion vinoja rivejä syntyy, mutta en saa mitään järkevää kaavaa aikaiseksi yleiseen tapaukseen. Apuja?

Esim. N=4 ja K=3 (4 choose 3):
0111
1011
1101
1110

valitaan 1110.

0111&1110=0110=>2
1011&1110=1010=>2
1101&1110=1100=>2
1110&1110=1110=>3

K|# yhteiset bitit
0|0
1|0
2|3
3|1

Kommentit (2)

Volta
Seuraa 
Viestejä123
11235
Otetaan kaksi N:n mittaista bittijonoa, jossa kummassakin on K bittiä ja N>K. Valitaan yksi kaikista mahdollista (N choose K) jonoista ja verrataan sitä kaikkiin jonoihin: jokaiselle jonolle tehdään looginen JA (AND) -operaatio valitun jonon kanssa ja sen jälkeen lasketaan tulosjonon bittien määrä - esim. jono 011 on itsensä (011) kanssa 011&011=011, missä bittien määrä on 2.

Haluaisin laskea tapauksen jakauman, missä jonoissa on aina päällekäisiä ykkösiä eli 2*K>N. On siis selvää, että tapauksia, joissa ei ole päällekäisiä ykkösiä on nolla. Mutta montako tapausta on muissa tapauksissa 1...K? Kun laskiskelin näitä paperilla, niin yksinkertaisilla tapauksilla näytti, että pascal:n kolmion vinoja rivejä syntyy, mutta en saa mitään järkevää kaavaa aikaiseksi yleiseen tapaukseen. Apuja?


Jos käsitin oikein, niin eikös tuosta tule jotain tällaista:

Ensinkin voit aina valita sellaisen luvun, jossa on alussa K ykköstä ja sen jälkeen N-K nollaa, koska valitun luvun bittien järjestys ei vaikuta tulokseen. Eli meillä on valittuna luku

1...10...0

Jos nollien määrä N-K on vähintään K, mahtuu kaikki ykköset nollien kohdalle. Tällöin näitä tapauksia on (N-K choose K). Niitä joissa yksi ykkönen on alun ykkösten päällä on (N-K choose K-1) kappaletta. Tapauksia, joissa kaksi ykköstä on ykkösten päällä on (N-K choose K-2) * (K choose 2) jne. Eli tapauksia joissa on n päällekäistä ykköstä on (N-K choose K-n) * (K choose n) kappaletta, jossa toki n on enintään K. Melkein sama toimii vaikka N-K < K, mutta tällöin kaikki ne tapaukset ovat nollia joissa N-K < K-n.

Sisältö jatkuu mainoksen alla
Sisältö jatkuu mainoksen alla

Suosituimmat

Uusimmat

Sisältö jatkuu mainoksen alla

Uusimmat

Suosituimmat