Módszeres Programozás

Szlávi Péter - Zsakó László, 1986

Tartalom

Bevezetés
Problémák a programkészítés körül
A programozási elvek
Programozási tételek
Példa a módszeres programozásra
A program helyessége
Tesztelés
Programhiba-keresés
Helyességbizonyítás
Példa a módszeres programozásra
Programok hatékonysága
Programcsaládok
Néhány szó a feladatmeghatározásról
Néhány szó a dokumentációról
Utószó
I. Függelék: A leíró nyelv szabályai
II. Függelék: BASIC kódolási szabályok


Bevezetés

Könyvünkkel a számítástechnika nem hivatásszerű alkalmazóinak szeretnénk segítséget nyújtani. Körükben is el kívánjuk terjeszteni azokat a programozási elveket, amelyek a számítástechnika szakemberei előtt már régóta ismertek és használtak. Egyrészt azokhoz szólunk, akiknek némi gyakorlatuk van már a programozásban. Számukra minden bizonnyal ismerősek lesznek a problémák. Lehet, hogy a kezdő programozók nem kellő átéléssel olvassák majd az első, a Problémák a programkészítés körül c. fejezetet, de higgyék el nekünk, hogy az elvek be nem tartása kétségkívül a leírt bonyodalmakhoz vezet.
Mondanivalónkat az elvek kialakulásához vezető problémákkal kezdjük, majd ennek orvoslására egy nyelvet vezetünk be, amelynek elsajátítása nem jelent különösebb gondot a nem számítástechnikai szakember számára sem. Mint kiderül, ennek mintájára bárki kialakíthatja a saját nyelvjárását, amit persze úgy célszerű megalkotni, hogy másoknak is könnyen érthető legyen.
A problémák után néhány feltétlenül megszívlelendő programozási (helyesebben programírási) elvet sorolunk fel. Már itt sietünk felhívni a figyelmet arra, hogy az elvek betartása nem lesz könnyű. Ez főleg azokra vonatkozik, akik már úgymond rutinból programoznak. Gondoljanak keserű tapasztalataikra, amikor kísértést éreznek letérni az elvek útjáról!
Az elvek ismertetése után bemutatjuk a módszeres programozás gyakorlatát. Ekkor válnak természetessé és magától értetődővé az elvek. Példáinkat kellően összetettnek választottuk, hogy az elvek használandóságára fény derüljön. A hatékonyság dimenzióit kutatjuk: a helyfoglalást, a végrehajtási időt, a bonyolultságot.
Közben olyan szabályokkal is találkozunk, amelyeket tapasztalt programozók fedeztek fel. Ezeket gyakoriságuknál és általánosságuknál fogva helyesebb lenne programozási típusalgoritmusoknak, vagy - ahogy a szakirodalomban hivatkoznak rájuk - programozási tételeknek nevezni. Nem garantálják ugyan a programozás egzakt, matematikai felépítését, de a felmerülő feladatok igen nagy részére alkalmazhatók.
A programozás gyakorlatáról ennyivel még nem lenne teljes a kép. Tegyük fel, hogy megszületett a mű: a program. A következő feladat: meg kell győződni arról, hogy vajon tényleg jó-e? Ha nem, akkor hogyan lehet kijavítani úgy, hogy ami eddig jó volt, az jó is maradjon. Itt fogjuk tisztázni, hogy mik a program helyességének formális követelményei, s ízelítőt adunk a helyességbizonyítás témaköréből is.
Sokszor hasznos, ha egy feladat megoldása előtt a feladattal rokon, s már megoldott problémák között kutatva bukkanunk rá a megoldásra. Így mintegy (program-) családi kapcsolataink juttatnak el a cél közvetlen közelébe. E családi kapcsolatok feltárásában, valamint a már önálló lépések megtételében nyújt segítséget a Programcsaládok c. fejezet. Ugyanitt más beállításban is felvetődik a rokonság figyelembevétele. Sokszor ui. a feladatra nem egy, hanem épp egy egész programcsalád ad kézenfekvő megoldást.
Végül a feladatmegoldás folyamatában oly mostohán kezelt, és e folyamat alapjaként tekintendő lépést, a feladatmeghatározást (vagy specifikálást) tárgyaljuk. Bár ez a programkészítés egyik első tevékenysége, mégis a végére hagytuk. Indokunk: kezdők számára kevéssé tudjuk a szükségességét korábban hangsúlyozni, és az amúgy is nehéz első fejezetek mellé nem akartunk még egy mély meggondolást igénylő részt helyezni.
A függelékekben egy javasolt nyelvet írunk le. Megadjuk, hogy mit s hogyan, azaz a nyelvtant (szintaxist) és a jelentést (szemantikát). Ezután összefoglaljuk, amit a BASIC-ről tudni kell: a kész programot milyen, ún. kódolási szabályokkal lehet átültetni az IS-BASIC nyelvre.

Befejezésül még két gondolatot kell felvetnünk!
Könyvünk hangvétele némi előzetes magyarázatra szorul. Úgy gondoltuk, hogy a pontos, definíciókra épített tárgyalásmód helyett eredményesebb, ha az elvek kialakulása felől, szabadabb stílussal közelítjük meg a programozás problematikáját. Így sokszor használunk olyan fogalmakat, amelyek félrevezetően túl tudományosnak tűnhetnek, s mégsem definiálunk. Ilyen pl. a frontális módszer, a módszeres program stb. Ezeket a szó köznapi értelmezése szerint kell érteni, használata közben a hangulatára célszerű gondolni Például a frontális módszer: a program teljes arcvonalán támadó módszer, amely a feladat minden egyes pontján egyszerre szeretne sikert aratni anélkül, hogy alkalmazkodna a feladat sajátos logikájához. Világos, hogy nagyobb lélegzetű probléma esetén ez a megoldási stratégia már nem lehet sikeres.
A programírás folyamatában feltételezzük a közvetlen ember-gép kapcsolatot Mondanivalónk elsősorban ilyen kapcsolatot biztosító számítógépekre és nyelvekre vonatkozik. Így a személyi számítógépek mindegyikére. Ezeknek ma még kétségkívül legelterjedtebb programnyelve a BASIC.
Végül köszönetét mondunk mindazon munkatársainknak az Eötvös Loránd Tudományegyetem Számítástechnikai Tanszékén, akik munkájukkal sok segítséget adtak könyvünk elkészítéséhez, valamint Megyeri József lektornak lelkiismeretes munkájáért.

Problémák a programkészítés körül

A programozók gyakori hibája, hogy a feladatot kézhez kapva, rögtön nekilátnak a program megírásának, pontosabban a program kódolásának. Vegyük szemügyre a feladat elleni ilyen frontális támadás hibáit!
A feladatmegoldás efféle megközelítése igen gyakran kudarcra ítélt: zavaros visszalépésekkel tagolt. A visszalépések oka az előrelátás hiánya. Ez azt jelenti, hogy a problémát csak fellépésekor érzékeli, akkor, amikor már kitérni nem tud, csak visszakozni!
Nem a visszalépés ténye rossz, hiszen nem lehet belelátni a feladatba első pillantásra. Kicsit bele kell élnünk magunkat a feladat sajátos problémavilágába ahhoz, hogy biztonságosan tudjunk tájékozódni a megoldás kidolgozása során. Gyanút csak a gyakori és zavaros visszalépések kell, hogy ébresszenek. A visszalépések megtagadása nem vezet célra. Az újabb és újabb csalafintaságok, a trükkök hatására csak még inkább belebonyolódunk a programba, s később még fájóbb az újrakezdés.
De tételezzük fel, hogy kudarcot nem ismerve, megküzdünk a feladattal: és elkészül a program. Azt hihetnénk, hogy megpróbáltatásainknak ezzel vége. Koránt sincs így! További próbatételek várnak ránk, s programunkra.
Használni kell ugyanis, de a program nem működik! Pedig mennyi leleményt és fortélyt alkalmaztunk! Talán éppen ezek a szunnyadó, rosszkor ébredező ötletek okozzák tragédiánkat?! A lecke fel van adva: ki kell javítani a programot! Ehhez először meg kell találni a hibát, ami nem is egyszerű dolog egy ilyen pokolian ravasz szerkezet esetén. Kérdés, hogy beszélhetünk-e egyáltalán szerkezetről, van-e a programnak szerkezete? S ha megtaláltuk a hibákat, milyen újabb varázslat szükséges a program működtetéséhez?
Készüljünk fel a legjobbra! A program elkészült, sőt - láss csodát! - működik is. Telik-múlik az idő, hasonló problémával találkozunk. Elővesszük jól megírt, kész programunkat abban a hiszemben, hogy használni tudjuk. Azonban hamar kiderül, hogy a hasonlatosság, bár valós, de nem elegendő ahhoz, hogy a program magától megbirkózzék a problémával. Például egy kicsit más formában kéri az adatokat vagy/és egy kicsit másként értelmezi, mint a mostani feladat igényelné. Nyilván a programot kell a feladathoz idomítani. Csalóka ábránd, hogy nagy nehezen meglelve a kritikus, kicserélendő részt, átalakítás után működő programot kapunk. Szomorúan ugyan, de kénytelenek leszünk tudomásul venni, hogy egyetlen kiút maradt: újra írni a programot!
Hasonló megrázkódtatás, ha programunk használatára nem nekünk, hanem barátunknak, munkatársunknak vagy - elképzelni is szörnyű - főnökünknek van szüksége. De ezen a ponton hagyjuk is abba a programírás fejetlenségéből származó gondok ecsetelését.
Mindezek a frontális módszer hibáiból származó problémák. A módszeresen írt programokkal is lehetnek gondok. Ezek csak technikai problémák, de egyáltalán nem jelentéktelenek.
Lássuk tehát, jól megírt programunk használata milyen követelményeket támaszt írójával szemben!
A programot elindítva még a legvakmerőbb felhasználónak is inába száll a bátorsága, ha a program első ténykedéseként egy kérdőjel jelenik meg a képernyőn. Legyen bármily fantáziadús is az illető, koránt sem biztos, hogy tudja, mit s hogyan feleljen a kérdésre. Tételezzük fel, hogy a kérdőjel ennek jelzése céljából került ki a képernyőre. Persze feltehető, hogy van elképzelése arról, mi is lehet a kérdés. Bár, ha sejti, hogy a programnak milyen paraméterekre van szüksége, ezek megadási sorrendjében akkor sem lehet biztos, így aztán a felhasználó vagy lemond a program segítségéről, vagy sietve megkeresi a program készítőjét. A bátrabbak, a kihívást elfogadva, automatizált rejtvénynek tekintik az adódott problémát, s kísérleti alapon próbálják megfejteni, kitalálni a várt választ.
A felhasználó reménytelen eset! E kijelentéssel arra a kellemetlen kötelességre utalunk, hogy a felhasználó minden ravaszkodására, jó vagy rosszindulatú tévedésére fel kell készülni. Kerülni kell annak eshetőségét, hogy nem természetes módon - általunk nem betervezetten - álljon le a program amiatt, hogy a felhasználó nem azt az adatot, vagy nem akkor adta, amit, illetve amikor kellett volna. Előfordulhat az is, hogy nem abban a sorrendben, esetleg nem egészen abban a formában íja be a választ, ahogyan a program várja.
A borzasztó programok kategóriájába tartozik az a program is, amely eltitkolja használója elől, hogy éppen mit csinál. Gondoljunk csak arra a bizonytalan érzésre, ami akkor keríti hatalmába az embert, amikor a program hosszú időn át semmi jelzést nem ad működéséről, s nem tudjuk, hogy valami hiba miatt áll, vagy pedig helyesen működik.
Ne is beszéljünk azokról a gyötrelmekről, amikben akkor van részünk, ha más jól-rosszul megírt, de az előbbiekben ecsetelt, barátságtalan programját kényszerülünk használni.
Foglaljuk össze, milyen, a programírás módszeréből fakadó, illetve milyen, a program használhatóságát érintő problémákról beszéltünk!

1. A feladat elleni frontális támadás módszere:

2. A módszeresen írt program kényelmetlen vonásai lehetnek:

A programozási elvek

Egyik legfontosabb, sokféleképpen alkalmazható elvünk az ókori latin kultúrából ránk maradt Oszd meg és uralkodj elve alapján fogalmazható meg: Oszd részekre, majd a részek független megoldásával az egész feladatot könnyebben oldhatod meg. Így programodat könnyen kézben tarthatod, vagyis uralkodhatsz felette.
Ezt a stratégiai elvet tartjuk szem előtt akkor, amikor gondolkodásmódunkat helyes mederbe igyekszünk terelni. Lépésenkénti finomításnak nevezik ezt az elvet a feladatmegoldás filozófiájában. A feladat megoldását először átfogóan végezzük el, nem törődve a részletekkel, amelyekről érdemben amúgy sem tudnánk helyesen dönteni az adott pillanatban sok, még pontosan előre nem látható probléma miatt. Tehát a feladatot néhány (nem túl sok!) részfeladatra bontjuk. Úgy is mondhatnánk: a feladatot megoldjuk a legfelső szinten. Ha volna olyan gép, amelyen léteznének azok az utasítások, amiket mi részfeladatokként megadunk, akkor máris futtatható lenne a program. Ezt az eljárást fogjuk követni az egyes részfeladatok megoldásakor is (a részek feletti uralkodás érdekében), mindaddig, amíg olyan utasítások szintjéig nem érünk, amelyeket gépünk (kódolás után) már végre tud hajtani.

Piramis elv

Mindez így elmondva rettentő egyszerűnek tűnik, holott az ilyen fegyelmezett gondolkodás nem könnyű.
A részfeladatokra bontás a következőket foglalja magában: pontosan ki kell jelölni, hogy az adott részművelet milyen adatokat kezel, milyeneket állít elő, és ezeket miként kell egymáshoz rendelni; vagyis ha ez az adat jött a részművelethez, akkor azt az adatot kell kapjuk eredményként. A hogyanról most nem elmélkedünk.
Nyilvánvaló, hogy két azonos szinten definiált részfeladat között biztosítani kell a harmóniát úgy, hogy a végrehajtásban előbb következő az utána következő adatait szolgáltassa. A részfeladatokra bontáskor persze felmerülhetnek illesztési problémák.


A feladat finomításának egy szintje a piramis egy szintjén

Az elmondottakból már körvonalazódik a lépésenként elnevezés értelme. Óvatosan, megfontoltan haladunk az ismeretlenbe; vigyázunk, hogy minden lépésnél megtartsuk uralmunkat az éppen megoldandó részfeladat felett. A finomítás pedig a lépésenkénti megközelítés mikéntjére utal. A lépés során kirajzolódott elemibb, egymástól már jól elhatárolható, s ezért egymástól függetlenül kezelhető tevékenységek még elemibbekre bontását jelenti. (Ezek a tevékenységek függetlenül kezelhetők, hiszen egymáshoz való viszonyukat az illesztéseik megadásakor már pontosan figyelembe vettük.)

Taktikai elvek
Milyen taktikai elveket - vagy kissé szerényebben szólva, jó tanácsokat - adhatunk a lépésenkénti finomítás elvének megvalósításához?

  1. A párhuzamos finomítás elve, amely szerint a szint összes részfeladatára kell elvégezni a finomítást. Nem szabad előre sietni valamelyik könnyebbnek vélt ágon, mert előfordulhat, hogy munkánk kárba vész (egy esetleges visszalépés miatt, s kár lenne ilyen lélektani terhet nyakunkba venni).
    Egy-egy szinthez szervesen hozzátartoznak a részfeladatok adatai is. Így világos, hogy az adatok finomítása során sem szaladhatunk előbbre, mint amit a szint eljárásai megkívánnak.

  2. A döntések elhalasztásának elve, amely szerint egyszerre csak kevés dologról, de következetesen kell rendelkezni. A problémát kevés, de jól körülhatárolt részproblémára kell bontani. Ám óvakodni kell a másik véglettől is, hiszen a túl kevés részre bontás általában nem vezet optimális döntésekhez, mert nem azonos nehézségű, súlyú részproblémákat eredményez. A részfeladatok pontos körvonalazásához eleinte még nincs elegendő ismeret birtokunkban, s ha döntésünket később felül kell bíráljuk, még visszalépések is adódhatnak. Az a jó döntés, amely a későbbiek során a legkevésbé köti meg kezünket. Célszerű az adatok és eljárások finomításánál minél későbbre halasztani azokat a döntéseket, amelyek kihasználják a gép, ill. a programozási nyelv konkrét sajátosságait. Annál jobb a programunk, minél többet tartalmaz a feladat lényegi felépítéséből és minél kevesebbet a gép, ill. a nyelv kötöttségeiből.

  3. Vissza az ősökhöz elv, amire akkor van szükségünk, amikor körültekintő megfontolásaink ellenére zsákutcába kerülünk. Ekkor vissza kell lépni az előző szinthez, és újra végig kell gondolni a részfeladatokra bontást, a keserű tapasztalatok figyelembevételével.
    Bármennyire is csábító lenne a zsákutcából csak a problémás részfeladat újra átgondolásával, kijutni, elkerülhetetlen minden részfeladatot újra megfontolni, hogy a beépített új elem hézagmentesen illeszkedjen.

  4. A nyílt rendszerű felépítés elve, miszerint nemcsak a feladatra, hanem a feladatot is tartalmazó feladatkörre alkalmazható programot érdemes definiálni. Ezzel elkerülhetjük a későbbi kényszerű feladat- vagy programidomítási gondokat, azaz nem egy nyárra hozunk létre programot. (Szokás ezt még a feladatáltalánosítás elveként is emlegetni.) Ennek az elvnek kifejezett alkalmazásával találkozunk majd a programcsaládokról szóló fejezetben.

  5. A döntések el nem mulasztásának elve: a ki nem mondott, de hallgatólagosan meghozott döntések rugalmatlanná és álnokká teszik a programot. Néha a döntések kinyilvánításának elveként is hivatkoznak rá. Szorosan összefügg azzal, hogy a fejlesztői dokumentációt a program tervezésével, írásával párhuzamosan kell készíteni. (Ebben úgy írjuk le a programot, hogy működését más is megérthesse, szükség esetén módosíthassa.)

  6. Az adatok elszigetelésének elve azt mondja ki, hogy a programot biztos mederben csak úgy lehet tartani, ha az egyes programegységek a megtervezett illesztéseken, kapcsolatokon kívül egymással nem érintkezhetnek. Ezért tehát a programegységekhez tartozó adatokat ki kell jelölni és el kell szigetelni más programegységektől. Az adatok kijelölését legcélszerűbb a programegységben betöltött szerepük alapján csoportosítani: közös (pontosabban fogalmazva globális), ezen belül bemeneti (input) és kimeneti (output) adatok. A programegységhez és csak hozzá tartozó ún. saját (pontosabban fogalmazva lokális) adatokat, amelyektől - mint később látni fogjuk - a jó helykihasználás miatt hasznos elválasztani az ún. munkaadatokat (ezeket szokták a programozók sajátnak nevezni). Ez utóbbiak a programegység csak egyszeri működéséhez, időlegesen felhasznált segédadatok.
    Programírás közben érdemes táblázatot készíteni. Ebben összegyűjtjük a megfelelő szintszámokhoz tartozó változóneveket, eljárásneveket és hatáskörüket.

Technológiai elvek
A programírás már ecsetelt didaktikai elveitől a technológiai elvek vezetnek el bennünket a technikai elvek birodalmához

  1. Kevés, de egyértelmű szabályt kell kialakítani az algoritmusok leírására. Ez legyen számunkra kellően kényelmes gondolataink szárnyalásához, de a kényelem nem mehet a precizitás, az egyértelműség rovására! Ebben a legfontosabb algoritmikus szerkezeteknek helyet kell kapniuk.

    Melyek is ezek a nevezetes szerkezetek?
    (A programozással még csak most ismerkedők számára az itt leírtak minden bizonnyal nehezen emészthetők és esetlegesnek hathatnak, egyelőre fogadják el magyarázkodás nélkül. A későbbi alkalmazások során - azaz a következő fejezetekben - ezek értelme, értelmezése, célszerűsége kiderül majd.)
    Az adatokat beolvasó és kiíró utasítások az ablak szerepét játsszák a külvilág felől, ill. a program felhasználója felé.
    A program változóinak értékkel való ellátását az értékadó utasítások végzik.
    A feltételektől függő végrehajtást teszik lehetővé az ún. feltételes utasítások.
    A számítógépre szánt feladatok mindegyike feltételezi bizonyos részfeladatok ismételt elvégzését. A számítógép erősségét, a gyorsaságot éppen ezek a mechanikus ismétlések használják ki a legjobban! Ezek megvalósítása a ciklusutasítások segítségével történik.
    A program adott szintjén elemi utasításként felhasznált, meghatározott, de nem finomított részprogramok beépítését (az ún. eljáráshívást) is megkell oldanunk nyelvünkben.
    Természetesen a felhasznált és még hiányzó eljárások finomítása (másként szólva: az eljárás kifejtése) sem hiányozhat.

    E sajátos nyelvjárás, ill. leíró nyelv mellett szólnak a következő érvek. Az így készült program mechanikusan átírható bármelyik gépre, ill. nyelvre. Csupán a kódolási szabályokat kell megadni. A kódolási szabályok megadása persze nem mindig problémamentes, de ugyanezek a problémák felmerülnek a program újbóli, közvetlen megírásánál is! Az e módszerrel szemben gyakran felhozott érv, hogy nem vezet optimális programra, mert nem számol a nyelv, ill. a gép sajátosságaival, általában nem igaz, ugyanis a kódolási szabályok megalkotásánál ezeket figyelembe vehetjük. A program viszont e lokális optimalitáson túl rendelkezik a feladat logikáját mélyen figyelembe vevő algoritmikus optimalitással.

  2. Az algoritmikus nyelv kialakításánál jó betartani a könnyű olvashatóság érdekében a bekezdéses leírás és az összetett utasítások zárójelezése elveket. Ahogy az író is főbb gondolatait, a történés főbb eseményeit fejezetekbe tömöríti, ahogy az egyes epizódok külön-külön bekezdéseket alkotnak a fejezeten belül, valahogy úgy kell algoritmikus gondolatainkat, az algoritmus főbb eseményeit, epizódjait is jól láthatóan elkülöníteni a programban. A program teljes levezetése (finomítása) után a program szerkezetének vissza kell tükröznie a szintekre tagozódást: egy szint elemi utasításai a bekezdések azonos szintjeit alkossák! Ezeket az elveket is szem előtt tartottuk nyelvünk megalkotásakor.

  3. A beszédes azonosítók elve. A változóknak olyan nevet érdemes adni, ami utal arra, hogy mire használjuk. Ez kizárja az azonosítók keveredését, hiszen a név sugallja a funkciót, az algoritmusban betöltött szerepet. Nagy segítséget nyújt a kódoláskor is, pl. lehetővé teszi, hogy minimális számú változót rendeljünk az adatokhoz, hiszen a munkaváltozókhoz azonos neveket is rendelhetünk.

Az elvek további magyarázata helyett egy példával illusztráljuk az előbbieket. Legyen a feladat az, hogy a szövegben szereplő JUNIUS nevet minden előfordulásánál helyettesítsük a JULIUS névvel. Az algoritmus legfelsőbb szintje ilyesmi lehet:

Állj a SZÖVEG elejére
Ciklus amíg nincs vége a SZöVEGnek
  Ha következő szava a SZöVEGnek "JUNIUS"
    akkor helyettesíteni "JULIUS"-sal
    különben helyben hagyni
  Elágazás vége
Ciklus vége.

Mi itt a szembetűnő? Valamit addig kell ismételten elvégezni, amíg a szöveg végére nem érünk. Ez a valami jól láthatóan elválik az őt mintegy keretbe foglaló ciklusutasítás kezdő és befejező zárójelétől:

Ciklus feltétel
  valami
Ciklus vége

Hasonlóan könnyen és főleg tévedésmentesen értelmezhető a ciklus magját (belsejét) alkotó elágazás. A bekezdéses leírás és az összetett utasítások zárójelezése elvek következetes alkalmazásával bonyolultabb program is világosan érthető szerkezettel írható meg. A program kissé formálisabbra így alakítható át:

Szócsere(SZÖVEG):
  elejére-állás(SZÖVEG)
  Ciklus amíg nem SZöVEG-vég
    Ha következő-szó(SZÖVEG)="JUNIUS"
      akkor helyettesit("JULIUS")
      különben helybenhagy
    Elágazás vége
  Ciklus vége
Eljárás vége.

Az eljárások paramétereit (azokat az adatokat, amelyeket kívülről kap, ill. kifelé ad) az eljárás neve mögötti zárójelpárok közé írtuk. A megoldásban elemi utasításként használjuk a következő szó, a helyettesit és a helybenhagy eljárásokat. Ezeket most nem finomítjuk!
A nyílt rendszerű felépítés elvét követve még általánosíthatjuk úgy a megoldást, hogy a JÚNIUS és JÚLIUS szövegeket is paraméterként soroljuk föl az eljárásban:

Szócsere(SZÖVEG,MIT,MIRE):
  elejére-állás(SZÖVEG)
  Ciklus amíg nem SZöVEG-vég
    Ha következő-szó(SZÖVEG)=MIT
      akkor helyettesit(MIRE)
      különben helybenhagy
    Elágazás vége
  Ciklus vége
Eljárás vége.

Az előző három elvből már körvonalazódik a programozás folyamata. Látható, hogy két jól elválasztható tevékenységre bomlik: az algoritmus készítésére és a kódolásra.

Emlékeztetünk a programkészítés technológiai elveire: beszédes azonosítók, bekezdéses leírás stb. Mit kell tudni a nyelvről, amelyen programjainkat írjuk? A példából látható, hogy - a formalizmuson túlmenően - nagyon hasonlít a magyar nyelvre. A programot egyszerűen mondatok sorozatának tekintjük, amelyek valamilyen tevékenységek egymás utáni elvégzésére szólítanak fel.

A feladat teljes - számítógépes - megoldása persze jóval többet jelent az eddig boncolgatott programozásnál. Ez a tevékenység (ti. a feladat megoldása) tartalmazza a programozásnál semmivel sem kisebb jelentőségű feladatmegfogalmazást - a feladatmegoldás első lépéseként -, az elkészült program tesztelését, sőt optimalizálását, s birtokbavételét, azaz használatát is. Könyvünkben később részletesen taglaljuk ezeket. Jelentőségük aláhúzására azonban már itt is ejtünk róluk néhány szót.
A feladatmeghatározást (specifikálást) szokták a leginkább félvállról venni és ebből származik később a legtöbb gond, mivel az elvárásokat nem kellően gondoljuk át. Magától értetődőnek véve elmarad a pontos megfogalmazás és az eredményeknek, ill. a rendelkezésre álló adatoknak az összehangolása. Nagyon fontos tudni, hogy a feladatmeghatározás jósága meghatározó szerepet játszik a programkészítésre fordított idő mennyisége és a készülő program jósága szempontjából.
A természetes emberi tényezők miatt a legnagyobb igyekezet és odafigyelés ellenére is előfordulhatnak kódolási, ill. algoritmikus hibák. Ezek feltárására a tesztelés hivatott. Teszteléskor a már kész programot megfelelően választott adatkombinációkkal módszeresen futtatjuk.
Bár a program helyessége szempontjából nem vettünk figyelembe hatékonysági kér-déseket, gyakran ezek a program használhatóságát súlyosan érintik. Legkésőbb teszteléskor derülhet fény a program leggyengébb (pl. lassú) pontjaira. Itt is kihasználható (sőt ki kell használni) a módszeres program azon jó tulajdonságát, hogy ez a leggyengébb láncszeme is - mint bármely másik - pontosan meghatározott, s így a programból kiemelhető és esetleg teljesen új alapgondolatokra építve újraírható. Ezután már veszély nélkül ültethető vissza az új, hatékonyabban működő programrész.

Technikai elvek
A továbbiakban technikai jellegű ismérveket sorolunk fel, amelyek a program kódjával kapcsolatosak. Inkább úgy mondhatjuk, hogy az előzőek a program megírásához szükségesek, ez utóbbiak pedig a program használhatóságához elengedhetetlenek. Ilyen értelemben beszélhetünk a csak helyes programról, amely a feladat logikája szempontjából tökéletes, és a jó programról, amely ezen túl elő is segíti saját felhasználását.

  1. Az udvarias program bemutatkozással kezdi ténykedését, s ezzel tudatja a felhasználójával képességeit, szolgáltatásait, használatának mikéntjét. Az udvariasság másik fontos megnyilvánulása, hogy a program futása során megjelenő kérdések bárki számára - azaz a nem számítástechnikus szakemberek számára is - érthetőek és a válaszok a lehető legegyszerűbben megadhatók legyenek. Így pl. nem rabolja feleslegesen a felhasználó türelmét azzal, hogy a már megadott adatokból kiszámítható, származtatható adatokat kér.

  2. A bolondbiztos (biztonságos) program, amit a kísérletezni vágyó, vagy éppen balszerencsés felhasználó sem képes ellenőrizetlen vágányokra terelni azáltal, hogy nem a megfelelő módon vagy nem a megfelelő pillanatban válaszol a feltett kérdésre. Ennek érdekében a program kritikus pontjait, azaz ahol a felhasználó közvetlenül avatkozik be a program további menetébe, nagy odafigyeléssel kell megírni. Az esetleges hibalehetőségekre fel kell készíteni a programot úgy, hogy a felhasználónak lehetősége legyen a helyesbítésre is. Nem támaszkodhatunk a számítógép, ill. az értelmezőprogram eleve meglevő hibajelzéseire. Ezek ugyanis arra valók, hogy segítségükkel felderíthessük és kijavíthassuk az esetleges programhibákat, tehát a program írója, nem pedig a használója számára készültek. A felhasználónak végeredményben semmi köze sincs ahhoz, hogy a program nem közvetlenül, hanem csak a BASIC közvetítésével mozgatja a számítógépet.
    A bolondbiztos tulajdonság egyébként nemcsak e technikai elv, hanem a piramis elv közvetlen folyománya is, mert ahogy megadtuk az egyes eljárások közötti elvárásainkat (tudni illik egy eljárás végső feltételei nem lehetnek bővebbek, mint az őt követő eljárás bemeneti feltételei), ugyanúgy rögzíteni kell a külvilág és a beolvasó eljárás kapcsolatára vonatkozó kívánalmakat is. A külvilág azonban a programnak nem része, s így nem is programozható, ezért a bemeneti eljárások kezdő feltételeinek körét megfelelően ki kell szélesíteni. Ez azt jelenti, hogy a bemenő adatok értéktartományát, összeférhetőségét ellenőrizni kell. Ha ezek az eredeti feltételeket nem teljesítik, akkor valamilyen jelzés kíséretében új adatbevitelt kell kezdeményezni.

  3. A jól olvasható program. A program módosításakor, továbbfejlesztésekor óriási előnyt jelent, ha nem kell programunk minden mellékes vonását újra feltérképezni a megértéshez, hanem lényeges tulajdonságai a program megfelelő helyén könnyen kiolvasható formában megtalálhatók, s így a sebész magabiztos mozdulatával nyúlhatunk bele a program legérzékenyebb részeibe is. Már két idevágó elvet is említettünk, a bekezdéses leírás és az összetett utasítások zárójelezése elveket. Ezt egészíthetjük ki a kódoláskor különösen nagy jelentőségűvé váló jó magyarázatok (kommentek) elvével. A programozási nyelvre való áttéréskor ugyanis - a programozási nyelv kötöttségei miatt - sok, az algoritmust nagyban jellemző tulajdonság elveszne, ha ezeket az információkat nem őriznénk meg egy-egy jól megfogalmazott megjegyzés formájában.

  4. A (jól) dokumentált program. Sokszor nincs lehetőség - a program méretére rótt korlátozások miatt - arra, hogy az előző elvet maradéktalanul megvalósíthassuk. Ekkor le kell írni a program fontos vonásait: az algoritmusát, a változóit és ezek szerepét és a kódolásnál követett szabályokat. Ezeket a dokumentációban is rögzíteni kell, amelyben ezenkívül még foglalkozni kell a használat mikéntjével és az esetleges, előrelátható fejlesztési lehetőségekkel is.

Emberközelség
A következőkben a már ismertetett udvariasságra és bolondbiztosságra vonatkozó elv finomításairól lesz szó. Ezek a használatot befolyásoló tényezőkre hívják föl a figyelmet. Legfőbb mondanivalójuk, hogy nagy gondot kell fordítani a program által megjelenített információk külalakjára. Ide nem csak az eredmény jellegű kiírandók tartoznak, hanem pl. a tájékoztató, a felhasználóval való párbeszéd módja is.

  1. A lapkezelési technika. A kiírandó szövegek, adatok logikai egységekre bontva, jól különüljenek el, egyszerre csak annyi és olyan ütemezésben, amennyit, s ahogy a felhasználó be tud fogadni. A képernyőre vonatkozó információk esetén ez a lapkezelési technika. Mit is jelent a lapkezelés? Egyszerre egy képernyőlapnyi információt jelenítünk meg, s a felhasználónak lehetősége van lapozásra, pl. egy adott billentyű lenyomásával jelzi a gépnek "Elolvastam! Lapozz!" (Többek között ennek megvalósítására használható a Várj, amíg szükséges utasítás.)
    Mit kell még figyelembe venni egy lap összeállításánál? Ügyelni kell pl. a képernyőlap arányos kitöltésére, és jó, ha az egy lapon belül szereplő, logikailag szorosan össze nem tartozó információk egymástól elkülönülnek.
    Hatásos, ha a mondanivaló legfontosabb elemeit - a gép adta lehetőségek figyelembevételével - kiemeljük (inverz betűkkel vagy villogtatva, vagy más színű háttérrel, ill. betűkkel stb.).

  2. A menütechnika a lapkezeléssel szorosan összefüggő módszer, amely a felhasználóval való párbeszéd elegáns megszervezésére alkalmas. Általában bonyolult szolgáltatásokkal rendelkező programoknál használatos, amelyből a felhasználó - akár egy menüből - kiválaszthatja a számára szükséges lehetőséget. Minden egyes válaszával (válaszcsoporttal) a kérdések egy nagy hányadát kizárja, ezeket a számítógépnek fel sem kell tennie, megkímélve a felhasználót a fölösleges válaszadásoktól.

  3. A kérdéseknél nagyon sokszor épp az okoz bizonytalanságot, hogy a felhasználónak fogalma sincs arról, hogy az adatot milyen mértékegységben kell megadni. Ezért a kérdés szövege mellett célszerű közölni az adat mértékegységét, sőt - ha nem magától értetődő, akkor - még az értéktartományt is.
    Így elkerülhető, hogy pl. a program egy szöget radiánban vár, a gyanútlan felhasználó pedig a legnagyobb természetességgel fokban adja meg az értéket. Az ilyesmiből származó hibát nyilván nem kell ecsetelnünk.

  4. A fontos adatok kiemelésének nemcsak az információk könnyebb megértése szempontjából van jelentősége - amint ezt már a lapkezelési technikánál taglaltuk -, hanem hasznos a program állapotának, meghatározó paramétereinek azonnali visszajelzésekor is.
    Például amikor a számítógép egy hosszadalmas számítást végez, vagy bármilyen időigényes tevékenységbe fog - a hangsúly a hosszadalmasságon, időigényességen van! - akkor ne maradjon el időnként egy-egy kiírás, ami értesíti a felhasználót, hogy mely tevékenységet végzi éppen a program, és, hogy még kis türelmet kér.

  5. A legelemibb elvárás a képernyőn megjelenő szövegekkel szemben, hogy a sorok/szavak tördelése a helyesírás szabályainak megfeleljen. Ne sajnálja a programozó a fáradságot mondanivalójának gördülékeny megfogalmazására, szép elhelyezésére, hiszen csak ily módon kaphat mindenki számára kellemes programot!

  6. Következetes beolvasási szokások. Tartsunk mértékletességet a beolvasási módszerek változatosságában. Nem díjazzák a felhasználók kiterjedt programozási ismereteinket, ha a választ hol <ENTER>-rel lezárva, hol anélkül várja a program.

  7. A hiba megfontolt kijelzése. A hibák kézben tartásának szükségességéről már volt szó, de a hibák jelzésének mikéntje is jellemzi a programot. Igyekezni kell a hibajelzés legmegfelelőbb módjának kiválasztására. Ehhez a következő szempontokat érdemes megfontolni:

A továbbiakban már megtehetjük első lépéseinket az elmélettől a gyakorlat felé. Vagyis arra a kérdésre keressük a választ néhány tanulságos példán keresztül, hogy hogyan készül a program.

Programozási tételek

Hogyan fogjunk hozzá egy feladat - módszeres - megoldásához! A példákból kiderült, hogy a felülről lefelé való kifejtés során háromféle szerkezetet használtunk: utasítá-sok egymás utáni végrehajtását, feltételtől függő elágazást, valamint utasítások ismételt végrehajtását (ciklus)-, utasításcsoportjainkat pedig eljárásokra tagoltuk. Mit lehet tenni azonban, ha nem tudjuk, hogy melyik kifejtést is alkalmazzuk? Honnan várhatunk segítséget? A segítség magukban a feladatokban található, csak fel kell ismerni!
Ismerkedjünk meg néhány tipikus programsémával! Néhány típusalgoritmust adunk meg, amelyek felhasználhatók konkrét feladatok megoldása során. Programozási tételeket fogunk kimondani (kicsit szerényebben programozási recepteknek is nevezhetnénk őket). Elnevezésük a matematikai tételekkel kapcsolatos hasonlóságból származik. Ezek a tételek azt mondják ki, hogy a megadott programok helyes megoldásai a hozzájuk tartozó feladatoknak. A tételek bizonyítását a közölt programok helyességének bizonyítása jelenti. Egy későbbi fejezetben programok helyességének bizonyításával is foglalkozunk, amelynek segítségével az itt megadott tételek is bizonyíthatók (bár bizonyításuk menetét nem közöljük).
Ezek után a legtöbb feladat megoldása során nincs is más dolgunk, mint a kifejtés adott szintjén meghatározni, hogy milyen feladatról van szó, s utána alkalmazni a megfelelő algoritmust. Csak néha-néha van szükség új tételek kimondására, alkalmazására. Az ilyen típusú programkészítés nyilvánvalóan biztosítja, hogy ha a feladatot jól értettük meg, akkor helyes algoritmust írunk megoldására. Megjegyzendő azonban, hogy a tételek gépies alkalmazásával nem mindig a lehető legkedvezőbb programot kapjuk. A helyes megoldás hatékonyabbra való átírása azonban már külön tevékenység, s általában erősen feladatfüggő.

Feladataink jól meghatározott osztályokba sorolhatók kiindulási adataik és az általuk szolgáltatott eredmény alapján. A legegyszerűbbek egy adatból egy adatot számolnak ki. Kicsit bonyolultabbak azok, amelyek egy adatból egy sorozatot adnak. (Például adjuk meg az X első elemű, L növekményű számtani sorozat első N tagját!)
Számítástechnikai szempontból bonyolultabbak az olyan feladatok, amelyekben egy sorozathoz kell rendelni egy értéket, vagy pedig egy újabb sorozatot. Például annak a vizsgálata, hogy egy adott szám (N) prim-e, azt jelenti, hogy el kell döntenünk, hogy a 2 és N/2 közötti számok közül osztója-e valamelyik az N-nek. Megjegyezzük, hogy egy sorozatot sokszor egyetlen bemeneti paraméter értékével meg tudunk adni, amiből arra a megtévesztő következtetésre juthatnánk, hogy valami nagyon egyszerű feladatról van szó.
Ezt a bonyolultabb csoportot tovább bontjuk. Az egyszerű feladatok esetén a sorozathoz egyetlen értéket kell hozzárendelni, bonyolultabb esetben pedig egy sorozatot
Az első osztályba tartoznak az olyan feladatok, amelyekben egyszerre csak a sorozat egyetlen elemének vizsgálatára van szükség, ill. olyanok is, amelyeknél egyszerre több elemet is figyelembe kell venni. A második csoportban lehetséges, hogy a sorozat elemeiből új értékeket kell kiszámolni (darabszámúk lehet az eredeti sorozat elemszámától különböző is), valamint az is, hogy az eredeti sorozat valamilyen permutációját kell elő állítani.

Az egyes típusalgoritmusoknál mindig megadjuk az általános feladatot, az azt meg oldó algoritmust, egy konkrét feladatot, a feladatot megoldó algoritmust, a feladatban szereplő adatok megfeleltetését az általános feladat adataival.

Érték-hozzárendelés sorozatokhoz
(elemenkénti feldolgozás)

Összegzés
A feladatban adott egy N elemű számsorozat. Számoljuk ki az elemek összegét! A sorozatot (számhalmazt) - most és a továbbiakban is - az N elemű A(N) vektorban tároljuk. (Bár sok egyszerű esetben a sorozat egyes elemeit a sorszámukból is meghatározhatjuk).

Eljárás:
  S:=0
  Ciklus I=1-től N-ig
    S:=S+A(I)
  Ciklus vége
Eljárás vége.

Példa: adjuk össze az első N természetes számot!

Megfeleltetés:
sorozat - 1,2...,N

Eljárás:
  S:=0
  Ciklus I=1-től N-ig
    S:=S+I
  Ciklus vége
Eljárás vége.

Rögtön ez az első példa mutatja, hogy a feladat megfogalmazása, a felhasznált adatok megadása, az elképzelés rögzítése mennyire befolyásolja a megoldást. A feladatra ugyanis egy sokkal egyszerűbb megoldást is kaphatunk, ha a következőképpen értelmezzük: számoljuk ki az NN*(N+1)/2 függvény értékét valamilyen N természetes számra. Így a megoldás:

Eljárás:
  S:=N*(N+1)/2
Eljárás vége.

Ez esetben az összegzési tétel alkalmazása elhibázott lépés lenne.

Eldöntés
Ebben a feladatban rendelkezésre áll egy N elemű sorozat és egy, a sorozat elemein értelmezett T tulajdonság. Az algoritmus eredménye: van-e a sorozatban legalább egy T tulajdonsággal rendelkező elem?

Eljárás:
  I:=1
  Ciklus amíg I<=N és A(I) nem T tulajdonságú
    I:=I+1
  Ciklus vége
  VAN:=I<=N
Eljárás vége.

Példa:
k készítsünk algoritmust, amely egy névről (X$) eldönti, hogy egy hónap neve-e!
Megfeleltetés:
N - 12;
sorozat: január,február, ... (A$(N));
tulajdonság: A$(I)= X$; (1<=I<=12).

HONAP_E(X$):
  I:=1
  Ciklus amíg I<=12 és A$(I)<>X$
    I:=I+1
  Ciklus vége
  HONAP_E:=I<=12
Eljárás vége.

IS-BASIC-ben:

DEF HONAP_E(X$)
  LET I=1
  DO WHILE I<=12 AND A$(I)<>LCASE$(X$)
    LET I=I+1
  LOOP
  LET HONAP_E=I<=12
END DEF

(A hónapok neveit kisbetűsen tároljuk.)

Hasonló feladat a következő: rendelkezésre áll egy N elemű sorozat és egy, a sorozat elemein értelmezett T tulajdonság. Az algoritmus eredménye: igaz-e, hogy a sorozat minden eleme T tulajdonságú?

Eljárás:
  I:=1
  Ciklus amíg I<=N és A(I) T tulajdonságú
    I:=I+1
  Ciklus vége
  IGAZ_E:=I>N
Eljárás vége.

Felhívjuk Olvasónk figyelmét a megoldás és az előző algoritmus nagymértékű hasonlóságára. Ez tulajdonképpen várható is volt, hiszen a mindegyik T tulajdonságú ugyanazt jelenti, mint a nem létezik nem T tulajdonságú.

Kiválasztás
Rendelkezésre áll egy N elemű sorozat, egy, a sorozat elemein értelmezett T tulajdonság, valamint azt is tudjuk, hogy a sorozatban van legalább egy T tulajdonságú elem. A feladat ezen elem sorszámának a meghatározása.
A megoldás az előző alapján nagyon egyszerű. Csupán annyi az eltérés, hogy azt a többletismeretet, hogy biztosan van T tulajdonságú elem, az eljárásban levő ciklusfeltétel egyszerűsítésére használjuk.

Eljárás:
  I:=1
  Ciklus amíg A(I) nem T tulajdonságú
    I:=I+1
  Ciklus vége
  SORSZ:=I
Eljárás vége.

Keresés
Rendelkezésre áll egy N elemű sorozat, egy, a sorozat elemein értelmezett T tulajdonság. Olyan algoritmust kell írni, amely eldönti, hogy van-e T tulajdonságú elem a sorozatban, és ha van, akkor megadja a sorszámát. (Ez a feladat az előző kettő összefoglalása.)
A legegyszerűbb - és rendezetlen lista esetén az egyetlen lehetséges megoldás -, ha végigszaladunk a listán, amíg meg nem találjuk a keresett elemet, vagy a lista végére értünk (ezt hívjuk lineáris keresésnek). Ez az eljárás egyszerű, de van egy hátránya: nagyon sok (a legrosszabb esetben n, átlagosan n/2) összehasonlítást igényel.

Eljárás:
  I:=1
  Ciklus amíg I<=N és A(I) nem T tulajdonságú
    I:=I+1
  Ciklus vége
  VAN_E:=I<=N
  Ha VAN_E akkor SORSZ:=I
Eljárás vége.

Példa:
Módosítsuk úgy a HONAP_E eljárást, hogy hamis értéket adjon vissza, ha a megadott név nem hónap neve, egyéb esetben a hónap sorszámát adja meg. (Feltételezzük, hogy a hónapok neveit sorrendben tároljuk.)

DEF HONAP(X$)
  LET I=1:LET HONAP=0
  DO WHILE I<=12 AND A$(I)<>LCASE$(X$)
    LET I=I+1
  LOOP
  IF I<=12 THEN LET HONAP=I
END DEF

Megszámolás
Rendelkezésre áll egy N elemű sorozat, egy, a sorozat elemein értelmezett T tulajdonság. Most a T tulajdonsággal rendelkező elemek megszámolása a feladat.

Eljárás:
  S:=0
  Ciklus I=1-től N-ig
    Ha A(I) T tulajdonságú akkor S:=S+1
  Ciklus vége
Eljárás vége.

Példa:
Készítsünk algoritmust, amely N ember fizetése alapján megadja a 3000 Ft-nál kevesebbet keresők számát!
Megfeleltetés:
sorozat: fizetés1, fizetés2,... (A(N));
tulajdonság: A(I)<3000.

Kis fizetésűek száma:
  S:=0
  Ciklus I=1-től N-ig
    Ha A(I)<3000 akkor S:=S+1
  Ciklus vége
Eljárás vége.

Megjegyzés: Érdemes elgondolkodni az e tételben szereplő, valamint az összegzési tételben szereplő algoritmusok formai hasonlóságán. Rádöbbenhetünk, hogy ez az összegzési tétel egy változata.

Keresés rendezett sorozatban
Adott egy N elemű rendezett sorozat és egy keresett elem (X). Olyan algoritmus készítése a feladat, amely megadja, hogy szerepel-e a keresett elem a sorozatban, s ha igen akkor megadja a sorszámát. Ez hasonló a korábbi keresési feladathoz. Most kihasználjuk, hogy a vizsgált sorozat rendezett, ennek alapján bármely elemről el tudjuk dönteni, hogy a keresett elem előtte vagy utána van-e vagy esetleg éppen megtaláltuk. Így egy bonyolultabb de hatékonyabb algoritmust alkalmazhatunk: ez a logaritmikus keresés (ui. az összehasonlítások száma az elemszám logaritmusával arányos, ellentétben az előző kereséssel, ahol az összehasonlítások száma lineárisan függ az elemszámtól). Az eljárás A és F változói mindig annak a részintervallumnak az alsó és felső végpontjai, amelyben a keresett elem benne lehet.

Eljárás:
  AH:=1: FH:=N
  Ciklus
    K:=INT((A+F)/2)
    Ha A(K)<X akkor AH:=K+1
    Ha A(K)>X akkor FH:=K-1
  amíg AH<=FH és A(K)<>X
  Ciklus vége
  VAN_E:=AH<=FH
  Ha VAN_E akkor SORSZ:=K
Eljárás vége.

Megjegyzések:

Érték hozzárendelése sorozatokhoz
Az eddigi tételeknél (típusfeladatoknál) egyszerre a kiinduló sorozat egyetlen elemét kellett vizsgálni. Most olyanok következnek, ahol egyszerre több elemre is szükségünk lehet. Ezek közül sok átfogalmazható a korábbi feladatoknak megfelelőre. Például: Döntsük el, hogy egy sorozat monoton növekvő-e!

Ebből a csoportból egyetlen feladattípussal ismerkedünk meg, amely nem vezethető vissza az előzőekre: ez a legnagyobb, ill. a legkisebb elem kiválasztásának feladata.

Maximumkiválasztás
Ebben a feladatban egy sorozat legnagyobb elemét kell megtalálni. Most egyszerre nem elég a sorozat egyetlen elemét vizsgálni, hiszen a legnagyobb az, amely mindegyiknél nagyobb, azaz mindegyikkel össze kell hasonlítani. A feladat megoldását úgy kapjuk, hogy visszavezetjük elemenkénti feldolgozásra. Ha ismerjük K elem közül a legnagyobbat és veszünk hozzá egy új elemet, akkor a maximum vagy az eddigi vagy pedig az új elem lesz. Induláskor az első elemet maximumnak tekintjük.

Eljárás:
  MAX:=1
  Ciklus I=2-től N-ig
    Ha A(MAX)<A(I) akkor MAX:=I
  Ciklus vége
Eljárás vége.

Megjegyzés: Minimumkiválasztásnál csak a feltételes utasítás feltétele fordul meg.
Ha a kérdést úgy tesszük fel, hogy mennyi a legnagyobb érték, akkor egy másik megoldást is kaphatunk:

Eljárás:
  ERTEK:=A(1)
  Ciklus I=2-től N-ig
    Ha ERTEK<A(I) akkor ERTEK:=A(I)
  Ciklus vége
Eljárás vége.

Megtehetjük azt is, hogy az előbbi két eljárást egybeépítjük. Ez főleg akkor célszerű, ha egy érték kiszámítása sok időbe telik, bonyolultan végezhető el.
Példa: Készítsünk algoritmust, amely N ember magasságának ismeretében megadja a legnagyobb magasságot és a legmagasabb sorszámát.
Megfeleltetés:
sorozat: magasság1, magasság2, ... (A(N)).

Eljárás:
  MAX:=1: ERTEK:=A(1)
  Ciklus I=2-től N-ig
    Ha ERTEK<A(I) akkor MAX:=I: ERTEK:=A(I)
  Ciklus vége
Eljárás vége.

Sorozat hozzárendelése sorozathoz
A következőkben áttérünk arra az esetre, amikor az eredmény is egy sorozat. Nem foglalkozunk olyan egyszerű példákkal, amikor a sorozat minden elemén (egymástól függetlenül) egy függvény értékét kell kiszámítani (pl. adjuk meg a sin(x) függvény értékét a [0,5] zárt intervallumban, 0.1 lépésközzel). Ide tartozik az az eset is, amikor a sorozat egyes elemeire más-más függvényt kell alkalmazni.

Kiválogatás
Ebben a feladatban egy N elemű sorozat összes T tulajdonsággal rendelkező elemét kell meghatározni. Gyűjtsük a kiválogatott elemek sorszámait a B( ) vektorban!

Eljárás:
  J:=0
  Ciklus I=1-től N-ig
    Ha A(I) T tulajdonságú akkor J:=J+1: B(J):=I
  Ciklus vége
Eljárás vége.

Sorozat elemeinek permutálása
Ezután olyan algoritmusokkal foglalkozunk, amelyek a sorozat elemeinek valamilyen permutálását végzik. Ilyen permutáció készítése a feladata pl. a rendezéseknek. Lényegük: a kapott adatokat növekvő vagy csökkenő sorrendbe kell rendezni.

A rendezési feladatok megoldásához mindig két elvet használunk: egy adott tulajdonságú permutáció előállítását, valamint az indukációt. Többféle rendezési módszert ismertetünk:

Minimumkiválasztásos rendezés
Állítsunk elő olyan sorozatot, amely az eredeti sorozat elemeiből áll, de a legkisebb elem a legelső helyre került. Az indukciós lépés: a sorozat I.-N. elemeit permutáljuk úgy, hogy közülük a legkisebb kerüljön az I. helyre. Így az első lépésben a helyére kerül a legkisebb, az I. lépésben az I., s ha I értéke N-1 lesz, akkor a feladatot megoldottuk.

Minimumkiválasztásos rendezés(N,A(N)):
  Ciklus I=1-től N-1-ig
    INDEX=I
    Ciklus J=I+1-től N-ig
      Ha A(INDEX)>A(J) akkor INDEX:=J
    Ciklus vége
    Csere(A(INDEX),A(I))
  Ciklus vége
Eljárás vége.

Mivel a tömbváltozók elemeihez való hozzáférés lassabb, célszerű az eddig legkisebb minimum értéket külön változóban tárolni:

Minimumkiválasztásos rendezés(N,A(N)):
  Ciklus I=1-től N-1-ig
    INDEX=I: ERTEK:=A(I)
    Ciklus J=I+1-től N-ig
      Ha ERETEK >A(J) akkor ERTEK:=A(J): INDEX:=J
    Ciklus vége
    A(INDEX):=A(I): A(I):=ERTEK
  Ciklus vége
Eljárás vége.

Buborékos rendezés
Állítsunk elő olyan sorozatot, amely az eredeti sorozat elemeiből áll, de minden szomszédos párt cseréljünk fel az 1. és az N. között, ha eredetileg fordított sorrendben voltak! Így a legnagyobb elem az utolsó helyre kerül. Az indukciós lépés: a sorozat 1.-I. elemeit cseréljük fel az előbbi módszer szerint. Tehát először az N. kerül a helyére, az I. vizsgálatánál az I., s legvégül a 2. (az első ekkor már automatikusan a helyén lesz). Előfordulhat, hogy ez a módszer egy lépésben nem csak a legnagyobbat teszi a helyére, hanem még néhányat a megelőzők közül is. Az utolsó csere helye határozza meg azt, hogy ezek az elemek hányan vannak.

Buborékos rendezés(N,A(N)):
  I:=N
  Ciklus amíg I>1
    CS:=0
    Ciklus J=1-től I-1-ig
      Ha A(J)>A(J+1) akkor Csere(A(J),A(J+1): CS:=J
    Ciklus vége
    I:=CS
  Ciklus vége
Eljárás vége.

Beillesztéses rendezés
Olyan sorozatot állítsunk elő, amely az eredeti sorozat elemeiből áll, de az első két elem sorrendje helyes. Az indukciós lépés: a sorozat elemeit úgy cseréljük fel, hogy az első I elem sorrendje legyen helyes. Így I értékét változtatva 2-től N-ig, a teljes sorozatot rendezzük.

Beillesztés:
  Ciklus I=2-től N-ig
    J:=I-1:X:=A(I)
    Ciklus amíg J>0 és A(J)>X
      A(J+1):=A(J)
      J:=J-1
    Ciklus vége
    A(J+1):=X
  Ciklus vége
Eljárás vége.

Újabb feladatunk nem rendezi sorba a sorozat elemeit, csupán egy részfeladatot végez el, mégis ez az alapja az egyik leggyorsabb rendezési módszernek.

Szétválogatás
Rendelkezésre áll egy N elemű sorozat, valamint egy kijelölt eleme (pl. X=A(1)). Cseréljük fel úgy a sorozat elemeit, hogy az X-nél kisebbek X előtt legyenek, a nála nagyobbak pedig utána.

Eljárás:
  X:=A(1)
  E:=1: U:=N
  Ciklus amíg E<U
    Ciklus amíg E<U és A(U)>=X
      U:=U-1
    Ciklus vége
    Ha E<U akkor
      A(E):=A(U): E:=E+1
      Ciklus amíg E<U és A(E)<=X
        E:=E+1
      Ciklus vlge
      Ha E<U akkor A(U):=A(E): U:=U-1
    Elágazás vége
  Ciklus vége
  A(E):=X
Eljárás vége.

Gondoljuk meg, hogy e szétválogatási eljárás alapján hogyan írhatnánk egy rendező algoritmust! Ebből arra is fény derül, miért oly hatékony e rendezési módszer.

Sorozatokhoz hozzárendelt sorozatok
Egy olyan feladatosztályra térünk át, ahol több sorozatból kell készíteni egy újabb sorozatot. Ezek általában visszavezethetők korábbi feladatokra, néhánnyal mégis érdemes külön is foglalkozni. A legegyszerűbbek közé tartoznak pl. olyanok, amelyek két sorozatból indulnak ki, ezeket halmazoknak tekintik, s valamilyen halmazműveletet végeznek rajtuk (egyesítés, metszet, ....). Ezek általában kiválogatási, eldöntési feladatokra vezethetők vissza.
Bizonyos esetekben kicsit bonyolultabb a helyzet, pl. ha az elemek sorrendje nem lehet tetszőleges.

Összefuttatás
Adottak két rendezett sorozat elemei. Állítsunk elő belőlük egy sorozatot úgy, hogy az eredeti sorozatok minden eleme szerepeljen benne, de amelyek mindkettőben benn voltak, azok csak egyszer, s ez a sorozat is rendezett legyen! (Például növekvő sorrendű sorozatokat vizsgálunk.)
A két sorozat: A(N), B(M). Az eredmény C(N+M).

Eljárás:
  I:=1: J:=1: K:=0
  Ciklus amíg I<=N és J<=M
    K:=K+1
    Elágazás
      A(I)<B(J) esetén C(K):=A(I): I:=I+1
      A(I)=B(J) esetén C(K):=A(I): I:=I+1: J:=J+1
      A(I)>B(J) esetén C(K):=B(J): J:=J+1
    Elágazás vége
  Ciklus vége
  Ciklus amíg I<=N
    K:=K+1
    C(K):=A(I): I:=I+1
  Ciklus vége
  Ciklus amíg J<=M
    K:=K+1
    C(K):=B(J): J:=J+1
  Ciklus vége
Eljárás vége.

Visszalépéses keresés (backtrack)
Az utolsó feladattal a problémamegoldás egy igen széles területén alkalmazható algoritmust mutatunk be, amelynek lényege a feladat megoldásának megközelítése rendszeres próbálgatásokkal. Sok esetben ennél jobb módszert nem is követhetünk! A következőkben az általános algoritmusát adjuk meg. Célszerű azonban megértéséhez egy konkrét feladattal párhuzamba állítva is meggondolni. Legyen pl. ez a klasszikus 8 vezér probléma!
Adott N sorozat, amelyek rendre M(1), M(2), ... elemszámúak. Ki kell választani mindegyikből egy-egy elemet úgy, hogy egyes sorozatokból való választások másokat befolyásolnak (pl. nem lehet két sorozatból azonos sorszámú elemet választani). Tulajdonképpen ez egy bonyolult keresési feladat: egy adott tulajdonsággal rendelkező szám N-est kell keresni. A megoldást úgy készítjük el, hogy ne kelljen az összes lehetőséget végignézni!

Először megpróbálunk az első sorozatból választani egy elemet, ezután a következőből, s ezt mindaddig csináljuk, amíg a választás lehetséges. Amikor áttérünk a következő sorozatra, akkor jeleznünk kell, hogy ebből még nem próbáltunk elemet választani. X(I) jelöli az I. sorozat kiválasztott eleme sorszámát, ha még nem választottunk, akkor értéke 0 lesz. Ha nincs jó választás, akkor visszalépünk az előző sorozathoz, s megpróbálunk abból egy másik elemet választani. Ez az egész eljárás vagy úgy ér véget, hogy minden soro-zatból sikerült választani (ekkor megkaptuk a megoldást), vagy pedig úgy, hogy a visszalépések sokasága után már az első sorozatból sem lehet újabb elemet választani (ekkor a feladatnak nincs megoldása).
A megoldás - mint a korábbi tételeknél láttuk - egyszerűbbé válik, ha tudjuk, hogy van megfelelő tulajdonságú elemsorozat. Most azonban kövessük az általános eset megoldását!

Eljárás:
  I:=1
  Ciklus amíg I>=1 és I<=N
    Ha VAN_JO_ESET(I) akkor I:=I+1: X(I):=0
    különben I:=I-1
  Ciklus vége
  VAN_E:=I>N
Eljárás vége.

Az I. sorozatból úgy választunk elemet, hogy próbálunk mindaddig új elemet venni, amíg egyáltalán van további elem, és az éppen vizsgáltat nem lehet választani. Ha a keresgélés közben a sorozat elemei nem fogytak el, akkor az előző szintnek válaszolhatjuk azt, hogy sikeres volt a választás. Ha pedig az utolsó sem felelt meg, akkor azt, hogy vissza kell lépni az előző sorozathoz.

VAN_JO_ESET(I):
  Ciklus
    X(I):=X(I)+1
  amíg X(I)<=M(I) és ROSSZ_ESET(I,X(I))
  Ciklus vége
  VAN_JO_ESET:=X(I)<=M(I)
Eljárás vége.

Rossz választásnak nevezzük azt, amelyet a korábbi választások közül valamelyik megakadályoz. (Például a következő 8 vezér feladatban egy vezért nem tehetünk olyan helyre, ahol a korábban elhelyezett vezérek ütnék.)

ROSSZ_ESET(I,X(I)):
  J:=1
  Ciklus amíg J<I és (J,X(J)) nem zárja ki (I,X(I))-t
    J:=J+1
  Ciklus vége
  ROSSZ_ESET:=J<1
Eljárás vége.

Megjegyzés: A backtrack algoritmusra alapozva a keresési feladatokhoz hasonlóan el lehet készíteni eldöntési, kiválasztási, megszámolási, kiválogatási feladatok megoldását, sőt még a valamilyen szempontból legjobb megoldás elkészítését is.

Készítsünk algoritmust, amely elhelyez egy sakktáblán 8 vezért úgy, hogy egyik sem üti a másikat!
Megfeleltetés:
N = 8;
sorozatok: az egyes vezérek lehetséges elhelyezései;
M(1)=M(2)=...=N
(J,X(J)) nem zárja ki (I,X(I))-t: X(I)<>X(J) és ABS(X(I)-X(J))<>I-J
(azaz a J. vezér nincs egy sorban vagy átlóban az I. vezérrel)
A megoldás:

8 vezér elhelyezése:
  I:=1
  Ciklus amíg I>=1 és I<=N
    Ha VAN_JO_ESET(I) akkor I:=I+1: X(I):=0
    különben I:=I-1
  Ciklus vége
  VAN_E:=I>N
Eljárás vége

VAN_JO_ESET(I):
  Ciklus
    X(I):=X(I)+1
  amíg X(I)<=N és ROSSZ_ESET(I,X(I))
  Ciklus vége
  VAN_JO_ESET:=X(I)<=N
Eljárás vége.

ROSSZ_ESET(I,X(I)):
  J:=1
  Ciklus amíg J<I és X(I)<>X(J) és ABS(X(I)-X(J))<>I-J
    J:=J+1
  Ciklus vége
Eljárás vége.

Példa a módszeres programozásra
(a tételek alkalmazhatósága)

Feladat: Írjuk ki a 2 és N közötti összes prímszámokat!
A feladat megoldására próbáljuk alkalmazni az előző fejezetben megismert programozási tételeket! A legfelső szint egy kiválogatási feladat, hiszen egy számhalmaz valamilyen tulajdonságú elemeit kell megadnunk. A számhalmaz elemei közvetlenül meghatározhatók, így csupán a legnagyobb elem értékére van szükségünk, így a megoldás legfelső szintje a következő lesz:

Program:
  Be: N [N>2 egész]
  Ciklus I=2-től N-ig
    Ha Prímszám(I) akkor Ki: I
  Ciklus vége
Program vége.

A megoldandó részfeladat: Egy számról el kell döntenünk, hogy prim-e! Fogalmazzuk át a feladatot: el kell döntenünk, hogy az I számnak 2 és 1/2 között van-e osztója!
Ez most egy eldöntési feladat, így megoldása:

Prímszám(i):
  J:=2
  Ciklus amíg J<=I/2 és J nem osztója I-nek
    J:=J+1
  Ciklus vége
  Prímszám:=J>I/2
Eljárás vége.

Már készen is vagyunk a feladat megoldásával. El kell ismernünk, hogy ez bizony nem a lehető legoptimálisabb megoldás. A legkézenfekvőbb módosítás, a ciklusfeltételben szereplő I/2-t - matematikai ismereteink alapján - ki kell cserélni I gyökére. (A hatékonysággal egyébként még egy későbbi fejezetben foglalkozunk.)
Az így kapott megoldást kódolva az alábbi programhoz jutunk:

PROGRAM "Prim1.bas"
INPUT PROMPT "Meddig kered a primszamokat: ":N
FOR I=2 TO N
  IF PRIM(I) THEN PRINT I;
NEXT
END
DEF PRIM(I)
  LET J=2:LET SQ=SQR(I)
  DO WHILE J<=SQ AND MOD(I,J)<>0
    LET J=J+1
  LOOP
  LET PRIM=J>SQ
END DEF

Próbáljunk egy másik megoldást készíteni! Bár a programozási tételek sokat segítenek a feladatok megoldásában, ne feledkezzünk meg a józan észről sem! Most is a feladat átfogalmazásával láthatjuk meg, hogyan lehet újabb megoldást találni.
Vegyük a 2 és N közötti összes számot! Hagyjuk el közülük azokat, amelyek nem prímek, majd írjuk ki a maradékot! Olyan halmazt kell ábrázolnunk, amelynek elemeit nem tudjuk egyszerűen meghatározni (a legvégén a prímszámok maradnak benne). Így tárolásához egy vektort használunk, ennek nem 0 értékű elemei tartoznak a halmazhoz.

Program:
  Be: N [N>2 egész]
  Ciklus I=2-től N-ig
    A(I):=I [a vektor feltöltése]
  Ciklus vége
  Nem prímek elhagyása
  Ciklus I=2-től N-ig
    Ha A(I)>0 akkor Ki: I [prímek kiírása]
  Ciklus vége
Program vége.

A nem prímszámok halmazát osszuk fel részekre: ilyenek a 2-vel osztható számok a 2 kivételével, a 3-mal oszthatók a 3 kivételével, stb. A megoldás ezt a felosztást foga követni: először a 2-vel oszthatóakat hagyjuk el...

Nem prímek elhagyása:
  Ciklus J=2-től N/2-ig
    A J-vel osztható számok elhagyása
  Ciklus vége
Eljárás vége.

A J-vel oszthatók elhagyása egy kiválogatási feladat. Gyorsabb megoldás azonban, ha kiszámoljuk, hogy melyik szám az első J-vel osztható, s mindegyik után megadjuk a következőt is:

A J-vel osztható számok elhagyása:
  Ha A(J)>0 akkor
    Ciklus K=2*J-től N-ig J-esével
      A(K):=0
    Ciklus vége
  Elágazás vége
Eljárás vége.

A megoldás kódolva:

PROGRAM "Prim2.bas"
INPUT PROMPT "Meddig kered a primszamokat: ":N
NUMERIC A(2 TO N)
FOR I=2 TO N
  LET A(I)=I
NEXT
CALL PRIMEK
FOR I=2 TO N
  IF A(I)>0 THEN PRINT I;
NEXT
DEF PRIMEK
  FOR J=2 TO N/2
    IF A(J)>0 THEN
      FOR K=2*J TO N STEP J
        LET A(K)=0
      NEXT
    END IF
  NEXT
END DEF

Ez volt az Eratosztenészi szita módszere.

A program helyessége

A programírás körüli bonyodalmakkal összemérhető nagyságrendű az elkészült program helyességének vizsgálata. Sőt ezen a területen olykor nagy a zűrzavar, sokan hajlamosak ezeket a kérdéseket félvállról venni.
Egy program helyességéről csak akkor beszélhetünk, ha valamilyen módszerrel meggyőződtünk róla. A program helyességének belátásához a következő módszerek használatosak:

  1. Programigazolás (vagy tesztelés): próbafeladatok lefuttatásával a program megbízhatóságát vizsgáljuk. Itt a programhiba felfedezése a cél.
  2. Programérvényesítés: a feladatmeghatározás alapján a program logikai helyességének igazolása valódi környezetben. Tehát gyakorlati feladatokra használjuk a programot.
    A cél annak belátása, hogy megoldásukra a program alkalmas-e.
  3. Programhitelesítés: a program helyességének és a feladatmeghatározás előírásainak jóváhagyása a hosszú idő alatt összegyűlt futtatási tapasztalatok alapján.
  4. Hibakeresés: az előző módszerek egyikével megtalált hiba helyének, okának a megtalálása.
  5. Programhelyesség-bizonyítás: a program logikai helyességének kimutatása axiómák, következtetési szabályok segítségével, a feladatmeghatározás alapján.

Az előbbiekből három módszerrel részletesen foglalkozunk, a másik kettőre csak néhány gondolattal utalunk. Éspedig:
A programérvényesítés a programnak egy vagy néhány gyakorlati feladatra való alkalmazását jelenti. Ennek során a feladat kitűzője meggyőződhet arról, hogy a program teljesíti-e elvárásait. Ebbe beletartoznak a helyesség, a hatékonyság, a formai szempontok és egyéb követelmények.
A programhitelesítés lényege a program végleges formában való rögzítése. A használat során szerzett tapasztalatok alapján pontosítható a megoldott feladatok köre, a kezelés,
a program által nyújtott szolgáltatások, az alkalmazás környezeti feltételei stb.

Tesztelés

A tesztelés célja, hogy minél több hibát megtaláljunk a programban. Ahhoz, hogy az összes hibát megtaláljuk, nem kell próbát tenni az összes lehetséges bemenő adattal. Ez nyilvánvalóan fölösleges és a legtöbb programnál - a lehetséges bemeneti adatok nagy száma miatt - lehetetlen is.Természetesen az a célunk, hogy a tesztelést olyan módszerrel hajtsuk végre, amellyel a próbák száma erősen lecsökkenthető. Tesztesetnek a be- és kimenő adatok és feltételek együttes megadását nevezzük. Fogalmazzuk meg a tesztelés alapelveit:

  1. A jó teszteset az, ami várhatóan egy még felfedezetlen hibát mutat ki a programban. Például két szám legnagyobb közös osztóját számoló programot az [5,5] adatpár után a [6,6]-tal teljesen felesleges kipróbálni.
  2. A teszteset nemcsak bemenő adatokból, hanem a hozzájuk tartozó eredményekből is áll. Egyébként nem tudnánk a kapott eredmény helyes vagy hibás voltáról beszélni. A későbbi felhasználás alatt célszerű a teszteseteket is leírni.
  3. A meg nem ismételhető tesztesetek kerülendők, feleslegesen megnövelik a programtesztelés költségeit, idejét. Nem is beszélve arról a bosszúságról, amikor a programunk egy hibás futását nem tudjuk megismételni, s így a hiba is felfedetlen marad.
  4. Teszteseteket mind az érvénytelen, mind az érvényes adatokra kell készíteni.
  5. Minden tesztesetből a lehető legtöbbet kell hasznosítani, azaz minden teszteset eredményét alaposan végig kell vizsgálni. Ezzel jelentősen csökkenthető a szükséges próbák száma.
  6. Egy próba eredményeinek vizsgálata során egyaránt fontos megállapítani, hogy miért nem valósít meg a program valamilyen funkciót, amit elvárunk tőle, ill., hogy miért végez olyan tevékenységeket is, amelyeket nem feltételeztünk róla.
  7. A program tesztelését csak a program írójától különböző személy tudja hatékonyan ellátni. A tesztelés ugyanis nem egy jóindulatú tevékenység. Saját munkáját pedig mindenki jónak feltételezi.

A programtesztelés módszereit két csoportba oszthatjuk aszerint, hogy a tesztelés során végrehajtjuk-e a programot vagy nem. Ha csak a program kódját vizsgáljuk, akkor statikus, ha a programot végre is hajtjuk a tesztelés során, akkor dinamikus tesztelésről beszélünk.

Statikus Tesztelési Módszerek

1. Kódellenőrzés
A kódellenőrzés a program szövegének megvizsgálását jelenti. Az algoritmus logikáját kell ekkor a programban végigkövetni, és megfigyelni, hogy a kettő egyező-e. Csupán a kód alapján is viszonylag könnyen tud hibákat felfedezni egy kívülálló. Sokszor a programozó maga veszi észre a hibákat, miközben valakinek részletesen magyarázza.

2. Formai ellenőrzés, kereszthivatkozási táblázatok készítése
Egy programban az előforduló hibákat két csoportra oszthatjuk: formai (szintaktikai), ill. tartalmi (szemantikai) jellegű hibákra. Például az ABC80-as, Sinclair Spectrum, Enterprise számítógépek a formai ellenőrzést a sor beírásakor elvégzik, s ha hibát találnak, akkor ezt jelzik, és a beírt sort nem fogadják el. A HT-1080Z vagy a Commodore számítógépek esetén nem beíráskor történik meg ez az ellenőrzés, hanem csak a program végrehajtása közben. Ekkor a formai ellenőrzést megfelelően választott tesztadatokkal való kipróbálással lehet elérni. A program minden utasítását végre kell hajtani legalább egyszer. Igen sok információt ad egy programról, ha különböző kereszt-hivatkozási táblázatot készítünk róla (keresztreferencia). Ennek egyik típusa a változókról készült táblázat, amelynek felépítése pl. a következő lehet:

Változónév Típus Sorszámlista

A sorszámlistában azok a sorok szerepelnek, amelyekben az adott változó előfordul. A sorszám előtt speciális jellel jelölhetjük, hogy a változó értéket kapott az adott sorban.
Természetesen kézzel készíteni ilyen táblázatot nagyon munkaigényes feladat, megfelelő segédprogrammal azonban a számítógép biztosíthatja automatikusan ezt a lehetőséget.

3. Tartalmi ellenőrzés, ellentmondás-keresés
A formai hibáknál sokkal nehezebb felfedni a programban a tartalmi hibákat. Ilyen hiba lehet az, hogy egy változónak értéket adunk, de ezután nem használjuk semmire, vagy közvetlenül utána még egyszer értéket kap.
Ellentmondás kereséssel a program vezérlési folyamában is fedezhetünk fel hibákat. Például egy utasításhoz a program soha nem jut el egy vezérlési szerkezetekben hibásan megválasztott feltételvizsgálat miatt.

Dinamikus tesztelési módszerek

Az előző részben a statikus tesztelési módszereket vizsgáltuk, ahol a tesztelést a program végrehajtása nélkül, a program szövegének vizsgálatával végeztük. A dinamikus tesztelési módszerek alapelve éppen az, hogy a programot működés közben vizsgáljuk. Teszteseteket kétféle módon tudunk választani. Egy lehetőség az ún. fekete doboz módszer, más néven adatvezérelt tesztelés. E módszer alkalmazásakor a tesztelő nem veszi figyelembe a program belső szerkezetét, pontosabban nem azt tekinti elsődleges szempontnak, hanem a teszteseteket a feladatmeghatározás alapján választja meg.
A cél természetesen a lehető leghatékonyabb tesztelés elvégzése, azaz az összes hiba megtalálása a programban. Ez ugyan elvileg lehetséges, ha a programot az összes lehetséges bemenő adatra kipróbáljuk (kimerítő bemenet tesztelés). Ezzel a módszerrel azonban, mint korábban láttuk, mennyiségi akadályok merülnek fel.
Egy másik lehetőség a fehér doboz módszer (logikavezérelt tesztelés). Ebben a módszerben a tesztesetek megválasztásánál lehetőség van a program belső szerkezetének figyelembevételére is.
A cél a program minél alaposabb tesztelése. Erre jó módszer a programban az összes lehetséges utat, azaz tesztesetet végigjárni, amennyiben ez megtehető (kimerítő út tesztelés). Ám még viszonylag kis programok esetén is igen nagy lehet a tesztelési utak száma. Gondoljunk a ciklusokra! Sőt ezzel a módszerrel a hiányzó utakat nem lehet felderíteni.
Mivel sem a fehér doboz módszerrel, sem a fekete doboz módszerrel nem lehetséges a kimerítő tesztelés, el kell fogadnunk, hogy nem tudjuk egyetlen program hibamentességét sem szavatolni. A további cél ezek után az összes lehetséges teszteset halmazából a lehető leghatékonyabb tesztesetcsoport kiválasztása lehet.

Fekete doboz módszerek

1. Ekvivalenciaosztályok keresése
A tesztelés alapelveinek ismertetésénél jó tesztesetnek neveztük azt, amelyre minél nagyobb valószínűséggel áll, hogy hibát találunk vele a programban. Másrészt megállapítottuk, hogy a kimerítő bemeneti tesztelés gyakorlatilag megvalósíthatatlan, így meg kell elégednünk a bemenő adatok egy szűk részhalmazával való teszteléssel. Ezek után azért, hogy ez a részhalmaz minél hatásosabb legyen, a benne szereplő tesztesetekre teljesüljenek a következők:

Ezeket az elveket veszi figyelembe az ekvivalenciaosztályok módszere. Megjegyzés: Ekvivalenciaosztályokat nem csak az érvényes, hanem az érvénytelen adatokhoz is létre kell hozni, és a programot azokkal is kipróbálni.
Néhány jó tanács az ekvivalenciaosztályok megtalálásához:

Ha már rendelkezésünkre állnak az ekvivalenciaosztályok, akkor a teszteseteket a következő két elv alapján határozhatjuk meg:

2. Határeset-elemzés
A határeset-elemzés két dologban különbözik az ekvivalenciaosztályok keresésének módszerétől.

Felsorolunk néhány szempontot a határeset-elemzéshez:

Fehér doboz módszerek

1. Utasítások egyszeri lefedésének elve
A módszer lényege olyan tesztesetek kiválasztása, amelyek alapján minden utasítást legalább egyszer végrehajthatunk a programban. Bár ez sokszor jó módszer, de nem tökéletes, nézzük meg ugyanis a következő egyszerű példát:

Ha X>0 akkor Ki: X

Ebben a példában egyetlen próbával elérhetjük az összes utasítás végrehajtását (pl. X=1), de ezzel a próbával nem derülne ki az, ha az X>0 feltétel helyett az X>=0 szerepelne, azaz a program hibás lenne.

2. Döntéslefedés elve
Itt az előzőnél egy kicsit erősebb követelményt alkalmazunk. A programban minden egyes elágazás igaz, illetve hamis ágat legalább egyszer be kell járni a tesztelés során. A döntéslefedés elvét figyelembe véve eleget teszünk az utasításlefedés követelményének is. Itt is maradnak azonban problémák. Nézzünk egy példát:

Ha X>0 vagy Y>0 akkor Ki: X*Y

Ebben az esetben az (X=1, Y=1) és az (X=-1, Y=-1) tesztesetek lefedik a döntéseket, de nem vennénk észre velük azt, ha a második feltételt (Y>0) rosszul írtuk (vagy lehagytuk) volna.

3. A feltétellefedés elve
Ebben az esetben olyan teszteseteket kell készíteni, amelyhez a döntésekben szereplő minden feltételt legalább egyszer hamis, ill. igaz eredménnyel értékelünk ki. Ez a módszer általában hatásosabb az előzőnél, de nem mindig. Például:

Ha X>0 és Y>0 akkor Ki: X*Y

Itt az (X=1, Y=-1) és az (X=- 1, Y=1) tesztadatok elégségesek ezen elv megvalósításához, de az elágazás igaz ágát egyiknél sem hajtjuk végre, s így ez az előző elv követelményét nyilvánvalóan nem teljesíti.

4. A döntés- vagy feltétellefedés elve
Az előző pontban levő példából látható, hogy a feltétellefedés követelményét kielégítő tesztesetek nem feltétlenül elégítik ki a döntéslefedés követelményét. Ezért az előző két elvet egyesítő módszert kell készíteni úgy, hogy mindkét elv érvényesüljön.

Következtetés: Az ismertetett módszerek nem zárják ki egymást, önmagában egyik sem célravezető, így általában együttes használatuk szükséges.
Van a tesztelésnek egy különleges fajtája, amelyet stressz-tesztnek hívnak. Olyan programok esetén alkalmazunk ilyet, amelyek vagy nagy adatmennyiséggel dolgoznak, vagy fontos, hogy feladatukat adott időn belül elvégezzék. (Gondoljunk arra, hogy az adatmennyiség növelésével új minőség állhat elő.) Sokszor előfordul, hogy programok rejtett hibáit csak a valós tesztadatokkal való kipróbálás hozza elő, ezek közül is csak az, amely a gyakorlatban is ritkán fordulhat elő. Tehát a stressz-teszt lényege: próbáljuk ki a programot nagy adatmennyiséggel, ha mód van rá, akkor a felhasználó minél gyakoribb beavatkozásával.

Programhiba-keresés

Az előző fejezetekben a hibafelderítéssel foglalkoztunk, ennek a fejezetnek a tárgya a hiba behatárolása, a hiba kijavítása. E két résztevékenységre vonatkozóan a tesztelés alapelveihez hasonlóan megfogalmazhatunk néhány alapelvet.
A hibakeresés alapelvei:

  1. A hibakeresési eszközök használata előtt célszerű igen alaposan végigvizsgálni a programot, és a program logikája alapján megkeresni a hiba okát. A hibakereső eszközöket csak a program alapos vizsgálata után vegyük igénybe!
  2. Amíg a hiba helyét és okát pontosan nem találtuk meg, addig ne kezdjünk bele a javításba! A programban végzett meggondolatlan javítások újabb hibákat okozhatnak.

A hibajavítás alapelvei:

  1. Ha a programban hibát találunk, akkor ennek a program más részeire is lehet hatása, azaz elképzelhető, hogy újabb hibákat is fogunk találni.
  2. A hibát kell kijavítani és nem csak a tüneteit megszüntetni! Ha nem vizsgáljuk meg elég körültekintően a hiba okát, akkor csak részben tudjuk javítani.
  3. A hibajavítás után a programot alapos tesztnek kell alávetni! Javítás közben új hibák keletkezhetnek!
  4. Annak a valószínűsége, hogy egy hibát jól kijavítottunk, a program méretével arányosan csökken.
  5. A hibák száma és súlyosságuk általában a program méreténél sokkal gyorsabban növekszik.
  6. A hibajavítás visszanyúlhat a program tervezési fázisába is. Nagy programok esetén a programhibák többsége a tervezés során keletkezik.

Programhiba-keresési módszerek

1. Indukciós módszer
(Indukció (Új Magyar Lexikon): Abból a tényből, hogy nagyszámú tárgynak meghatározott tulajdonsága van és közös nemhez tartozik, arra következtetünk, hogy az adott nemhez tartozó összes tárgynak megvan ez az ismertetőjegye.)
A hibakeresést a következőképpen végezzük: kiindulunk a rendelkezésre álló teszteset-eredményekből, majd megpróbáljuk őket rendezni. Azokat a teszteseteket is célszerű megvizsgálni, amelyek nem idézik elő az adott hibát. A rendezett adatokból megpróbálunk valamilyen feltevést tenni a hiba okára vonatkozóan. Ha ezt a feltevést igazolni tudjuk, akkor következhet a hiba kijavítása, egyébként a folyamatot elölről kell kezdeni.

Például:
X=0, 1, 5, 100 esetén a program jól működik;
X=-1, -7, -50 esetén rosszul működik.
Feltevés: a program a negatív számokra működik hibásan.

2. Dedukciós módszer
(Dedukció (Új Magyar Lexikon): Abból az ítéletből, hogy az adott nemhez tartozó összes tárgy meghatározott ismertetőjeggyel rendelkezik, arra következtetünk, hogy bizonyos, az adott nemhez tartozó tárgyak szintén rendelkeznek a szóban forgó ismertetőjeggyel.)
A módszer lényege az, hogy egyre szűkíti a hiba lehetséges okainak körét. A meglevő teszteset-eredményekből adódó mindenféle lehetséges okot fel kell tételezni az első lépésben, majd ezek közül ki kell küszöbölni azokat, amelyek a részletesebb vizsgálat során nem állják meg a helyüket. Ha élünk egy feltevéssel, ugyanúgy igazolnunk kell, mint az előző módszer esetén. Ha nem sikerül, akkor újabb információkat kell gyűjtenünk a hibakereséshez a hibajelenségről.

Például:
Feltevés: a program mindig rosszul működik.
Teszt: X=3,5,7 esetén rossz eredmény;
X=12, 20 esetén jó eredmény.

Feltevések:

Amelyik feltevés igaz, az az által kijelölt halmaz (ekvivalenciaosztály) minden egyes tagjára rosszul fog működni a program.

Ez a két módszer elsősorban az algoritmusbeli hibák keresésére jó, a következő pedig a BASIC program vizsgálatához nyújt segítséget.

3. Visszalépéses technika
A legismertebb hibakeresési módszer, amelyet úgy végzünk el, hogy kiindulunk a hiba előfordulásának helyéről és a programot visszafelé hajtjuk mindaddig, amíg a végrehajtás eredményét hibásnak találjuk. Ha elérkeztünk egy olyan ponthoz a programban, ahol a hibás eredmények után helyes eredményeket kapunk, akkor valószínűleg megtaláltuk a hiba forrását.

4. Teszteléssel segített hibakeresés
A teszteseteket megkülönböztethetjük aszerint, hogy hibát akarunk felfedezni, vagy pedig egy ismert hibát akarunk előidézni a programban (a hiba okát keresve). Az utóbbi típusú tesztesetek szolgálnak hibakeresésre (emlékeztetünk a tesztesetek megismételhetőségére). Ezeknek a teszteseteknek jellegzetessége, hogy csak egyetlen feltételt fednek le.
Ezt a módszert általában nem önállóan, hanem az előző három módszer segítésére használjuk.

Hibakeresési eszközök
A legegyszerűbb eszköz - amely minden személyi számítógépen rendelkezésre áll - a programban elhelyezett alkalmas kiíró utasítások, amelyek segítségével nyomon követhetjük programunk működését. Más hasznos eszközök már sajnos nem minden esetben találhatók meg az egyes géptípusokon.

Nyomkövetés
A nyomkövetés lehetővé teszi, hogy megfigyeljük, programunk milyen utasításokat hajtott végre. A BASIC-ek - így az IS-BASIC is - általában azt a lehetőséget adják, hogy a végrehajtott utasítások sorszámait kiírathatjuk a képernyőre. Erre a célra a TRACE ON parancs szolgál, a nyomkövetés kikapcsolását pedig a TRACE OFF paranccsal érhetjük el. Ezek az alapszavak magába a programba is elhelyezhetők, így a program egy részét is nyomon lehet követni. Lehetőség van a TRACE parancs kimenetét tetszőleges videólapra irányítani (TRACE ON TO £csat), így a program által megjelenített képet sem kuszálja össze.

Nyomkövetés a hibától visszafelé
A BASIC nyelvjárások túlnyomó többségében sajnos nincs meg ez a lehetőség, ami lehetővé teszi, hogy hiba esetén megkapjuk az utoljára végrehajtott néhány utasítás sorszámát és egyéb jellemzőit. Az IS-BASIC a hibát okozó sort jeleníti meg.

Lépésenkénti végrehajtás
Ez inkább a gépi kódú programozáshoz használható segédeszköz, egy-egy utasítás végrehajtása után mindig a felhasználó dönthet a következő feladat kiválasztásáról.

Töréspontok elhelyezése
Néhány BASIC változatban - így az IS-BASIC-ben is - lehetőség van STOP utasítások elhelyezésére a programban. Ezeknél a végrehajtás megszakad, a változók értékei kiírathatok, megváltoztathatók, majd a CONTINUE paranccsal folytatható a program. Sajnos vannak olyan géptípusok, ahol a megszakított program nem folytatható, tehát ez a lehetőség nem használható. Fejlettebb rendszerekben megadható a törésponton való áthaladások száma, ami után megszakad a program végrehajtása.

Helyességbizonyítás

A teszteléssel csak annyit tudunk kimutatni, hogy a program hibás, avagy, hogy a hiba nem került felszínre. Megnyugtatóan a programhelyesség-bizonyítással lehet a program jóságáról meggyőződni.
Egy feladat felől fogjuk e problémát megközelíteni, amelyhez megadjuk a programot, s bebizonyítjuk, hogy ez helyes megoldása a feladatnak. Legyen a feladat egy N elemű A( ) vektor maximális és minimális elemének (helyének, indexének) a megkeresése. Ennek egy megoldása lehet a következő programrészlet:

Eljárás Max-Min(A(),N):
  MAX:=A(1): MIN:=A(1): MAXH=1: MINH:=1
  Ciklus I=2-től N-ig
    Elágazás
      MAX<A(I) esetén MAX:=A(I): MAXH:=I
      MIN>A(I) esetén MIN:=A(I): MINH:=I
    Elégazás vége
  Ciklus vége
  Ki: MAXH;MAX,MINH;MIN
Eljárás vége.

IS-BASIC:

...
LET MAX,MIN=A(1):LET MAXH,MINH=1
FOR I=2 TO N
  IF MAX<A(I) THEN LET MAX=A(I):LET MAXH=I
  IF MIN>A(I) THEN LET MIN=A(I):LET MINH=I
NEXT
PRINT MAXH;MAX,MINH;MIN

Lássuk be a program helyességét! Egyáltalán hogyan fogjunk neki? Próbáljunk elvárásainknak megfelelő állításokat beilleszteni a programba, majd ezek teljesülését ellenőrizni. Ha ezen a kétségkívül nehéz, sok megérzést igénylő munkán túl vagyunk, akkor már csak ezen állítások egymásba való átalakulását kell kimutatni. Az átalakulást maguk az állítások közötti programrészek biztosítják.
Hogy milyen legyen az állítás? Hogyan találhatók az egyes szerkezethez legjobban simuló formulák? Mik ezek jellegzetes, egyedi - de mégis eléggé általános - sajátosságai? Ezekre a kérdésekre keressük a választ az előbbi program elemzése során.

Eljárás Max-Min(A(),N):
  [ E ]
  MAX:=A(1): MIN:=A(1): MAXH=1: MINH:=1
  [ p1 ]
  Ciklus I=2-től N-ig
    [ p2 ]
    Elágazás
      MAX<A(I) esetén MAX:=A(I): MAXH:=I
      MIN>A(I) esetén MIN:=A(I): MINH:=I
    Elégazás vége
  [ p3 ]
  Ciklus vége
  [ p4 ]
  Ki: MAXH;MAX,MINH;MIN
  [ U ]
Eljárás vége.

Az eljárást megtűzdeljük állításokkal. Egyelőre csak helyük rögzített. Hogy miért éppen ezeket a helyeket jelöljük ki, miért éppen ezeket tekintjük kritikus helyeknek, erre később még visszatérünk, addig is érdemes ezen eltöprengeni.

Az állítások társas kapcsolatai
Kezdjük azzal az elfajult esettel, hogy egyetlen elem közül kell a legkisebbet és a legnagyobbat kiválasztani. (Bár a feladat így leegyszerűsítve önmagában valószínűtlen, hogy valaha is előforduljon - erre ugyanis senki nem használ számítógépet -, egy nagy feladat részeként már nem elképzelhetetlen.) Ekkor a ciklus végrehajtására nincs szükség, így

a 'p1 és N=1'-ből következzen a 'p4'.

A ciklusba való belépéskor elvárjuk - a folytonosság miatt -, hogy

a 'p1 és N>1 és I=2'-ből következzen a 'p2'.

A ciklus többszöri lefutásához elengedhetetlenül szükséges folytonosság biztosítását kívánja meg a ciklusmagot alkotó utasításoktól a következő állításazonosság:

'p3(i)' = 'p2(i+1)' (I=2,...,N-1)

(az egyszerűbb írásmód kedvéért bevezettük és később is alkalmazzuk az állítások függvényszerű írását; pl. a p3(i) jelentése: a p3 a ciklusváltozó i értéke mellett).
Másként ezt így is megfogalmazhatjuk:

a 'p3 és I<N'-ből következzen a 'p2'.

Végül a ciklusból kilépve is igaznak kell lennie a p4-ben megfogalmazott állításnak. Formálisan:

a 'p3 és I=N'-ből következzen a 'p4'.

Bizonyításunk logikai vázát megadtuk. Most már csak pontos kivitelezése marad hátra és beláthatjuk (sőt bebizonyíthatjuk) a program helyességét vagy helytelenségét.

A bizonyítás
Induljunk ki a programtól elvárt tulajdonságból (az eljárás utófeltételéből):

U = MAX>=A(j)   (J=1..N) és A(MAXH)=MAX és
      MIN<=A(j)    (J=1..N) és A(MINH)=MIN.

A kiírás során a program állapotterében nem történik változás (Az állapottér egy képzeletbeli sokdimenziós tér, amelyben a program "mozog" a végrehajtott utasításai segítségével. Az állapottér egy-egy dimenzióját alkotja a program egy-egy változója. Így a változók pillanatnyi értékei határozzák meg, hogy a program az állapottér éppen melyik pontjában tartózkodik.), így

p4 = U.

A ciklusban p3-t úgy kell megfogalmazni, hogy az változatlanul igaz (invariáns) maradjon a ciklus akárhányszori lefutása után is. Hiszen csak így remélhetjük, hogy a ciklus egyszeri végiggondolásával is következtetni tudjunk a hatására bekövetkezett megváltozásra. Tehát pl. igaz legyen a ciklusba való belépés pillanatában, ill. onnan kilépve is. Egy ilyen mindig igaz állítás (legalábbis elvárásaink szerint) maga a p3:

p3 = MAX>=A(j)   (J=1..I) és A(MAXH)=MAX és
        MIN<=A(j)   (J=1..I) és A(MINH)=MIN.

azaz az éppen érvényes I-ig rendelkezünk a legnagyobb és legkisebb értékkel (MAX.MIN), s ezek helyével (MAXH, MINH).
Ekkor nyilvánvaló, hogy ha a ciklus lejár, vagyis, ha I=N, akkor p3 éppen a kívánt p4 állításba megy át:

p3 és I=N=p4.

A ciklusból kilépve az állítástranszformáció tehát folytonos. Kérdés, hogy az algoritmus e folytonosságot biztosítja-e a ciklus egyszeri lefutása során is? Ez jelentené az állítás állandóságát, invariáns voltát. E kérdés megválaszolásához p2-ről kell többet tudnunk!
A p2 és p3 között egy elágazás van, tehát e tényt kell p2 felépítéséhez megfognunk, Írjuk föl az elágazásbeli három (!) esetet úgy, hogy p3 következzék belőle! Ha a végrehajtás során a MIN:=A(I): MINH:=I. utasításokat végrehajtva jutottunk a p3-hoz rögzített ponthoz, akkor p4 csak úgy maradhat igaz, ha 'A<A(j)   (j=1...I-1)'. Vagyis p3 igazsága fenntartható, ha az utasításokat a 'MIN>A(j)' feltétel teljesüléséhez kötjük. Ezt tettük az elágazás megfelelő feltételével! Hasonló megfontolásokkal látható be az elágazás másik ága. Ha ''A(j)' a jelenlegi MAX és MIN értékek közé esik (ez a 3. eset), akkor az elágazás p3-at nem módosítja, így állandóságát (invarianciáját) nem bántja.
Nos, az elágazással az 'A(1),...,A(I-1),A(j)' halmaz minimumát, ill. maximumát a MIN, MAX, MINH, MAXH változókban állítottuk elő. p2-re a ciklusváltozó eggyel való megnövekedése miatt az adódik, hogy az 'A(1),...,A(I-1)' halmaz minimumát, maximumát tartalmazzák az előbbi változók. Más szóval

P2(I)=p3(I-1).

Az elágazásra vonatkozó következtetéseinket foglalja össze a következő három állítás:

p3(I-1) és MIN>A(I) => p3(I), és
p3(I-1) és MAX<A(I) => p3(I), és
p3(I-1) és MIN<A(I) <=MAX =>p3(I).

Megnyugtató eredmény:

P3(I-1)=>P3(I).

Tehát azt beláttuk, hogy az utófeltétel teljesülni fog, feltéve, hogy a ciklusból egyszer kilépünk. (A ciklusból való kilépést a szakmai nyelv a ciklus terminálásaként említi.) E probléma persze az ilyen számlálásos ciklusoknál normális esetben nemigen merülhet föl (Nem normálisnak tekintjük a véges pontosságból és az aritmetikai műveletek pontatlanságából származó kisiklásokat, amik nem is olyan ritkán fordulnak elő. Ám ez nem az algoritmus logikai hibája.) mégis érdemes meggondolni, hogy miként látható be - általában is - a terminálás. A kilépés feltételéhez való határozott közeledést kell ügyesen detektálnunk! Például, ha találunk egy, a ciklusra jellemző adattól függő függvényt, amely értéke a ciklus minden egyes lefutása során csökken, és véges lépés során szükségképpen eléri a 0-t, akkor máris célhoz értünk. A konkrét számlálásos ciklusra a c(I):=N-I függvény ilyen.

Terminálás: c(I)=c(I- 1)- 1 és c(I)>=0.

Ahhoz, hogy a ciklus a p3-t ne változtassa, p3-nak belépéskor is igaznak kell lennie. Vizsgáljuk meg, milyen p1-ből következik p3! Vegyük p3-hoz az 'I=1' feltételt! Ezt sugallja, hogy a ciklust I=2-től indítjuk.

p1 = p3 és I = 1.

Ezt a korábbi jelölésünkkel így írhatjuk:

p1 = MAX>=A(j)   (J=1..1) és A(MAXH)=MAX és
        MIN<=A(j)    (J=1..1) és A(MINH)=MIN.

egyszerűbben írva:

p1 = MAX>=A(1)   és A(MAXH)=MAX és
        MIN<=A(1)   és A(MINH)=MIN.

Az E-re visszakövetkeztetni már nem jelent nehézséget, hiszen épp a p1 - előző kívánalmak szerinti - beállítását végzi az első két utasítás. Így E-re megkötésünk nincs, vagyis

E = igaz.

Ha szigorúan vesszük a bizonyítást, az E azononsan igaz volta helyett a bemenő adatok tulajdonságaira vonatkozó állítást kellett volna kapjuk. (E=az N természetes szám, a vizsgált A(1),...,A(N) vektorelemek valós számok.) Mivel a bizonyítás során nem tekintettük ezek teljesülését kétségesnek, ezért nem bukkant föl egyik állításunkban sem.
Képzeljük el ezt a módszert komolyabb méretű programok esetén! Sajnos gyakorlatilag járhatatlan az út és valljuk be, túlságosan mesterkéltnek, természetellenesnek is tűnik! Mégsem lehet lemondani a program helyességének belátásáról. Megoldásként egyetlen lehetőség marad - egyszer már segített, hátha most is hasznos lesz -: követni azt az elvet, amely már programozási vezérfonalunk is volt: a lépésenkénti finomítást. Nem elképzel-hetetlen, hogy eredményre vezet, hiszen úgyis pontosan megadtuk az eljárásokat, azaz az általuk megvalósított transzformációkat, vagyis az elő- (E) és utófeltételt (U).
Bizonyítandó tehát csak a következő állítás lesz:

E Program U,

(azaz az E-nek eleget tevő bemeneti paraméterek esetén a program kimeneti paraméterei U-beliek lesznek és befejeződik), ha

Program: Program1[P1] ... Programn [Pn],

(vagyis a programot elemibb eljárásokból állítottuk össze).
Meggondolandó részállítások:

E       Program1   P1
...
Pn-1   Programn-1   Pn
        Pn=>U.

E részállítások bizonyítására a megfelelő (rész)program további kifejtése után nyílik lehetőség. Mindenesetre az elkészült program helyessége máris bizonyítható e részállítások helyességéből kiindulva, sőt bizonyítani is kell. Egy fontos szemléletről van szó: a program bizonyítását már az egyes szintek megírásával párhuzamosan kell elvégezni.
A 'p' feltételek nemcsak a program egyedi transzformációt írják le, hanem az összes korábbi eredményt is tartalmazzák.
Nem mindig kell egyébként a részállítások bizonyításához az előfeltétel szigorú alakját felhasználni, néha elegendő annak egy gyengített változata is. Ezzel többnyire egyszerűbb alakú feltételhez jutunk, vagy a bizonyításhoz alkalmasabb formulát kapunk.

Megjegyzések:

Példa a módszeres programozásra
(Programok összehasonlíthatóságáról)

Gyakran kell olyan jellegű feladatot megoldani, ahol a megoldás jelentősen befolyásolhatja a program hatékonyságát.

Feladat: Adott egy N elemű T táblázat, amelynek: elemeit K hellyel kell ciklikusan balra léptetni (K<N).
Ezt a részfeladatot egy titkosírás megfejtéséhez készítettük, amelyet egy kódtáblázat alapján működik. A táblázat egy eleme megmutatja, hogy egy betűt milyen másik betűvel kell helyettesíteni, a táblázat I. eleme az ábécé I. betűje helyére írt betűt tartal-mazza. Ez a titkosírás hosszú szövegek esetén viszonylag könnyen megfejthető az egyes betűk előfordulásának gyakorisága alapján. Tudjuk pl., hogy a magyar nyelvben az "a" a leggyakoribb betű. Ha úgy módosítjuk a titkosírást, hogy minden sor vagy akár minden betű más kódtáblázat alapján készül, akkor a megfejtés sokkal nehezebb. A táblázat soronkénti transzformációját a táblázat elemeinek ciklikus eltolásával oldjuk meg.
Egy táblázat elemeinek eggyel balra való ciklikus léptetése jelentse azt, hogy minden elem eggyel előbbre kerül, az elsőt pedig a végére tesszük.

1. megoldás:
A balra eggyel léptetésnél megjegyezzük az első elemet, az első helyére tesszük a másodikat, a második helyére a harmadikat, ..., s végül az utolsó helyőre a korábban megjegyzett elsőt. A megjegyzéshez szükségünk van egy új változóra. Ha mindezt K-szor végezzük el, akkor megtörtént a K-val balra léptetés.

Léptetés:
  Ciklus J=1-től K-ig
    X:=T(1)
    Ciklus I=2-től N-ig
      T(I-1)=T(I)
    Ciklus vége
    T(N):=X
  Ciklus vége
Eljárás vége.

IS-BASIC:

DEF LEPTET(K)
  FOR J=1 TO K
    LET X=T(1)
    FOR I=2 TO N
      LET T(I-1)=T(I)
    NEXT
    LET T(N)=X
  NEXT
END DEF

2. megoldás:
Próbálkozzunk egy másik megoldással! Ha megjegyeztük az első K db elemet, akkor a
K+1-diket rögtön a helyére, az első helyre tehetjük, a K+2-diket a másodikra, ..., s végül a megjegyzett K db elemet az előremásoltak mögé tesszük. Az első K elem ideiglenes tárolásához szükségünk van egy vektorra - X(K)).

Léptetés:
  Ciklus I=1-től K-ig
    X(I)=T(I)
  Ciklus vége
  Ciklus I=K+1-től N-ig
    T(I-K):=T(I)
  Ciklus vége
  Ciklus I=1-től K-ig
    T(N-K+I):=X(I)
  Ciklus vége
Eljárás vége.

IS-BASIC:

DEF LEPTET(K)
  NUMERIC X(1 TO K)
  FOR I=1 TO K
    LET X(I)=T(I)
  NEXT
  FOR I=K+1 TO N
    LET T(I-K)=T(I)
  NEXT
  FOR I=1 TO K
    LET T(N-K+I)=X(I)
  NEXT
END DEF

Próbálkozzunk egy harmadik megoldással is!
Jegyezzük meg az első elemet! Tegyük a helyére a K-val később levőt, a K-val később levő helyére a nála K-val később levőt,s ha N-1 ilyen előremásolást elvégeztünk, akkor az utolsónak maradt üres helyre tegyük az először megjegyzettet!
Megjegyzés: Módszerünk jól működik, ha szavatolni tudjuk, hogy minden egyes elemet előrehoztunk, egy lépésben K hellyel, és mindegyiket csak egyszer hoztuk előre.

Léptetés:
  L1:=1: X:=T(L1)
  Ciklus I=1-től N-1-ig
    L2:=L1+K
    Ha L2>N akkor L2:=L2-N
    T(L1):=T(L2)
    L1:=L2
  Ciklus vége
  T(L1):=X
Eljárás vége.

IS-BASIC:

DEF LEPTET(K)
  LET L1=1:LET X=T(L1)
  FOR I=1 TO N-1
    LET L2=L1+K
    IF L2>N THEN LET L2=L2-N
    LET T(L1)=T(L2):LET L1=L2
  NEXT
  LET T(L1)=X
END DEF

Vajon jó-e ez a módszer? Próbáljuk ki! N=6, K=1 esetben a megoldás jó, azonban az N=6, K=3 esetben a program csak az első és a negyedik elemet cserélgeti! Keressük meg, hogy milyen K értékekre működik az algoritmus helyesen. Tegyük fel, hogy N és K olyan számok, hogy csak egyetlen közös pozitív osztójuk van, az 1! Ekkor igaz: I*K   (I=0,1,2,...,N-1) N-nel való osztásának maradékai mind különbözőek, és így kiadják az összes számot 0 és N-1 között. Ezekhez az értékekhez egyet hozzáadva megkapjuk az összes 1 és N közötti számot és mindegyiket pontosan egyszer. Vegyük észre, hogy ha ezeket a számokat indexnek használjuk, akkor a sorozat első helyén levő indexű betű helyére pontosan a második helyen levő indexű betűt kell tenni, mivel a második index pontosan K hellyel mutat későbbre a táblázatban. Ez az összefüggés az összes egymást követő számpárra érvényes.
Mivel az előbbi számsorozatban az összes 1 és N közötti index szerepel, ezért minden elem léptetését elvégeztük. Mivel mindegyik pontosan egyszer szerepel, ezért mindegyiket egyszer hoztuk előre. Mivel két elem közül a második (amit előrehoztunk) mindig K-val volt hátrább, ezért mindegyiket K-val hoztuk balra.
Matematikai érdeklődésű Olvasóinkra bízzuk a feladat megoldását abban az esetben, amikor K-nak és N-nek van az 1-től különböző pozitív osztója.

Térjünk rá a fejezet fő kérdésére: van három megoldásunk, vajon melyik a jobb? Válaszunk: attól függ, mi a célunk! Ez nagyon fontos megállapítás, egy feladat két megoldása általában sohasem hasonlítható össze önmagában. Az összehasonlításhoz mindig kell valamilyen követelményrendszer, amit a feladat kitűzésekor kell megállapítani.
Vegyünk példánkkal kapcsolatban három követelményt: a megoldás

Vizsgáljuk meg megoldásainkat a követelményeink szempontjából!

Sebesség (S):
Egy megoldás sebességét mérjük a végrehajtott értékadó utasítások számával!

1. megoldás: S=K*(N+1);
2. megoldás: S=N+K;
3. megoldás: S=4*N-1;
ha az aritmetikai értékadásokat nem vesszük figyelembe: S=N+1.

Tehát a sebesség szempontjából az első megoldás kirívóan rossz.

Helyfoglalás (H):
Mérjük a helyfoglalást a változók, tömbelemek számával!

1. megoldás: H=N+1;
2. megoldás: H=N+K;
3. megoldás: H=N+1.

Ebből a szempontból tehát a második megoldás rosszabb a többieknél.

Egyszerűség:
Az első és a második megoldást nagyon könnyen elkészítettük, a harmadikhoz azonban némi matematikai ismeretre volt szükségünk. Ennek az elkészítése bizony hosszabb időt vett igénybe, több munkánkba került.

Minden szempontból kielégítő megoldást nem kaptunk, ahogyan teljesen rosszat sem. Tehát a követelményeket rangsorolni kell, s azt a megoldást fogadjuk el legjobbnak, amelyik a legfontosabb követelmény(ek) szerint jó, a kevésbé fontos(ak) szerint pedig nem kell annyira jónak lennie.
Azt tapasztaltuk, hogy egy feladat megoldásai közül a feladat kitűzésekor megadott követelményrendszer alapján tudunk választani. Természetesen minden feladat megoldásakor nem készíthetjük el az összes megoldást. Mi ilyenkor a teendő? Ha a lépésenkénti finomítás során eljutunk egy, a megoldást befolyásoló döntésig, akkor ott fel kell vázolni a megoldási lehetőségeket, és ezen lehetőségek teljes kifejtése nélkül - korábban szerzett programozási tapasztalatokra hagyatkozva - kell kiválasztani azt, amit a legjobbnak tartunk.

Programok hatékonysága

A hatékonyságvizsgálat, a hatékonyabbra átírás előfeltétele a program helyessége. Annak ugyanis semmi értelme sincs, hogy egy hibásan működő program gyorsabban működjön.
A programozásban hatékonyságon általában a helyfoglalás és a futási idő lehető legkisebb értékét értjük. Ez a két szempont legtöbbször ellentmondó követelményeket támaszt a programmal szemben, így ilyenkor engedményeket kell tenni. A hatékonyság vizsgálatánál mindig meg kell különböztetni a hatékonyság két fajtáját: az algoritmus és a kód hatékonyságát. A fontos jellemzők:

Az algoritmus hatékonysága
Legtöbbször a program hatékonyságát elsősorban az algoritmus befolyásolja, s a kódolásnak, a BASIC nyelv jellemzői figyelembevételének lényegesen kisebb a hatása. Elsőként ott érdemes a hatékonyság vizsgálatával foglalkozni, ahol a program sokszor hajt végre egy műveletet, azaz a ciklusokat kell vizsgálni. Két lehetőség van: csökkentsük a ciklusok végrehajtásainak számát vagy a ciklusok egyszeri végrehajtási idejét. Az előbbire akkor van lehetőségünk, ha ki tudjuk használni az adatok valamilyen speciális tulajdonságát vagy matematikai ismereteinket.

Nézzünk először a keresési feladatot az algoritmus hatékonysága bemutatására!
Az lineáris keresés algoritmusa esetén egy szám megtalálásához a vizsgálatok átlagos száma kb. N/2, a második esetben (logaritmikus leresés) pedig N 2-es alapú logaritmusával arányos. Tehát a hatékonyabb algoritmus egyben bonyolultabb is, így több helyet foglal és elkészítéséhez nagyobb programozási tapasztalat szükséges.

Második példánkban próbáljuk minimalizálni a ciklusmag végrehajtásainak számát.
A prímszámkeresés algoritmusban a ciklus végrehajtásainak számát csökkentettük. Egyrészt tudjuk, hogy a legnagyobb osztó nem lehet N/2-nél nagyobb, így az N-1-es határt máris N/2-re csökkenthetjük. Másrészt azt is tudjuk, hogy ha van osztó, akkor közülük a legkisebb még az adott szám négyzetgyökénél sem lehet nagyobb, így a felső határt tovább csökkenthetjük.

Gyakori módszer a hatékonyabbra írásra, hogy a program már kiszámolt értékeit indexelésre használjuk, amivel sok feltételes utasítást takaríthatunk meg. Vizsgáljuk meg a következő két algoritmust:

1. algoritmus:
  Ciklus I=1-töl 100-ig
    X:=RND(6)
    Ha X=1 akkor S1:=S1+1
    Ha X=2 akkor S2:=S2+1
    Ha X=3 akkor S3:=S3+1
    Ha X=4 akkor S4:=S4+1
    Ha X=5 akkor S5:=S5+1
    Ha X=6 akkor S6:=S6+l
  Ciklus vége
  Ki: S1,S2,S3,S4,S5,S6
Eljárás vége.

2. algoritmus:
  Ciklus I=1-től 100-ig
  X:=RND(6)
  S(X):=S(X)+1
  Ciklus vége
Ki: S(1),S(2),S(3),S(4),S(5),S(6)
Eljárás vége.

Ebben az esetben, tehát az algoritmus (és így a program) szövege is rövidebb lett és az átlagos végrehajtási időt is jelentősen csökkentettük.

Most egy formális módszert ismertetünk a végrehajtási idő várható értékének kiszámítására:

  1. Határozzuk meg a bemenő adatok eloszlását!
  2. Határozzuk meg a program részeredményeinek eloszlását!
  3. Az előbbiek segítségével határozzuk meg a programon átvezető utak végrehajtásának valószínűségét! P(uj)
  4. Határozzuk meg az egyes utak végrehajtási idejét! t(uj)
  5. Ezek felhasználásával számoljuk ki a várható értéket!

Ez a módszer kis programoknál tökéletesen, ill. nagy programoknál a 3. és a 4. pont kivételével elvégezhető. Nagyobb és bonyolultabb programoknál azonban a kézi módszerek nem megfelelőek, túlságosan sokáig tartanak.
Bonyolultabb esetekben a program speciális tesztesetekkel való lefuttatására van szükség, és a ténylegesen mért végrehajtási idők segítségével kell becsülni az átlagos végrehajtási időt. Itt a teszteseteknek a megválasztása lényeges, amihez szintén ismerni kell a bemenő adatok várható eloszlását.
Tesztadat választásnál megismertük az ekvivalenciaosztályok módszerét, amelyben a lehetséges bemenő adatokat osztályokba soroltuk, majd minden osztályból egy adattal (adatcsoporttal) próbáltuk ki a programot. Most is osztályokra kell bontani a lehetséges adatokat, de úgy, hogy az egyes osztályokba tartozó adatokra nagyjából azonos végrehajtási időt kapjunk. Eddig a módszer megegyezik a formális módszerrel, az újdonság ezután az, hogy egy-egy ilyen adattal a programot valóban kipróbáljuk, s a mért értéket használjuk fel mérőszámnak.

Ahhoz, hogy felfedezzük programunkban a kevésbé hatékony részeket, szükségünk van a program részeinek végrehajtásához szükséges idő becslésére. (Tapasztalatok szerint a program futási idejének 90%-áért a programszöveg 3-5%-a a felelős!) Ehhez a programban időmérési kezdő- és végpontokat kell kijelölni és elvégezni az egyes tartományok mérését. Ezt a legegyszerűbb esetben valamilyen figyelemfelhívó utasítással (kiírás a képre, hangjelzés) lehet a felhasználóra bízni, olyan gépeken pedig, ahol van belső óra, ott automatikus időmérést végezhetünk.

A bonyolultság, ill. a kód hosszának csökkentésére két egyszerű elvet mondunk ki. Az első a kivételes eset kiküszöbölésének elve, a második pedig a fiktív kezdőértékadás elve.

A kivételes eset kiküszöbölése
Ha a feladat pl. egy szövegben a szavak számának meghatározása, akkor a következőképpen járhatunk el. A szavak száma megegyezik a szavak kezdeteinek számával. Egy szó úgy kezdődik, hogy szóköz után betű következik, kivéve az első szót. Ha a szöveg első karaktere szóköz, akkor az előbbi állítás az első szóra is igaz, ha betű. akkor nem (ez a kivételes eset). Helyezzünk el ekkor a szöveg első karaktere elé egy szóközt, így a kivételt megszüntethetjük, a megoldó programot rövidebbé, egyszerűbbé tehetjük.
Ugyanezt az elvet szemléltetjük a kiválasztási algoritmus átalakításával. Korábban az algoritmus ciklusfeltételében két dolgot kellett vizsgálni: azt, hogy van-e még vizsgálandó elem, s hogy megtaláltuk-e a keresettet. Helyezzük az N+1. elem helyére a keresettet, így biztosan meg tudjuk találni, s ha a legvégén találtuk meg, akkor nem volt az eredeti sorozatban. Az új algoritmus (van-e X elem az A(N) sorozatban?):

Eljárás:
  I:=1: A(N+1):=X
  Ciklus amig A(I)<>X
    I:=I+1
  Ciklus vége
  VAN_E:=I<=N
Eljárás vége.

A fiktív kezdőértékadás
Az elv bemutatására a maximumkiválasztás programját módosítjuk, ahol az N elemű A() vektor maximális értékű elemének az értékét kell megadni:

Eljárás:
  ERTEK:=A() alsó korlátja
  Ciklus I=1-től N-ig
    X:=A(I)
    Ha ERTEK<X akkor ERTEK:=X
  Ciklus vége
Eljárás vége.

A megoldás lényege: ha A() egy elemének bonyolult a meghatározása, akkor azt csak egyszer végezzük el, s kiinduló értéknek egy olyan fiktív értéket választunk, amelyet az algoritmus biztosan módosít.

A programkód hatékonysága
A kód hatékonyságának javításával csak ciklusok belsejében érdemes foglalkozni, akkor, amikor egy utasítást sokszor végre kell hajtani. Eléréséhez adunk néhány jó tanácsot:

1. változat:

LET A=1:LET E=1
FOR I=1 TO 36
  LET U=SIN(A)+SIN(E)
  LET E=A:LET A=U
  PRINT U;
NEXT

2. változat:

LET A,E=SIN(1)
FOR I=1 TO 36
  LET U=A+E
  LET E=A:LET A=SIN(U)
  PRINT U;
NEXT

Az első változat kb. kétszer annyiszor számítja ki a szinusz függvény értékét, mint a második.

Bevezetünk néhány programtranszformációt, amelyek segítségével helyes programunkat hatékonyabbá tehetjük. A következő algoritmusokban a feltételeket F-fel, a ciklusfeltételeket CF-fel, az utasításokat U-val jelöljük. A példákban az eredeti és a hatékonyabbra átírt programokat formailag másként helyezzük el.

1.

Ha F akkor U1: U2
különben U1: U3
U1
Ha F akkor U2
különben U3

2.

Ha F akkor U1: U3
különben U2: U3
Ha F akkor U1
különben U2
U3

3.

Ha F akkor U1 különben
  Ha nem F akkor U2
Ha F akkor U1
különben U2

4.

Ha F akkor U1
Ha F akkor U2
Ha F akkor U1: U2

Példa:

IF A(I,J)>0 THEN LET S=S+1
IF A(I,J)>0 THEN PRINT I;J

helyett:

IF A(I,J)>0 THEN LET S=S+1: PRINT I;J

5.

Ciklus amíg CF
  U1
Ciklus vége
Ciklus amíg CF
  U2
Ciklus vége
Ciklus amíg CF
  U1: U2
Ciklus vége

Példa:

LET MIN=A(1)
FOR I=2 TO N
  IF MIN>A(I) THEN LET MIN=A(I)
NEXT I
LET MAX=A(1)
FOR I=2 TO N
  IF MAX<A(I) THEN LET MAX=A(I)
NEXT I

helyett:

LET MIN,MAX=A(1)
FOR I=2 TO N
  IF MIN>A(I) THEN LET MIN=A(I)
  IF MAX<A(I) THEN LET MAX=A(I)
NEXT

6.

Ciklus amíg CF
  Ha F akkor U
Ciklus vége

Ha F akkor
  Ciklus amíg CF
    U
  Ciklus vége
Elágazás vége

Példa:

LET S=0
FOR I=1 TO N
  IF A(1)>0 THEN LET S=S+A(I)
NEXT I

helyett:

IF A(1)>0 THEN
  LET S=0
  FOR I=1 TO N
    LET S=S+A(I)
  NEXT
END IF

7.

Ciklus amíg CF
  U1
  U2
Ciklus vége

U1
Ciklus amíg CF
  U2
Ciklus vége

Példa:

FOR H=HO TO 0 STEP -1
  LET EH=M*G*H
  LET EM=M*G*HO-M*G*H
  PRINT H,EH,EM
NEXT

helyett:

LET X=M*G: LET Y=X*HO
FOR H=HO TO 0 STEP -1
  EH=X*H: EM=Y-EH
  PRINT H,EH,EM
NEXT

Ha a programot átírtuk hatékonyabbra, elképzelhető, hogy a javításokkal hibákat is helyeztünk el benne (legtöbbször sajnos éppen ez a helyzet áll fönn). Alapvető követelmény, hogy az átírt program ugyanazokat az, eredményeket adja, mint a korábbi változat. Erről meggyőződni csak úgy lehet, ha lefuttatjuk az összes korábbi tesztadattal. Ilyenkor (is) jó az, ha a tesztelés módját és eredményeit leírtuk, mert akkor az eredményeket könnyen összehasonlíthatjuk a korábbiakkal.

Programcsaládok

Ha a program a használat során helyesnek bizonyul, akkor is szükség lehet módosításra. Ez akkor fordul elő, ha a felhasználójának újabb igényei születnek, egyes részfeladatokat másképp szeretne megoldani, hasonló feladat megoldására szeretné a programot alkalmazni. Ekkor egy meglevő, helyes programból egy újabbat kell előállítani, amely megfelel a módosított igényeknek.
Két megközelítésmódot követhetünk. Az elsőben a két programot egy közös ős leszármazottjának tekintjük. A két feladat (az eredeti és a módosított) valamilyen szintig azonos megoldást igényel, s ettől a szinttől kezdve érvényesülnek az eltérések. Célszerű ilyenkor a közös őst külön is elkészíteni, majd a közös alatti szinteken a korábbi tervezés során hozott egyes döntéseket felülbírálni, az új részeket teljesen kidolgozni.
A másik megközelítésben - ahol a feladatok között sokkal nagyobb rokonság áll fönn - megpróbáljuk a módosításokat a korábbi megoldás néhány, de nem feltétlenül a legalsó szintjére korlátozni. Mindkét módszer lényeges eleme, hogy a módosításokat nem a program szövegében kezdjük elvégezni. Azzal ugyanis súlyos hibákat okozhatunk, amelyek kijavítása tovább tarthat, mint az egyes részek újratervezése. A másik tény, ami a közvetlen programszövegbeli javítás ellen szól: a sok meggondolatlan belejavítástól a program szövege egyre áttekinthetetlenebb lesz.
Ha eleve számítunk ilyen programcsaládok létrehozására, akkor célszerű az első módszert követni. Tehát a feladatot a várható feltételeltérések alapján feladatosztályra szélesítjük, majd hozzáfogunk a feladat (családot)ot megoldó program felső szintjeinek meghatározásához. Igyekszünk az egyes szinteknél a lehető legáltalánosabban fogalmazni (nyílt rendszerű felépítés elve), s ameddig csak lehet, halogatni az egyes feladatok felé kanyarodó döntéseket (a döntések elhalasztásának elve). Így jutunk el a feladatcsaládhoz tartozó közös ős programhoz.
Ha pedig utólagos - és egyedi - igény merült fel, akkor a kisebb ráfordítást követelő második módszert használjuk.

A következő feladatokhoz felépítünk egy programcsaládot.
Ismerünk N darab szülő-gyerek kapcsolatot,

A megoldások közös részéhez tartozik az adatábrázolás megválasztása. Legyen N a szülő-gyerek kapcsolatok száma, a kapcsolatokat tároljuk az X(N,2) mátrixban! Itt emberek sorszámait fogjuk elhelyezni, az első oszlop minden egyes kapcsolatban a szülőt, a második pedig a gyereket azonosítja. Tároljuk az egyes feladatoknak megfelelő emberek sorszámait az S(2*N) vektorban! D jelezze a sorra vett emberek számát, a vektor első eleme pedig annak a sorszáma legyen, akinek valamilyen rokonait kell megadni (beolvasáskor K-val jelöljük!)
A megoldás legfelső szintje azonos az összes feladatnál:

[ 1. szint ]
Program:
  Az adatok beolvasása [N, X(N,2),K]
  D:=0
  A megfelelő tulajdonságú emberek kiválogatása
    [ az S() vekror első eleme tartalmazza a sorszámokat ]
  Az eredmény kiírása
Program vége.

Az adatok beolvasását és az eredmény kiírását nem részletezzük (ezek ráadásul az algoritmus szintjén azonosak is), csak a kiválogatással foglalkozunk.
Az első két feladatban olyan sorszámokat kell keresnünk, amelyek párja egy adott érték a mátrix valamelyik sorában. A 4., 5., 6. feladatban az így kapott sorszámú emberekhez újra kell keresni ilyen párokat. A legbonyolultabb a 3. eset. Itt ugyanis először meg kell határozni a keresett ember szüleit, majd pedig a szülők összes gyerekét. Így a 2. szintből három változatot készítünk:

[ 2. (1,2) szint ]
A megfelelő tulajdonságú emberek kiválogatása:
  A K. ember felvétele S()-be
  Az S(1) ember megfelelő rokonai felvétele
Eljárás vége.

Az összes megfelelő rokon kiválogatását a SOR nevű adatszerkezet felhasználásával oldjuk meg. A SOR egy olyan sorozat, amelyből elvenni mindig csak az elejéről lehet, a SOR-ba felvenni új számokat pedig csak a végére lehet. A SOR-t egy vektorban tároljuk. Az elvétel miatt tudnunk kell, hogy a vektor melyik elemét tekintjük a SOR első elemének, ezt egy mutató jelzi.

[ 2. (4, 5, 6) szint ]
A megfelelő tulajdonságú emberek kiválogatása:
  A K. ember felvétele S()-be
  A:=1
  Ciklus amíg A<=D
    Az S(A). ember megfelelő rokonai felvétele
    A:=A+1
  Ciklus vége
Eljárás vége.

A harmadik változatban a megtalált szülőket átmásoljuk az S() második felébe, majd megkeressük a gyerekeiket.

[ 2. (3) szint ]
A megfelelő tulajdonságú emberek kiválogatása:
  A K: ember felvétele S()-be
  Az S(1). ember szülei felvétele
  D1:=D
  Ciklus I=2-től D-ig
    S(I+N-1):=S(I)
  Ciklus vége
  D:=1
  Ciklus I=N+1-től N+D-ig
    Az S(I). ember gyerekei felvétele
  Ciklus vége
Eljárás vége.

A 6. feladat kétféle típusú rokonságot enged meg, míg a többiek most már csak egyfélét. Így a harmadik szintet csak ennél a feladatnál dolgozzuk ki.

[ 3. (6) szint ]
Az S(A). ember megfelelő rokonai felvétele:
  Az S(A). ember gyerekei felvétele
  Az S(A). ember szülei felvétele
Eljárás vége.

A többi feladatnál a megfelelő rokonok megegyeznek az adott ember gyerekeivel illetve szüleivel, így ezen szintet nem részletezzük.
A negyedik szinten újra hasonló feladatokat kell megoldani, itt aszerint bontjuk szét a megoldásokat, hogy szülőket vagy gyerekeket kell keresni. Alkalmazzuk a kiválogatásra megismert tételt, megoldásuk a következő lesz:

[ 4.1. (2, 3, 4, 6) szint ]
Az X. ember szülei felvétele:
  Ciklus L=1-től N-ig
    Ha X(L,2)=X akkor Az X(L,1). felvétele
  Ciklus vége
Eljárás vége.

[ 4.2. (1, 3, 5, 6) szint ]
Az X. ember gyerekei felvétele:
  Ciklus L=1-től N-ig
    Ha X(L,1)=X akkor Az X(L,2). ember felvétele
  Ciklus vége
Eljárás vége.

Maradt a legutolsó, 5. szint elkészítése, amely mindegyik feladatnál azonos. Egy adott sorszámú embert akkor kell felvenni, ha még nem szerepel az S( ) vektorban.

[ 5. szint ]
Az X. ember felvétele:
  Ha S(J)<>X [J=1,2,...D] akkor
    D:=D+1: S(D):=X
Eljárás vége.

Ezzel elkészült a teljes programcsalád. Természetesen a kódolás során is érdemes követni az előbbi módszert, így azt a munkát is megkönnyíthetjük, s biztonságossá tehetjük. Célszerű a programok beírását a közös részek elkészítésével és felvételével kezdeni, majd ehhez egyenként beírhatok az egyes megoldások egyedi részei, így sok gépelési munkától is mentesülünk.
Javasoljuk Olvasónknak, hogy az egyes feladatokhoz elkészült algoritmusokat külön-külön is írja le! Így még szembetűnőbb lesz hasonlóságuk és egyszerűségük.

Megjegyzések:

Néhány szó a feladatmeghatározásról

Ha a megoldás algoritmusát elkészítettük, majd a programot kódoltuk, leteszteltük, ezenkívül hatékonysága is jó, akkor vajon mondhatjuk-e, hogy a feladatot jól megoldottuk? Sajnos nem mindig! Előfordulhat, hogy nem értettük meg pontosan a feladatot, és így mást csináltunk, mint amit kellett volna.
A feladatmeghatározás hiánya szokta a legtöbb vitát okozni a programozó és a feladat kitűzője között. Érdekes, hogy az ellentmondás akkor is fellép, ha e két ember egy és ugyanaz. Ennek többnyire az az oka, hogy az elvárások nincsenek átgondoltan megfogalmazva, a rendelkezésre álló adatok nincsenek összhangban, az algoritmizálhatóság szempontjából a fogalmak nincsenek tisztázva. A sikeres feladatmeghatározás tehát erősen befolyásolja a programkészítésre fordított időt, és a kész program alkalmazhatóságát.
Mitől rosszak a feladatmeghatározások? A legtöbb esetben maga a feladat nem teljesen tisztázott, a használt fogalmak nem egyértelműek, a szöveges leírás félreérthető. Sokszor a feladat kitűzője nem ért a számítástechnikához, ezért nem tudja megítélni, hogy mit, s mennyit kell leírnia.
Miből áll a feladatmeghatározás? Szerepeljen benne mindaz, ami a feladat pontos megoldásához szükséges. Adjuk meg:

Milyen legyen a feladatmeghatározás? Mindenképpen olyannak kell lennie, amelyből a program készítője pontosan azt a feladatot és pontosan úgy oldja meg, ahogyan a feladat kitűzője várta. Három, egymástól eltérő követelményeket állító szempontrendszer adható meg. Az első szerint a feladatmeghatározás legyen egyértelmű, pontos, teljes (ne legyen definiálatlan fogalom). A második szerint legyen rövid, tömör (ha lehetséges, akkor formalizált). A harmadik szemléletes, érthető, tagolt formát követel. A baj abból származik, hogy általában az egyértelmű, pontos feladatmeghatározás hosszú, s így nehezen áttekinthető. A tömör, formális feladatmeghatározás ugyan pontos lehet, de sajnos, nem szemléletes. Ami pedig szemléletes, az legtöbbször se nem pontos, se nem egyértelmű. Mindezekből nyilvánvaló, hogy valamilyen kompromisszumot kell találni.
Például (nem törekszünk a teljes formalizálásra):

Feladat: Ismerjük adott számú ember magasságát! Határozzuk meg a legmagasabb sorszámát és magasságát!

Jelölések:
N      - az emberek száma;
X(N) - a magasságok;
LM   - a legmagasabb magassága;
LS    - a legmagasabb sorszáma.

A program N és X(N) ismeretében kiszámítja LM és LS értékét.
Bemenet: N természetes szám és X(I)>0 valós számok [1=1,2,...,N].
Eredmény: LM >= X(I) [I=1,2,...,N] és
             1 <= LS <= N és LM = X(LS).
Egyéb feltételek: N, X(N) változatlan marad. Ha több egyforma magasságú is van, akkor elég egyet megadni.

Látható, hogy a megoldás helyessége már a feladat megértésének pillanatában eldőlhet, hiszen ha valamit félreértelmezünk, akkor egészen más programot készíthetünk, mint amire szükségünk van.

Néhány szó a dokumentációról

Hátra van még a programdokumentálás. Miért van egyáltalán szükség rá? Nos, két okból is: A programot

  1. használni,
  2. néha módosítani, továbbfejleszteni kell.

Talán azt kérdezi az Olvasó, hogy: "Miért kell életünket újabb papírhegyekkel nehezíteni? Hiszen az elveket betartva a felhasználót maga a program eligazítja. Minek kell a használat mikéntjét még papírra is rögzíteni? ..." E dohogás érthető, de a programdokumentálás mégis elkerülhetetlen. Megnyugtatásul sietünk előre jelezni, hogy nem újabb többletmunkára szeretnénk rábírni az Olvasót, hanem arra, hogy amit a feladat megoldása közben kitalál, amiről dönt, azt rögtön írja is le a dokumentációba. Tehát a dokumentáció a feladatmegoldás kezdetétől a program átadásáig elkíséri a program íróját. Térjünk rá a részletekre!
A használatot támogató programleírást felhasználói dokumentációnak, a továbbfejlesztés érdekében készítettet fejlesztői dokumentációnak hívják.

A felhasználói leírás
Nézzük meg, milyen feladatokat ró a leírásra a használhatóság!
Abból az alapelvből kell kiindulni, hogy a felhasználónak több hasonló feladatot megoldó program közül van lehetősége válogatni. Tehát mindent el kell követni, hogy választása az elvárásainak leginkább megfelelő programra essék. Ezért közölni kell a program feladatának pontos leírását.
Semmiképpen nem maradhat ki annak a környezetnek a leírása, amely szükséges a program zavartalan működéséhez. Így pl. a tárigény, vagy a hardver kellékek (magnó / lemezegység, televízió, botkormány, nyomtató), vagy a programozási segédeszközök. Továbbá sokszor jó tudni, hogy a program milyen módszert követ a feladat megoldásában. Nevezetes módszereknél elegendő csak névre utalni, máskülönben megéri néhány mondatban összefoglalni a tulajdonságait. A program nyelve már a betöltésnél lényeges lehet.
Bár a módszerből is, a program nyelvéből is következtetni lehet a gyorsaságra, mégis egy átlagos futási időt meg kell adni a dokumentációban.
A következő fontos tanács, hogy a felhasználó tárgyhoz tartozó ismereteiről minél kevesebbet tételezzünk fel. Ez nem lebecsülés, hanem segítség.
A betöltés módját teljes alapossággal kell leírni (milyen paranccsal, s hogyan?)!
Ha mindezen kívül még készítünk egy képernyőtervet is, amelynek adatait elsőként olvastatjuk be, hogy a betöltés perceiben ne unatkozzék a felhasználó, akkor elmondhatjuk, hogy igazán barátságos programot készítettünk.

A futó program használatának leírása azt jelenti, hogy megadjuk, milyen kérdéseket tesz fel a program, és mit felelhet rá a felhasználó. Figyelem! Ez nem teszi fölöslegessé a programba beépített segítséget, mivel nem várható el a felhasználótól, hogy állandóan a dokumentációból, mint egy partitúrából lesse a teendőket! A leírásnak tartalmaznia kell a program figyelmeztető jelzéseit, a hiba okát és kiküszöbölésének módját. Végül néhány, akár hibás felhasználói válaszokat is tartalmazó példafuttatást is mutassunk be!

A fejlesztői leírás
A fejlesztői leírás tartalmáról e könyvben már sok szó esett, így itt csak összefoglaljuk a korábban elhangzottakat. A fejlesztői leírás olyanoknak készül, akik a programon módosítani szeretnének, a programot más feladatra alkalmazni, vagy kiterjeszteni akarják. Ezért minden ehhez szükséges tudnivalót tartalmaznia kell.
A fejlesztői leírás készítése lényegesen egyszerűbb feladat, mint a felhasználói megírása, mivel a programkészítés végére érve szinte minden anyag elkészül hozzá. Nézzük, melyek is ezek:

A dokumentáció formai követelményei
A dokumentáció elsődleges célja a program leendő felhasználóinak, továbbfejlesztőinek való segítségnyújtás. Ezért olyannak kell lennie, hogy minden számukra szükséges tudnivalóhoz könnyen hozzájuthassanak. Ehhez elsődleges szempont természetesen, hogy a dokumentáció mindezeket tartalmazza, de a használatát egyéb követelmények betartásával jelentősen megkönnyíthetjük. Ezek a következők:

Utószó

A könyv végére érve tekintsük át még egyszer a programkészítés lépéseit!

  1. Feladatmeghatározás (mit kell megoldani?).
  2. Algoritmuskészítés (hogyan kell megoldani a feladatot?).
  3. Kódolás (eredménye a programozási nyelven megírt program).
  4. Helyességbelátás (eredménye a helyesen működő program).
  5. Minőség- és hatékonyságvizsgálat, javítás (eredménye a minden igényt kielégítő, jó program).
  6. Dokumentálás (eredménye a mások által is használható program).

Felsorolásunk bizonyos sorrendiséget is jelöl, de felhívjuk a figyelmet arra, hogy az egyes tevékenységek időben átfedik egymást, olyannyira, hogy a dokumentálást már a feladatkitűzés pillanatában el kell kezdeni.
Mindazon elvek és módszerek, amelyekről e könyvben szó esett, a professzionális programozási kultúrának is részei. Mi igyekeztünk úgy bemutatni és kiegészíteni őket, hogy ez nem számítástechnikai szakemberek számára is világos és hasznos legyen. Természetesen a programozó matematikusok még nagyszámú, újabb elvet és módszert is alkalmaznak, amelyek elsajátításához több éves tanulás szükséges. Ezek ismeretére és alkalmazására csak nagyméretű feladatoknál van szükség, amelyeket már jobb, ha rájuk hagyunk.

I. Függelék: A leíró nyelv szabályai

A megoldás algoritmusának, adatszerkezeteinek leírására egy, a magyar nyelvhez közel álló - nem túl szigorú - nyelvet használunk. Nézzük meg ezt a nyelvet egy kicsit részletesebben! Felsoroljuk utasításait. Egy utasítás neve mindig nagy betűvel kezdődik. A kis betűkkel írt fogalmakat részletesebben kifejtjük, a nagy betűkkel írtakat nem. Egy utasítás általában egy mondat.

Program:

Program:
  utasítássorok
Program vége.

Utasítássor:

utasítás: utasítássor
vagy utasítás

Értékadó utasítás:

azonosító:=kifejezés
Jelentése: a megadott változó felveszi a kifejezés értékét.

Azonosító:

változónév vagy tömbelem vagy tömbnév.

Kifejezés:

Tetszőleges, a matematikában megszokott kifejezés.

Olvasó utasítás:

Be: azonosítók
Jelentése: beolvas tetszőleges adatokat a megadott változókba, amelyeket vesszővel kell elválasztani egymástól.

Író utasítás:

Ki: kifejezések [tetszőleges szöveg]
Jelentése: kiírja a megadott kifejezéseket a képernyőre. Ha az egyes kifejezések között pontosvessző van, akkor közvetlenül egymás mögé; ha vessző, akkor a következő, ún. tabulátorpozícióra - a BASIC konvencióknak megfelelően. Megadható egy speciális kifejezés, amely azt jelzi, hogy a következő kiírás hova kerüljön a képernyőn (sor, oszlop). A szögletes zárójelben megadott szöveg tetszőleges, a kiírás formátumára vonatkozó megjegyzés lehet.
Megjegyzés: [,] jelek között tetszőleges szöveg lehet. Ezt használjuk föl arra is, hogy állításokat helyezzünk el a programban elvárásainkról, amelyeket bizonyos utasítások környezetében a program kódolásakor végrehajtható utasításokká is átalakíthatunk.

Feltételes utasítás:

Ha logikai kifejezés akkor utasítássor

vagy

Ha logikai kifejezés akkor
  utasítássorok
Elágazás vége

vagy

Ha logikai kifejezés akkor utasítássor
különben utasítássor

vagy

Ha logikai kifejezés akkor
  utasítássorok
különben
  utasítássorok
Elágazás vége

Jelentése: A logikai kifejezés igazságértékétől függően a megfelelő utasítássorok hajtódnak végre, s ezek után a feltételes utasítás utáni első utasítás. Ha a feltételes utasításbeli utasítássorokban további feltételes utasítás van, akkor az 'Elágazás vége' alapszó kiírásával egyértelművé kell tenni hogy melyik, hol fejeződik be.

Várakozás:

Várj, amíg kell

Jelentése: vár, amíg a felhasználó nem avatkozik közbe (nem nyom le egy billentyűt a billentyűzeten).

Ciklus:

Ciklus ciklusváltozó = kezdőérték-től végérték-ig
  utasítássorok
Ciklus vége

Jelentése: a közbezárt utasítássorokat (ciklusmag) végrehajtjuk a ciklusváltozó lehetséges értékeivel, amelyeket a kezdőértéktől a végértékig egyesével felvesz.

Ciklus ciklusváltozó=kezdőérték-től végérték-ig lépésköz-ösével
  utasítássorok
Ciklus vége

Jelentése: a közbezárt utasítássorokat végrehajtjuk a ciklusváltozó lehetséges értékeivel, amelyeket a kezdőértéktől a végértékig a megadott lépésközzel felvesz.

Ciklus amíg logikai kifejezés
  utasítássorok
Ciklus vége

Jelentése: a ciklusmag végrehajtása a logikai kifejezés értéke alapján történik. A ciklusmagot addig kell végrehajtani, amíg a logikai kifejezés igaz. Ezt az első végrehajtás előtt is megvizsgáljuk. Amikor hamis lesz, akkor a 'Ciklus vége' utáni utasítással folytatjuk a program végrehajtását.
Az előző háromféle ciklusutasítás esetén előfordulhat, hogy a ciklus magját egyszer sem hajtjuk végre.

Ciklus
  utasítássorok
amíg logikai kifejezés
Ciklus vége

Jelentése: Az előzőtől abban különbözik, hogy a ciklusmagot egyszer mindenképpen végrehajtjuk és a végén vizsgáljuk meg, hogy kell-e még.

Ciklus amíg szükséges
  utasítássorok
Ciklus vége

Jelentése: a közbezárt utasítássorokat a felhasználó engedélyével hajtja végre. Az utasítások egyszeri végrehajtásának engedélyezésére tetszőleges billentyű lenyomása felel meg, kivéve az 'N' betűt. Az utóbbi esetén a 'Ciklus vége' utáni utasításon folytatódik a program végrehajtása. Az utasítást értelmezhetjük úgy is, hogy csupán a ciklus befejezése igényel felhasználói beavatkozást, egyébként a végrehajtás automatikusan folytatódik. A kódolási lehetőségektől függ, hogy melyiket választjuk.

Eljáráshívás:

Tetszőleges magyar nyelvű mondat, amelyet később kifejtünk. Mögötte zárójelben megadhatók az eljárás paraméterei.

Jelentése: Végezzük el az eljárásban leírt tevékenységet, majd folytassuk a programot az eljáráshívás utáni utasítással.

Eljárásdefiníció:

Eljárás név:
  utasítássorok
Eljárás vége

Jelentése: Ha a programban az 'Eljárás név' szöveget látjuk, akkor a helyére behelyettesítendők a megadott utasítássorok.

Adatleírás:

Tömb tömbnév (max. index[ek])

Jelentése: Megállapítjuk, hogy a továbbiakban az adott néven legfeljebb max. indexű vektort, ill. mátrixot fogunk használni.

Függvényhivatkozás:

Tetszőleges magyar nyelvű mondat, amelyet zárójelek között követnek a függvény paraméterei (kifejezések).

Jelentése: (csak kifejezésben használható) számoljuk ki a függvény értékét a zárójelben felsorolt értékekkel, s ezzel az értékkel végezhetjük a további műveleteket.

Függvény definíció:

Függvény név (azonosítók):
  A függvény értékének kiszámítása
  Függvény név:=a kiszámított érték
Függvény definiálás vége.

Jelentése: így kell kiszámítani a függvény értékét, amelyet a 'Függvény név' nevű változóba kell elhelyezni.

Függvény név (azonosítók):=kifejezés

Jelentése: a függvényt ezzel a kifejezéssel kell kiszámítani.

Sokirányú elágazás:

Elágazás
  feltétel1 esetén
    utasítássorok1
  feltétel2 esetén
    utasítássorok2
  feltételn esetén
    utasítássorokn
Elágazás vége

Jelentése: Azokat az utasítássorokat kell végrehajtani, amelyek feltétele a leírás sorrendjében először teljesül. Utána, vagy ha egyik sem teljesül, akkor az elágazás utáni első utasítással kell folytatni a program végrehajtását.

Elágazás
  feltétel1 esetén
    utasítássorok1
  feltétel2 esetén
    utasítássorok2
  egyéb esetben
    utasítássorokn
Elágazás vége

Jelentése: Az előzőtől csupán annyiban tér el, hogy az n. feltételt 'minden egyéb'-bé tágítottuk ki.

II. Függelék: BASIC kódolási szabályok

Nézzük meg ezután, mit kell tudnunk a BASIC programozási nyelvről! Tulajdonképpen más nyelvek esetén sem kellene sokkal több információt megjegyezni, de e könyvben csak a IS-BASIC-kel foglalkozunk. (Az egyes személyi számítógépek a BASIC-nek sajnos más-más nyelvjárásait értik.) Az algoritmusleírást az előző függelékben leírtak szerint készítjük és mögé írjuk az egyes utasítások BASIC megfelelőjét. Á BASIC program minden sora elé sorszámot írunk. A változó- és függvényneveket is kódolni kell a BASIC programban. Bár mechanikusan elvégezhető kódolási szabályokat mondunk ki, mégse felejtsük, hogy ezek nagyvonalú használata az igazán célszerű!

Program:

Program:
  utasítássorok
Program vége.
PROGRAM név(paraméterlista)
...
END

Értékadó utasítás:

azonosító:=kifejezés
LET azonosító=kifejezés

Olvasó utasítás:

Be: azonosítók
INPUT PROMPT "kérdés":vált.lista

Író utasítás:

Ki: kifejezések
Ki: szöveg
PRINT kifejezések
PRINT "szöveg"

Feltételes utasítás:

Ha log. kif. akkor ut.
IF log.kif THEN ut.

vagy

Ha log. kif akkor
  utasítássorok
Elágazás vége
IF log.kif THEN
  utasítássorok
END IF

vagy

Ha log kif. akkor
  utasítássorok
különben
  utasítássorok
Elágazás vége
IF log.kif THEN
  utasítássorok
ELSE
  utasítássorok
END IF

Várakozás:

Várj, amíg kell
DO
LOOP WHILE INKEY$=""

Ciklus:

Ciklus cv=kezd.-től vég.-ig
  utasítássorok
Ciklus vége
FOR cv=kezd. TO veg.
  utasítássorok
NEXT

vagy

Ciklus cv=kezd.-től vég.-ig lép-köz-ösével
  utasítássorok
Ciklus vége
FOR cv=kezd. TO veg. STEP lép.köz.
  utasítássorok
NEXT

vagy

Ciklus amíg log. kif.
  utasítássorok
Ciklus vége
DO UNTIL/WHILE log. kif.
  utasítássorok
LOOP

vagy

Ciklus
  utasítássorok
amíg log. kif.
Ciklus vége
DO
  utasítássorok
LOOP UNTIL/WHILE log. kif.

Eljáráshívás:

Tetszőleges magyar nyelvű mondat, amelyet később kifejtünk. Mögötte zárójelben megadhatók az eljárás paraméterei.
CALL eljárás(paraméterlista)

Eljárásdefiníció:

Eljárás név:
  utasítássorok
Eljárás vége
DEF eljárásnév(paraméterlista)
  utasítássorok
END DEF

Függvényhivatkozás:

Tetszőleges magyar nyelvű mondat, amelyet zárójelek között követnek a függvény paraméterei (kifejezések).
CALL eljárás(paraméterlista)

Függvény definíció:

Függvénynév (azonosítók):
  A fügv. ért. kiszámítása
  Függvénynév:=kisz. érték
Függvény definiálás vége.
DEF függvénynév(paraméterlista)
  utasítássorok
  LET függvénynév=kisz. érték
END DEF

Sokirányú elágazás:

Elágazás
  feltétel1 esetén
    utasítássorok1
  feltétel2 esetén
    utasítássorok2
  feltételn esetén
    utasítássorokn
Elágazás vége
SELECT CASE vált.
CASE kif1
  utasítások1
CASE kif2
  utasítások2
CASE kifn
  utasításokn
END SELECT

vagy

Elágazás
  feltétel1 esetén
    utasítássorok1
  feltétel2 esetén
    utasítássorok2
egyéb esetben
    utasítássorokn
Elágazás vége

SELECT CASE vált.
CASE kif1
  utasítások1
CASE kif2
  utasítások2
CASE ELSE
  utasításokn
END SELECT

Megjegyzés:

[ megjegyzés szövege ]
REM megjegyzés szövege
   vagy
! megjegyzés szövege

Vissza a könyvekhez