Tip:
Highlight text to annotate it
X
Mi az az algoritmus?
A számítástechnikában
olyan utasítások sora, mely
lépésekben haladva problémákat old meg.
Ezeket rendszerint számítógépek hajtják végre,
de mi emberek is rendelkezünk algoritmusokkal.
Például hogy számolnád meg
az embereket egy szobában?
Nos, hozzám hasonlóan,
valószínűleg rámutatnál mindenkire
szépen egyesével,
és összeadnád őket nullától:
1, 2, 3, 4 és így tovább.
Ez már egy algoritmus!
Fejezzük ki ezt
kissé formálisabban, pszeudokódban,
mely emberi nyelv,
de hasonlít a programozási nyelvekhez.
Legyen n = 0.
Minden egyes ember esetén legyen n = n + 1.
Hogyan értelmezzük ezt?
Az 1. sor, hogy úgy mondjam deklarálja
az n nevű változót
és beállítja az értékét nullára.
Ez annyit tesz, hogy az algoritmus elején
a számítandó dolog értéke
nullával kezdődik.
Végül is a számítás előtt
nem is számoltunk meg semmit.
Csak megszokásból hívom n-nek ezt a változót.
Gyakorlatilag bárhogy nevezhetném.
Namost, a 2. sor egy ciklus elejét jelzi,
lépések sorozatát, melyek bizonyos számmal ismétlődnek.
Példánkban ez a lépés
az emberek számlálása a szobában.
A 2. sor alatt van a 3.,
mely pontosan megmondja, hogy haladjunk tovább.
A behúzás itt azt jelenti, hogy a harmadik sor
fog ismétlődni.
Tehát a pszeudókód azt fejezi ki,
hogy miután nullával kezdtünk,
minden egyes személlyel
növeljük n-t egyel.
Helyes ez az algoritmus?
Fussunk át rajta gyorsan!
Helyesen működik, ha 2 ember van a szobában?
Lássuk!
Az 1. sorban n-t beállítjuk nullára.
Mindkét emberünk esetén
aztán növeljük n-t egyel.
Tehát a ciklusunk első körében
felülírjuk n-t nulláról egyre,
majd ezen ciklus második körében
felülírjuk n értékét 1-ről 2-re.
Az algoritmusnak vége, n értéke pedig 2,
ami megegyezik a szobában lévők számával.
Eddig jók vagyunk.
Mi a helyzet a különleges esetekkel?
Tegyük fel, hogy 0 ember van a szobában,
leszámítva engem, aki a számolást végzi.
Az 1. sorban ismét nullára állítjuk n-t.
Ebben az esetben azonban a 3. sor le sem fut,
mivel nincs senki az egész szobában,
így hát n értéke 0 marad,
ami ismét egyezik a szobában lévők számával.
Egyszerű, igaz?
Ám egyesével számolni az embereket nem túl hatékony, igaz?
Biztosan megy ez jobban is!
Miért nem számoljuk őket kettesével?
Miért számolunk így: 1, 2, 3, 4, 5, 6, 7, 8, és így tovább
ahelyett, hogy
2, 4, 6, 8, és így tovább?
Már eleve rövidebben hangzik, és tényleg az.
Fejezzük ki ezt az optimalizálást pszeudokódban!
Legyen n értéke nulla.
Minden szobában lévő pár esetén
legyen n = n + 2.
Nem túl nagy változtatás, igaz?
Ahelyett, hogy egyesével számolnánk őket,
két embert számolunk meg egy időben.
Ez az algoritmus kétszer olyan gyors, mint az előző.
De vajon helyes-e?
Lássuk!
Helyesen működik, ha 2 ember van a szobában?
Az 1. sorban n értékét nullára állítjuk.
Van egyetlen párunk, így növeljük n értékét kettővel.
Ezzel az algoritmus a végéhez is ért, és n értéke 2,
amely megegyezik a szobában lévő emberek számával.
Most legyen 0 ember a szobában.
Az első sorban beállítjuk n értékét nullára.
S mint korábban, a 3. sor most sem fut le,
mivel hogy nincs egyeltenegy pár sem a szobában,
ezért n értéke nulla marad,
mely ismét megegyezik a szobában lévő emberek számával.
Ám mi történik, ha három ember van a szobában?
Hogy muzsikál az algoritmusunk?
Lássuk!
Az első sorban beállítjuk n-t nullára.
Az egy pár ember kapcsán
növeljük n értékét 2-vel,
ám ezután?
Nincs annyi ember, hogy kitegyen egy párt,
ezért a 2. sor már nem fut le.
Ezzel az algoritmus a végéhez ért,
n még mindig 2, ami helytelen.
Ezt az algoritmust hibásnak tekintjük,
mert tartalmaz egy tévedést.
Szabjuk át kicsit újabb pszeudokóddal!
Legyen n értéke nulla.
Minden pár esetén a szobában,
legyen n = n + 2.
Ha egy ember pár nélkül marad,
legyen n = n + 1.
Hogy megoldjuk ezt a problémát,
a 4. sorban bevezettünk egy feltételt,
másnéven elágazást,
mely akkor fut csak le, ha marad egy ember,
aki nem talál párt magának.
Tehát akár 1, vagy 3,
vagy más páratlan számú ember van a szobában,
ez az algoritmus meg tudja számolni őket.
Ezt is felülmúlhatjuk?
Ami azt illeti, számolhatunk egyszerre 3, 4, 5, vagy 10 embert,
ám ezen túl már kicsit macerás
lenne rájuk mutogatni.
Végezetül pedig,
akár számítógép, vagy ember hajtja végre,
az algoritmus csupán utasítások sora,
mellyel problémákat oldunk meg.
Ez csupán három volt.
Te milyen problémát oldanál meg egy algoritmussal?