5. hét: vegyes feladatok, gyakorlás

Czirkos Zoltán, Frey Balázs · 2023.10.01.

1. 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(f'{szan:5}|{oszto}')
        szam = szam // oszto
    else:
        oszto = oszto + 1
print(f'{1:5}|')

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(f'{szam:5}|', end="") # nincs sortörés
while szam > 1:
    if szam % oszto == 0:
        print(f'{oszto:}')
        # print(oszto) # elég lenne ez is
        szam = szam // oszto
        print(f'{szam:5}|', 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?

2. 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)

3. Útiterv

Egy kamionsofőr autópályán vezet, 100 km/h-val haladva. A benzinkutak egymástól való távolságát előre ismeri a térképről. Minden másfél órányi vezetés után pihenőt kell tartania. Szeretne egy útitervet készíteni: előre eldönteni azt, hogy melyik benzinkúton kell majd pihennie. A szabály egyszerű: minden olyan benzinkútnál megáll, amelynél ha nem tartana pihenőt, a következő kúthoz már csak úgy érne el, ha túllépné a másfél órás egyfolytában vezetést.

Írj programot, amely soronként beolvassa az egyes benzinkutak közötti távolságot km-ben! Előbb megkapja a távolságok számát, majd magukat a távolságokat (soronként egy darabot). Végül pedig írja ki az útitervet. Például ha bemenetként a 45.3, 30.7, 64, 35, 72 számsort kapja (km-ek), akkor a kimenet az alábbi kell legyen:

45.3 km, 30.7 km, 64 km, szünet.
35 km, 72 km, vége.
Megoldás
sebesseg = 100  # km/h
szunet = 1.5    # h

n = int(input("n = "))
tavok = []
for _ in range(n):
    tavok.append(float(input("Táv (km): ")))

megtett = 0     # km
for tav in tavok:
    if (megtett + tav)/sebesseg > szunet:
        print('szünet.')
        megtett = 0
    print(f'{tav} km, ', end='')
    megtett += tav

print('vége.')

4. Kő, papír, olló

Kő (k), papír (p), olló (o) vagy vége (v)?

Szerinted: k
Szerintem: k.
Senki nem kap pontot.

Szerinted: p
Szerintem: k.
p>k, ezt te vitted!

Szerinted: v

Te nyertél, 1>0 ponttal.

Írj programot, amelyik „kő, papír, olló” játékot játszik! A program először kérje el a felhasználó tippjét (k, p, o betűk, mint kő, papír, olló). Ezután válasszon ő maga is egyet, és hasonlítsa a kettőt össze! A kő erősebb, mint az olló, mert kicsorbítja. A papír erősebb, mint a kő, mert becsomagolja. Az olló erősebb, mint a papír, mert elvágja. Ezek alapján a gép vagy a játékos kapjon egy pontot! Ha egyformát tippeltek, akkor semelyikük nem kap. A v beírása után írja ki a program, hogy ki nyert!

Tipp

A gépnek háromféle választása lehet. Érdemes ehhez a random.choice() függvényt használni egy listával, amiben a három választás van.

5. Memóriajáték

6×6 kártya van lefordítva a játékosok előtt, 18 pár, amelyek egyformák. A kártyákon betűk vannak, A, B, C, ... Írj egy programot, amelyik generál egy véletlenszerű leosztást! Természetesen egy betűnek pontosan kétszer kell szerepelnie (egy pár)!

Tipp

Ehhez érdemes előbb a listát úgy feltölteni, hogy sorrendben szerepelnek benne a kártyák, és utána összekeverni. Úgy nem kell mindig vizsgálni, hogy minden kártya pontosan kétszer szerepel-e benne. A lista megkeveréséhez minden elemet cserélj meg egy véletlenedikkel!

6. További feladatok

Érdemes gyakorolni a statisztikával, indirekt adateléréssel illetve az adatok kezelésével és beolvasással kapcsolatos feladatokat, mert a 2. kis zárthelyin ilyen feladat lesz.

A feladatgyűjteményben találsz még különféle játékokat. Írj programot ahhoz, amelyik tetszik, vagy fejleszd az eddigieket a saját ötleteid alapján!