V nalogi dobimo seznam števil v dvojiškem zapisu. Odkriti moramo, kakšna je najpogostejša vrednost prvega bita, drugega bita in tako naprej do konca. Če je obojih enako, rečemo, da je pogostejša enica. Te, najpogostejše vrednosti sestavimo v število. Se pravi, vsak bit novega števila izračunamo kot najpogostejšo vrednost bit na tem mestu med vsemi števili na seznamu.
To število moramo nato pomnožiti s komplementom tega števila.
Podatki so videti takole:
00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010
Preberimo jih v tabelo: odpremo datoteko, gremo z zanko
for
čez vrstice, vsaki vrstici odluščimo \n
,
nato pa gremo čez znake te vrstice in vsakega posebej spremenimo v
int
. Vse skupaj zložimo v seznam in ga damo funkciji
np.array
.
import numpy as np
= np.array([[int(x) for x in v.strip()] for v in open("example.txt")])
data data
array([[0, 0, 1, 0, 0],
[1, 1, 1, 1, 0],
[1, 0, 1, 1, 0],
[1, 0, 1, 1, 1],
[1, 0, 1, 0, 1],
[0, 1, 1, 1, 1],
[0, 0, 1, 1, 1],
[1, 1, 1, 0, 0],
[1, 0, 0, 0, 0],
[1, 1, 0, 0, 1],
[0, 0, 0, 1, 0],
[0, 1, 0, 1, 0]])
Mimogrede poglejmo še dimenzije naše tabele:
data.shape
(12, 5)
Prva dimenzija ima velikost 12; imamo 12 vrstic. Druga je 5, 5 stolpcev oziroma, v naši zgodbi, bitov.
Najpogostejšo vrednost v vrstici lahko dobimo, recimo, tako da izračunamo vsoto po osi (dimenziji) 0, torej po vrsticah.
sum(data, axis=0) np.
array([7, 5, 8, 7, 5])
Enica je večinska vrednost, kadar je ta vsota večja (ali enaka) od
polovice števila vrstic. To dobimo z len(data)
ali z
data.shape[0]
. data.shape
je namreč terka, ki
vsebuje dimenziji tabele.
sum(data, axis=0) >= data.shape[0] / 2 np.
array([ True, False, True, True, False])
Kar smo pravkar naračunali, poimenujmo bits
. To sicer ni
potrebno, a da bomo lepše videli, kaj se dogaja, pretvorimo tabelo iz
bool
v int
.
= (np.sum(data, axis=0) >= data.shape[0] / 2).astype(int)
bits
bits
array([1, 0, 1, 1, 0])
Namesto seštevanja in primerjanja z dolžino, bi lahko s funkcijo
np.mean
izračunali poprečno vrednost in preverjali, ali je
večje ali enako 0.5.
Tudi to, kar sledi - pretvarjanje v desetiški zapis - bi lahko naredili na več načinov. Tu bomo uporabili najbolj zabavnega in poučnega. Glede na gornjo tabelo je število, ki ga iščemo, enako
1 * 16 + 0 * 8 + 1 * 4 + 1 * 2 + 0 * 1
Zmnožiti moramo torej naslednji tabeli
[ 1, 0, 1, 1, 0]
[16, 8, 4, 2, 1]
Prvo imamo, drugo moramo pripraviti. Kako pripravimo tabelo potenc dvojke?
Najprej pripravimo števila od 0 do toliko, kolikor bitov imamo.
Število bitov, kot smo videli, izvemo v data.shape[1]
1]) np.arange(data.shape[
array([0, 1, 2, 3, 4])
Izračunati moramo tabelo [2 ** 0, 2 ** 1, 2 ** 2, ...]
.
Se pravi
2 ** np.arange(data.shape[1])
array([ 1, 2, 4, 8, 16])
Vse skupaj moramo še obrniti, saj mora biti najpomembnejši bit, 16,
na levi. Potence shranimo v powers
.
= 2 ** np.arange(data.shape[1])[::-1]
powers
powers
array([16, 8, 4, 2, 1])
Če tabeli zmnožimo, dobimo
* bits powers
array([16, 0, 4, 2, 0])
To moramo le še sešteti.
sum(powers * bits) np.
22
Komplement bomo dobili z 1 - bits
(če tabele ne bi
spreminjali iz bool
v int
, pa bi lahko
uporabili tudi operator za dvojiški komplement, ~bits
).
sum(powers * (1 - bits)) np.
9
Celotna rešitev prvega dela je torej
= (np.sum(data, axis=0) >= data.shape[0] / 2).astype(int)
bits sum(powers * bits) * np.sum(powers * (1 - bits)) np.
198