Mert programozni jó!
Abonyi-Tóth Andor
2005/01/27 10:13
818 megtekintés
A cikk már legalább egy éve nem frissült, az akkor még aktuális információk lehet, hogy mára elavultak.
A fenti mondat sajnos egyre kevesebb gyermek szájából hangzik el, és számuk évről évre csökken. Lehetne bűnbakot keresni, hogy ki és mi az oka, miért szorultak háttérbe a programozói ismeretek, az algoritmizálás oktatása elegendő-e, miért nem tudnak vagy akarnak még a frissen végzett informatika tanárok sem programozni.

Sorozatunk célja azonban nem az okok feltárása, hanem a programozás iránti érdeklődés felkeltése. Ezt tesszük egyrészt azért, hogy  megmutassuk, mit lehet célszerű programozási feladatként megoldani, ezzel segítsünk a versenyekre és az emelt szintű érettségire készülőknek a már korábban esetleg látott, megismert feladatok megoldásának bemutatásával a felkészülésben. Sorozatunk minden cikkében kitűzünk egy újabb problémát is, amelyre a megoldásokat diákok és tanárok is beküldhetik címünkre, díjak reményében.

Fontos tudnivalók

A feladatok megoldása során fontos tudnunk azt, hogy a versenyeken - a nemzetközi gyakorlatnak megfelelően - az elkészítendő programoknak fájlból kell olvasniuk, és fájlba kell megadniuk válaszként a megoldást. Az emelt szintű érettségi esetében várhatóan hibás program esetén lehetőség van a programba való betekintésre is.

1. Gazda

Egy gazdának van néhány útja, amelyek mentén nyárfákat ültetett.
Minden két szomszédos nyárfa közé pontosan egy szilvafát ültetett.
A gazda a halála előtt a következőt mondta legidősebb fiának: "Kiválaszthatsz magadnak N darab nyárfát, és a tiéd lesz minden két szomszédos nyárfád közötti szilvafa is!"
A fiú úgy szeretné kiválasztani az N darab nyárfát, hogy a lehető legtöbb szilvafája legyen.

Készíts programot, amely a kiválasztható nyárfák (1<= N <=10000) és az utak számának (1<=K<=1000) ismeretében kiszámítja, hogy legjobb esetben hány nyárfája lesz a fiúnak!

A GAZDA.BE fájl első sora a kiválasztható N fa számát és a fasorok K számát tartalmazza. A második sorban a K darab fasorban az egymás mellett lévő nyárfák száma szerepel.
A GAZDA.KI fájl egyetlen számot tartalmazzon: a legjobb esetben elérhető szilvafák számát.

Például:

GAZDA.BE

10 3
4 8 6

 

GAZDA.KI

8

A feladat az idei Nemes Tihamér Verseny 2. fordulójában került kitűzésre a 9-10. évfolyamos versenyzők számára. A feladat szövege ugyan tartalmazott pár hibát, de itt ezeket már javítottuk, és némileg pontosítottuk a feladat szövegét. Így a következő megállapításokat tehetjük meg.

  • Minden fasorban legalább 2 nyárfa van (ez nem szerepel a szövegben), de egy nyárfa  hosszúságú fasort nem is lenne értelme kiválasztani, mert...
  • Csak olyan fasort célszerű kiválasztani, amelyben legalább két nyárfánk lesz, és...
  • Minden fasorban eggyel kevesebb szilvafa van, mint nyárfa;
  • Nem kötelező egész fasort kiválasztani (Ez sem szerepel kimondottan vagy tiltva a szövegben, ami azért okozhatott gondot, mert ha csak egész fasort lehetne kiválasztani, akkor a feladat nagyságrendekkel nehezebb.);
  • Két fasor közül az a jobb szilvafa/nyárfa arányú, amelyik hosszabb;
  • Azt a fasort célszerűbb kiválasztani a lehetségesek közül, amelyben a legjobb a szilvafa/nyárfa arány.

A fenti megállapítások alapján sejthető, hogy a mohó algoritmus célravezető lesz. Ez a megoldási stratégia azt jelenti, hogy a lehetséges fasorok közül minden esetben azt választjuk, amelyre az utolsó megállapítás a legkedvezőbb, és még nem választottuk ki. Ha már nincs annyi, még nem kiválasztható nyárfánk, hogy  egy teljes fasort kiválasszunk, akkor a még ki nem választott, leghosszabb fasor elejéről választunk fákat.

Itt jegyezzük meg, hogy a feladat kitűzésében a dőlt betűvel jelzett pontosítások elmaradása a versenyen egy olyan probléma megoldása irányába sodorhattak, amely messze meghaladja a középiskolásoktól ebben az életkorban elvárható ismereteket. Ha csak teljes fasorokat lehetne kiválasztani, akkor a feladat nem oldható már meg a mohó algoritmussal. Erre példa a 11 9 8 6 5 4 hosszúságú fasorok esetében a 23 kiválasztható nyárfa, ahol a mohó algoritmus 18 szilvafát eredményezne − 11 9  fasorok választásával −, míg az optimális választás  − 8 6 5 4 − fasorok esetén 19 szilvafa boldog tulajdonosa lehetne a gazda fia.

A korábbi megállapítások alapján tehát a következő lépéseket kell tennünk a válasz megadásához:

  1. Rendezzük a fasorokat hosszuk szerint csökkenő sorrendbe;
  2. Amíg a leghosszabb fasor hossza is kevesebb, mint a még kiválasztható fák száma 3. pont, különben 7. pontban folytassuk;
  3. Válasszuk ki a leghosszabb fasort;
  4. A már megszerzett szilvafák számához adjuk hozzá az új fasor hosszánál eggyel kevesebbet;
  5. Töröljük a leghosszabb fasort;
  6. Lépjünk vissza a 2. pontba;
  7. Ha legalább még egy kiválasztható fa maradt, akkor a szilvafák számához adjunk hozzá a megmaradt kiválasztható fák számából egyet;
  8. Vége.

1. Feladat

Készítsük el a leírtakat megvalósító programot Pascal nyelven! Ne felejtsük el, hogy a fasorok hosszát a megadott fájlból kell beolvasni és fájlba is kell kiírni a végeredményt!

Comenius LOGO

A feladat megoldható Comenius LOGO nyelven is, és e nyelven szinte kínálja magát a rekurzív megoldás.

A :db változó itt a korábban K-val jelölt kiválasztható nyárfák számát jelenti, az :l lista pedig a fasorok hosszát tartalmazza már csökkenő sorrendben.

A rekurzív megvalósítás alapgondolata a fentiekhez nagyon hasonló:

  1. Ha nincs már több kiválasztható fasor, akkor vége az eljárásnak, nem lehet növelni a már megszerzett szilvafák számát;
  2. Ha a leghosszabb fasor több elemű, mint ahány fát még kiválaszthatunk, akkor ennek eggyel csökkentett hosszát adjuk hozzá a csökkentett nyárfaszám és a leghosszabb fasor nélküli esethez (térjünk vissza az 1. pontba), különben ha legalább még két kiválasztható nyárfa van még, akkor annál eggyel kevesebbet adjunk hozzá a korábbi összeghez, vagy nem kell semmit tennünk (0 vagy 1 nyárfa maradt), készen vagyunk.

Mint látható, a LOGO megoldás egyszerű és kézenfekvő, így igazából nem érthető, hogy a versenyen miért zárták ki LOGO-ban való programkészítés lehetőségét. Az eljárás már beolvasott és csökkenően rendezett listát használ, emiatt hátra van még az alkalmazást megelőző részfeladat:

2. Feladat

Készítsük el a fájlból az :l listába beolvasó algoritmust LOGO nyelven, és rendezzük is a kapott elemeket a listában!

Módszertani ajánló

tantárgyinformatika
témakörprogramozás, emelt szintű érettségi
évfolyam/korosztály8-12. évfolyam
módszerPéldaprogramon keresztül egy feladat megoldásának bemutatása, a megoldáshoz vezető módszer/algoritmus általános ismertetésével
idő45 perc
célokAz érintett tanulók megismerjék az alkalmazható problémamegoldási módszereket.
tanulási helyzetAz algoritmizálási és programkódolási alapismeretek után a megoldási stratégiák és azok lekódolásának megismerése.
szükségeskivetítő, használt nyelvi fordítók (LOGO/Pascal)
szerzőRozgonyi-Borus Ferenc
címhttp://www.sulinet.hu/tart/cikk/ae/0/24964/1

Linkek

Csatlakozz hozzánk!

Ajánljuk

European Schoolnet Academy Ingyenes online tanfolyamok tanároknak
School Education Gateway Ingyenes tanfolyamok és sok más tanárok számára
ENABLE pilot Program iskoláknak a bullying ellen
eBiztonság Minősítés Minősítési rendszer oktatási intézményeknek