Lineáris keresés

Nézzük meg, mit csinált az előző két programozási tétel:

  • Az eldöntés arra volt jó, hogy megnézzük, van-e adott tulajdonságú elem a sorozatban
  • A kiválasztás esetében biztosak voltunk benne, hogy van adott tulajdonságú elem, és a tétel megmondta, hogy melyik ez az elem.
Gyilkos méh

Nem csináltad meg a feladatokat?? Akkor neked zzzz!

A keresés ez a kettő együtt: megmondja, hogy melyik az adott tulajdonságú elem, ha van, ha meg nincs, akkor megmondja, hogy nincs.

Valójában már csináltunk is ilyet, méghozzá a 23h feladatban. Nézd csak meg a kiválasztásos posztot!

Mindenesetre itt van róla a videó:

A lineáris keresés programozási tétel pszeudokódja a következő:


sorozat = valamilyen lista, range, vagy más bejárható objektum

ciklus sorozat minden elem-ére
    ha az elem keresett tulajdonságú:
        egy változóba tesszük az indexét
        logikai változóban felírjuk magunknak, hogy találtunk ilyet
        break (azaz kilépünk a ciklusból)
    elágazás vége
ciklus vége

ha volt keresett tulajdonságú elem:
    kiírjuk az elemet, vagy az indexét
különben:
    kiírjuk, hogy nem volt ilyen elem
elágazás vége

Bár szó szerint lekódolható a fenti algoritmus Pythonban is, a tétel igazi Python-kódja kicsit másmilyen, mégpedig azért, mert a for utasítás else-záradéka annyira ritka csoda a proramozás nyelvek széles világában, hogy nem szokás gondolni rá. Te azért csak gondolj!

Átfogalmazzuk a pszeudokódot a for-else lehetőséget szem előtt tartva:


sorozat = valamilyen lista, range, vagy más bejárható objektum

ciklus sorozat minden elem-ére
    ha az elem keresett tulajdonságú:
        kiírjuk, vagy logikai változóban tároljuk az elemet vagy az indexét
        break (azaz kilépünk a ciklusból)
    elágazás vége
ciklus vége
ha rendesen végigfutott a ciklus (azaz nem volt break):
    kiiírjuk, hogy nem volt ilyen elem
elágazás vége

Na, akkor ez Pythonban, értékek szerint bejárva a listánkat:


for elem in bejárható_objektum:
    if elem olyan_amilyet_keresünk:
        print(elem)
        break
else:
    print('nem volt ilyen')

És indexek szerint bejárva a listánkat:


for index in range(len(bejárható_objektum)):
    if bejárható_objektum[index] olyan_amilyet_keresünk:
        print('Az elem helye:', index, 'maga az elem:', bejárható_objektum[index])
        break
else:
    print('nem volt ilyen')

A Python egyszerűsítése:

  • Lényegében az előző két tétel egyszerűsítését nézzük, együtt. Az in operátorral meg tudjuk mondani, hogy van‑e keresett érték, a lista objektumtípus index() tagfüggvényével meg azt, hogy ez az érték hányadik.
  • Megjegyezzük, hogy az index() csak az első előfordulás indexét adja meg, azaz csak egy előfordulást talál meg. Ha több is van – akkor így jártunk. Persze a tétel teljes formája sem jobb.
  • És az egyszerűsítés szokás szerint csak olyan esetben használható, amikor konkrét értéket keresünk. Azaz megtaláljuk vele az első 1241-et a megtanulandó évszámok listájában, de nem találjuk meg az első olyan számot, ami nagyobb 1000-nél. (Illetve deeee, de majd csak ha már lényegesen okosabbak vagyunk:))
  • És akkor, ennyi pofázás után:
    if elem in bejárható_objektum:
        print('Van', elem, 'itt:', bejárható_objektum.index(elem))
    else:
        print('Nincs', elem)
    

De miért “lineáris” keresés?

Részint “csak”, de valójában azért, mert a végrehajtásához szükséges idő lineárisan (egyenesen) arányos a bejárható objektum elemszámával. Hogy akkor van másmilyen keresés is? Fogadhatsz rá. Nagyon ráérünk megtanulni.

Feladatok

F0024a: Vágd be a lineáris keresés tételét! (Megoldás itt :P)

F0024b: Kódold le a pszeudokód első változatát!

F0024c: Adott az 5, 4, 3, 4, 5, 4, 4, 5, 3, 1 sorozat. Van-e benne egymás mellett két azonos szám? Ha igen, hol? (Megoldás itt.)

F0024d: Adott a ['Sanyi', 'Manyi', 'Jani', 'Pali', 'Olga', 'Pali', 'Pista'] lista. Van-e benne két egyforma név (nem csak egymás mellett, hanem bárhol)? (Megoldás itt.)
(Ha már végeztél, akkor elolvashatod – igen, fehérrel van írva, kijelölöd, és látszik – : Megtanultad a videóból, hogy mennyire jó, ha átgondolod, hogy pontosan mi a francot kérdeznek? Hogy megfogalmazható-e egyszerűbben a kérdés?)

F0024e: Adott a 3, 6, 4, 9, 8, 11, 12, 20 sorozat. Van-e benne két olyan szomszédos szám, amelyek csak 1-gyel térnek el egymástól? (Barátod az abs.) (Megoldás itt.)

Az előző alkalommal kiválasztottunk. Legközelebb megszámolunk.

(A méh: http://www.azkillerbeessoftball.com/uploads/8/5/0/6/8506277/4778556.jpg)

Reklámok

Lineáris keresés” bejegyzéshez ozzászólás

  1. Szia!

    A d feladathoz próbáltam olyan megoldást találni, ami a megegyező nevek helyét is kiírja. Sikerült is összetákolni egyet, de gondolom ez nem túl szép (viszont legalább úgy ahogy működik)..:D

    nevek = [‘Sanyi’, ‘Manyi’, ‘Jani’, ‘Pali’, ‘Olga’, ‘Pali’, ‘Pista’]
    torolt = 0
    helyek = []

    for nev in nevek:
    if nevek.count(nev) > 1:
    helyek.append(nev)
    while nevek.count(nev) != 0:
    hely = nevek.index(nev)+torolt
    helyek.append(hely)
    nevek.remove(nev)
    torolt += 1
    print(helyek)

    Hogyan lehetne ezt megoldani szebben?

    Kedvelés

    • Nyami, érdekes probléma:) Szóval, ha a Pythonidomár elejétől tanulsz és idáig jutottál, akkor a jelenlegi eszközkészleteddel ez egy szép megoldás.

      Kicsit javul a helyzet, ha az index tagfüggvénynek megnézed a második paraméterét. A generátorkifejezés csak a join miatt érdekes, ott alakítom át az int listaelemeket str-r, de az mát nem szigorúan a feladat része.
      A set azért kell, hogy minden év csak egyszer legyen kiírva, a sorted tisztán kozmetika.

      nevek = [‘Sanyi’, ‘Manyi’, ‘Jani’, ‘Pali’, ‘Olga’, ‘Pali’, ‘Pista’, ‘Pali’]

      for név in sorted(set(nevek)):
      indexek = []
      utolsó = -1
      for _ in range(nevek.count(név)):
      indexek.append(nevek.index(név,utolsó+1))
      utolsó = indexek[-1]
      print(név, ‘, ‘.join(str(index) for index in indexek))

      Az igazán klassz megoldáshoz szükséged van az enumerate függvényre, ami nem nehéz, meg a listaértelmezésre, ami nem könnyű:)

      nevek = [‘Sanyi’, ‘Manyi’, ‘Jani’, ‘Pali’, ‘Olga’, ‘Pali’, ‘Pista’, ‘Pali’]

      for név in sorted(set(nevek)):
      indexek = [index for (index, elem) in enumerate(nevek) if elem == név]
      print(név, ‘, ‘.join(str(index) for index in indexek))

      Kedvelés

Vélemény, hozzászólás?

Adatok megadása vagy bejelentkezés valamelyik ikonnal:

WordPress.com Logo

Hozzászólhat a WordPress.com felhasználói fiók használatával. Kilépés /  Módosítás )

Google+ kép

Hozzászólhat a Google+ felhasználói fiók használatával. Kilépés /  Módosítás )

Twitter kép

Hozzászólhat a Twitter felhasználói fiók használatával. Kilépés /  Módosítás )

Facebook kép

Hozzászólhat a Facebook felhasználói fiók használatával. Kilépés /  Módosítás )

w

Kapcsolódás: %s