Gyakorlat, 1. hét: tanult algoritmusok

Ehhez a recept a következő:

Leírom, hogy 1.
Leírom, hogy 2.
Leírom, hogy 3.
…
Leírom, hogy 10.

Megfigyelhető, hogy ez még nem túl pontos leírás. Van egy apró lépés, ami annyira magától értetődőnek tűnik, hogy nem szerepel. Pedig a feladat szövegében is benne volt: egymás alá kell írni a számokat. A kiegészített „program” így néz ki:

Leírom, hogy 1. Ebbe a sorba már nem írok többet.
Leírom, hogy 2. Ebbe a sorba sem írok már.
…
Leírom, hogy 10. (És ide sem írok már többet, de ez mindegy.)

Egyszerű, egymás után végrehajtandó lépésekről van itt szó, amiket végrehajtva elvégezhető a feladat. Észrevehetjük, hogy minden sor egyforma, csak a szám változik. Így általánosítható:

Az 1-es számra gondolok.
Leírom, a számot, amire gondolok. Új sort kezdek.
Megnövelem a gondolt számot.
Leírom, a számot, amire gondolok. Új sort kezdek.
Megnövelem a gondolt számot.
Leírom, a számot, amire gondolok. Új sort kezdek.
Megnövelem a gondolt számot.
…

És innen továbbvihető:

   1. Az 1-es számra gondolok.
   ↓
┌> 2. Leírom, a számot, amire gondolok. Új sort kezdek.
│  ↓
│  3. Megnövelem a gondolt számot.
│  ↓
└─ 4. Ha a gondolt szám ≤ 10, akkor visszaugrok a 2. lépésre.
   ↓
   5. Kész.

   Az 1-es számra gondolok.
   ↓
┌> Ismétlem a következő műveleteket:
│    ↓
│    Leírom, a számot, amire gondolok. Új sort kezdek.
│    ↓
│    Megnövelem a gondolt számot.
│    ↓
└─── Újra, ha a gondolt szám ≤ 10, amúgy megyek tovább.
   ↓
   Kész.

   X = 1
   ↓
┌> Amíg X ≤ 10, addig ismétlés:
│    ↓
│    Leírom X-et. Új sort kezdek.
│    ↓
│    X = X+1
│    ↓
└─── Ismétlés vége.
   ↓
   Kész.

Nem kell, csak 2-től indítjuk a ciklust, és kettesével növeljük a változót, mert „szabályos” sorban jönnek egymás után a kiírandó értékek.

Ehhez muszáj egyesével mennünk, mert a kiírt és nem kiírt számok között nem szabályos a lépésköz. Bevezetünk egy elágazást:

   X = 1
   ↓
┌> Amíg X < 100, addig ismétlés:
│    ↓
│    Ha X 3-mal és 5-tel sem osztható, akkor:
│        ↓
│        Leírom X-et. Új sort kezdek.
│    ↓
│    X = X+1
│    ↓
└─── Ismétlés vége.
   ↓
   Kész.

Mi itt a teendő? A legkisebb helyiértéktől (az egyesektől) indulunk. Összeadjuk a két számjegyet, és leírjuk a tíznél kisebb részt. Ha az eredmény nagyobb lett 9-nél (10, vagy annál több), akkor az átvitelt feljegyezzük, mert azt majd hozzá kell adni a következő helyiértéknél. Itt 9+4 az 13, vagyis a 3-at írjuk le, az 1-est pedig majd a következő körben a 3+2-höz kell hozzáadni (így lesz ott az összeg 3+2+1=6). Ezt addig kell folytatni, amíg el nem fogynak a számjegyek.

Az összeg soron következő számjegyének előállításához, és az átvitel képzésekor használhatjuk a 10-zel osztást és annak maradékát. Ezzel matematikailag precízen is meg tudjuk fogalmazni a tíz feletti és alatti részt. Például ahol az összeg 13 volt, ott 13/10 lefelé kerekítve 1 (az az átvitel), az osztás maradéka pedig 3 (azt kell leírnunk az egyesek oszlopába). Ezt a program megírásakor kihasználjuk. Írhatnánk azt is az 5. lépésben, hogy „ha összeg≥10, akkor van átvitel”, de a nullás érték, mint az átvitel lehetséges értéke ugyanúgy megfelelő.

   1. Indulunk az egyesektől.
   ↓
┌> 2. Összeadjuk a két egymás alatti számjegyet.
│  ↓
│  3. Ha van, hozzáadjuk az előző körből hozott átvitelt is.
│  ↓
│  4. Elosztjuk tízzel, a maradékot leírjuk alájuk.
│  ↓
│  5. Megjegyezzük az átvitelt, ha van (az osztás eredménye, lefelé kerekítve).
│  ↓
└─ 6. Ha van még további helyiérték (tízes, százas…), ugrás vissza a 2. lépésre.

Ennek a feladatnak a megoldására általános iskolában is tanítanak már egy módszert. Új dolgot most sem fogunk kitalálni, csak tisztázzuk az eddigieket.

Vegyük példának a 120-et. Mit is csinálunk itt? Van egy számunk, az a 120. Ezt kell osztogatnunk az egyre nagyobb prímszámokkal. 2-től indulunk, mert az a legkisebb prímszám. Ha sikerül elosztani vele (maradék nélkül osztható), akkor leírjuk, hogy osztottunk (120|2 ), és el is osztjuk a számot. Ha nem sikerül, akkor viszont a következő prímszámra van szükségünk, és azzal kell próbálkoznunk. Mindezt addig ismételgetjük, amíg el nem jutunk az 1-ig, mert akkor készen vagyunk.

Két apróság, mielőtt leírjuk a programot. Egyrészt fontos tisztázni, hogy a következő prímszámra csak akkor van szükségünk, ha nem sikerült az osztás; egy adott prímtényezővel lehet, hogy többször is oszthatunk (jelen esetben a 2 ilyen). Másrészt igazából mindig vehetjük az eggyel nagyobb számokat is osztónként, nem kell a következő nagyobb prímszámot megkeresni. (Jelen példában 2-vel, 3-mal osztunk; 4-gyel nem baj, ha megpróbáljuk, úgysem fog sikerülni, mivel annyiszor már leosztottuk 2-vel a számot, ahányszor csak lehetett.) Ez az utóbbi gondolat jelentősen leegyszerűsíti a megoldást, mivel tudjuk, hogy nincsen szükségünk a prímszámok listájára.

   1. Megkérdezzük, melyik számot kell felbontani.
   ↓
   2. A legkisebb szám, amivel osztani próbálunk, a 2.
   ↓
┌> 3. Megvizsgáljuk, hogy a szám osztható-e a vizsgált osztóval.
│     ├─> Ha igen, akkor leírjuk: szám | osztó; és el is osztjuk.
│     └─> Ha nem,  akkor a következő, eggyel nagyobb osztóra gondolunk.
│  ↓
└─ 4. Amíg nem érjük el így az 1-et, csináljuk újra a 3. sortól.
   ↓
   5. Leírjuk, hogy 1|.

120│2
 60│2
 30│2
 15│3
  5│5
  1│

A megoldást egy kicsit másképpen is meg lehet adni. Hogy miért, az is jól látszik a 120 példáján. Először 2-vel osztunk, és utána pedig megint 2-vel osztunk. Sőt, egészen addig osztunk újra és újra 2-vel, amíg lehet. Ha nem lehet, akkor pedig az osztót gondolkodás nélkül megnövelhetjük 1-gyel (3 lesz), és ezt folytathatjuk 1-ig.

Ez a megoldás elviekben különbözik az elsőtől, viszont végeredményben teljesen ugyanazt adja. A programozásban nagyon gyakran előfordul, hogy többféle, különböző elvű megoldást lehet adni még a legegyszerűbb problémákra is.

      1. Megkérdezzük, melyik számot kell felbontani.
      ↓
      2. A legkisebb szám, amivel osztani próbálunk, a 2.
      ↓
┌> ┌> 3. Ha a szám osztható, akkor leírjuk: szám | osztó; és el is osztjuk.
│  └──── Újra próbáljuk, vagyis ha osztható volt, ismételjük meg a 3. sort.
│     ↓
│     4. Eggyel nagyobb osztóra gondolunk.
│     ↓
└──── 5. Amíg nem érjük el így az 1-et, csináljuk újra a 3. sortól.
      ↓
      6. Leírjuk, hogy 1|.