Search
Mějme tři nádoby o objemu 2, 5, 9. S nádobami můžeme provádět následující akce:
Napište program, který najde nejmenší počet kroků takový, že v poslední nádobě bude objem 6.
Naplánujte nejkratší cestu pro šachového koně z políčka 2 na políčko 4. Sudá čísla znamenají volné políčko, lichá čísla obsazené.
m=[[0,0,0,0,0,0,0,0], [0,0,0,0,0,0,4,0], [0,0,0,0,1,0,0,0], [1,1,1,0,1,1,0,0], [0,0,0,1,0,1,0,0], [0,2,0,0,0,1,0,0], [0,0,0,0,0,1,0,0], [0,0,0,0,0,1,0,0]]
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
P name1 name2 sex1 sex2
name1
name2
sex1
sex2
M name1 name2 sex1 sex2
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: """ binarni halda __init__ konstruktor """ def __init__(self): self.heap = [] # indexujeme od nuly def bubble_up(self,i): """ probubla prvek i nahoru, zajisti splneni podminek haldy """ while i>0: j=(i-1)//2 # index rodice 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): """ vloz prvek do haldy """ self.heap+=[k] self.bubble_up(len(self.heap)-1) def peek(self): """ vrati nejmensi prvek """ return self.heap[0] def size(self): """ vrati pocet prvku v halde """ return len(self.heap) def is_empty(self): """ je halda prazdna? """ return self.size()==0 def bubble_down(self,i): """ probublej prvek dolu """ n=self.size() while 2*i+1 < n: j=2*i+1 # zjisti index leveho potomka 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): """ odebere nejmensi prvek a uprav haldu """ element=self.heap[0] self.heap[0]=self.heap[-1] self.heap.pop() # smaz posledni 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}
VOL = [5,3,2] #max volume of each bucket class State: def __init__(self, water): self.water = water[:] #array of three ints self.action = "" def expand(self): result = [] #Nx for x in range(3): if self.water[x] != VOL[x]: s = State(self.water) s.water[x] = VOL[x] s.action = "N" + str(x) result.append( s ) #Vx for x in range(3): if self.water[x] > 0: s = State(self.water) s.water[x] = 0 s.action = "V" + str(x) result.append( s ) for y in range(3): for x in range(3): if x != y: s = State(self.water) if VOL[y] > s.water[y] and s.water[x] != 0: deficit = VOL[y] - s.water[y] if s.water[x] >= deficit: s.water[y] = VOL[y] s.water[x] = s.water[x] - deficit if s.water[x] < deficit: s.water[y] = s.water[y] + s.water[x] s.water[x] = 0 s.action = str(x) + "P" + str(y) result.append(s) return result s = State([3,0,2]) newStates = s.expand() for i in newStates: print("State: ", i.water) def bfs(start, end): queue = [ start ] isKnown = {} isKnown[ str(start.water) ] = None while len(queue) > 0: actual = queue.pop(0) if actual.water == end.water: print("GOAL") path = [] while actual != None: path.append(actual.action) actual = isKnown[ str(actual.water) ] return path newStates = actual.expand() #list of states for state in newStates: if not str(state.water) in isKnown: isKnown[ str(state.water) ] = actual queue.append( state ) start = State([5,1,0]) end = State([0,0,1]) print(bfs(start, end))
Lehká úloha Testovací data lehká úloha
Těžká úloha Testovací data těžká úloha