Implementacija s tabelo logičnih vrednosti

Denimo, da se omejimo na množice, ki vsebujejo kvečjemu cela števila med 0 in vključno Z − 1, pri čemer je Z neko ne preveliko celo število. Takšno množico lahko predstavimo s tabelo z Z elementi logičnega tipa. Če število i pripada množici, ima element tabele na indeksu i vrednost True, sicer pa False. Na primer če vzamemo Z = 10, potem množico {0, 2, 3, 7} predstavimo s to tabelo:

[True, False, True, True, False, False, False, True, False, False]

Vaja

Kako bi z drugimi besedami opisal množico, ki jo predstavlja spodnja tabela z 2k elementi?

[True, False, True, False, True, False, ..., True, False]

Tovrstna predstavitev množice je časovno izjemno učinkovita. Prisotnost števila x ∈ {0, 1, ... , Z − 1} preverimo tako, da preverimo vrednost elementa v tabeli na indeksu x. Število x v množico dodamo tako, da element tabele na indeksu x postavimo na True, pri odstranjevanju pa pripadajoči element tabele postavimo na False. Časovna zahtevnost vseh treh operacij znaša O(1), saj je čas, ki ga potrebujejo operacije, povsem neodvisen od števila elementov v množici, pa tudi od velikosti tabele. Oglejmo si modul mnozicaTabelaLogicnih.py (glej kodo).

V razmislek

Kaj se zgodi, če s funkcijo Dodaj v množico dodamo celo število izven intervala med 0 in Z − 1 ali pa vrednost nekega drugega tipa?

# Implementacija množice s tabelo logičnih # vrednosti # Vrne prazno množico, ki lahko vsebuje kvečjemu # števila od 0 do vključno Z - 1. def Ustvari(Z): # Na naslednji način najlažje ustvarimo tabelo, # sestavljeno iz Z elementov False. return [False] * Z # Vrne True, če je podani element prisoten v # podani množici, sicer pa vrne False. def JePrisoten(mnozica, element): return mnozica[element] # Doda podani element v podano množico. def Dodaj(mnozica, element): mnozica[element] = True # Odstrani podani element iz podane množice. def Odstrani(mnozica, element): mnozica[element] = False # Vrne niz, ki predstavlja podano množico; # npr. '{1, 2, 3}' za množico, ki vsebuje # elemente 1, 2 in 3. def NizElementov(mnozica): # Elementi množice so sestavljeni iz indeksov # vseh elementov z vrednostjo True. izpis = [] for indeks in range(len(mnozica)): if mnozica[indeks]: izpis.append(str(indeks)) # Združimo nize iz tabele in niz izpišemo. return ('{' + ', '.join(izpis) + '}') def main(): razpon = 20 s = 'Množica lahko vsebuje števila od 0 do ' s += str(razpon - 1) + '.' print(s) t = [5, 2, 5, 5, 1, 6, 8, 3, 2, 3] print('Ustvarjam prazno množico m ...') m = Ustvari(razpon) for element in t: print('Dodajam element: ' + str(element)) Dodaj(m, element) print('Množica m: ' + NizElementov(m)) print('JePrisoten(m, 3): ' + str(JePrisoten(m, 3))) print('JePrisoten(m, 5): ' + str(JePrisoten(m, 5))) print('JePrisoten(m, 6): ' + str(JePrisoten(m, 6))) print('JePrisoten(m, 7): ' + str(JePrisoten(m, 7))) print('Odstranjujem element: 3') Odstrani(m, 3) print('JePrisoten(m, 3): ' + str(JePrisoten(m, 3))) print('Množica m: ' + NizElementov(m)) # Spomnimo se: s spodnjima vrsticama dosežemo, # da lahko modul uporabljamo tudi kot samostojen # program. if __name__ == '__main__': main()

Izvedi Počisti