Mert programozni jó! 2. rész
Abonyi-Tóth Andor
2005/02/23 13:01
1262 megtekintés
A cikk már legalább egy éve nem frissült, az akkor még aktuális információk lehet, hogy mára elavultak.
Sorozatunk előző részében a Nemes Tihamér programozói verseny feladataival foglalkoztunk. E cikkünkben a programkészítés egyik buktatóját mutatjuk be, amely nagyon sok kezdő programozó életét keseríti meg.

A probléma bemutatására egy igen egyszerű feladatot adunk meg: Készítsünk programot, amely egy háromszögről a három oldalának ismeretében meghatározza, hogy derékszögű-e a háromszög! A feladat megoldásához a Pitagorasz-tétel ismerete kell, azaz ha egy háromszögben a leghosszabb oldal négyzete egyenlő a másik két oldal négyzetének összegével, akkor a háromszög derékszögű.

Derékszögűség vizsgálata

A megoldás Pascal nyelven igen gyorsan megadható, ha feltesszük, hogy az oldalakat növekvő sorrendben adatjuk meg.

program pitagorasz;
var
  a, b, c :integer;
Begin
 WriteLn('Add meg a három oldalt szóközzel elválasztva, növekvő sorrendben: ');
 ReadLn(a,b,c);
 if a*a+b*b=c*c
   then WriteLn('Derékszögű háromszög')
   else WriteLn('Nem derékszögű háromszög');
 ReadLn;
End. program pitagorasz;
var
  a, b, c :integer;
Begin
 WriteLn('Add meg a három oldalt szóközzel elválasztva, növekvő sorrendben: ');
 ReadLn(a,b,c);
 if a*a+b*b=c*c
   then WriteLn('Derékszögű háromszög')
   else WriteLn('Nem derékszögű háromszög');
 ReadLn;
End.

Az elkészített program remekül működik, ha a mindenki által ismert 3, 4, 5 számhármassal teszteljük. De ha az oldalakat nagyobbnak szeretnénk választani, például 3000, 4000, 5000 hármassal vizsgáljuk a programunkat, akkor már nem ad helyes eredményt a program.

Az ok persze nyilvánvaló: az integer adattípus nem akármekkora egész szám tárolására alkalmas, -32 768 és 32 767 közötti előjeles egész számok tárolására szolgál, tehát nem meglepő, hogy az 5000 négyzete túlcsordulást okoz, és a futtató rendszer beállításaitól függően vagy túlcsordulási hibával leáll a programunk, vagy hibás eredményt ad: nem derékszögűnek minősíti a háromszöget.

A megoldást szinte hallom: a változókat integer helyett real típusnak adjuk meg, amit az is indokol, hogy nem csak egész szám hosszúságú lehet egy háromszög oldala.

A gondolat remek, pontosabban csak annak tűnik! Az eddig kiváló programunk most már átmegy az ezres teszten, de a kegyetlen valóság azt mutatja, hogy a törtekkel még így sem tud megbirkózni: a programunk a 0,3 0,4 0,5 érték esetén elvérzik, ami valljuk be, csúfos.

Az ok persze nem bennünk keresendő, hanem szegény Leonardo Torres y Quevedo (1852-1936) a hibás, aki kitalálta közel száz éve a lebegőpontos számábrázolást. Most persze mondhatjuk, hogy nem véletlen, hogy a nevét az ismeretlenség homálya fedi, mert így legalább kevesebben emlegetik eme "baklövése" miatt.

Pedig inkább hálásnak kell lennünk, mert nem ő hibázott, hanem mi!

A számítógép - kis túlzással - a görögök fénykorában uralkodó számfogalmat tartja napjainkban is életben. Az egészekkel több-kevesebb sikerrel, de jól boldogul, a valós számoktól viszont irtózik: egyszerűen a számok tárolására előre meghatározott típusokban nem lehet irracionális számokat tárolni, de még a racionális számok is csak igen foghíjasan tárolhatóak.

1/3-ból 1

A 0,3 és a 0,4 például igen szép és egyszerű számnak tűnik, de csak tízes számrendszerben, mindkettő szám kettes számrendszerben végtelen szakaszos kettedes tört: 0,3=0,01000111  és a 0,4 = 0,001100. Ezeket az értékeket a számítógép persze nem az előbbi módon, hanem csak bizonyos számú kettedes jegy pontossággal tudja ábrázolni. Hogy ezt a számítógépünk hány jegyig, és milyen módon kezeli, azt a következő kis programmal meg tudjuk vizsgálni!

Írjunk programot, amely az alábbi műveletsort végzi el:


legyen x 1/3
ismételjük meg 22-szer
            írassuk ki az x értékét
            legyen x 4x -1

A matematikában járatlan olvasók is szerény mosollyal néznek a folytatás elé: a világrengetőnek beharangozott programocska húszszor fogja kiírni az 1/3 értéket, mármint sejtésük szerint. Szerintük, és szerinted is, kedves Olvasó?

A programterv nem sok variációt enged, íme az egyik legvalószínűbb megoldás:

program buta_gep;
var
  i : integer;
  x : real;
Begin
  x:=1/3;
  for i:=1 to 22 do
    begin
      WriteLn(i:2,'. x=',x:1:12);
      x:=4*x-1;
    end;
  ReadLn;
End. program buta_gep;
var
  i : integer;
  x : real;
Begin
  x:=1/3;
  for i:=1 to 22 do
    begin
      WriteLn(i:2,'. x=',x:1:12);
      x:=4*x-1;
    end;
  ReadLn;
End.

A futás eredménye egy Pentium 4-es gépen így néz ki, Turbo Pascal 7.0-ás rendszerben:

Ha nem pont ezt látjuk saját gépünkön, nem baj, például Free Pascal futtatóval Intel Celeron processzoron 0 adódik végeredménynek 27 lépésben.

Okok

E két, némileg sokkoló hatású szösszenet után az okokat is fel kell tárnunk. A valósnak nevezett számok a valóságban legtöbbször nem ábrázolhatóak teljes matematikai igényességgel a számítógépben, a legtöbb szám csak közelítőleg kerülhet tárolásra. Ez a hiba az esetek többségében nem okoz gondot, viszont utóbbi programunkban minden lépésben a 4-gyel való szorzás miatt az ábrázolás pontosságát két kettedes jeggyel csökkentjük. A 22 lépés így azt jelentheti számunkra, hogy 44 kettedes jegy szolgál a real típusban a mantissza ábrázolására, pontosabban ezt a pontosságot lehet elérni az 1/3 esetében, és emiatt lesz csak 1 az 1/3 értékből 22 lépésben.

A most taglalt sajátosság következménye az első programunk hibájának is. A program elkészítése során egyszerűen nem vettük figyelembe a kerekített ábrázolást, amelynek hibáját a négyzetre emelés még tovább fokozza, és emiatt a feltételnek megadott egyenlőség szinte csak a szerencse révén jön létre.

A profi programozó - kis túlzással - real típusú változók esetén soha nem ad meg egyenlőséget, hanem ehelyett a két oldal eltérését vizsgálja valamilyen pontossággal. Ez a pontosság erősen függhet a feladattól, esetünkben a 10-10-en biztosan elegendő lehet, mivel a hossz mérése tíz értékes jegyre értelmes, ha fizikusszemmel nézzük.

program pitagorasz;
var
  a, b, c : real;
Begin
 WriteLn('Add meg a három oldalt szóközzel elválasztva, növekvő sorrendben: ');
 ReadLn(a,b,c);
 if abs(a*a+b*b-c*c)<1e-10
   then WriteLn('Derékszögű háromszög')
   else WriteLn('Nem derékszögű háromszög');
 ReadLn;
End. program pitagorasz;
var
  a, b, c : real;
Begin
 WriteLn('Add meg a három oldalt szóközzel elválasztva, növekvő sorrendben: ');
 ReadLn(a,b,c);
 if abs(a*a+b*b-c*c)<1e-10
   then WriteLn('Derékszögű háromszög')
   else WriteLn('Nem derékszögű háromszög');
 ReadLn;
End.

A program persze nem alkalmas a matematikusok meghatására, nehezen győzhetnénk meg vele őket arról, hogy mennyire alkalmas eszköz a számítógép matematikai problémák megoldására.

A házi feladat most sem marad el

Készítsünk programot, amely meghatározza a p értékét 6 tizedesjegy pontossággal két szám arányaként, azaz racionális számformában.

A feladat megoldásához táblázatkezelőt is használhatunk, mint azt a következő cikkünkben látni is lehet.

Jó munkát kívánunk, és a megoldásokat az info-rovat@sulinet.hu címre várjuk pi tárggyal.

Módszertani ajánló

tantárgy informatika
témakör programozás, emelt szintű érettségi
évfolyam/korosztály 8-12. évfolyam
módszer Példaprogramon keresztül a számábrázolás problémáinak ismertetése
idő 45 perc
célok Az érintett tanulók ismerjék meg az alkalmazható problémamegoldási módszereket.
tanulási helyzet Az algoritmizálási és programkódolási alapismeretek után a megoldási stratégiák és azok lekódolásának megismerése.
szükséges kivetítő, használt nyelvi fordítók (Pascal)
szerző Rozgonyi-Borus Ferenc
cím http://www.sulinet.hu/tart/cikk/ae/0/25439/1

ABAX (Rozgonyi-Borus Ferenc)
 

Csatlakozz hozzánk!

Ajánljuk

European Schoolnet Academy Ingyenes online tanfolyamok tanároknak
School Education Gateway Ingyenes tanfolyamok és sok más tanárok számára
All you need is code Minden a kódolás tanulásához
eBiztonság Minősítés Minősítési rendszer oktatási intézményeknek