Számelméleti algoritmusok
írta: Rozgonyi-Borus Ferenc

Bevezetés

Az egyik első fennmaradt tízes számrendszerbeli számításokról szóló könyvet Al-Hvárizmi, Muhammad Ibn Músza (780?-850) perzsa-arab matematikus írta, melynek latin fordítása maradt fenn Algorithmi de Numero Indorum címmel. E munkájában szereplő eljárásokat neve latinra való felületes fordításából származóan algorithmusoknak nevezték el. A későbbiek folyamán ez az eltorzított név minden, valamely előírt módon és sorrendben végrehajtandó számolási eljárást jelentett. Ma már általánosabban használt fogalom: az algoritmus egyértelműen meghatározott műveletsort jelent, amely feladatok vagy feladatcsoportok megoldására alkalmazható. Egy algoritmus megadása esetén bizonyítanunk is kell, hogy az az adott feladat megoldását szolgáltatja. Erre általában a gyakorlatban - és ebben a dolgozatban is - a tapasztalatot elegendőnek fogadjuk el.

A matematikával való ismerkedés kezdetén mindenki tulajdonképpen algoritmusokat sajátít el, hogy ne kelljen fejben tartania például az összes számnevet vagy az alapműveletek eredményeit. Ekkor, öt-hat éves korban a szabályok azok, amelyek alapján a kisgyermek önállóan készít saját, testre szabott algoritmusokat. Később ez az önálló, spontán módon való algoritmuskészítő képesség háttérbe szorul, a készen kapott algoritmusok dominálnak. A tanulók többsége talán tanárai hibájából is gyakorlatilag elsorvasztja ezen algoritmusalkotó képességét. A számítástechnikán belül a programozás tanítása keretében pedig pont ezen képesség újbóli felélesztése lehet az egyik cél.

A számítástechnikát tanító tanárok az utóbbi időben megosztottak a programozás tanítása kérdésében. Az egyik csoport szerint a fejlett felhasználói programok minden igényt kielégítenek, nem szükséges programokat készíteni, a tanulóknak a felhasználást kell tanítani.

E tábor véleményem szerint a programozás tanítását azonosítja egy programozási nyelv tanításával. (Legrosszabb esetben a BASIC nyelvvel.)

Én a másik csoport álláspontját képviselem, mely szerint a programozás tanítása feltétlenül szükséges. A programozás tanítása a számítógépes problémamegoldás tanítását jelenti számukra. E csoport szerint sem szabad elhanyagolni a felhasználói ismeretek oktatását, az egyéb tárgyak oktatási-tanulási folyamatában betöltött szerepét pedig hasznos motivációként ki is kell aknázni.

Persze nem programozó képzést kell folytatni, hanem a programozáson keresztül az algoritmikus gondolkodással kell megismertetni a tanulókat.

Az önálló programozási gyakorlatokon egy problémát az ötlettől a teljes kivitelezéséig kidolgozva a sikerélményen túl a módszeres munkára való nevelés is megvalósulhat. Ehhez persze alaposan átgondolt, a tanár által már előre kidolgozott problémagyűjteménnyel kell rendelkezni.

Tapasztalat szerint egy probléma megértését, illetve új ismeret elsajátítását a programban való megvalósítás lényegesen jobban segíti, mint a hagyományos tanulási folyamat.

Szakdolgozatomban megpróbálok egy olyan főleg számelméleti feladatokból álló példagyűjteményt bemutatni, amely az algoritmikus gondolkodásra nevelés mellett a matematika tanár szempontjait is figyelembe veszi: olyan programozási feladatot adni a diákoknak, amely azonnali alkalmazást tesz lehetővé, és a középiskolai matematika tananyaghoz szorosan kapcsolódva, annak jobb elmélyítését, begyakorlását teszi lehetővé.

A dolgozatban igyekszem minimálisra korlátozni a programozás technikai megjegyzéseket, mivel nem ez a főcél, de néhol elkerülhetetlenül jelentkezni fog. A programok leírását külön nem közlöm, mivel ezek a lemezmellékleten forrásállományi formában megtalálhatóak. Az algoritmusok leírását egyrészt mondatszerű formában, másrészt a lemezen PASCAL nyelven is megadom, bőven kommentálva.

Az egyes algoritmusokhoz ugyan a dolgozatban nem mutatok be konkrét számpéldákat, de azokat soha ne hagyjuk el a programok tényleges ismertetése vagy megvalósítása előtt. Ez egyrészt az algoritmus megértését segíti, másrészt az önálló elemzőkészség kialakításához elengedhetetlen. (Az utóbbi időben a számítástechnikai versenyek szinte csak ezen képességet mérik.)

Az áttekinthetőbb programszerkezet, a szebb futási kép, és a biztonságos adatbevitel érdekében használom az általam készített RUTIN eljárásgyűjteményt. Ennek speciális utasításait a zárszóban röviden leírom.

A dolgozat olvasásakor célszerű, ha számítógépen a programokat megemlítésükkor le is futtatjuk.

A dolgozat egyes fejezetei végén található feladatsorok a tanulók önálló algoritmus elemző és készítő képességét hivatottak fejleszteni, ezek többnyire megoldhatóak a példák alapján, megvalósításukat külön nem közlöm.

Matematikai alapok felmérése

A különböző általános iskolákból középiskolába kerülő tanulók nagyon eltérő matematikai alapképzettséggel rendelkeznek. A tudásuk felmérésében minimális támpontot ad a bizonyítványukban szereplő érdemjegyük. Sajnálatos módon a négy alapművelet elvégzése fejben már tízes számkörben is komoly gondot okoz a tanulók majdnem felének. Ennek valószínű oka az alapműveletek begyakoroltságának alacsony szintje.

Sajnálatos módon a sorozatos tantervi kísérletek és reformok során ez a szerintem feltétlenül fontos, de monotonsága miatt unalmas tevékenység elmaradása szüli a tanulók legtöbb kudarcát. A számolási hiba miatt elrontott feladatok nem nyújtják azt a sikerélményt, amit a sok jó ötlet megérdemelne. Azaz nem a matematikai gondolkodás képessége hiányzik, hanem a jó gondolatok kivitelezési rutinja. Emiatt is fontosnak tartom a módszeres programozás megismerését.

Az eltérő begyakoroltsági szint felmérését és az esetleges hiányok pótlását hivatott az ALAPMUV.PAS nevű program elvégezni.

(A program egérrel kényelmesebben használható, de az nem szükséges hozzá feltétlenül.) A tanuló a programot önállóan használhatja gyakorlásra, vagy tudását mérheti fel vele, illetve ha nyomtatott formában kapja a feladatokat, akkor az elért szint tanári lemérésére is alkalmazható. A javításhoz a megoldó kulcsot egyből szolgáltatja.

Tapasztalatom szerint 1200-1500 gyakorlat megoldása a tanulókat eljuttatja egy alapvető automatizmusi szintre, ezután elenyésző mennyiségű hiba fordul elő a számolásaikban, jobban tudnak az adott feladatra koncentrálni. Mivel ezt a felmérést és begyakoroltatást az első osztályosokkal először jegy nélkül végzem, szinte azonnal tanévkezdéskor, az esetlegesen előforduló számítógéptől való óvakodás is könnyebben leküzdhető, mivel mint egy türelmes gyakorlótárssal találkoznak a géppel. A gyakorló üzemmódban előforduló hibákra adott üzenetek ugyan nem pótolják a tanári munkát, de némi segítséget adnak a tanulónak a hibák forrásának kiderítéséhez.

Az érettségi előtt álló tanulók számára nehezítésként 20-as számkört szoktam használni, nagyobb pontossági előírással.

Számolási algoritmusok

A számítógéppel megismerkedő tanuló számára a számítógépet többnyire mint tökéletesen hibátlanul dolgozó eszközt szoktuk bemutatni. Ez sajnos nem igaz. A számítógép és az ember számkezelése nem azonos. A kettő leginkább az egész számok területén fedi egymást, bár itt is igen jelentős a gép számára a korlátosság. Az igazán mellbevágó a különbség a valósnak nevezett számhalmazokban van. Az eltérés bemutatására a BUTAGEP.PAS programot szoktam használni.

A programban látszólag egyszerű dolgot csinálunk: hússzor kiszámítjuk az egyharmad értéket.Az n jelöli a 3-as számot, x a reciprokát, majd hússzor vesszük az n+1 x-szeresét és ezt 1-gyel csökkentjük, ez lesz az új értéke az x-nek. A mindenkori x értéket kiírjuk.

A programozásban járatlan felhasználó számára szinte elképzelhetetlen, hogy milyen súlyos hibát okoz a gép belső számábrázolási pontosságából származó kerekítés, ha nem figyelünk rá. Tehát a jó algoritmus nem biztosítéka a jó programnak, a számítógép adottságait is ismernünk kell a probléma szabatos megoldásához. A már kész eljárások ismerete megkönnyítheti ezt a folyamatot.

Alap számolási algoritmusok

Al-Hvárizmi említett könyvében a tízes számrendszerbeli műveletek végrehajtására eljárásokat javasol. Emiatt sokan a tízes számrendszer megalkotójának is tekintik. Sajnos vagy szerencsére az általa javasoltak helyett az abakuszra épülő algoritmusok terjedtek el Európában. Ez sokáig gátat szabott a matematika köznapivá válásának, mivel igen bonyolult lépéssorokat kellett megjegyezni már az alapműveletek elvégzéséhez is.

Az igen gyakran előforduló hatványozásra szinte alkalmatlan is az abakusz, pedig igen gyakran előforduló számolási feladat. Kezdjük ezzel az ismerkedést. Magát a pozitív egész kitevős hatvány fogalmát a tanulók ismerik, de előszeretettel felejtik ki az 1-es kitevő esetét.

Definíció. Bármely valós szám első hatványa önmaga. Bármely valós számot, ha kitevője 1-nél nagyobb egész szám, annyiszor veszünk szorzótényezőül, ahányszor a kitevője mutatja.

A 0 kitevővel is érdemes már itt foglalkozni, hiszen gyakran előkerül számolási feladatokban.

Definíció. Bármely 0-tól különböző valós szám 0 kitevőjű hatványa 1.

A 00 definiálását néha elhagyják [1], én a 0 értéket szoktam tanítani függvénytani megfontolások alapján. A permanencia-elv szerint 1 is lehetne, erre a figyelmet érdemes felhívni. A hatványozásra vonatkozó azonosságokat általában jól ismerik, de az algoritmus kedvéért is érdemes átismételni.

Példa. Készítsünk tetszőleges valós számot nem negatív egész kitevőre emelő eljárást!

A hagyományos definíción alapuló ismételt szorzásokkal való hatványozás helyett sokkal elegánsabb és gyorsabb, ha Legendre algoritmusát alkalmazzuk :

1. ha a k kitevő 0, akkor kész, a hatvány értéke 1, vagy 0, ha az alap is 0 volt;

2. legyen az s segédváltozónk kezdőértéke 1;

3. ha a kitevő páratlan, akkor s-t szorozzuk meg az a alappal, és csökkentsük 1-gyel a k kitevőt, egyébként (ha a k kitevő páros), az alapot emeljük négyzetre és legyen ez az új a alap, a k kitevőt pedig felezzük el;

4. ha k > 0 akkor 3. pontban folytassuk, egyébként vége, az s értéke a keresett hatvány.

Az algoritmus megvalósítása a HATVANY.PAS program.

A hatványozás mellett a gyökvonás a másik gyakran elvégzendő számolás. A négyzetgyök és a köbgyök fogalma szerepel az általános iskolai tananyagban, általánosítása a feladatunk elsőként.

Definíció. Egy a nem negatív valós szám k-adik gyökén értjük azt a nem negatív valós számot, amelynek k-adik hatványa maga a szám.

A definíciót páros és páratlan kitevőre külön is szokás kimondani, mivel általánosabban használható abban a formában. Feladatok megoldása kapcsán viszont most is célszerű kitérni a kettő alapja közti különbségekre.

Példa: Készítsünk k-adik gyökvonást elvégző eljárást!

A gyök pontos meghatározása általában nem szükséges a véges számolási pontosság miatt. Ezért valamilyen közelítő módszert szokás alkalmazni, amelynek a kívánt pontosságát előre megadjuk.

A binomiális tételt felhasználhatjuk az iterációs módszer alapjául. Ismeretes, ha , akkor képlettel számítható. Ezt felhasználva eljuthatunk a Newton-féle algoritmushoz:

illetve

közelítő formula alkalmazható. Az indiai Árjabhatta (476-550?) már említi a módszert könyvében, a négyjegyű függvénytáblázatban is megtalálható k = 2,3 esetekre. Gyakorlatilag az általánosítás ezek alapján is megtörténhet, ekkor az elkészített program igazolhatja sejtésünket.

Érdemes felhívni a figyelmet arra, hogy a kapott képlet tulajdonképpen egy középérték számítást ír elő, amelyből nagy előnyként a folyamatos közelítés származik. Ez igazolható a számtani és a mértani közép közti összefüggés alapján.

Érdemes az algoritmus elemzése folyamán az iterációs lépések számát figyelni, illetve azt, hogy a lépésszámtól hogyan függ a pontosság, s mekkora a maximális gépi pontosság. Ehhez felhasználhatjuk a számítógép beépített függvényeit is.

Az algoritmus tehát a következő:

A k kitevő és az A alap értékének beolvasása után

1. legyen x0:=1 és x1:=A az alappal;

2. ha , akkor x1 a gyök, és vége;

3. legyen x0:=x1;

4. számítsuk ki a képlettel az új x1-et :

5. vissza a 2. lépésre.

A számolást a GYOKVONO.PAS program végzi el, a fenti képlet alapján legalább 10-8 pontossággal adja meg a gyök értékét.

Példa. Készítsünk binomiális együtthatót kiszámoló eljárást!

Maga a feladat egyszerűnek tűnhet, ha ismert az kiszámítási módja :

Ha tehát készítünk egy faktoriális számolást végző rutint, akkor a feladatot ezek osztásával megoldottuk. A faktoriális fogalmát általában ismerik a tanulók, jóllehet a definiálásakor a speciális esetekről rendre elfelejtkeznek.

Definíció. Az első n pozitív egész szám szorzatát n faktoriálisnak nevezzük, és n! jellel jelöljük. Továbbá megállapodunk abban, hogy 1!=1 és 0!=1.

A megállapodások indoklását a diákok már szinte önállóan is képesek elvégezni, ha a permanencia-elvet ismerik. Sajnos azonban így a már viszonylag kis binomiális együtthatók sem számolhatóak ki az egész számok belső ábrázolásából származó korlátok miatt. Átalakítást kell a képleten végeznünk:

Sajnos ez sem teljes megoldás, mivel például kiszámolható így, de már nem!

A szorzásnál fellépő túlcsordulás elkerülése érdekében a szorzást és az osztást felváltva kell végeznünk:

Most viszont a képletből származóan az együttható értéke nem egész szám lesz, a kapott értéket kerekítenünk kell. A számolási hiba jóllehet halmozódik, de azért nem olyan nagy, hogy az egyszerű kerekítés ne lenne elegendő.

Más lehetőség is van. Felhasználhatjuk a binomiális együtthatók közötti összefüggéseket. A legegyszerűbb a Pascal-háromszöget alkalmaznunk, hisz itt a szorzás elkerülhető. Az alábbi összefüggést használjuk fel tehát:

Az algoritmus megvalósításában kiszámítjuk a Pascal-háromszög összes elemét a fenti összefüggés alapján, felhasználva, hogy a szélelemek mindegyike 1, majd utána adjuk meg a keresett binomiális együttható értékét.

A két algoritmust a BINOM.PAS program mutatja be.

Feladatok

Feladat. Alakítsuk át a hatványozást elvégző algoritmust úgy, hogy racionális szám kitevőjű hatványt is számoljon ki!

Feladat. Alakítsuk át úgy a gyökvonó algoritmust, hogy az írja ki minden lépés után a kapott közelítő értéket, illetve annak hibáját!

Feladat. A gyökvonó algoritmusban cseréljük ki a 4. lépés képletét

összefüggésre. Vizsgáljuk meg, mennyiben tér el a két algoritmus egymástól!

Feladat. Hogyan lehetne elkerülni a gyökvonó eljárásban a nagy alap esetén előforduló túlcsordulást a hatványozásban? Módosítsuk a programot!

Feladat. Trianguláris számoknak nevezzük az (ahol az n = 2,3,...) alakban írható természetes számokat. Készítsünk programot, mely ezeket a számokat állítja elő!

Feladat. Keressük meg azokat a természetes számokat, amelyekre (n-1)!+1=n2.

Oszthatóság

A számelméleti feladatok igen jelentős csoportját alkotják az alapműveletekkel kapcsolatos kérdések eldöntése. Az első osztályban a halmazelméleti alapfogalmak után az egész számkörben elvégezhető műveleteket és azok tulajdonságait szokás tanítani.

Az osztás művelet és az oszthatósági reláció közti különbség felismerése problémát szokott okozni, ha nem megfelelő formában definiáljuk az oszthatóságot.

Definíció. Az a egész szám osztója a b egész számnak, illetve a b többszöröse az a-nak, ha található olyan egész szám, amellyel a-t megszorozva b-t kapjuk.

Ezen definíció szerint nem kell tudnunk elvégezni az osztást az adott számkörben, s nem fontos az a szám, amellyel az osztót szorozni kell, csak a létezése a lényeges. Ennek elfogadása a matematikában jártasabb tanulók számára tapasztalataim szerint nehezebb. A 00 értelmezés viszont a harmadik osztályban jelentős szerepet kap a mértani sorozat meghatározásában.

Prímszámok

Ezen definíció után a prímszám meghatározása a következőképpen hangzik:

Definíció. Prímszámnak nevezzük azt a pozitív egész számot, amelynek pontosan két pozitív egész szám osztója van.

A tipikus definiálási mód az szokott lenni, hogy olyan szám, amelynek csak az 1 és önmaga az osztója [2], így a fenti oszthatósági definíció szerint csak az 1 és a -1 lenne prímszám. Ez általában meglepi a diákokat. Érdemes eljátszani a prímszám definíciójával úgy, hogy a jelzőket rendre elhagyjuk, és megvizsgáljuk milyen számhalmazt kapunk.

Példa. Döntsük el egy adott számról, hogy prím-e !

Az alapötlet a megvalósításra igen kézenfekvő: meg kell nézni, hogy az adott szám osztható-e a 2,3,4,... egészekkel, vagy sem.

E feladat kapcsán már célszerű az algoritmus hatékonyságát vizsgálni. Nagy szám esetén a programunk lassú lesz, ha minden számot végig kell vizsgálnunk 2-től az adott számig. A gyorsítás érdekében szinte azonnali javaslat, hogy csak a szám feléig végezzük a vizsgálatot. Nehezebb felismerés, hogy az összetett számok osztópárja közül az egyik nem nagyobb a szám gyökénél, tehát elegendő a vizsgálatot az adott szám négyzetgyökéig folytatni. További észrevétel, hogy a 2-vel való oszthatósági vizsgálatot leválasztva, a többi páros számot kihagyhatjuk, tehát kettesével lépkedhetünk.

Ezen felismerések alapján készült a PRIM-E.PAS program, amelyen célszerű az észrevételek kihagyásával is futásidő vizsgálatokat végezni nagy prímek esetén.

Ha kíváncsiak leszünk arra, hogy adott intervallumon belül összesen hány darab prímszám található, akkor a fenti módszer általában lassúnak bizonyul. Az intervallum megválasztása erősen befolyásolhatja az algoritmusunkat. Ha az összes prímszámot keressük 1-től N-ig, akkor a legismertebb módszer az Eratoszthenész prímszám-szitája.

Példa. Határozzuk meg 1-től adott N számig az összes prímet!!

A klasszikus módszer szerint felírjuk 1-től N-ig a számokat, majd

1. kihúzzuk az 1-et, mivel nem prím;

2. bekarikázzuk a következő számot, amit még nem húztunk ki, ez már prím lesz, a p;

3. ha a talált , akkor a még át nem húzottakat mind bekarikázzuk, mivel prímek és vége az eljárásnak;

4. kihúzzuk a p összes valódi többszörösét N-ig;

5. a 2. lépésre ugrunk.

Általában valamilyen tömböt szokás használni, amelynek mérete megegyezik az N maximális értékével, és e tömb elemei IGAZ vagy HAMIS logikai értékek, hogy prím-e vagy sem az illető indexének megfelelő szám. Az így definiált tömb [3] mérete nem lehet tetszőlegesen nagy a számítógép véges memóriája miatt! A tanulók számára ez elég szokatlan.

Az algoritmus azért tovább javítható az alábbi észrevételekkel:

a kettőn kívül nincs másik páros prím, tehát a páros számokat kihagyhatjuk;

a többi ( páratlan ) prím páratlan számú többszöröseit elegendő kihúzogatni;

az indexeléssel ügyesen dolgozva elegendő a páratlan számokat felírni, 2k+1-et a
k-adikként.

Ezen észrevételek alapján készült el a SZITA.PAS program.

Ha az intervallum nem 1-től kezdődik, akkor sajnos a szita elvének alkalmazása nehézkes, mivel bonyolulttá válik az első szitáló prím megtalálása, és a megelőző prímekkel ekkor is szitálnunk kell.

Példa. Keressük meg a prímszámokat adott intervallumban!

Az algoritmus legegyszerűbb változata, ha minden n számot megvizsgálunk az adott intervallumban, hogy prímszám-e.

Nyilvánvalóan n a 2 kivételével nem lehet páros szám, így a 2-vel való oszthatóságot nem kell ellenőrizni külön.

Az algoritmus tovább gyorsítható, ha észrevesszük, hogy hat egymást követő egész szám: 6k+5, 6k+6, 6k+7, 6k+8, 6k+9, 6k+10 (k egész) közül csak az első és a harmadik lehet prímszám, hiszen a többi 2-vel vagy 3-mal osztható. Tehát elegendő az n=6k+5 és n=6k+7 alakú számokat vizsgálni. Kivételt képeznek ekkor az 5-nél kisebb prímszámok.

Az észrevételek alapján készült a PRIMSOR.PAS program.

Érdemes 1-től 100 000-ig megkeresni a prímszámokat összehasonlításképpen a két programmal. Az utóbbi ugyan jóval lassabbnak bizonyul, de lényegesen magasabb felső korlátú és kisebb intervallumban gyorsabb. Jelentősen javítható az algoritmus, ha a prímszámokat egyszer meghatározva eltároljuk, és csak velük végezzük a vizsgálatot. Itt érdemes megjegyezni, hogy a ma ismert legnagyobb prímszám a Mersenne-prím, a 2756839-1, amelynek 227831 számjegye van. Ezt a számot 1992. március 26-án jelentették be. Az angliai Harwell Laboratóriumban egy CRAY-2-es számítógépen határozták meg. A futásidőről a közlemény nem tesz említést.

Példa. Keressünk ikerprímeket adott intervallumban!

A tanulók többsége az ikerprím fogalmat nem ismeri meg az általános iskolában, így elsőként ezt kell tisztáznunk:

Definíció. Ikerprímnek nevezzük azt a prímszámpárt, amely különbsége 2.

Az algoritmus legegyszerűbb változata, ha minden (n;n+2) szám pár esetén megvizsgáljuk az adott intervallumban, hogy mindkettő prímszám-e. Nyilvánvalóan n nem lehet páros szám, így a 2-vel való oszthatóságot nem kell ellenőrizni.

Az algoritmus tovább gyorsítható, ha alkalmazzuk az előbbi módon hatos csoportokban való vizsgálatot, és ha észrevesszük, hogy elegendő az n=6k+5 alakokat vizsgálni, ha az prím, csak akkor kell a lehetséges párt megnézni. Egyedüli kivétel a fentiek alól a (3;5) ikerprím pár.

Ez alapján készült az IKERPRIM.PAS program.

Máig el nem döntött kérdés, hogy véges vagy végtelen sok ikerprím van-e. Ez a probléma is igen hatékonyan használható fel motivációként a jobb képességű tanulóknál az önálló algoritmus tervezésre.

Legnagyobb közös osztó és legkisebb közös többszörös

Az általában ismert legnagyobb közös osztó és a legkisebb közös többszörös meghatározó módszerhez fel kell bontanunk a mindkét számot prímtényezőik szorzatára. Ehhez kapcsolódik alábbi példánk.

Példa. Bontsunk fel adott számot prímtényezői szorzatára!

Az algoritmus alapgondolata szerint ha megtaláljuk egy osztóját a 2-től kezdve a számnak, akkor avval addig kell osztanunk, míg lehetséges, s utána keresünk további osztót. Ezek az osztók biztosan prímszámok lesznek, hiszen a megelőző osztók a lehetséges többszörösöket kiszűrik. Ezt addig folytatjuk, amíg a maradék kisebb nem lesz, mint a soron lévő lehetséges osztó. Ezen gondolat alapján működik a FELBONTO.PAS program.

Lényegesen hatékonyabb módszer a legnagyobb közös osztó meghatározására, ha nem bontjuk fel a számokat, hanem alkalmazzuk Euklidész algoritmusát.

Példa. Határozzuk meg két szám legnagyobb közös osztóját!

Az eljárás pozitív egész számokra adott, így amennyiben a korábbi oszthatósági definíciót használjuk, vesszük az a és a b abszolút értékét, ha azok negatívok, majd

1. az a számot osztjuk b-vel, és meghatározzuk az m maradékot;

2. ha az m maradék 0, akkor a b a legnagyobb közös osztó, különben végrehajtjuk az a:=b és a b:=m helyettesítést;

3. az 1. pontot megismételjük.

Felhasználva azt a felismerést, hogy két szám legnagyobb közös osztójának és legkisebb közös többszörösének szorzata egyenlő a két szám szorzatának abszolútértékével, a legkisebb közös többszörös is megkapható.

Példa. Határozzuk meg két szám legkisebb közös többszörösét!

A két érték kiszámítását végzi el az EUKLIDES.PAS nevű program.

Tökéletes és barátságos számok

Számmisztikai jelentőségük miatt is érdekesek a tökéletes és a barátságos számok. Ezek meghatározása szinte ismeretlen a tanulók előtt:

Definíció. Tökéletes számnak nevezzük azt a természetes számot, amelynek a nála kisebb pozitív osztóinak összege maga a szám.

Példa. Keressünk adott intervallumban tökéletes számokat!

A hagyományos matematikai módszerekkel, kézzel ezek már nagyon nehezen határozhatóak meg. Ma ismert legnagyobb tökéletes szám a 2756838(2756839-1). Nikomakhosz (i.sz. 100 körül) kimondta, majd Euler később bebizonyította ugyan, hogy az összes páros tökéletes szám 2n(2n+1-1) alakú, ahol 2n+1-1 prímszám, de máig nem eldöntött kérdés, hogy létezik-e páratlan tökéletes szám vagy sem, ugyanis minden ismert tökéletes szám páros. Az viszont már kiderült, hogy nem lehet 10200-nál kisebb, mivel ezen értékig már átvizsgálták a páratlan számokat. Nikomakhosz ma sem igazolt sejtése szerint minden tökéletes szám 6-ra vagy 8-ra végződik.

E probléma kapcsán már érdemes felhívni a tanulók figyelmét arra, hogy a számítógép hogyan segítheti a matematikust sejtéseinek megfogalmazásában, illetve azok helyességének eldöntésében.

A TOKELET.PAS programban alkalmazott algoritmusban a szám osztóit keressük meg, az eljárás meggyorsítására az osztót és a komplementerét együtt határozzuk meg. Ekkor a négyzetszámokat külön meg kell vizsgálnunk. Az osztókat összegezve végül megvizsgáljuk, hogy megegyezik-e az összeg a számmal. Az algoritmusunkat tovább gyorsíthatjuk, ha elfogadjuk Nikomakhosz sejtését. Természetesen programunk a ma ismert 32 darab tökéletes szám közül csak a kisebbeket képes megtalálni.

A barátságos számok meghatározása is hasonló algoritmus alapján történik.

Definíció. Két pozitív egész szám barátságos, ha az egyik nála kisebb pozitív osztóinak összege megegyezik a másik számmal, és viszont.

Hagyományos módszerekkel már szinte reménytelennek tűnik ilyen számokat keresni. Az ókorban a püthagoreusok csak a (220;284) számpárt ismerték, Euler zsenialitását mutatja, hogy a korábban ismert 4 páron túl további 61 baráti számpárt határozott meg.

Példa. Keressünk barátságos számokat adott intervallumban!

Az algoritmus alapgondolata a tökéletes szám keresési módszerén alapul. Az eltérés gyakorlatilag az, hogy ha egy szám osztóinak összegét meghatároztuk, akkor megnézzük, hogy e szám osztóinak összege megegyezik-e a vizsgált számmal. A vizsgálatra csak akkor kerítünk sort, ha az összeg kisebb a számnál. Önmagában is érdekes feladat lehet eldönteni, hogy milyen nagyságú általában az osztók összege a számhoz képest.

Az algoritmust BARATSAG.PAS program valósítja meg.

Feladatok

Feladat. Keressünk olyan p prímeket, amelyekre a) p+10 b) p+14 c) p2+2 is prímszám!

Feladat. Mersenne-prímnek nevezzük a 2p-1 alakú prímszámot, ha p prím. Keressünk ilyen alakú összetett számot!

Feladat. Fermat-féle számoknak szokás nevezni a 22n+1 alakú számokat. Keressük meg közülük a prímszámokat! [4]!

Feladat. Négyesiker prímeknek nevezzük azokat a számokat, amelyekre p, p+2, p+6 és p+8 is prímszám. Keressünk adott intervallumban ilyen négyesikreket! Miért nem szerepel a sorban a p+4?

Feladat. Keressük meg az összes olyan n természetes számot, amelyekre az n+1, n+3, n+7, n+9, n+13 és n+15 számok mindegyike prímszám! Ha az utolsó feltételt elhagyjuk, akkor találunk-e további számot?

Feladat. Keressünk olyan n természetes számot, amelyre n2-3 osztható 1-nél nagyobb négyzetszámmal!

Feladat. Keressünk olyan természetes számot, ami után legalább 12 összetett szám következik!

Feladat. Keressünk olyan természetes számpárokat, amelyeknek az euklideszi algoritmusuk 2,3,... lépésből áll!

Feladat. Keressünk olyan természetes számpárt, amelynek legkisebb közös többszöröse egy adott d számmal nagyobb a legnagyobb közös osztónál! Milyen szám lehet a d?

Feladat. Keressük meg adott számig a legtöbb osztójú természetes számot!

Feladat. Erősen összetett számnak nevezzük azokat a természetes számokat, amelyek osztói száma több, mint bármely náluk kisebb természetes szám osztói száma. Készítsünk adott N-ig erősen összetett számot kereső programot!

Feladat. Határozzuk meg adott intervallumban, hogy a számok hány százaléka esetében kisebb a valódi osztók összege a számnál!

Feladat. Suryanarayana nevezte el nagyon tökéletesnek azt a természetes számot, amelyre teljesül, hogy az osztóinak összegének osztóinak összege a szám kétszerese. Keressünk ilyen számokat!

Feladat. Egy számot k-szorosan tökéletesnek nevezünk, ha a nála kisebb pozitív osztóinak összege a szám k-szorosa. Keressünk 2, 3, 4, 5-szörösen tökéletes számokat adott intervallumban! (Ez ideig nem találtak 7-nél nagyobb tökéletességű számot!)

Speciális számok

A speciális szám fogalma alatt valamilyen különleges tulajdonságú számot értünk. Ilyen számok keresési algoritmusai néha igen mély matematikai és programozási ismereteket igényelnek, ha azt akarjuk, hogy a gép gyorsan produkáljon eredményt. Ezek a feladatok viszont igen alkalmasak az oszthatósági gyakorlatok színesítésére.

Speciális számok keresése

Definíció. Egy természetes szám Thibault-féle, ha magát a számot és a négyzetét tízes számrendszerben felírva minden 0-tól különböző számjegyet pontosan egyszer használunk fel.

Példa. Keressünk Thibault-féle számokat!

Mivel minden számjegyet pontosan egyszer kell felhasználnunk hamar felismerhető, hogy a szám csak háromjegyű lehet és a négyzete hatjegyű. A számra ekkor már további megállapítások is kimondhatók:

és 987 közé kell esnie;

nem végződhet az 0,1,5,6 számjegyekre, mivel az ilyen négyzetszámok végződése megegyezik az alapéval;

ha van a számban egyforma jegy, akkor nem kell vizsgálnunk már a négyzetét.

További programozás-technikai probléma, hogyan döntjük el, hogy van-e számjegy ismétlődés. Ehhez segítségünkre lehetnek a számot szöveggé alakító eljárások. A két jegysort összeillesztve tulajdonképpen azt kell eldöntenünk, hogy az egy permutációja-e az 123456789 számnak. Ezt legegyszerűbben egy 9 elemű logikai változó tömb segítségével oldhatjuk meg: a tömb elemeit HAMIS-ra állítjuk, végighaladunk a kapott jegyeken, s amelyik szerepel, az annak megfelelő indexű elemet IGAZ-ra változtatjuk. Ha marad a tömbben HAMIS érték, akkor az a számjegy nem került felhasználásra, tehát nem permutáció a kapott jegysor.

Az algoritmust a THIBAULT.PAS program mutatja be.

A fogalom általánosítását a feladatok kapcsán tesszük meg.

Definíció. Egy háromjegyű természetes szám Armstrong-féle, ha jegyeit köbre emelve és összeadva magát a számot kapjuk.

Példa. Keressünk Armstrong-féle számokat !

A legegyszerűbb megoldás, ha a számot jegyenként előállítjuk, majd az egyenlőséget megvizsgáljuk.

Az ARM.PAS program mutatja be ezt a megoldást.

A feladat sokkal érdekesebb, ha a jegyszámot nem rögzítjük, illetve ha a kitevőt módosítjuk. Az általánosítási lehetőségekről többet a feladatok kapcsán szólunk.

A számelmélet fejlődésében Euler és Ramanudzsan kiemelkedő szerepet játszott. Hardy érdeme szintén meghatározó munkássága mellett, hogy felismerte Ramanudzsan tehetségét. Kettejük nevéhez fűződik a következő történet.

Mikor egyszer Hardy és Ramanudzsan Londonban taxin ment, Hardy a taxi távozása után vette észre, hogy aktatáskáját a kocsiban felejtette. Kéziratok lévén a táskában, ez kétségbe ejtette, de Ramanudzsan megnyugtatta, hogy a taxi száma 1729. Hardy igen örült ennek, de nem hagyta nyugodni a kérdés, hogyan lehetett megjegyezni egy ilyen érdektelen számot. Nem érdektelen ez a szám, felelte Ramanudzsan, ez a legkisebb olyan egész szám, amely kétféleképpen bontható fel két köbszám összegére!

Tiszteletükre szolgáljon a következő példa.

Példa. Keressük meg adott intervallumban a két szám köbösszegeként felírható számokat!

A megoldás alapgondolata: ha két szám köbének összege az adott intervallumba esik, akkor az összeget eltároljuk, majd kiválogatjuk azokat, amelyek legalább kétszer előfordulnak. Ez utóbbi rész teszi majd lassúvá főleg programunkat. Rendezési algoritmust alkalmazva programunk gyorsítható.

Az algoritmust a KETKOB.PAS program mutatja be.

Igen érdekes a tanulók számára Goldbach sejtése, amit 1742-ben tett : minden 6-nál nem kisebb egész szám felírható három prímszám összegeként. Euler javaslata szerint ezt elegendő lenne csak páros számokra bizonyítani, hisz abból már következne a páratlanokra is. Az első eredményt 1931-ben Snyirelman érte el ezen a téren : megmutatta, hogy minden természetes szám felírható 300000(!)-nél nem több prímszám összegeként. 1936-ban Ricci finomította a határt, bebizonyította, hogy 67 darab prím is elegendő. Majd 1937-ben Vinogradov megmutatta, hogy minden elegendően nagy páratlan szám előállítható 3 prím összegeként. Ez az elegendően nagy 3315! Ez akkora szám, hogy tulajdonképpen a sejtés ma sem igazolt, mivel nem végezhető el addig az ellenőrzés.

Példa. Adott intervallumban igazoljuk a Goldbach-sejtést páros számokra!

A feladat megoldásához célszerű a prímszámokat előre előállítani. Ezt a prímszámszitával megtehetjük. Majd a számok vizsgálatát az alábbi észrevételek alapján végezni:

mindhárom nem lehet páratlan, azaz elegendő csak két páratlan prímet keresni a 6-nál nagyobb számokra;

a felbontásban szereplő legnagyobb prím nem kisebb a szám felénél 8-tól kezdve;

az ikerprímek ismerete gyorsít az eljáráson.

Az algoritmust a GOLDBACH.PAS program mutatja be.

Feladatok [5]

Feladat. Keressük meg azokat a háromjegyű számokat, amelyeknek számjegyeiből képzett számok faktoriálisainak összege vagy szorzata megegyezik a számmal

Feladat. Keressünk olyan számokat, amelyekre a számjegyek négyzetösszege egyenlő magával a számmal!

Feladat. Keressünk olyan számokat, amelyek négyzete azonos a szám kétszeri leírásával kapott számmal!

Feladat. Keressünk olyan általános Armstrong-féle számot, amelynek ha jegyeit a) négyzetre b) köbre emeljük és összeadjuk, magát a számot kapjuk!

Feladat. Keressük meg azt a legkisebb természetes számot, amelynek utolsó jegyét törölve, de egyidejűleg a többi számjegy elé átírva az eredeti szám négyszeresét kapjuk!

Feladat. Keressünk olyan természetes számokat, amelynek jegyei az 1234567890 szám jegyeinek permutációja, és valamilyen hatvány!

Feladat. Keressünk olyan számokat, amelyeknek négyzete azonos két, illetve három jegyre végződik az alappal!

Feladat. Keressünk olyan számokat, amelyekre teljesül, hogy a rákövetkezőket utánuk írva négyzetszámot kapunk!

Feladat. Keressünk olyan prímszámokat, amelyek egyszerre összegei és különbségei két prímszámnak!

Feladat. Keressünk olyan n>1 természetes számot, amelyre az 1-től n-ig terjedő természetes számok négyzeteinek összege valamely szám négyzete!

Egyenletek megoldása

Egész együtthatós egyenletek megoldása az egész számhalmazon gyakran előforduló feladat. A számítógép ezek megoldásában tud talán legbiztosabban segíteni.

Diophantikus egyenlet

Egy klasszikus feladat fűződik Euler nevéhez.

Vásárolni akarunk kereken 100 aranyért pontosan 100 állatot: sertést, darabja 3 és fél arany, kecskét, darabja 1 és egyharmad arany és juhot, darabja fél arany. Hány darabot vegyünk meg az egyes állatokból?

Példa. Oldjuk meg Euler feladatát!

A feladat megoldására szinte kínálkozik a három egymásba ágyazott ciklussal való keresés gondolata, azaz minden eset kipróbálása. De ez nagyon időigényes, főleg ha arra gondolunk, hogy meddig futna a programunk, ha 1000 állatot kellene vásárolnunk például 1386 aranyért!

Mindenféleképpen célszerű a feladatunkat átgondolni.

A szöveg alapján két egyenletet írhatunk fel:

és 21x+8y+3z=600

ahol x a sertések, y a kecskék és z a vásárlandó juhok számát jelenti.

az első egyenlet alapján máris látszik, hogy a z kifejezhető x-szel és y-nal : z=100-x-y;

x nem lehet nagyobb 600/21-nél, és az y 600/8-21x-nél;

Ezeket az észrevételeket figyelembe véve készült el az EULER.PAS program.

Persze ez a módszer jóval lassabb, mint a diophantikus egyenletek algebrai megoldása. A feladatot és ezen megoldását a módszerek bevezetéseként szoktam felhasználni. A fejezet feladatai között számos további példa található.

A nagy Fermat-tétel kiterjesztései

A matematikatörténet talán egyik legérdekesebb és legtöbb bizonyítási kísérletet megélt problémáját vetette papírra Fermat akkor, amikor egy Diophantosz eredményeit tárgyaló könyv egyik feladata mellé - egy négyzetszám két másik négyzetszám összegére bontandó - a következő megjegyzést írta. "Teljesen lehetetlen egy köböt két köbre, egy negyedik hatványt két negyedik hatványra, és általában a négyzeten kívül egy hatványt ugyanolyan kitevőjű két hatványra bontani. Erre én egy valóban csodálatos megoldást találtam, de a lapszél túl keskeny ahhoz, hogy befogadja." Ez az ún. nagy Fermat-tétel tehát azt állítja, hogy az xn+yn=zn egyenletnek nincs megoldása a 0-n kívül a természetes számok halmazán, ha n kettőnél nagyobb. Később a bizonyításról Fermat már nem tesz említést. Euler belátta n=3 és n=4, majd később Legendre az n=5 esetre. Az 1908-ban kitűzött 100000 márka pénzjutalom hatására a göttingeni Akadémiára több ezer bizonyítási kísérlet érkezett. Ma igaznak tudott a tétel, ha n<30000.

Euler a tétel alapján egy sejtést fogalmazott meg: n darab n-edik hatvány kell ahhoz, hogy összegük újra n-edik hatvány legyen! Igazoljuk n=3 esetre a sejtést!

Példa. Keressük meg az x3+y3+z3=t3 egyenlet megoldásait adott intervallumban!

Algoritmusunk igen egyszerű: előállítjuk az összes (x;y;z) számhármast az adott intervallumban, majd megvizsgáljuk, hogy köbeik összege is köbszám-e. Az algoritmust a FERMAT3.PAS program tartalmazza.

Igen meglepő, hogy a feladatnak megoldása a (3;4;5;6) számnégyes! Sajnos ez már nem általánosítható az n=4 esetre sem.

Euler sejtését 1966-ban megdöntötték egy ellenpéldával: találtak pozitív számötös megoldást az x5+y5+z5+t5=w5 egyenletre. Az ellenpéldát feladatként keressük meg.

A Pitagorasz-tétel másik általánosítási irányát Waring angol matematikus 1770-ben indította el. Sejtése szerint minden k hatványhoz található egy tőle függő K szám, hogy minden természetes szám előállítható legfeljebb K számú k-adik hatvány összegeként. Hardy K számra megfogalmazott sejtése a 4k érték. A Waring-problémát 1945-ben elemi módszerekkel megoldotta Linnik. Lagrange bebizonyította, hogy bármely természetes szám felírható négy négyzetszám összegeként. Ez alapján könnyen megoldhatjuk az alábbi problémát.

Példa. Keressük meg az összes olyan természetes számot, amely nem írható fel 5 pozitív egész szám négyzetének összegeként!

Állításunk ugyan gyengébb, mint Hardy sejtése, de lényegesen könnyebb így a probléma. Ahhoz, hogy az összes ilyen számot biztosan megtaláljuk, meg kell mutatnunk, hogy ezek biztosan kisebbek egy konkrét M számnál. Használjuk fel a "négy négyzetszám tételt"! Ha találunk egy olyan négyzetszámot, amely felbontható kettő, három illetve négy négyzetszám összegére is, akkor készen vagyunk a következők miatt:

Tegyük fel, hogy n>M szám esetén az n-M=a2+b2+c2+d2. Feltehetjük, hogy . Attól függően, hogy hány nulla van köztük kell az M-et felbontanunk négyzetek összegére. Mivel mind a négy nem lehet nulla, elegendő is az M-re tett feltétel. Ekkor tehát n = a2+b2+c2+d2+M alapján minden M-nél nagyobb szám felírható. A legkisebb ilyen M a 169:

169=132=52+122=32+42+122=12+22+82+102.

Az algoritmus most már egyszerű. Veszünk egy 170 elemű logikai változó tömböt, s minden értékét HAMIS-ra állítjuk. Az összes lehetséges számötöst előállítjuk, az előálló n-ekkel megegyező indexű elemeket IGAZ-ra állítjuk át. Ami HAMIS maradt, az nem bontható fel. Itt jegyzem meg, hogy a számhoz a felbontásának megkeresése sokkal több időt venne igénybe! Az algoritmus még tovább gyorsítható, ha az ötösök előállításánál figyelembe vesszük a határok megadásánál a már kiválasztott előző számokat.

Az algoritmust a NEMBOMLO.PAS program valósítja meg.

Feladatok

Feladat. Valaki a következőket mondja: születési évszámom számjegyeinek összege annyi, ahányadik életévemet 1968-ban betöltöttem. Mikor született az illető?

Feladat. Hányféleképpen lehet felváltani egy 20-ast 1-es, 2-es és 5-ös pénzdarabokra?

Feladat. Hányféleképpen lehet összerakni 100 forintot 1, 2, 5, 10, 20 és 50 forintos pénzértékekből?

Feladat. Egy 5 méter hosszú kerítés szegélyéhez 15, 20 és 93 cm hosszúságú lécek állnak rendelkezésre. Adjuk meg a legkevesebb darabból összeállított szegélyt!

Feladat. Keressük meg az x3+y3=z3+1 egyenlet legkisebb pozitív egész megoldását!

Feladat. Keressünk megoldását az x2+4=y3 egyenletnek.

Feladat. Keressünk két olyan természetes számot, amelyek külön-külön felírhatók három négyzetszám összegeként, de a szorzatuk nem!

Feladat. Határozzuk meg az x2+y2=z4 egyenlet egy megoldását!

Feladat. Keressük meg az

egyenlet összes olyan megoldását, melyre teljesül!

Feladat. Adjuk meg az x2-2y2=1 Pell-egyenlet összes megoldását adott intervallumban!

Feladat. Keressünk olyan természetes számötöst, amely megoldása az x5+y5+z5+t5=w5 egyenletnek! (Az Euler-sejtés ellenpéldája.) [6]

Feladat. Bontsuk fel adott intervallumban a természetes számokat négy természetes szám négyzetének összegére! (Hardy sejtésének próbája.)

Pi közelítési módszerek

A kör kerületének és átmérőjének arányát már az ókorban is pontosan szerették volna tudni. Műszaki jelentősége miatt a p értékének meghatározása régi feladata a matematikával foglalkozóknak. Mivel irracionális szám, a meghatározás pontossága lehet inkább a kérdés. Az ókorban kidolgozott geometriai közelítések után a végtelen sorokra és szorzatokra támaszkodó módszerek alakultak ki. Kezdetben a p közelítésére a = 3,1428571, a = 3,1622777, illetve néhol a = 3,1555556 volt használatos. A középkorban lánctörtekkel próbálták megközelíteni a pontos értéket. E korból származik az igen jó = 3,1415929 közelítés. Az újkorban jelentek meg a sorfejtések és a valószínűségi módszerek.

Végtelen összeggel és szorzattal való közelítés

Egyik végtelen összegen alapuló közelítés Leibniz nevéhez fűződik, noha valószínűleg James Gregory skót matematikus fedezte fel:

A másik nevezetes összegzés Euler-től származik:

Számítógépes módszerekkel a Leibniz-sorra építve több mint kétmillió jegy pontosságra ismert ma a p értéke.

A szorzaton alapuló módszerek közül szintén kettőt érdemes kiemelnünk.

Egyik a Wallis-összefüggés:

A másik az igen érdekes Vieta-összefüggés:

Ez utóbbi módszer az összes közül a leggyorsabban konvergáló. Gyakorlatilag 30 tag szolgáltatja a gépi értéket.

Példa. Készítsük el a pi közelítő eljárásokat!

A fenti négy számolási képlet alapján a PI.PAS program meghatározza adott tagszámra a közelítő értéket.

Véletlen módszerek

Igen érdekes volt számomra a következő programozási versenyen kitűzött példa:

Példa. Egy 2 egységnyi oldalú négyzetbe nyilat dobálunk célzás nélkül. A négyzet belsejében eltalált pontok közül összeszámoljuk azokat, amelyek a közepétől 1 egységen belül vannak. Elosztva az összes találatok számával a belül esőek számát mit kapunk eredményül?

A feladatot célszerű gyakorlatban néhányszor elvégezni 100-100 dobással. Én az osztálynak fel szoktam adni házi feladatként, s következő órán átlagoljuk a kapott eredményeket.

A feladatot először látva nem gondoltam, hogy pi-t közelítő eljárással találkoztam. Ezért elkészítettem DOBAL.PAS programot. Ebben a programban kirajzolunk egy 200 képpont oldalú négyzetet, majd véletlengenerátorral 100000 pont koordinátáját generáljuk. Ha a pont belülre esik, akkor pirossal kivilágítjuk a neki megfelelő koordinátájú pontot, valamint a jók számát 1-gyel növeljük. Ha kívül esik, akkor zölddel világítjuk ki a neki megfelelő pontot. Végül a hányadost kiírjuk. Nagyobb pontszám esetén, vagy a kapott értékeket átlagolva meglepően jó pi közelítést kaphatunk.

A geometriai valószínűség bevezetésére igen jó példának tartom.

A másik módszer a valószínűségszámítás egyik úttörőjének számító francia Buffon-tól származik, az úgynevezett tűprobléma.

Példa. A padlóra vonalakat rajzolunk egymástól egyenlő d távolságra. E távolságnál rövidebb, l hosszúságú tűt ejtünk a padlóra. Összeszámoljuk azokat a dobásokat, amelyek vonalra esnek, és elosztjuk az összes dobás számával. Mit kapunk eredményül?

Az algoritmus számítógépes szimulációja némileg bonyolultabb az előzőnél. A dobás szimulálásához nem elegendő csak a tű középpontjának koordinátáit generálnunk, hanem egy szöget is meg kell adnunk. Az így adódó tűhelyzeteket pirossal rajzoljuk ki, ha az vonalra esik, és zölddel, ha nem. Megmutatható, hogy a kapott p relatív gyakoriságra fennáll, hogy

Tehát ha 2l=d értéket választjuk, akkor éppen pi reciprokát kapjuk jó közelítéssel.

A BUFFON.PAS program szintén 100000 dobás elvégzését szimulálja.

Feladatok

Feladat. Készítsünk az alábbi összefüggés alapján pi közelítő eljárást:

Feladat. 1706-ban Machin francia matematikus adta meg az igen gyorsan közelítő alábbi sort:

Készítsünk eljárást, amely ez alapján dolgozik!

Feladat. Készítsünk programot, amely a kör kerületét a beírt szabályos sokszög kerületével közelíti! Ha az oldalszám megduplázásával végezzük a közelítést, akkor a kapott

összefüggés mellett próbáljuk ki az előbbi képletben az

helyettesítéssel kapottat is!

Feladat. Adott intervallumban válasszunk ki véletlenszerűen egész számokat. Számoljuk össze azokat az eseteket, amikor a két szám relatív prím, s osszuk el az összes kiválasztás számával. Az így kapott szám reciproka micsoda? (Csebisev feladata nyomán.)

Zárszó

Sajnálatos módon a 70-es évek eleje óta létező számítógéppel támogatott oktatás hazai elterjedése a mai napig sem történt meg. Csak azok próbálkoznak, akik a számítástechnikával szorosabb kapcsolatban vannak, mivel kész oktató programok kaphatóak ugyan, de azok vagy nem megfizethetők, vagy nem alkalmazhatóak magyar viszonyok között.

Tapasztalatom szerint a matematika tanárok többsége használná az órákon a számítógépet, ha ahhoz könnyen kezelhető, a tananyaghoz jól illeszkedő, és szabatos módszertani leírást tartalmazó programokat kapna. Ez utóbbi talán a legfontosabb ezen a területen. Remélem dolgozatom segíthet ebben és a matematikában való alkalmazás megismertetésében.

Az algoritmusok egy része nem a leghatékonyabb, mivel így könnyebben érthetőek. Másrészt nem tartom azokat a feladat- vagy programgyűjteményeket jónak, amelyek nem adnak lehetőséget a problémák továbbgondolására, a megoldások saját stílusra való formálására.

Az algoritmusok helyességének igazolását elhagytam. Ezt az igen fontos lépést csak a matematika és a számítástechnika iránt jobban érdeklődő tanulók számára szakkörön szoktam elvégezni. Az igazolási igény kialakítása és módszereinek megismertetése már az informatika tanításához kapcsolódik, s nem volt célja e dolgozatnak.

A programokban használt nem standard PASCAL eljárások rövid leírása a következő:

WriteXY(sor,oszlop,szöveg) : az adott (sor;oszlop) ponttól kezdi el a megadott szöveg kiírását

IntRead(azonosító) : beolvas védelemmel egy egész számot

LongRead(azonosító) : beolvas védelemmel egy hosszú egész számot

RealRead(azonosító) : beolvas védelemmel egy valós számot

Felhasznált irodalom

Sain Márton : Nincs királyi út! GK 1986

Sain Márton : Matematikatörténeti ABC TK 1977

A.P. Juskevics : A középkori matematika története GK 1982

Davis-Hersh : A matematika élménye MK 1984

Dr. Hámori Miklós : Tanulás és tanítás számítógéppel TK 1983

R. R. Skemp : A matematika tanulás pszichológiája GK 1975

Pólya György : A problémamegoldás iskolája TK 1985

Pólya György : Matematikai módszerek a természettudományban GK 1984

Csikós Zsolt : Számítógéppel Számországban Magánkiadás 1990

Dr. Perge Imre : A számítástechnika alapjai TK 1978

Gyapjas-Molnár-Hortobágyi : Elemi matematika I-V. TK 1991

Simonovits Miklós : Számítástechnika TK 1985

Borsányi-Hack : Matematika feladatgyűjtemény III. TK 1989

Appel-Kőhegyi-Zsakó : Számítógépes feladatok Interpress 1985

Telegdi Zsigmond : Bevezetés az általános nyelvészetbe TK 1984

Sárközy-Surányi : Számelmélet feladatgyűjtemény TK 1991

Lőcs Gyula : A BASIC és a Kíváncsi TK 1986

W. Sierpinski : 200 feladat az elemi számelméletből TK 1972

Obádovics J. Gyula : Gyakorlati számítási eljárások GK 1972

Turán Pál : Egy különös életút MatTan LV/2. 1977

Csirmaz-Simonovits : Algoritmusok I-II MatTan XXIX/2-3. 1982

Megyesi László : Tökéletes számok Polygon II/1. 1992


Footnotes

[1]Például Hajnal Imre : Matematika I. gimnáziumi tankönyv

[2]Sajnos jó pár iskolában ezt tanítják minden további kiegészítés nélkül.

[3]További memória-megtakarítás érhető el, ha az IGAZ-HAMIS logikai értékeket 0-1 bittel tároljuk a memóriában.

[4]GAUSS mutatta meg, hogy ezek éppen a szerkeszthető prímszámoldalú sokszögek

[5]Néhány feladat esetén bizonyíthatóan nem létezik a keresett szám!

[6]A számítást 8B hosszú egészekkel vagy legalább 15 jegy pontossággal végezzük!