Informatika2-2012/Kukaba12

A MathWikiből
(Változatok közti eltérés)
 
(egy szerkesztő 4 közbeeső változata nincs mutatva)
219. sor: 219. sor:
 
print szorzat    # 24
 
print szorzat    # 24
 
</python>
 
</python>
 +
Az enumerate() függvény egy bejárható objektumot kap, második opcionális argumentuma pedig egy kezdőérték, mely alapértelmezésben 0. Visszaadja a bejárható objektum sorszámmal ellátott elemeiből álló párokat.
 +
<python>
 +
e = enumerate([1,2,4])
 +
for i in e:
 +
    print i
 +
#(0, 1)
 +
#(1, 2)
 +
#(2, 4)
 +
</python>
 +
A következő kódban egy fájlból kiírjuk az üres sorok sorszámait:
 +
<python>
 +
f = open('data.txt', 'r')
 +
for i, sor in enumerate(f, 1):
 +
    if sor.strip() == '':
 +
        print 'A(z) %i. sor üres' % i
 +
</python>
 +
 +
=== Az függvényközpontú programozást segítő modulok ===
 +
 +
itertools, functools, operator
 +
 +
 +
==== GYAKORLAT ====
 +
 +
=== A Mathematica funkcionális függvényeihez hasonlók ===
 +
 +
0. Számítsuk ki az első 10 számát a két Beatty-sorozatnak. A <math>\phi=\frac{\sqrt5+1}{2}</math> jelöléssel <math>a_n=\lfloor n\phi\rfloor</math>, illetve <math>a_n=\lfloor n\phi^2\rfloor</math>.
 +
 +
1. Írjunk egy Nest nevű függvényt, mely a Nest(f, x, n) hívásra visszaadja az f(f(f(...f(x)...))) értéket, ahol f n-szer szerepel.
 +
 +
1a. Keressünk numerikus megoldást a cos(x)=x egyenletre!
 +
 +
2. Írjunk egy NestList nevű függvényt, mely a NestList(f, x, n) hívásra visszaadja az [x, f(x), f(f(x)), ..., f(f(f(...f(x)...)))] listát.
 +
 +
2a. Tudjuk, hogy az [1,1,1,....] végtelen lánctört értéke az aranymetszés arányát adó <math>\phi=\frac{\sqrt5+1}{2}</math>. Számítsuk ki a lánctört első néhány szeletének értékét!
 +
 +
3. Írjunk Fold nevű programot, mely a Fold(f, x, [a, b, c, d]) hívásra az f(f(f(f(x,a),b),c),d) értéket adja vissza.
 +
 +
3b. Számoljuk ki a Horner-elrendezéssel az x^3+2x^2+3x+4 polinom értékét a -2 helyen!
 +
 +
4 Írjunk programot a Collatz-problémára (3x+1), és írjuk meg annak generátorfüggvényes változatát (ami a next hívására a következő számot adja)!
 +
 +
5a. Programozzuk be azt az újraírási rendszert, mely a 0 -> 01, 1 -> 0 helyettesítéseket végzi a 0-ból indulva. Vegyük észre, hogy a 0-k és 1-ek sorszámai a Beatty-sorozat elemei.
 +
 +
5b. Olyan karakterláncot keresünk, amely egy n-elemű ábécéből készült, maximális hosszú, és nincs benne két egymást követő azonos részlánc. Be van bizonyítva, hogy 2-elemű ábécé esetén e maximum 3, 3-elemű ábécé esetén viszont van ilyen végtelen hosszú sorozat is, melyet a A -> ABC, B -> AC, C -> B helyettesítésekkel megkaphatunk az 'A' karakterláncból indulva. Írjunk e karakterláncot adó generátort!

A lap jelenlegi, 2012. május 9., 22:59-kori változata

Tartalomjegyzék

Függvényközpontú (funkcionális) programozás python-ban

Programozási paradigmák

Egy probléma megoldásához többféleképp közelíthetünk. Az, hogy a problémát hogyan bontjuk részekre, meghatározza a használható/andó programnyelvi elemeket. Ennek megfelelően a programnyelvi elemeknek négy fő típusát szokás megkülönböztetni:

  • Parancsközpontú (imperative), vagy vele majdnem azonos értelemben használt eljárásközpontú (procedurális, procedural)
    • algoritmikus gondolkodás, receptszerű programozás, ,,tedd ezt, majd ezt,..."
    • A Neumann-elvű számítógép ötletére épül
    • Számítási lépések időben egymás utáni elvégzése (parancsok végrehajtása)
    • Tipikus parancsok: értékadás, eljárás meghívása,
    • Az eljárások megváltoztatják a program kontrollstruktúráinak állapotát
  • Objektumközpontú (objektumorientált, object-oriented)
    • Az emberek közti interakciókat és a való világ jelenségeit modellezi
    • A fogalmakat osztályok, a jelenségeket objektumok valósítják meg
  • Függvényközpontú (funkcionális, functional)
    • A függvények matematikai elméletére épül,
    • A függvények értéket adnak vissza, de nincs mellékhatásuk, nincsenek változók
    • A program függvényhívásokból áll
    • A parancsközpontúnál egyszerűbb struktúra, könnyebben bizonyítható a program helyessége, könnyebben tesztelhető, debug-olható
  • Logikai, vagy a nála általánosabb értelemben használt deklaratív (logic, declarative)
    • A program végrehajtása az axiómáknak és a következtetési szabályoknak (deklarációknak) megfelelő lehetőség(ek) megkeresésből áll
    • Matematikai logikai alapú
    • Szűkebb alkalmazási lehetőségek

A függvényközpontú programozás klasszikus elemei a Pythonban

A lambda kifejezések névtelen függvények, alakjuk:

lambda paraméterek: kifejezés

ahol a paraméterek egy esetleg üres lista, a kifejezés pedig egy elágazást, ciklust, return vagy yield utasítást nem tartalmazó (de esetleg feltételes) kifejezés lehet. Előnyük, hogy csak kifejezések, ezért más kifejezésekben is szerepelhetnek, és ha nem szükséges, nem kell nevet adni nekik. Csak nagyon egyszerű (félsoros) függvényekre használjuk!

lambda x: x ** 2
lambda x: "pozitív" if x > 0 else "nem pozitív"
lambda x, y: x + y

A ciklusok elkerülésére három egyszerű ,,klasszikus függvény szolgál:

  • megfeleltetés -- egy függvény egy bejárható (iterable) objektum minden elemére hat: map()
map(lambda x: x ** 2, [1, 2, 3, 4])  # [1, 4, 9, 16]
map(lambda x, y: x + y, [1, 2, 3, 4], [0, 10, 100, 1000]) 
                                # [1, 12, 103, 1004]
map(lambda x, y: x ** y, itertools.repeat(2)[1, 2, 3, 4], [0, 10, 100, 1000]) 
                                # [1, 12, 103, 1004]
  • szűrés -- egy bejárható objektumnak csak azokat az elemeit tartjuk meg, amelyre egy függvény True értéket ad: filter()
filter(lambda x: x > 0, [-1, 2, -3, 4])  # [2, 4]
  • redukálás: reduce() (3.0-tól a standard könyvtárból törölve: functools.reduce())
reduce(lambda x, y: x + y, [1, 2, 3, 4])  # 10

Az üres listára hibaüzenetet kapunk. Ez ellen véd a harmadik argumentum, ahol a kezdőérték megadható:

reduce(lambda x, y: x + y, [1, 2, 3, 4], 0)  # 10
reduce(lambda x, y: x * y, [1, 2, 3, 4], 1)  # 24


Listaértelmezések (list comprehensions) és generátorkifejezések

Megfeleltetés és szűrés másként

A fenti három függvény helyettesítésére szolgál a lista elemeinek a matematikában szokásos halmazmegadási módjára emlékeztető leírása, amelyben ciklus-szerű és feltétel-szerű nyelvi elem is szerepelhet. Alakjuk azonnal érthető:

[kifejezés for elem in bejárható_objektum]
[kifejezés for elem in bejárható_objektum if feltétel]
[kifejezés for elem1 in bejárható_objektum1 if feltétel1
           for elem2 in bejárható_objektum2 if feltétel2
           for elemN in bejárható_objektumN if feltételN]

Az utóbbi listaértelmezés a következő kóddal ekvivalens:

for elem1 in bejárható_objektum1:
    if not (feltétel1):
        continue
    for elem2 in bejárható_objektum2:
        if not (feltétel2):
            continue
        for elemN in bejárható_objektumN:
            if not (feltételN):
                continue
            kifejezés

Megadjuk a megfeleltetés és szűrés fenti első két példája e szintaktika szerinti változatát:

[x ** 2 for x in [1, 2, 3, 4]]  # [1, 4, 9, 16]
[x for x in [-1, 2, -3, 4] if x > 0]

A harmadik esetre Guido van Rossum azt mondja, hogy tipikusan csak asszociatív függvényekre használjuk, mint + vagy *.

sum([1, 2, 3, 4])   # 10

A Google is azt javasolja, hogy map, filter, reduce helyett használjunk listaértelmezéseket vagy for ciklust, jobban olvasható.

Az egymásba ágyazott ciklusok is helyettesíthetőek listaértelmezéssel.

for x in (1,2,3):
    for y in [1,2,3,4]:
        if x < y:
            print (x, y, x*y),
# (1, 2, 2) (1, 3, 3) (1, 4, 4) (2, 3, 6) (2, 4, 8) (3, 4, 12)

E helyett írható a következő kód:

[(x, y, x * y) for x in (1,2,3) for y in [1,2,3,4] if x < y]
# [(1, 2, 2), (1, 3, 3), (1, 4, 4), (2, 3, 6), (2, 4, 8), (3, 4, 12)]


Egy példa: a nyolc királynő

Feladat: Hányféleképp lehet nyolc királynőt föltenni egy sakktáblára, hogy semelyik kettő ne üsse egymást?

Azt tudjuk, hogy az ilyen bástyaelhelyezések száma 8! = 40320. A királynők azonban átlósan is üthetik egymást.

Az i-edik és j-edik sorban lévő királynő pontosan akkor üti egymást, ha abs(i - j) != abs(x[i] - x[j]). Így a megoldás:

from itertools import permutations
for x in permutations(range(8)):
    if all([i == j or abs(i - j) != abs(x[i] - x[j]) 
        for i in range(8) for j in range(8)]):
        print x
Generátorkifejezések

A listaértelmezésekhez hasonló szintaktikával (szögletes helyett kerek zárójelekkel) generátorkifejezés is konstruálható. Ez tehát a next() függvény meghívásakor számítja ki a következő elemet. Szintaktikája:

(kifejezés for elem in bejárható_objektum)
(kifejezés for elem in bejárható_objektum if feltétel)
(kifejezés for elem in bejárható_objektum1 if feltétel1
           for elem in bejárható_objektum2 if feltétel2
           for elem in bejárható_objektumN if feltételN)

A alábbi generátorkifejezés mindig a következő négyzetszámot adja:

>>> y = (x**2 for x in range(10))
>>> print y
<generator object <genexpr> at 0xb740bb6c>
>>> y.next()
0
>>> y.next()
1
>>> y.next()
4
>>> y.next()
9
.......
>>> y.next()
64
>>> y.next()
81
>>> y.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

A következő két program ekvivalens, az egyikben generátorkifejezéssel, a másodikban yield segítségével adunk meg olyan függvényt, mely az első n négyzetszámot generáló függvényt ad vissza.

>>> def kovetkezo_negyzet(n):
...     for x in range(n):
...         yield x ** 2
... 
>>> y = kovetkezo_negyzet(3)
>>> print y
<generator object kovetkezo_negyzet at 0xb740ba7c>
>>> y.next()
0
>>> y.next()
1
>>> y.next()
4
>>> y.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

A második változat generátorkifejezéssel:

>>> def kovetkezo_negyzet(n):
...     return (x ** 2 for x in range(n)) 
... 
>>> y = kovetkezo_negyzet(3)
>>> print y
<generator object <genexpr> at 0xb740baa4>
>>> y.next()
0
>>> y.next()
1
>>> y.next()
4
>>> y.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Iterátorok (bejárók) és bejárható adattípusok

Bejárható (iterálható, iterable) az az adattípus, melynek elemei egyesével megkaphatók. Minden objektum bejárható, melynek van __iter__() nevű metódusa (tagfüggvénye), és bejárható minden sorozat (melynek van __getitem__() metódusa). A bejárható objektumból bejáró (iterátor) képezhető, ezek rendelkeznek __next__() metódussal, mely a következő elemet adja, és végül StopIteration kivételt dob. Egy példa for ciklussal:

szorzat = 1
for i in [1, 2, 3, 4]:
    szorzat *= i
print szorzat    # 24

Ekvivalens kód iterátorral:

szorzat = 1
i = iter([1, 2, 3, 4])
while True:
    try:
        szorzat *= next(i)
    except StopIteration:
        break
print szorzat    # 24

Az enumerate() függvény egy bejárható objektumot kap, második opcionális argumentuma pedig egy kezdőérték, mely alapértelmezésben 0. Visszaadja a bejárható objektum sorszámmal ellátott elemeiből álló párokat.

e = enumerate([1,2,4])
for i in e:
    print i
#(0, 1)
#(1, 2)
#(2, 4)

A következő kódban egy fájlból kiírjuk az üres sorok sorszámait:

f = open('data.txt', 'r')
for i, sor in enumerate(f, 1):
    if sor.strip() == '':
        print 'A(z) %i. sor üres' % i

Az függvényközpontú programozást segítő modulok

itertools, functools, operator


GYAKORLAT

A Mathematica funkcionális függvényeihez hasonlók

0. Számítsuk ki az első 10 számát a két Beatty-sorozatnak. A \phi=\frac{\sqrt5+1}{2} jelöléssel a_n=\lfloor n\phi\rfloor, illetve a_n=\lfloor n\phi^2\rfloor.

1. Írjunk egy Nest nevű függvényt, mely a Nest(f, x, n) hívásra visszaadja az f(f(f(...f(x)...))) értéket, ahol f n-szer szerepel.

1a. Keressünk numerikus megoldást a cos(x)=x egyenletre!

2. Írjunk egy NestList nevű függvényt, mely a NestList(f, x, n) hívásra visszaadja az [x, f(x), f(f(x)), ..., f(f(f(...f(x)...)))] listát.

2a. Tudjuk, hogy az [1,1,1,....] végtelen lánctört értéke az aranymetszés arányát adó \phi=\frac{\sqrt5+1}{2}. Számítsuk ki a lánctört első néhány szeletének értékét!

3. Írjunk Fold nevű programot, mely a Fold(f, x, [a, b, c, d]) hívásra az f(f(f(f(x,a),b),c),d) értéket adja vissza.

3b. Számoljuk ki a Horner-elrendezéssel az x^3+2x^2+3x+4 polinom értékét a -2 helyen!

4 Írjunk programot a Collatz-problémára (3x+1), és írjuk meg annak generátorfüggvényes változatát (ami a next hívására a következő számot adja)!

5a. Programozzuk be azt az újraírási rendszert, mely a 0 -> 01, 1 -> 0 helyettesítéseket végzi a 0-ból indulva. Vegyük észre, hogy a 0-k és 1-ek sorszámai a Beatty-sorozat elemei.

5b. Olyan karakterláncot keresünk, amely egy n-elemű ábécéből készült, maximális hosszú, és nincs benne két egymást követő azonos részlánc. Be van bizonyítva, hogy 2-elemű ábécé esetén e maximum 3, 3-elemű ábécé esetén viszont van ilyen végtelen hosszú sorozat is, melyet a A -> ABC, B -> AC, C -> B helyettesítésekkel megkaphatunk az 'A' karakterláncból indulva. Írjunk e karakterláncot adó generátort!

Személyes eszközök