Informatika2-2015/Gyakorlat03
A MathWikiből
(Változatok közti eltérés)
(egy szerkesztő 2 közbeeső változata nincs mutatva) | |||
10. sor: | 10. sor: | ||
# osztosor2 | # osztosor2 | ||
# tornyok | # tornyok | ||
+ | |||
+ | == Feladatok megoldása == | ||
+ | |||
+ | === zarojel === | ||
+ | |||
+ | <python>def zarojel(l): | ||
+ | szamlalo = 1 | ||
+ | for elem in l: | ||
+ | szamlalo += zarojel(elem) | ||
+ | return szamlalo</python> | ||
+ | |||
+ | === cserebere === | ||
+ | |||
+ | <python>def cserebere(szo, cserek): | ||
+ | for hely, betu in cserek: | ||
+ | szo_eleje = szo[:hely] | ||
+ | szo_vege = szo[hely+1:] | ||
+ | szo = szo_eleje + betu + szo_vege | ||
+ | return szo</python> | ||
+ | |||
+ | === osztosor2 === | ||
+ | |||
+ | <python>megoldott = {} | ||
+ | |||
+ | def osztosor2(szam, osztok): | ||
+ | if (szam, osztok) in megoldott: | ||
+ | return megoldott[(szam, osztok)] | ||
+ | else: | ||
+ | megoldas = 1 | ||
+ | for oszto in osztok: | ||
+ | if szam % oszto == 0: | ||
+ | megoldas += osztosor2(szam / oszto, osztok) | ||
+ | megoldott[(szam, osztok)] = megoldas | ||
+ | return megoldas</python> | ||
+ | |||
+ | === tornyok === | ||
+ | |||
+ | <python>def tornyok(magassagok, k): | ||
+ | n = len(magassagok) | ||
+ | # Létrehozzuk az k*n-es táblázatot csupa 0 elemmel. | ||
+ | tablazat = [[0 for j in range(n)] for i in range(k)] | ||
+ | |||
+ | # tablazat[i][j] értékének reszfeladat(i+1, j+1) értékét | ||
+ | # szeretnénk kiszámolni (a 0-tól indexelés miatt). | ||
+ | |||
+ | tablazat[0][0] = magassagok[0] | ||
+ | for j in range(1, n): | ||
+ | tablazat[0][j] = max(magassagok[j], tablazat[0][j-1]) | ||
+ | |||
+ | for i in range(1, k): | ||
+ | for j in range(n): | ||
+ | if magassagok[j] >= j: | ||
+ | epit_osszeg = magassagok[j] | ||
+ | else: | ||
+ | epit_osszeg = magassagok[j] + tablazat[i-1][j - magassagok[j] - 1] | ||
+ | nem_epit_osszeg = tablazat[i][j-1] | ||
+ | tablazat[i][j] = max(epit_osszeg, nem_epit_osszeg) | ||
+ | return tablazat[k-1][n-1]</python> | ||
+ | |||
+ | == Házi feladatok megoldása == | ||
+ | |||
+ | === pascal === | ||
+ | |||
+ | <python>def pascal(n): | ||
+ | haromszog = [[0 for j in range(i+1)] for i in range(n)] | ||
+ | haromszog[0][0] = 1 | ||
+ | for i in range(1, n): | ||
+ | for j in range(i+1): | ||
+ | if j == 0 or j == i: | ||
+ | haromszog[i][j] = 1 | ||
+ | else: | ||
+ | haromszog[i][j] = ( | ||
+ | haromszog[i-1][j] + | ||
+ | haromszog[i-1][j-1]) | ||
+ | return haromszog</python> | ||
+ | |||
+ | === nalattak === | ||
+ | |||
+ | Ezt a feladatot többféleképpen meg lehetett oldani, pl. a faktoriálisok kiszámításával. Számomra a legegyszerűbb megoldás a ''pascal'' megoldásának felhasználása volt: | ||
+ | |||
+ | <python>def nalattak(n, k): | ||
+ | haromszog = [[0 for j in range(i+1)] for i in range(n+1)] | ||
+ | haromszog[0][0] = 1 | ||
+ | for i in range(1, n+1): | ||
+ | for j in range(i+1): | ||
+ | if j == 0 or j == i: | ||
+ | haromszog[i][j] = 1 | ||
+ | else: | ||
+ | haromszog[i][j] = haromszog[i-1][j] + haromszog[i-1][j-1] | ||
+ | return haromszog[n][k]</python> |
A lap jelenlegi, 2015. március 19., 12:58-kori változata
Tartalomjegyzék |
3. gyakorlat - rekurzió és ciklus
Ezen a gyakorlaton az előző heti előadás anyagát dolgozzuk fel.
Feladatok
Feladatok a CloudCoder-en megtalálhatóak. Ajánlott sorrend:
- zarojel
- cserebere
- osztosor2
- tornyok
Feladatok megoldása
zarojel
def zarojel(l): szamlalo = 1 for elem in l: szamlalo += zarojel(elem) return szamlalo
cserebere
def cserebere(szo, cserek): for hely, betu in cserek: szo_eleje = szo[:hely] szo_vege = szo[hely+1:] szo = szo_eleje + betu + szo_vege return szo
osztosor2
megoldott = {} def osztosor2(szam, osztok): if (szam, osztok) in megoldott: return megoldott[(szam, osztok)] else: megoldas = 1 for oszto in osztok: if szam % oszto == 0: megoldas += osztosor2(szam / oszto, osztok) megoldott[(szam, osztok)] = megoldas return megoldas
tornyok
def tornyok(magassagok, k): n = len(magassagok) # Létrehozzuk az k*n-es táblázatot csupa 0 elemmel. tablazat = [[0 for j in range(n)] for i in range(k)] # tablazat[i][j] értékének reszfeladat(i+1, j+1) értékét # szeretnénk kiszámolni (a 0-tól indexelés miatt). tablazat[0][0] = magassagok[0] for j in range(1, n): tablazat[0][j] = max(magassagok[j], tablazat[0][j-1]) for i in range(1, k): for j in range(n): if magassagok[j] >= j: epit_osszeg = magassagok[j] else: epit_osszeg = magassagok[j] + tablazat[i-1][j - magassagok[j] - 1] nem_epit_osszeg = tablazat[i][j-1] tablazat[i][j] = max(epit_osszeg, nem_epit_osszeg) return tablazat[k-1][n-1]
Házi feladatok megoldása
pascal
def pascal(n): haromszog = [[0 for j in range(i+1)] for i in range(n)] haromszog[0][0] = 1 for i in range(1, n): for j in range(i+1): if j == 0 or j == i: haromszog[i][j] = 1 else: haromszog[i][j] = ( haromszog[i-1][j] + haromszog[i-1][j-1]) return haromszog
nalattak
Ezt a feladatot többféleképpen meg lehetett oldani, pl. a faktoriálisok kiszámításával. Számomra a legegyszerűbb megoldás a pascal megoldásának felhasználása volt:
def nalattak(n, k): haromszog = [[0 for j in range(i+1)] for i in range(n+1)] haromszog[0][0] = 1 for i in range(1, n+1): for j in range(i+1): if j == 0 or j == i: haromszog[i][j] = 1 else: haromszog[i][j] = haromszog[i-1][j] + haromszog[i-1][j-1] return haromszog[n][k]