1. NZH, NHF

Jelentkeztél NZH-ra? Biztos? Ellenőrizted?! Ez az utolsó lehetőség.

Nézted a nagy házik listáját? Választottál feladatot?

Ne feledd, ezek határidős feladatok!

2. Ikerprím

Ikerprímeknek nevezzük azokat a prímszám együtteseket, amelyeknél n és n+2 is prím. Az első 3 ilyen pár (3, 5), (5, 7) és (11, 13). Melyik a 60-adik? Határozd meg Python programban! Használj top-down tervezést, ne duplikáld a prímkereső algoritmust!

Megoldás
def prim(szam):
    for i in range(2, szam):
        if szam % i == 0:
            return False
    return True


def main():
    szam = 1
    i = 0
    while i < 60:
        szam += 2
        while not (prim(szam) and prim(szam+2)):
            szam += 2
        i += 1
    print("{}. ikerprim: {} {}".format(i, szam, szam+2))

 
main()

Az ikerprímek vizsgálatát lehetne még gyorsítani. A vizsgált számpárok: (5;7), (7;9), (9;11) stb., azaz minden számpár második tagja a következő számpár első tagja. A vizsgálat eredményét el lehetne tárolni egy változóban, és a következő iterációban felhasználni.

Maga a prim() függvény is gyorsítható: elég csak a szám gyökéig menni.

3. Prímtényezős felbontás

Írj egy programot, amelyik kér egy számot a felhasználótól, és kiírja a prímtényezős felbontását!

Melyik számot? 75

 75│3
 25│5
  5│5
  1│
Tipp

Tippek

  • Addig kell végezni a kísérletezést – osztogatást, amíg 1-hez nem jutunk. Egy while szam != 1-ünk máris van!
  • Növekvő sorban kell haladni az osztók vizsgálatával.
  • Baj, ha megpróbálunk összetett számmal osztani (pl. 4-gyel, 6-tal)? Miért?
  • Ha osztható a szám, elosztjuk, kiírjuk. Ha nem osztható, másik osztót kell keresni.
  • Alkalmazd a sztringek formázási lehetőségeit, az előadáson tanult módon!
Megoldás

A lenti megoldás mindig egy egész sort ír ki, pl. 150|2. Egy kiírás akkor történik meg, amikor az oszthatóságot már megvizsgáltuk, és a maradék nullának adódott. A 150|2 azt jelenti, hogy a 150-et osztjuk el 2-vel; ezért a konkrét osztás előtt írjuk ki a sort, hogy még az osztás előtti szám látszódjon. Így aztán az utolsó sort, amelyben az 1-es van, külön utasítással kell kiírni.

szam = int(input("Melyik számot? "))
oszto = 2
while szam > 1:
    if szam % oszto == 0:
        print('{:5}|{}'.format(szam, oszto))
        szam = szam // oszto
    else:
        oszto = oszto + 1
print('{:5}|'.format(1))

Esetleg van, akinek jobban tetszik a következő megoldás: mindig kiírjuk előre a számot, amit osztani fogunk, és az oszthatóság vizsgálata után már csak az osztót. Ez is helyes megoldás. Ilyenkor az eredeti számot ki kell írni a ciklus előtt külön. A végén viszont az 1-et nem, mert az a legutolsó osztásnál megjelenik:

szam = int(input("Melyik számot? "))
oszto = 2
print('{:5}|'.format(szam), end="") # nincs sortörés
while szam > 1:
    if szam % oszto == 0:
        print('{:}'.format(oszto))
        # print(oszto) # elég lenne ez is
        szam = int(szam / oszto)
        print('{:5}|'.format(szam), end="")
    else:
        oszto = oszto + 1

Érdemes elgondolkozni azon, hogy jobb lenne-e előbb meghatározni a prímszámokat, hogy csak azokkal kelljen osztani. Mennyivel lenne hatékonyabb az a program?

4. A Fisher-Yates keverés

Előadáson szerepelt Fisher és Yates algoritmusa, amellyel egy listát lehet megkeverni. Az ott bemutatott verzió helyben keveri meg a listát (egyetlen listát módosít az elemek cseréjével), és az elejétől a végéig halad. A működése:

CIKLUS i = 0-tól n-2-ig:
    j = véletlenszám i ≤ j < n között
    csere: lista[i] ↔ lista[j]

Implementáld újra az algoritmust a pszeudokód alapján! (Csak akkor nézd meg az előadásanyagot, ha elakadtál.) Utána írd meg két további változatban:

  • Az első verzióban dolgozz egy listával, de keverd azt a végétől haladva az eleje felé! Vagyis cseréld meg az utolsó elemet egy véletlenszerűen választottal, az utolsó előttit egy véletlenszerűen választottal és így tovább.
  • A második verzióban dolgozz két listával! Az eredeti lista véltelenszerűen választott elemeit tedd át egy másik listába, törölve azt folyamatosan az előbbiből!

Mindkét változatban írd ki a listát (listákat) folyamatosan, iterációnként, hogy látszódjon, mi történik!

Megoldás

Helyben:

import random

szamok = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(szamok)

for i in range(len(szamok)-1, 0, -1):
    j = random.randrange(0, i + 1)
    temp = szamok[i]
    szamok[i] = szamok[j]
    szamok[j] = temp
    print(szamok)

Itt figyelni kell arra, hogy visszafelé menő ciklus esetén a range() függvény meg kell kapja harmadik paraméterként a lépésközt; ez itt –1. Továbbá arra, hogy a keverés közben elő kell tudnia fordulni annak, hogy egy elemet nem mozdítunk el a helyéről. Az i == j eset lehetséges kell legyen. Ezért a j véletlenszerűen választott értékét a range(0, i+1) tartományból vesszük, i-t beleértve.

Másik listába áthelyezve:

import random

eredeti = [1, 2, 3, 4, 5, 6, 7, 8, 9]
uj = []
print(eredeti, "->", uj)

while len(eredeti) > 0:
    i = random.randrange(0, len(eredeti))
    uj.append(eredeti[i])
    del eredeti[i]
    print(eredeti, "->", uj)

5. Labirintus játék

A labirintus egy fallal körülvett 10×10-es tábla. A labirintust körülvevő falon egy kijárat található. A labirintusban több kincset rejtettek el. A játékos feladata, hogy összeszedje a kincseket és eljusson a kijáratig.

XXXXXX XXX
X*   X   X
XXXX XXX X
X        X
X XXXX XXX
X X    X*X
X XX*X X X
X@ XXX X X
X   *X   X
XXXXXXXXXX

A labirintust a fenti formában kell megjeleníteni. A falakat X jelzi, a járható részeket szóköz, az elrejtett kincseket a * karakter, a játékost pedig a @. Ha a játékos felvette, a kincs helyére is szóköz kerül.

Ebben a feladatban az alább látható részfeladatok mind egymásra épülnek, vagyis sorban kell megcsinálnod őket. Minden függvény megírásakor írj egy rövid programrészt a főprogramba, amely meghívja a függvényt – így lépésenként ellenőrizni tudod azt, hogy helyesen működik-e.

A pálya

Hozz létre egy két dimenziós listát a labirintus tárolására! Tárolja ez a pálya egyes celláit, először sorral, aztán pedig oszloppal indexelve. Alább megadjuk a pályát sztringek listájaként; ezt kell átmásolnod a saját, 10×10-es kétdimenziós listádba úgy, hogy minden listaelem egy karakter legyen:

kiindulas = [
    "XXXXXX XXX",
    "X*   X   X",
    "XXXX XXX X",
    "X        X",
    "X XXXX XXX",
    "X X    X*X",
    "X XX*X X X",
    "X@ XXX X X",
    "X   *X   X",
    "XXXXXXXXXX",
]

Kirajzolás

Írj függvényt, amely paraméterként veszi a labirintust tároló adatszerkezetet és kirajzolja azt a képernyőre!

Kincsek száma

Írj függvényt, amelyik megadja, hogy a pályán hány kincs van!

A játékos mozgása

Írj függvényt, amelyik a játékot vezérli! Ez a következő feladatokat kell végrehajtsa egy ciklusban:

  • Kérje be a felhasználótól a mozgási irányt. A felhasználó az A,S,D,W betűk valamelyikét nyomja majd (rendre balra, le, jobbra, fel irányokhoz), utána pedig entert.
  • Ellenőrizze ezután, hogy lehet-e arra menni, nem ütközik-e falba a játékos.
  • Ha nem, mozgassa, és vegye figyelembe azt is, hogy kincset talált-e, vagy a kijárathoz ért-e.
  • Ha üres sort kapott, vagy elérte a kijáratot, akkor vége a játéknak, amúgy rajzolja ki újra a pályát.

Kincsek száma

Miután vége lett a játéknak, ellenőrizze a program a pályát, és számolja meg, hány kincs maradt!

Megoldás
def palyat_letrehoz(kiindulas):
    # sztringek listájából pálya. a feladat szerint elég
    # 10×10-esre működnie, de ez működik bármekkorára
    palya = []
    for sztringkent in kiindulas:
        sor = []
        for cella in sztringkent: 
            sor.append(cella)
        palya.append(sor)
    return palya

def kirajzol(palya):
    for sor in palya:
        for cella in sor:
            print(cella, end="")
        print()

def kincsek(palya):
    db = 0
    for sor in palya:
        for cella in sor:
            if cella == '*':
                db += 1
    return db

def jatek(palya):
    # játékos megkeresése. a feladat nem kérte, lehet
    # fix pozícióval is indulni (1 7)
    jx = None
    jy = None
    for y in range(len(palya)):
        for x in range(len(palya[0])):
            if palya[y][x] == '@':
                jx = x
                jy = y
    
    while True:
        be = input("Lépés: ")
        if be == "":
            break
        # új kordináták ezek lesznek
        ux = jx
        uy = jy
        irany = be[0].upper()
        if irany == 'A':
            ux = jx-1
        elif irany == 'S':
            uy = jy+1
        elif irany == 'D':
            ux = jx+1
        elif irany == 'W':
            uy = jy-1
        if palya[uy][ux] != 'X':
            palya[jy][jx] = ' '
            jx = ux
            jy = uy
            palya[jy][jx] = '@'
            kirajzol(palya)
        else:
            print("Nem lehet arra menni")
        # kijárat?
        if uy == 0:
            break

def main():
    kiindulas = [
        "XXXXXX XXX",
        "X*   X   X",
        "XXXX XXX X",
        "X        X",
        "X XXXX XXX",
        "X X    X*X",
        "X XX*X X X",
        "X@ XXX X X",
        "X   *X   X",
        "XXXXXXXXXX",
    ]
    
    palya = palyat_letrehoz(kiindulas)
    kirajzol(palya)
    jatek(palya)
    db = kincsek(palya)
    if db == 0:
        print("Megvan az összes kincs!")
    else:
        print("A labirintusban hagytál {} kincset.".format(db))

main()

A sztringek listává alakítására sok más lehetőség is van. Pl. mivel a sztring iterálható (működik rajta a for ciklus is), ezért közvetlenül listává konvertálható:

def palyat_letrehoz(kiindulas):
    palya = []
    for sor in kiindulas:
        palya.append(list(sor))
    return palya

Szorgalmi feladat: a kijárat helye

A fenti példában és mintamegoldásban a kijáratot nem jelöli semmilyen karakter; csak a pálya északi részén lehet. Egészítsd ki úgy a programod, hogy a kijáratnak is adsz egy jelet, pl. a # karaktert, és oda kell eljutnia a játékosnak!

6. További feladatok

  • Szorgalmi feladat: a labirintusos játékba építsd be a PyConio modult! Ezzel megoldhatod azt is, hogy színes legyen a kimenet, továbbá hogy ne kelljen minden lépés után entert nyomni.
  • Írhatsz további játékokat is.
  • Dolgozhatsz a nagy házi feladatodon is.