Programozás | Programozás-elmélet » Rozgonyi-Borus Ferenc - Számelméleti algoritmusok

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 képlettel számítható. Ezt felhasználva eljuthatunk a Newton-féle algoritmushoz: , akkor

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 FELBONTOPAS 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 (isz 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 kszorosa 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 FERMAT3PAS 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 Eulersejté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ó újkorban jelentek meg a sorfejtések és a valószínûségi

módszerek. = 3,1415929 közelítés. Az 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!