Search
class Person: def __init__(self, name, sex): self.name = name self.sex = sex self.children = [] self.parents = [] # parents of this node self.partner = None # partner (=husband/wife of this node) def addChild(self, node): self.children.append(node) def addParent(self, node): self.parents.append(node) def setPartner(self, node): self.partner = node def __repr__(self): s = "Female" if self.sex == 'F' else "Male" return self.name + " " + s
Vstupní soubor family.txt:
M Jana Jan F M P Jana Martin F M P Jana Robert F M P Robert Gabriel M M P Robert Oleg M M P Robert Ondrej M M P Martin Jiri M M P Martin Rudolf M M P Jan Petra M F P Jan Uxana M F P Uxana Klara F F P Uxana Jakub F M P Uxana Adam F M P Petra Alex F M P A C M M P A D M F P D K F F P C J M M P C I M F P C H M M P B E F F P B F F M P B G F F
Schéma rodiny ve family.txt:
Uložení načtených dat do ' Dot ' souboru, který lze pak vykreslit do png nástrojem dot z balíku nástrojů Graphviz:
dot -Tpng family.dot > family.png
Příklad family.dot:
digraph G { Jana[ color=red]; Jana->Martin [label="child"]; Jana->Robert [label="child"]; Jana->Jan[color=blue; penwidth=4]; Jan[ color=green]; Jan->Petra [label="child"]; Jan->Uxana [label="child"]; Jan->Jana[color=blue; penwidth=4]; Martin[ color=green]; Martin->Jiri [label="child"]; Martin->Rudolf [label="child"]; Martin->Jana [style=dashed]; ... }
Binární halda je binární stromová datová struktura. Je tvořena uzly, které mají max. dva potomky (levý a pravý potomek) (odtud přídavné jméno binární), pričemž potomek je opět uzel. Její důležitou vlastností je, že:
Binární haldu lze samozřejmě realizovat i s opačnou vlastností:
Použití binární haldy:
Předpokládejme, že máme existující binární haldu. Při vyjmutí prvky stačí vzít prvek v kořeni stromu, neboť ten již z definice obsahuje nejmenší hodnotu mezi všemi uzly. Po odebrání prvku je ale nutné zbylé prvky přeskupit a určit nový kořen haldy. Postup je:
Předpokládejme, že máme existující binární haldu. Vložení prvku se provede takto:
Tento algoritmus se nazývá bubble-up, jelikož při něm procházíme haldu ze spodní úrovně nahoru.
Nejjednodušší realizací binární haldy je implementaci na poli. Použijeme jednoduchý trik:
# Implementace haldy # # http://interactivepython.org/runestone/static/pythonds/Trees/BinaryHeapImplementation.html # Jan Kybic, 2016 class MinHeap: """ binární halda, implementovaná pomocí metod """ def __init__(self): self.heap = [] # indexujeme od nuly def bubble_up(self,i): """ probublá prvek 'i', zajistí splnění vlastnosti haldy """ while i>0: j=(i-1)//2 # index rodiče if self.heap[i] >= self.heap[j]: break self.heap[j],self.heap[i]=self.heap[i],self.heap[j] i = j def insert(self,k): self.heap+=[k] self.bubble_up(len(self.heap)-1) def peek(self): """ vrátí nejmenší prvek """ return self.heap[0] def size(self): return len(self.heap) def is_empty(self): return self.size()==0 def bubble_down(self,i): n=self.size() while 2*i+1 < n: j=2*i+1 # zjisti index menšího syna if j+1 < n and self.heap[j] > self.heap[j+1]: j+=1 if self.heap[i]>self.heap[j]: self.heap[i],self.heap[j]=self.heap[j],self.heap[i] i=j def pop(self): """ odeber a vrať nejmenší prvek """ element=self.heap[0] self.heap[0]=self.heap[-1] self.heap.pop() # smaž poslední prvek self.bubble_down(0) return element
Implementujte metody pro odebrání prvku na pozici i z binární haldy:
delete(i)
Pomocí této funkce smažte z haldy vytvořené z pole všechna sudá čísla (Nejdříve haldu vytvořte se všemi čísly a pak smažte všechna sudá čísla z haldy):
pole=[10,21,7,11,31,6,1,-11,31,42,-12,80,25,-7,-12,9,14]
cards = [[0, 'Q'], [2, '6'], [1, 'K'], [1, '8'], [2, '10'], [2, '4'], [3, '4'], [0, '4'], [1, '3'], [2, '5'], [0, 'K'], [3, 'A'], [1, 'J'], [0, '3'], [0, '9']]
conv={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
for line in sys.stdin: # zpracuj line
60 se 58 zbraní 90 zelnou 38 mě 100 Polévku 57 střelnou 80 jedla -1 -1 -1 32 polila 20 skolila 51 pasem 24 ji 75 jsem -1 -1 40 kdyby 55 za -1 -1 25 bych 30 na -1 -1 35 byla 27 místě
Polévku zelnou jedla jsem se zbraní střelnou za pasem kdyby mě byla polila na místě bych ji skolila
Úkolem je implementovat kompresi textu pomocí algoritmu LZ77.
for line in sys.stdin:
zn = chr(0x80 | (offset << 2) | ((length-2)&0x3))
Vstupní řádka obsahuje
nenaolejuje-li te julie naolejuje te julian
nenaolejuje-li te °À·µan
nenaolejuje-li te (7,2)(12,2)(16,2)(2,5)(7,4)(13,5)(13,3)an
nenaole|ju|je-li te (7,2) 0123456|78|911111111 | | 01234567 |ju|
enaolejuje-li| te j|ulie naolejuje(13,5) 0123456789111|11111|11222222222233 012|34567|89012345678901 | te j|
length = 2+(ord(zn)&3) offset = ((ord(zn)>>2) & 0x1f)
python3 lz77.py -d <rikadla_lz.txt >rikadla.txt
python3 lz77.py <rikadla.txt >rikadla.lz