Programkészítés menete¶
- Feladat értelmezése
- Tervezés
- Implementálás
- Tesztelés
- Valamit elcsesztünk, vissza egy korábbi ponthoz!
Tervezés¶
- Adatszerkezet kitalálása. Milyen adatokat fogok tárolni? Hogyan érdemes őket tárolni?
- Milyen műveletekre lesz szükségem? Azokat hogyan lehet algoritmussal megvalósítani?
- Mennyire számít a sebesség? Ha számít, akkor hogyan érhetem el, hogy gyors legyen?
- Mennyire pontos eredményt szeretnék? Numerikus vs szimbolikus számítás.
- Objektum orientáltan csináljam vagy procedurálisan, esetleg funkcionálisan?
- Hogyan lehet ezeket objektum orientáltan megoldani? Milyen osztályokat érdemes elkészíteni?
Implementálás és tesztelés¶
- Apró lépésekben érdemes dolgozni. Kb mindig legyen működő a program.
- Ne feledjük el, hogy rengeteg mindent már megírtak, érdemes ezt kihasználni.
- Érdemes kommentekkel ellátni a kódot, és beszédes változóneveket használni, hogy pár nap múlva is érthető legyen.
- Minden lényegesebb lépés után teszteljünk.
- Általában az implementálás, a tesztelés és a hibajavítás gyorsan váltogatja egymást.
"For some people, programming and debugging are the same thing. That is, programming is the process of gradually debugging a program until it does what you want. The idea is that you should start with a program that does something and make small modifications, debugging them as you go, so that you always have a working program." (https://runestone.academy/)
Példa 1. Sodoku megoldó¶
In [1]:
import numpy as np
In [12]:
board=np.array( [
[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,0,4,0,0],
[0,4,9,2,0,6,0,0,0]
])
In [13]:
def print_board(bo):
for i in range(len(bo)):
if i % 3 == 0 and i != 0:
print("- - - - - - - - - - - - - ")
for j in range(len(bo[0])):
if j % 3 == 0 and j != 0:
print(" | ", end="")
if j == 8:
print(bo[i][j])
else:
print(str(bo[i][j]) + " ", end="")
In [14]:
print_board(board)
In [7]:
def find_empty(bo):
for i in range(len(bo)):
for j in range(len(bo[0])):
if bo[i][j] == 0:
return (i, j)
return None
In [8]:
find_empty(board)
Out[8]:
In [9]:
def valid(bo, num, pos):
#1-től 9-ig
if num not in range(1,10):
return False
if bo[pos[0],pos[1]]!=0:
return False
# sor
for i in range(len(bo[0])):
if bo[pos[0]][i] == num and pos[1] != i:
return False
# oszlop
for i in range(len(bo)):
if bo[i][pos[1]] == num and pos[0] != i:
return False
# négyzet
box_x = pos[1] // 3
box_y = pos[0] // 3
for i in range(box_y*3, box_y*3 + 3):
for j in range(box_x * 3, box_x*3 + 3):
if bo[i][j] == num and (i,j) != pos:
return False
return True
In [10]:
for i in range(1,10):
print(i,valid(board,i,(1,3)))
Az ötlet, hogy próbáljunk végig mindent. A brute force megoldások sokszor lassúak, viszont néha nincs jobb lehetőség. Mire kell figyelni?
- Az összes eseten végig akarunk menni, de azokból túl sok van, hogy mind tároljuk.
- Ezért egy sorrendet állítunk föl, és a szerint próbáljuk végig.
- Tehát azt kell ügyesen megvalósítani, hogy ha egy adott próbálkozásnál tartunk, abból hogyan lehet a következő próbálkozásra áttérni.
In [16]:
# 1. megoldás
def solve(bo):
find = find_empty(bo)
if not find:
return bo
# lépések listája, éppen mit és hova próbálunk beírni.
listofsteps=[[bo.copy(),1,find]]
while True:
# éppen hol tartunk
lastboard=listofsteps[-1][0]
lastnum=listofsteps[-1][1]
lastpos=listofsteps[-1][2]
# ha helyes a próbálkozás, továbblépünk a következő üres mezőre
if valid(lastboard, lastnum,lastpos):
newboard=lastboard.copy()
newboard[ lastpos[0], lastpos[1]]= lastnum
newfind = find_empty(newboard)
if not newfind:
bo[:] =newboard
return True
else:
listofsteps.append([newboard,1,newfind])
elif lastnum<10:
listofsteps[-1][1]=listofsteps[-1][1]+1
else:
# ha beszoroltunk visszalépünk az egyel korábbi pozícióhoz és ott tekinjük a következő számot
del listofsteps[-1]
if len(listofsteps)==0:
return False
else:
listofsteps[-1][1]=listofsteps[-1][1]+1
In [17]:
print_board(board)
solve(board)
print("________________________")
print_board(board)
Második megoldás, rekurzió
In [24]:
board=np.array( [
[0,0,0,0,0,0,1,9,0],
[2,3,0,0,0,0,6,0,0],
[0,0,0,2,4,0,0,0,0],
[0,0,0,0,0,0,9,6,0],
[0,0,0,1,6,0,0,7,0],
[0,4,8,0,7,0,0,0,0],
[0,0,1,0,0,3,4,0,5],
[0,0,9,0,0,8,0,0,0],
[0,0,6,0,0,5,8,0,0]
])
In [22]:
# 2. megoldás, rekurzió
def solve2(bo):
find = find_empty(bo)
if not find:
return True
else:
row, col = find
for i in range(1,10):
if valid(bo, i, (row, col)):
bo[row][col] = i
if solve2(bo):
return True
bo[row][col] = 0
return False
In [25]:
print_board(board)
solve2(board)
print("________________________")
print_board(board)
Példa 2. Edmonds Karp¶
Adott egy folyamfeladat. Keressünk maximális folyamot benne.
Ford Fulkerson algoritmusnak az Edmonds Karp verzióját valósítjuk meg.
- mindig keresünk egy javító utat, ami mentén tudunk növelni a folyamon
- ehhez fenntartunk egy segédgráfot, amit mindig frissítünk
- ha van a segédgráfban javító út, akkor a mentén javítunk. Mindig a legrövidebb javító utat válasszuk.
In [26]:
import collections
In [30]:
class Iranyitott():
def __init__(self,graph):
self.graph=graph
self.num=len(graph)
def __str__(self):
return "\n".join([str(x) for x in self.graph])
def bfs(self, s, t, parent):
visited = [False] * (self.num)
queue = collections.deque()
# a kezdő csúcsot visitedre állítjuk és a sorba rakjuk
queue.append(s)
visited[s] = True
# szoksásos BFS bejárás
while queue:
u = queue.popleft()
# nézzük u szomszédait, ha valamelyiken még nem jártunk, mehet a sorba, és visited-re állítjuk
for ind, val in enumerate(self.graph[u]):
if (visited[ind] == False) and (val > 0):
queue.append(ind)
visited[ind] = True
parent[ind] = u
# hal elértünk t-ig akkor igazzal térünk vissza, különben hamis
return visited[t]
def edmonds_karp(self, source, sink):
# ebben fogjuk tárolni a bfs eredményét
parent = [-1] * (self.num)
max_flow = 0
# Amíg van javító út
while self.bfs (source, sink, parent):
# megnézzük mennyivel tudunk javítani
path_flow = float("Inf")
s = sink
while s != source:
path_flow = min(path_flow, self.graph[parent[s]][s])
s = parent[s]
# növeljük a folyam értékét
max_flow += path_flow
# a javító út mentén javítunk
v = sink
while v != source:
u = parent[v]
self.graph[u][v] -= path_flow
self.graph[v][u] += path_flow
v = parent[v]
return max_flow
In [33]:
I=Iranyitott( [[0, 16, 13, 0, 0, 0],
[0, 0, 10, 12, 0, 0],
[0, 4, 0, 0, 14, 0],
[0, 0, 9, 0, 0, 20],
[0, 0, 0, 7, 0, 4],
[0, 0, 0, 0, 0, 0]])
In [29]:
print(I)
In [ ]:
par=dict()
I.bfs(1,0, [-1] * (I.num))
In [34]:
I.edmonds_karp(4,5)}
Out[34]:
In [ ]: