Az tárgyalt algoritmusok leírását a legtöbb esetben rövid JavaScript programokkal is bemutatjuk. A példák kipróbálásához felhasználható online JavaScript interpreter:
A folyamatábra a 'for' ciklust nem megfelelően ábrázolja, ezért érdemes ezeket mindig átírni 'while' ciklusra, mielőtt megjelenítenénk a program folyamatábráját.
Példák algoritmusokra:
1. bináris szám átalakítása decimális számmá⇒
Szótár:
– bináris számok = kettes számrendszerbeli számok
– decimális számok = tízes számrendszerbeli számok
Példa: 11012 = ?10
az átváltandó kettes számrendszerbeli szám (pl. 1101) minden számjegyét megszorozzuk a szám helyi értékével
balról az első számjegy 1, helyi értéke 23=8, tehát a szorzat 1*8=8
a következő számjegy 1, helyi értéke 22=4, tehát a szorzat 1*4=4
a következő számjegy 0, helyi értéke 21=2, tehát a szorzat 0*2=0
az utolsó számjegy 1, helyi értéke 20=1, tehát a szorzat 1*1=1
A fenti algoritmust megvalósító JavaScript program:
// bináris szám átalakítása decimális számmá
var x="1101";
writeln("Bináris szám: "+x);
writeln();
var d=0;
var helyiertek=1;
for(var i=1;i<x.length;i++) {
helyiertek*=2;
}
for(var i=0;i<x.length;i++) {
var sz;
if(x[i]=="1") {
sz=1;
}
else {
sz=0;
}
writeln(" Számjegy : "+sz);
writeln(" Helyi érték: "+helyiertek);
var r=sz*helyiertek;
writeln(" Részösszeg: "+r);
d+=r;
helyiertek/=2;
}
writeln();
writeln("Decimális szám: "+d);
writeln("__________");
A fenti JavaScript program egyszerűsített változata és ennek a folyamatábrája a következő:
// bináris szám átalakítása decimális számmá (ver 2.0)
var x="1101";
writeln("Bináris szám: "+x);
writeln();
var d=0;
var helyiertek=1;
var i=1;
while(i<x.length) {
helyiertek=helyiertek*2;
i=i+1;
}
i=0;
while(i<x.length) {
var sz;
if(x[i]=="1") {
sz=1;
}
else {
sz=0;
}
var r=sz*helyiertek;
d=d+r;
helyiertek=helyiertek/2;
i=i+1;
}
writeln("Decimális szám: "+d);
writeln("__________");
A fenti JavaScript programokban előforduló fontosabb programnyelvi szerkezetek rövid magyarázata megtalálható itt.
A bináris egész számokhoz hasonlóan tudjuk a bináris törtszámokat átváltani tizedestörtekké. A különbség csak az, hogy a törtszámok helyiértékei 2 negatív egész hatványai lesznek (a 2−1=1/2 helyiértéktől kezdődően).
Elég csak olyan számokkal foglalkoznunk, amelyek pozitívak és 1-nél kisebbek (azaz egész részük zérus), mivel egy bináris szám egész részét és törtrészét külön-külön átalakíthatjuk decimális számmá.
Példa: 0.11012 = ?10
az átváltandó kettes számrendszerbeli szám (pl. 0.1101) minden számjegyét megszorozzuk a szám helyi értékével
balról az első számjegy 1, helyi értéke 2−1=1/2, tehát a szorzat 1*1/2=1/2
a következő számjegy 1, helyi értéke 2−2=1/4, tehát a szorzat 1*1/4=1/4
a következő számjegy 0, helyi értéke 2−3=1/8, tehát a szorzat 0*1/8=0
az utolsó számjegy 1, helyi értéke 2−4=1/16, tehát a szorzat 1*1/16=1/16
a kapott szorzatokat összeadjuk:
1/2+1/4+1/16= 8/16+4/16+1/16=
13/16
A fenti algoritmust megvalósító JavaScript program:
// hexadecimális szám átalakítása decimális számmá
// var x=["2","4","C"];
var x="24C";
write("Hexadecimális szám: ");
for(var i=0;i<x.length;i++) {
write(x[i]);
}
writeln();
writeln();
var d=0;
var helyiertek=1;
for(var i=1;i<x.length;i++) {
helyiertek*=16;
}
for(var i=0;i<x.length;i++) {
var sz;
switch(x[i]) {
case "a":
case "A": sz=10; break;
case "b":
case "B": sz=11; break;
case "c":
case "C": sz=12; break;
case "d":
case "D": sz=13; break;
case "e":
case "E": sz=14; break;
case "f":
case "F": sz=15; break;
default:
sz=parseInt(x[i]);
}
writeln(" Számjegy : "+sz);
writeln(" Helyi érték: "+helyiertek);
var r=sz*helyiertek;
writeln(" Részösszeg: "+r);
d+=r;
helyiertek/=16;
}
writeln();
writeln("Decimális szám: "+d);
writeln("__________");
A fenti JavaScript program egyszerűsített változata és ennek a folyamatábrája a következő:
// hexadecimális szám átalakítása decimális számmá (ver 2.0)
var x="24C";
write("Hexadecimális szám: "+x);
writeln();
var d=0;
var helyiertek=1;
var i=1;
while(i<x.length) {
helyiertek=helyiertek*16;
i=i+1;
}
i=0;
while(i<x.length) {
var sz;
switch(x[i]) {
case "a":
case "A": sz=10; break;
case "b":
case "B": sz=11; break;
case "c":
case "C": sz=12; break;
case "d":
case "D": sz=13; break;
case "e":
case "E": sz=14; break;
case "f":
case "F": sz=15; break;
default:
sz=parseInt(x[i]);
}
var r=sz*helyiertek;
d=d+r;
helyiertek=helyiertek/16;
i=i+1;
}
writeln("Decimális szám: "+d);
writeln("__________");
A fenti JavaScript program megvalósítható egymásba ágyazott if-else szerkezetekkel is.
Végezetül egy nagyon fontos programszerkezetet fogunk bevezetni.
A fenti JavaScript program megvalósítható egy függvény létrehozásával is. Figyeljük meg, hogy így mind a hexadecimális számjegyeket kezelő függvény, mind az átváltást megvalósító program jóval egyszerűbb lett.
Jegyezzük meg, hogy a 'hex2dec' függvény létrehozható mind a korábban megismert 'switch' szerkezettel, mind egymásba ágyazott if...else... utasításokkal, például a következőképpen:
Ennek a megvalósításnak az előnye, hogy a függvény bemenetét (hx) és kimenetét (sz) egyértelműen egy-egy változóval tudjuk megadni.
Példák algoritmusokra:
3. decimális szám átalakítása bináris számmá⇒
Szótár:
– decimális számok = tízes számrendszerbeli számok
– bináris számok = kettes számrendszerbeli számok
1. egész szám átváltása
Példa: 31410 = ?2
az átváltandó tízes számrendszerbeli egész számot (pl. 314) addig osztjuk 2-vel, amíg a hányados 0 nem lesz
minden lépésben felírjuk az osztás maradékát (0 vagy 1)
az átváltandó szám kettes számrendszerbeli alakját (pl. 100111010) úgy kapjuk meg, hogy az osztások maradékait fordított sorrendben felírjuk
hányados
maradék
314
314:2=
157
0
157:2=
78
1
78:2=
39
0
39:2=
19
1
19:2=
9
1
9:2=
4
1
4:2=
2
0
2:2=
1
0
1:2=
0
1
Eredmény:
31410 = 1|0011|10102
Megjegyzés: mivel egy kettes számrendszerbeli szám rendszerint elég sok számjegyből áll ("hosszú"), érdemes a számjegyeket jobbról négyes csoportokra bontani.
A fenti algoritmust megvalósító JavaScript program:
// decimális szám átalakítása bináris számmá
var x=314;
writeln("Decimális szám: "+x);
writeln();
var b="";
var q=1;
while(q>0) {
q=Math.trunc(x/2); // egész osztás!!
write(" Hányados: "+q);
if(x%2==1) {
b="1"+b;
writeln(", maradék: "+1);
}
else {
b="0"+b;
writeln(", maradék: "+0);
}
x=q;
}
writeln();
writeln("Bináris szám: "+b);
writeln("__________");
A JS Math.trunc(...) függvénye a zárójelek között megadott valós szám egész részét adja vissza. Tehát ha két egész szám hányadosát adjuk meg a függvény argumentumaként, a Math.trunc(...) függvény értéke a tört hányadosának egész része lesz, vagyis a függvény segítségével egész osztást tudunk végezni.
(Például 79=9*8+5 esetén a Math.trunc(79/8) függvény '9'-et ad vissza, a nyolccal való osztás maradékát pedig a (79%8) kifejezés segítségével kaphatjuk meg, amelynek az értéke az '5'-ös szám.)
A fenti program azonban egyszerűen megvalósítható az egész osztást lehetővé tevő Math.trunc() függvény nélkül is:
A későbbiekben (például a pakolt BCD számábrázolás⇒ kódolásakor) szükségünk lesz egy olyan függvényre, amely egy megadott decimális számjegyet egy 4 bites kettes számrendszerbeli számmá alakít. Ehhez először alakítsuk át a fenti programot:
// decimális számjegy átalakítása 4 bites bináris számmá
var x=3;
writeln("Decimális számjegy: "+x);
writeln();
var b="";
var q,m;
while(x>0) {
if(x%2==1) {
m="1";
x=x-1;
}
else {
m="0";
}
q=x/2;
b=m+b;
x=q;
}
var i=b.length;
while(i<4) {
b="0"+b; // vezető 0 hozzáadása
i=i+1;
}
writeln("Bináris szám: "+b);
writeln("__________");
Ezután hajtsuk végre a következő lépéseket:
(1) hozzunk létre egy 'dec2bin4' nevű függvényt a program elején, és adjuk meg zárójelek közt a függvény argumentumát szolgáltató 'x' változót, majd
(2) a programnak azt a részét, amely az 'x' változó megadott értékéből előállítja a 'b' változóban a keresett 4 bites kettes számrendszerbeli számot, tegyük bele a 'dec2bin4' nevű függvény blokkjába, és végül
(3) a blokk utolsó utasításának adjuk meg a 'return b;' utasítást, amely a 'dec2bin4(...)' függvény értékét adja vissza.
Így a következő programhoz jutunk:
// decimális számjegy átalakítása 4 bites bináris számmá függvény segítségével
function dec2bin4(x) {
// függvény blokkjának kezdete
var b="";
var q,m;
while(x>0) {
if(x%2==1) {
m="1";
x=x-1;
}
else {
m="0";
}
q=x/2;
b=m+b;
x=q;
}
var i=b.length;
while(i<4) {
b="0"+b; // vezető 0 hozzáadása
i=i+1;
}
return b;
// függvény blokkjának vége
}
var x=3;
writeln("Decimális számjegy: "+x);
writeln();
writeln("Bináris szám: "+dec2bin4(x));
writeln("__________");
Figyeljük meg, hogy a függvény kipróbálásához elegendó a program végén (az ún. "főprogramban") 5 sor. A függvényt pedig innentől kezdve akárhányszor meghívhatjuk anélkül, hogy a számítás lépéseit újra és újra le kellene írnunk.
Egy alternatív lehetőség egy decimális egész szám bináris számmá alakítására a következő:
megkeressük kettőnek azt a legmagasabb hatványát, amely az átváltandó számnál kisebb vagy egyenlő;
a talált hatványhoz mint helyi értékhez tartozó számjegy '1' lesz;
ezt kivonjuk az átváltandó számból;
a kivonás eredményére (mint átváltandó számra) addig ismételjük az 1. és 2. lépéseket, ameddig a kivonás eredménye zérus nem lesz;
az átváltandó szám kettes számrendszerbeli alakjában azok a számjegyek, amelyekhez nem rendeltünk '1' értéket, '0' értékűek lesznek.
Példa: 31410 = ?2
hatvány
átváltandó szám/maradék
számjegy
314
28=256
314−256=58
1
27=128
58<128
0
26=64
58<64
0
25=32
58−32=26
1
24=16
26−16=10
1
23=8
10−8=2
1
22=4
2<4
0
21=2
2−2=0
1
20=1
0<1
0
Eredmény:
31410 = 1|0011|10102
A fenti algoritmust megvalósító JavaScript program:
// decimális szám átalakítása bináris számmá kivonásokkal
var x=314;
writeln("Decimális szám: "+x);
writeln();
var b="";
var helyiertek=1;
while(2*helyiertek<=x) {
helyiertek*=2;
}
while(helyiertek>=1) {
if(helyiertek<=x) {
b+="1";
writeln(" Számjegy: "+1);
writeln(" Helyi érték: "+helyiertek);
x-=helyiertek;
}
else {
b+="0";
writeln(" Számjegy: "+0);
writeln(" Helyi érték: "+helyiertek);
}
helyiertek/=2;
}
writeln();
writeln("Bináris szám: "+b);
writeln("__________");
2. törtszám átváltása
Példa: 0.687510 = ?2
az átváltandó tízes számrendszerbeli törtszámot (pl. 0.6875) addig szorozzuk 2-vel, amíg
a tört rész 0 nem lesz, vagy
az algoritmus által szolgáltatott bináris számjegyek szakaszos ismétlődést nem mutatnak.
minden lépésben felírjuk a szorzat egész részét (0 vagy 1), és ezt kivonjuk a szorzatból (a szorzatok egész részei adják a keresett bináris számjegyeket!)
ha az algoritmus folytatódik, a következő lépésben a kivonások eredményét (a szorzatok tört részét) ismét szorozzuk 2-vel
az átváltandó szám kettes számrendszerbeli alakját (pl. 0.1011) úgy kapjuk meg, hogy a szorzatok felírt (majd kivont) egész részeit eredeti sorrendben a számot kezdő 0. után leírjuk
szorzat
egész rész
tört rész
0.6875
0.6875*2=
1.375
1
0.375
0.375*2=
0.75
0
0.75
0.75*2=
1.5
1
0.5
0.5*2=
1
1
0
Eredmény:
0.687510 = 0.10112
Megjegyzések:
(1) négynél több bináris számjegy esetén most is érdemes a számjegyeket négyes csoportokra bontani (balról, a "kettedespont" után);
(2) ha az átváltandó tízes számrendszerbeli szám egész része 0-nál nagyobb, a szám egész részét és tört részét külön-külön alakítsuk át kettes számrendszerbeli számmá.
A fenti algoritmust megvalósító JavaScript program:
// tizedestört átalakítása kettedestörtté
var x=0.6875;
writeln("A törtszám: "+x);
writeln();
var maxi=50;
var s="";
var i=1;
while(x>0 && i<=maxi) {
x*=2;
if(x<1) {
write(" egész rész: 0,");
s+="0";
}
else {
write(" egész rész: 1,");
s+="1";
x=x-1;
}
writeln(" törtrész: "+x);
if(i%4==0) {
writeln("..... "+i+". ciklus .....");
s+=" ";
}
i++;
}
writeln();
writeln("A tört (első "+maxi+" kettedesjegy): 0."+s);
writeln("__________");
Második példa:
(a)
0.4510 = ?2
(b)
0.810 = ?2
Ha egy (véges) tizedestört 2-vel való szorzásakor az algoritmus által szolgáltatott bináris számjegyek szakaszos ismétlődést mutatnak, akkor kell az algoritmust befejeznünk, ha egy korábban már előfordult tört részt kapunk. Ekkor két eset lehetséges:
Ha az ismételten előforduló tört részhez különböző bináris számjegyek (vagyis különböző egész részek) tartoznak, a tört rész az ismétlődő szakasz végét jelzi (például 0.45 esetén, az (a) feladatban).
Ha az ismételten előforduló tört részhez azonos bináris számjegyek (vagyis azonos egész részek) tartoznak, a tört rész az ismétlődő szakasz kezdetét jelzi (például 0.8 esetén, a (b) feladatban).
Oldjuk meg mindkét feladatot és ellenőrizzük a kapott eredményeket.
(a) 0.45 átalakítása kettedestörtté
szorzat
egész rész
tört rész
megjegyzés
Eredmény:
0.4510 = 0.01110011001100...2
Megjegyzés: az algoritmus lépései során 0.80 az első olyan tört rész, amely ismétlődik, vagyis innentől a bináris számjegyek is ismétlődni fognak. Azonban 0.8 kétféleképpen kapható meg (0.90 és 0.40 kettővel való szorzásával), ezért a táblázatban a 0.80-at tartalmazó sorokban az egész rész értéke először 1, másodszor pedig 0.
A bináris számjegyek ismétlődő sorozata tehát csak 0.80 után, azaz a 0.60 tört részt tartalmazó sortól kezdődik el és a 0.80 tört részt tartalmazó sorral fejeződik be (vagyis 0.8 az ismétlődő szakasz végét jelzi).
Vezessük be a következő változókat:
q=0.01110011001100...
p=4*q=1.110011001100... (a kettedespont kettővel jobbra mozog)
r=16*p=11100.110011001100... (a kettedespont néggyel jobbra mozog)
Ekkor teljesülnek az alábbi összefüggések:
r−p=16*p−p=15*p
valamint
r−p=
11100.110011001100...−1.110011001100...=
11100−1=
110112=2710
A fentiekből egyszerű átalakításokkal
15*p=27 ⇒ p=27/15 és
p=4*q ⇒
q=p/4=27/60=9/20=0.45
következik (ok).
(b) 0.8 átalakítása kettedestörtté
szorzat
egész rész
tört rész
megjegyzés
Eredmény:
0.810 = 0.110011001100...2
Megjegyzés: az algoritmus lépései során 0.60 az első olyan tört rész, amely ismétlődik, vagyis innentől a bináris számjegyek is ismétlődni fognak. A táblázatban a 0.60 tört részt tartalmazó sorokban az egész rész értéke (1) megegyezik.
A bináris számjegyek ismétlődő sorozata tehát a 0.60 tört részt tartalmazó sortól kezdődik el és a 0.80 tört részt tartalmazó sorral fejeződik be.
Vezessük be a következő változókat:
q=0.110011001100...
r=16*q=1100.110011001100... (a kettedespont néggyel jobbra mozog)
Ekkor teljesülnek az alábbi összefüggések:
r−q=16*q−q=15*q
valamint
r−q=
1100.110011001100...−0.110011001100...=
11002=1210
A fentiekből egyszerű átalakításokkal
15*q=12 ⇒ q=12/15=4/5=0.8
következik (ok).
Mivel a végtelen tizedestörtek szorzását a számítógép véges számú biten hajtja végre, ezért szorzáskor a szorzat közelítő értékét kapjuk meg. Ezért érdemes a végtelen szakaszos tizedestörteket először racionális törtekké alakítani, és utána átváltani őket kettedestörtekké (ld. a következő példát).
Harmadik példa: 5/7=0.714285714285...10 = ?2
Egy végtelen szakaszos tizedestört (q) átváltásakor először keressük meg a tizedestörtet előállító racionális törtszámot (q=a/b, ahol a,b∈ℤ, b≠0).⇒
szorzat
egész rész (b)
tört rész (x/y)
x/y
Eredmény:
5/710 = 0.101101101...2
Ha adott egy q=a/b (b≠0) alakú racionális törtszám, a fenti algoritmus egész számok szorzásával is elvégezhető. Az egyszerűség kedvéért tegyük fel, hogy
0<q<1, és a tört számlálója és nevezője pozitív természetes számok (amelyekre 0<a<b teljesül).
Az előző algoritmust módosítsuk a következőképpen:
legyen x=a és y=b
(az átváltandó tört a/b; kezdetben x/y=a/b, majd a további lépésekben x/y-t szorozzuk 2-vel, és x-et úgy módosítjuk, hogy x/y mindig a szorzat tört részét adja meg)
ha 2*x<y, akkor
legyen b=0 és írassuk ki 'b'-t
(ha 2*x/y<1, akkor 2-vel szorozva az x/y törtet, az egész rész 0 lesz)
legyen x=2*x
(ha 2*x/y<1, akkor 2-vel szorozva az x/y törtet, a tört rész számlálója 2*x lesz)
ha 2*x≥y, akkor
legyen b=1 és írassuk ki 'b'-t
(ha 2*x/y≥1, akkor 2-vel szorozva az x/y törtet, az egész rész 1 lesz)
legyen x=2*x−y
(ha 2*x/y≥1, akkor 2-vel szorozva az x/y törtet, a tört rész számlálója 2*x−y lesz, mivel
2*x/y−1=2*x/y−y/y=(2*x−y)/y
teljesül)
ha x==0 vagy az x/y tört rész megegyezik egy korábbi értékkel, akkor ugrás a 6. lépésre
(ha x==0, akkor véges kettedestörtet kaptunk; ha az x/y tört rész (ill. ennek 'x' számlálója) korábban már előfordult, akkor innentől az egész részek eddig kapott sorozata végtelen sokszor ismétlődni fog, azaz végtelen szakaszos kettedestörtet kaptunk)
ugrás a 2. lépésre
algoritmus vége
Nézzük meg, hogyan hajtható végre az algoritmus, ha a q=5/7 racionális törtszámot alakítjuk át kettedestörtté.
Vezessük be a következő változókat:
p=0.101101101...
r=8*p=101.101101101... (a kettedespont három pozícióval jobbra mozog)
Ekkor teljesülnek az alábbi összefüggések:
r−p=8*p−p=7*p
valamint
r−p=
101.101101101...−0.101101101...=
101−0=
1012=510
A fentiekből egyszerű átalakításokkal
7*p=5 ⇒ p=5/7
következik (ok).
A fenti algoritmust megvalósító JavaScript program (első, egyszerűbb változat):
// racionális törtszám átalakítása kettedestörtté (1. verzió)
/* feltétel: az átalakítandó törtszám pozitív és 1-nél kisebb (azaz x<y teljesül) */
var x=5, y=7;
writeln("A törtszám: "+x+"/"+y);
writeln();
var maxi=50;
var s="";
var i=1;
while(x>0 && i<=maxi) {
if(2*x<y) {
write(" egész rész: 0,");
s+="0";
x=2*x;
}
else {
write(" egész rész: 1,");
s+="1";
x=2*x-y;
}
writeln(" törtrész: "+x+"/"+y);
if(i%4==0) {
writeln("..... "+i+". ciklus .....");
s+=" ";
}
i++;
}
writeln();
writeln("A tört (első "+maxi+" kettedesjegy): 0."+s);
writeln("__________");
A fenti algoritmust megvalósító JavaScript program (második, teljes változat; kiegészítő anyag):
// racionális törtszám átalakítása kettedestörtté (második verzió)
/* feltétel: az átalakítandó törtszám pozitív és 1-nél kisebb */
var vereme=[];
var veremt=[];
function betesz(b,x) {
var n=vereme.length; // ennyi elem van a veremben
vereme[n]=b;
veremt[n]=x;
}
function beteszjelolot(index,s1,s2) {
for(var k=index;k<vereme.length;k++) {
vereme[vereme.length-k]=vereme[vereme.length-k-1];
veremt[veremt.length-k]=veremt[veremt.length-k-1];
}
vereme[index]=s1;
veremt[index]=s1;
vereme[vereme.length]=s2;
veremt[veremt.length]=s2;
}
function keres(x) {
var index=-1;
for(var k=0;k<veremt.length;k++) {
if(veremt[k]==x) {
index=k;
break;
}
}
return index;
}
function kivesze(index) {
if(0>index || index>=vereme.length) return -1;
return vereme[index];
}
function kiveszt(index) {
if(0>index || index>=veremt.length) return -1;
return veremt[index];
}
function kiveszmindet() {
var s="";
for(var k=0;k<vereme.length;k++) {
s+=vereme[k];
}
return s;
}
/*************************************
törtszám megadása (feltétel: x<y)
**************************************/
// var x=1, y=2;
var x=5, y=7;
// var x=9, y=14;
// var x=9, y=20;
// var x=5, y=14;
// var x=706, y=990;
writeln("A törtszám: "+x+"/"+y);
writeln();
var maxi=100;
var s="";
var jel1="{";
var jel2="}...";
var i=1;
while(x>0 && i<=maxi) {
var b;
if(2*x<y) {
b=0;
x=2*x;
}
else {
b=1;
x=2*x-y;
}
write(" egész rész: "+b+",");
writeln(" törtrész: "+x+"/"+y);
var index=keres(x);
if(index>=0) {
writeln(" ** ismétlődés **");
write(" korábbi egész rész: "+kivesze(index)+",");
writeln(" korábbi törtrész: "+kiveszt(index)+"/"+y);
if(b==kivesze(index)) {
writeln(" [ismétlődő szakasz kezdete]");
writeln(" [ismétlődő szakasz hossza: "+(i-index));
beteszjelolot(index,jel1,jel2);
}
else {
writeln(" [ismétlődő szakasz vége]");
betesz(b,x); // ezt még betesszük a verembe
beteszjelolot(index+1,jel1,jel2);
}
break;
}
betesz(b,x);
if(i%4==0) {
writeln("..... "+i+". ciklus .....");
}
i++;
}
s=kiveszmindet();
writeln();
writeln("A tört értéke (első max. "+maxi+" kettedesjegy): 0."+s);
writeln("__________");
Példák algoritmusokra:
4. bináris szám átalakítása hexadecimális számmá⇒
Szótár:
– bináris számok = kettes számrendszerbeli számok
– hexadecimális számok = tizenhatos számrendszerbeli számok
1. egész szám átváltása
Példa: 1010|11012 = ?16
Két fontos dolgot tudnunk kell az algoritmus megértéséhez:
(1) Mivel a kettes számrendszerbeli (egész) számok rendszerint elég sok számjegyből állnak, érdemes a bináris számjegyeket jobbról négyes csoportokra osztani (az utolsó csoportot pedig balról kiegészíteni "vezető" nullákkal).
Például ha a
1010010110
bináris szám számjegyeit jobbról négyes csoportokra bontjuk, akkor
0010|1001|0110
adódik.
(2) A hexadecimális számok számjegyei a decimális számjegyek (0, 1, ..., 9) mellett az A, B, C, D, E és F számjegyeket is magukba foglalják.
A bináris egész számokat hexadecimális számokká alakító algoritmus lépései:
az átváltandó kettes számrendszerbeli egész szám számjegyeit (pl. 1010|1101) jobbról négyes csoportokra osztjuk fel; a példa esetén ekkor
jobbról az első csoport 1101
jobbról a második csoport 1010
a kapott négy bináris számjegyből álló csoportokat tetszőleges sorrendben, például
balról jobbra haladva
egyenként tízes számrendszerbeli számokká alakítjuk (alkalmazva a korábban megismert 2. algoritmust⇒)
10102=8+2=1010
11012=8+4+1=1310
az egyes csoportoknak megfelelő tízes számrendszerbeli számokat tizenhatos számrendszerbeli (hexadecimális) számjegyekké alakítjuk
10102=8+2=1010=A16
11012=8+4+1=1310=D16
a kapott tizenhatos számrendszerbeli számjegyeket egymás után felírva megkapjuk a keresett hexadecimális számot
A fenti algoritmust megvalósító JavaScript program:
// bináris szám átalakítása hexadecimális számmá
function dec2hex(sz) {
var hx="-1";
switch(sz) {
case 10: hx="A"; break;
case 11: hx="B"; break;
case 12: hx="C"; break;
case 13: hx="D"; break;
case 14: hx="E"; break;
case 15: hx="F"; break;
default:
hx=""+sz;
}
return hx;
}
var x="10101101";
while(x.length%4!=0) {
x="0"+x; // vezető 0-k beírása
}
var k=x.length-1;
var t=""; // végeredmény
var s="";
var h=0;
var helyiertek=1;
for(var i=0;i<x.length;i++) {
s=x[k]+s;
if(x[k]==1) {
h+=helyiertek;
}
helyiertek*=2;
k--;
if(i%4==3) {
writeln(" "+s+" = "+h+" = "+dec2hex(h));
t=dec2hex(h)+t;
writeln(" ");
s="";
h=0;
helyiertek=1;
}
}
writeln(x+" = "+t);
writeln("____________");
A fordított irányú átváltás, azaz egy hexadecimális szám átváltása bináris számmá az előző algoritmushoz teljesen hasonlóan működik. Vegyünk egy tetszőleges hexadecimális számot, és
alakítsuk át a hexadecimális számjegyeket egyenként (pl. balról jobbra haladva) négy számjegyből álló (4 bites) bináris számokká;
ha szükséges, tegyünk be vezető nullákat, hogy a kapott bitsorozatok mindig 4 bitből álljanak
balról jobbra haladva "olvassuk össze" a kapott négy bites bitsorozatokat (szükség esetén a bitsorozatok közé betehetünk elválasztó karaktereket (pl. függőleges vonalat vagy szóközt) a könnyebb olvashatóság kedvéért)
Példa: 2AD16 = ?2
216 = 00102
A16 = 10102
D16 = 10112
Tehát az eredmény: 2AD16 = 0010|1010|10112
Az algoritmust megvalósító JavaScript program:
// hexadecimális szám átalakítása bináris számmá
function hex2dec(hx) {
var sz=-1;
switch(hx) {
case "a":
case "A": sz=10; break;
case "b":
case "B": sz=11; break;
case "c":
case "C": sz=12; break;
case "d":
case "D": sz=13; break;
case "e":
case "E": sz=14; break;
case "f":
case "F": sz=15; break;
default:
sz=parseInt(hx);
}
return sz;
}
var x="2AD";
writeln("A hexadecimális szám: "+x);
writeln();
var t=""; // végeredmény
for(var i=0;i<x.length;i++) {
var h=hex2dec(x[i]);
var helyiertek=8;
var s=""; // részeredmény
while(helyiertek>=1) {
if(h>=helyiertek) {
s=s+"1";
h-=helyiertek;
}
else {
s=s+"0";
}
helyiertek/=2;
}
writeln(" "+x[i]+" = "+hex2dec(x[i])+" = "+s);
if(i>0) {
t=t+" ";
}
t=t+s;
}
writeln();
writeln(x+" bináris alakja: "+t);
writeln("____________");
2. törtszám átváltása
Példa: 0.1011|01012 = ?16
Mivel a kettes számrendszerbeli (tört) számok rendszerint elég sok számjegyből állnak, érdemes a bináris számjegyeket balról (0. után kezdődően) négyes csoportokra osztani (az utolsó csoportot pedig jobbról kiegészíteni "vezető" nullákkal).
Például ha a
0.10110101
bináris szám számjegyeit balról négyes csoportokra bontjuk, akkor
0.1011|0101
adódik.
A bináris törtszámokat hexadecimális számokká alakító algoritmus lépései:
az átváltandó kettes számrendszerbeli egész szám számjegyeit (pl. 0.1011|0101) balról négyes csoportokra osztjuk fel; a példa esetén ekkor
balról az első csoport 1011
balról a második csoport 0101
a kapott négy bináris számjegyből álló csoportokat
balról jobbra haladva
egyenként tízes számrendszerbeli számokká alakítjuk (alkalmazva a korábban megismert 2. algoritmust⇒)
10112=8+2+1=1110
01012=4+1=510
az egyes csoportoknak megfelelő tízes számrendszerbeli számokat tizenhatos számrendszerbeli (hexadecimális) számjegyekké alakítjuk
10112=8+2+1=1110=B16
01012=4+1=510=516
a kapott tizenhatos számrendszerbeli számjegyeket egymás után felírva megkapjuk a keresett hexadecimális számot
Egy decimális számot a következő algoritmussal egy lépésben is átalakíthatjuk hexadecimális számmá:
az átváltandó tízes számrendszerbeli számot (pl. 314) addig osztjuk 16-tal, amíg a hányados 0 nem lesz
minden lépésben felírjuk az osztás maradékát (amely egy 0 és 15=F közötti szám lesz)
az átváltandó szám hexadecimális számrendszerbeli alakját úgy kapjuk meg, hogy az osztások maradékait fordított sorrendben felírjuk
hányados
maradék
ellenőrzés
314
314:16=
19
10=A
314=16*19+10
19:16=
1
3
19=16*1+3
1:16=
0
1
1=16*0+1
Eredmény:
31410 = 13A16
A fenti algoritmust megvalósító JavaScript program:
// decimális szám átalakítása hexadecimális számmá osztással
function hex2dec(hx) {
var sz=-1;
switch(hx) {
case "a":
case "A": sz=10; break;
case "b":
case "B": sz=11; break;
case "c":
case "C": sz=12; break;
case "d":
case "D": sz=13; break;
case "e":
case "E": sz=14; break;
case "f":
case "F": sz=15; break;
default:
sz=parseInt(hx);
}
return sz;
}
function dec2hex(sz) {
var hx="-1";
switch(sz) {
case 10: hx="A"; break;
case 11: hx="B"; break;
case 12: hx="C"; break;
case 13: hx="D"; break;
case 14: hx="E"; break;
case 15: hx="F"; break;
default:
hx=""+sz;
}
return hx;
}
var x="314";
writeln("Decimális szám: "+x);
writeln();
var h="";
var q=1;
while(q>0) {
q=Math.trunc(x/16); // egész osztás!!
write(" Hányados: "+q);
var m=x-16*q;
writeln(", maradék: "+m);
h=dec2hex(m)+h;
x=q;
}
writeln();
writeln("Hexadecimális szám: "+h);
writeln("__________");
Egy további lehetőség egy decimális szám hexadecimális számmá alakítására a következő:
megkeressük 16-nak azt a legmagasabb hatványát, amely az átváltandó számnál kisebb vagy egyenlő;
a talált hatványt annyiszor vonjuk ki az átváltandó számból, amíg a különbség a hatványnál kisebb nem lesz;
a talált hatványhoz mint helyi értékhez tartozó számjegy a kivonások számával egyezik meg (értelemszerűen 9-nél nagyobb számjegynél a hexadecimális számjegyeket kell használnunk);
a kivonás maradékára addig ismételjük az eljárást, ameddig a kivonás eredménye 16-nál kisebb nem lesz;
az egyesek számát a kivonás eredménye adja;
az átváltandó szám hexadecimális számrendszerbeli alakjában azok a számjegyek, amelyekhez nem rendeltünk (zérusnál nagyobb) számjegyet, '0' értékűek lesznek.
A fenti algoritmust megvalósító JavaScript program:
// decimális szám átalakítása hexadecimális számmá kivonásokkal
function hex2dec(hx) {
var sz=-1;
switch(hx) {
case "a":
case "A": sz=10; break;
case "b":
case "B": sz=11; break;
case "c":
case "C": sz=12; break;
case "d":
case "D": sz=13; break;
case "e":
case "E": sz=14; break;
case "f":
case "F": sz=15; break;
default:
sz=parseInt(hx);
}
return sz;
}
function dec2hex(sz) {
var hx="-1";
switch(sz) {
case 10: hx="A"; break;
case 11: hx="B"; break;
case 12: hx="C"; break;
case 13: hx="D"; break;
case 14: hx="E"; break;
case 15: hx="F"; break;
default:
hx=""+sz;
}
return hx;
}
var x=1526;
writeln("Decimális szám: "+x);
writeln();
var h="";
var helyiertek=1;
while(16*helyiertek<=x) {
helyiertek*=16;
}
while(helyiertek>=1) {
if(helyiertek<=x) {
var sz=0;
while(helyiertek<=x) {
sz++;
x-=helyiertek;
}
h+=dec2hex(sz);
writeln(" Számjegy: "+dec2hex(sz));
writeln(" Helyi érték: "+helyiertek);
}
else {
h+="0";
writeln(" Számjegy: "+0);
writeln(" Helyi érték: "+helyiertek);
}
helyiertek/=16;
}
writeln();
writeln("Hexadecimális szám: "+h);
writeln("__________");
Példák algoritmusokra:
6. végtelen szakaszos tizedes tört átalakítása racionális törtszámmá
A végtelen tizedes törtek szakaszosak, ha a tizedespont (.) után egy adott helyiértéktől kezdődően azonos számjegycsoportok ismétlődnek (végtelen sokszor). Az ismétlődő számjegycsoportokat a továbbiakban aláhúzással jelöljük.
Például
12.8333333... esetén az ismétlődő számjegycsoport egy számjegyből áll (3);
0.538461538461538461... esetén pedig az ismétlődő számjegycsoport hat számjegyből áll (538461).
Minden racionális törtszám felírható véges vagy végtelen szakaszos tizedes tört alakban.
Feladat:
Egy 'q' végtelen szakaszos tizedes tört esetében határozzuk meg azt az a/b racionális törtszámot (a,b∈ℤ, b≠0), amelyre q=a/b teljesül.
Példák:
ha q=0.666666..., akkor a/b=2/3, mivel
2/3≈0.666666...
ha q=0.8333333..., akkor a/b=5/6, mivel
5/6≈0.8333333...
ha q=12.8333333..., akkor a/b=77/6, mivel
12=72/6 és 5/6≈0.8333333...
ha q=0.538461538461538461..., akkor a/b=7/13, mivel
7/13≈0.538461538461538461...
Korábban láttuk, hogy a végtelen szakaszos kettedestörtek is felírhatók racionális törtszámként:
ha q=0.0111001100...2, akkor a/b=9/20 (lásd 0.45 átalakítását kettedestörtté⇒)
ha q=0.11001100...2, akkor a/b=4/5 (lásd 0.8 átalakítását kettedestörtté⇒)
ha q=0.101101...2, akkor a/b=9/20 (lásd 5/7 átalakítását kettedestörtté⇒)
A feladat általános megoldása:
Egy végtelen szakaszos tizedestörtet egy egyszerű algoritmus segítségével mindig elő tudunk állítani a/b (a,b∈ℤ, b≠0) alakú racionális törtszámként.
Az algoritmusban a végtelen szakaszos tizedes törteknek három fontos tulajdonságát használjuk ki. Az algoritmus vázlatos leírása a következő:
(1) Legyen 'q' végtelen szakaszos tizedes tört (az egyszerűség kedvéért tegyük fel, hogy 1>q>0).
Ha 'q'-t "felszorozzuk" 10 megfelelő hatványával (10n), akkor elérhető, hogy az ismétlődő szakaszok közvetlenül a tizedespont után kezdődjenek:
p=q*10n
Ekkor 'p' egész részét pontosan azok a számjegyek alkotják, amelyek 'q'-ban közvetlenül a tizedespont után és az ismétlődő szakaszok kezdete előtt állnak (ha nincsenek ilyen számjegyek, azaz n=0, akkor 'p' egész része 0 és p=q teljesül).
(2) Mivel a 'p' törtben az ismétlődő szakaszok közvetlenül a tizedespont után kezdődnek, ezért a törtet "felszorozva" 10 megfelelő hatványával (10m) mindig elérhető, hogy pontosan egy szakasz a tizedespont elé kerüljön:
r=p*10m=q*10n+m
Ekkor 'r' egész részét úgy kapjuk meg, hogy vesszük azokat a számjegyeket, amelyek 'q'-ban közvetlenül a tizedespont után állnak, és hozzávesszük ezekhez egy ismétlődő szakasz számjegyeit.
(3) a 'p' törtben és az 'r' törtben az ismétlődő szakaszok megegyeznek és közvetlenül a tizedespont után kezdődnek; ezért a 'p' és 'r' törtek tizedespont utáni része megegyezik, vagyis az (r−p) különbség egész szám lesz (a törtrész zérus lesz):
r−p=[r]−[p] (ahol [r] és [p] az 'r' és 'p' törtszámok egész részét jelöli).
A 'p' végtelen szakaszos tizedes tört a fentiek alapján a következőképpen fejezhető ki két egész szám hányadosaként:
r−p=p*10m−p=p*(10m−1)
⇒
p=(r−p)/(10m−1)
vagyis p=([r]−[p])/(10m−1)
ahol 'm' az ismétlődő szakasz hossza.
(4) Ezek után 'q'-t is könnyen meghatározhatjuk:
q=p/10n.
ahol 'n' azoknak a számjegyeknek a száma, amelyek a 'q' szám tört részében az ismétlődő szakasz kezdete előtt helyezkednek el. (Korábban már láttuk, hogy ha az ismétlődő szakaszok közvetlenül a tizedespont után kezdődnek, akkor n=0 miatt q=p teljesül.)
A fenti képletekből egyszerű behelyettesítéssel adódik, hogy ha 'q'-t egyszer 10n+m-mel, majd 10n-nel szorozzuk, akkor a 'q' előállítását racionális törtszámként közvetlenül is megkaphatjuk:
q=([q*10n+m]−[q*10n])/(10n+m−10n)
A fenti képletben 'n' azoknak a tizedesjegyeknek a száma, amelyek a 'q' szám tört részében az ismétlődő szakasz kezdete előtt helyezkednek el és 'm' az ismétlődő szakasz hossza.
(1) Például tekintsük a q=0.666666... végtelen szakaszos tizedes törtet, amelyben az ismétlődő szakaszok közvetlenül a tizedespont után kezdődnek (n=0). Szorozzuk be q-t 10-zel (m=1), majd vonjuk ki q-t a kapott szorzatból, hogy eltűnjenek a tizedesjegyek:
10*q=6.666666...
10*q−q=6.666666...−0.666666...=6
Ebből már egyszerű átalakítással
9*q=6 ⇒ q=6/9=2/3
adódik, ami éppen a keresett alak.
(2) Egy másik példaként tekintsük a q=0.8333333... végtelen szakaszos tizedes törtet. Szorozzuk be q-t 100-zal (n+m=2), majd 10-zel (n=1), és vonjuk ki a kapott szorzatokat egymásból, hogy eltűnjenek a tizedesjegyek:
100*q=83.333333...
10*q=8.3333333...
100*q−10*q=83.333333...−8.3333333...=83−8=75
Ebből már egyszerű átalakítással
90*q=75 ⇒ q=75/90=5/6
adódik, ami éppen a keresett alak.
(3) Utolsó példaként tekintsük a q=0.538461538461538... végtelen szakaszos tizedes törtet, amelyben az ismétlődő szakaszok közvetlenül a tizedespont után kezdődnek (n=0). Szorozzuk be q-t 106-nal (ahol m=6 az ismétlődő szakasz hossza!), és vonjuk ki q-t a kapott szorzatból, hogy eltűnjenek a tizedesjegyek:
106*q=538461.538461538461538...
106*q−q=538461.538461538461538...−0.538461538461538...=538461
Ebből már egyszerű átalakítással
(106−1)*q=538461 ⇒ q=538461/999999=7/13
adódik, ami éppen a keresett alak. (Megjegyzés: mivel
lnko(538461,999999)=76923, ezzel egyszerűsíthetjük a törtet:
538461/76923=7 és 999999/76923=13
miatt a fenti eredmény adódik.)
A fenti algoritmus általánosítható bármilyen számrendszerben ábrázolt végtelen szakaszos (kettedes, harmados, negyedes stb.) törtszámokra. Például végtelen szakaszos kettedestörtek esetén azt használjuk ki, hogy
– a törtszámot 2-vel szorozva a kettedespontot egy hellyel jobbra mozgathatjuk,
– a törtszámot 4=22-vel szorozva a kettedespontot két hellyel jobbra mozgathatjuk,
– a törtszámot 8=23-cal szorozva a kettedespontot 3 hellyel jobbra mozgathatjuk,
...
– a törtszámot 2n-nel szorozva a kettedespontot 'n' hellyel jobbra mozgathatjuk.
(4) Például tekintsük a q=0.101101101... végtelen szakaszos kettedes törtet, amelyben az ismétlődő szakaszok közvetlenül a tizedespont után kezdődnek (n=0). Szorozzuk be q-t 8=23-cal (m=3), majd vonjuk ki q-t a kapott szorzatból, hogy eltűnjenek a tizedesjegyek:
8*q=101.101101101...
8*q−q=101.101101101...−0.101101101...=1012=510
Ebből már egyszerű átalakítással
7*q=5 ⇒ q=5/7
adódik. Erről a racionális törtszámról azonban korábban⇒ már beláttuk, hogy kettedes törtként éppen a fenti alakú.
Egy fontos kiegészítés:
Bármely véges tizedes tört felírható úgy, hogy az utolsó tizedesjegyét 1-gyel csökkentjük, és utána csupa 9-esből álló végtelen számsorozatot írunk (Pappné Ádám 1996: 95).
Például alakítsuk racionális törtszámmá a
q=0.99999...
végtelen szakaszos tizedes törtet. A korábbi algoritmust használva
10*q=9.99999... miatt fennáll a
10*q−q=9
összefüggés. Másrészt
10*q−q=9*q
nyilvánvalóan teljesül. A két összefüggésből
9*q=9
teljesül, amiből q=1 következik.
A fenti összefüggés bármely számrendszerre megfogalmazható, azonban kettedestörtek esetén 9 helyett 1, tizenhatodos törtek esetén pedig 9 helyett F értendő. Ezért azokat a végtelen szakaszos tizedestörteket, amelyekben a legnagyobb értékű számjegy végtelen sokszor szakaszosan ismétlődik, a továbbiakban nem használjuk. Ennek megfelelően
decimális számok esetén kizárjuk az egy hosszúságú szakaszokból álló, csupa 9-et tartalmazó végtelen szakaszos tizedes törteket;
bináris számok esetén kizárjuk az egy hosszúságú szakaszokból álló, csupa 1-et tartalmazó végtelen szakaszos kettedestörteket;
hezadecimális számok esetén kizárjuk az egy hosszúságú szakaszokból álló, csupa F-et tartalmazó végtelen szakaszos tizenhatodos törteket.
A fenti algoritmust megvalósító JavaScript program:
// végtelen szakaszos tizedestört átalakítása racionális törtszámmá (lépésenként)
/* feltétel: a szám
0.xy...
alakú, ahol
'x' az ismétlődő szakasz előtti számjegyeket,
'y' az ismétlődő szakasz számjegyeit (legalább egy van)
tartalmazza */
function hatvany(x,n) {
/* feltétel: n pozitív egész szám */
var q=1;
for(var i=1;i<=n;i++) {
q*=x;
}
return q;
}
var x="", y="6";
// var x="8", y="3";
// var x="", y="538461";
writeln("A törtszám: 0."+x+y+y+y+"...");
writeln();
var n=x.length;;
var m=y.length;
var pe=0;
if(n>0) {
pe=Number(x);
}
var pa=Number(x+y)-pe;
var pb=hatvany(10,m)-1;
var a=pa;
var b=pb*hatvany(10,n);
writeln("A racionális törtszám: "+a+"/"+b);
writeln("__________");
A fenti algoritmust a korábban megadott képlet alkalmazásával is megvalósíthatjuk egy JavaScript program segítségével:
// végtelen szakaszos tizedestört átalakítása racionális törtszámmá (képlettel)
/* feltétel: a szám
0.xy...
alakú, ahol
'x' az ismétlődő szakasz előtti számjegyeket,
'y' az ismétlődő szakasz számjegyeit (legalább egy van)
tartalmazza */
function hatvany(x,n) {
/* feltétel: n pozitív egész szám */
var q=1;
for(var i=1;i<=n;i++) {
q*=x;
}
return q;
}
// var x="", y="6";
// var x="8", y="3";
var x="", y="538461";
writeln("A törtszám: 0."+x+y+y+y+"...");
writeln();
var a=Number(x+y);
if(x.length>0) {
a=a-Number(x);
}
var n=x.length;;
var m=y.length;
var b=hatvany(10,n+m)-hatvany(10,n);
writeln("A racionális törtszám: "+a+"/"+b);
writeln("__________");
Példák algoritmusokra:
7. két egész szám legnagyobb közös osztójának meghatározása (euklideszi algoritmus)
Amikor egy végtelen szakaszos tizedes törtet racionális törtszámmá alakítunk, hosszú ismétlődő szakaszok esetén könnyen előfordulhat, hogy az algoritmus végén olyan törtet kapunk, amelynek mind a számlálója, mind a nevezője viszonylag nagy abszolút értékű egész szám. Ilyenkor célszerű a törtet a lehető legjobban leegyszerűsíteni, azaz a tört alapalakját meghatározni (amikor a számláló és a nevező relatív primek, azaz legnagyobb közös osztójuk 1).
(Például az előző szakasz harmadik példájában a 'q' végtelen szakaszos tizedes törtre, amely m=6 hosszúságú ismétlődő szakaszokat tartalmazott, a q=538461/999999 racionális törtszámot kaptuk.)
Az a/b racionális törtszám (a,b∈ℤ, b≠0) alapalakját úgy kaphatjuk meg, hogy először meghatározzuk az 'a' és 'b' egész számok legnagyobb közös osztóját, majd ezzel egyszerűsítjük a törtet.
Feladat:
Határozzuk meg a 'a' és 'b' egész számok (a,b∈ℤ) legnagyobb közös osztóját. Az egyszerűség kedvéért tételezzük fel, hogy 'a' és 'b' pozitív természetes számok, amelyekre a≥b teljesül.
legyen x=a és y=b
osszuk el az 'x' számot maradékosan 'y'-nal , és legyen
x=y*q+r
ahol az 'r' maradékra 0≤r<y teljesül
ha r==0, ugorjunk az 5. lépésre
legyen x=y és y=r, és folytassuk az algoritmust a 2. lépéssel
az 'a' és 'b' számok legnagyobb közös osztója
lnko(a,b)=y
az algoritmus befejeződött
Például határozzuk meg az euklideszi algoritmus alapján az a=999999 és b=538461 számok legnagyobb közös osztóját.
Ekkor az algoritmus lépései a következők:
legyen x=999999, y=538461 (1. lépés)
999999=538461*1+461538, vagyis q=1 és r=461538 (2. lépés)
mivel r≠0, ezért legyen x=538461 és y=461538 (4. lépés)
538461=461538*1+76923, vagyis q=1 és r=76923 (2. lépés)
mivel r≠0, ezért legyen x=461538 és y=76923 (4. lépés)
461538=76923*6 vagyis q=6 és r=0 (2. lépés)
mivel r==0, megtaláltuk a legnagyobb közös osztót, és ugorjunk az 5. lépésre (3. lépés)
lnko(999999,538461)=76923 (5. lépés)
Osszuk el a tört számlálóját és nevezőjét a megtalált legnagyobb közös osztóval.
Mivel
999999/76923=13 és
538461/76923=7,
ezért
999999/538461=13/7
teljesül.
Az a/b=999999/538461 tört alapalakja tehát a/b=13/7.
(Megjegyzés: az előző szakasz harmadik példájában a fenti tört reciproka szerepelt, amelyre nyilvánvalóan
538461/999999=7/13
teljesül.)
A fenti algoritmust megvalósító JavaScript program:
// két szám legnagyobb közös osztójának meghatározása (euklideszi algoritmus)
/* feltétel: a>b>0 teljesül */
function egesz_osztas(x,y) {
/* x és y nemnegatív egész számok */
var q=0;
if(y<=0 || x<0) return "NaN";
while(x>=y) {
x-=y;
q++;
}
return q;
}
var a=999999, b=538461;
writeln("A két szám: a="+a+", b="+b);
writeln();
var x=a, y=b;
var q, r=1;
while(true) {
q=egesz_osztas(x,y);
// q=Math.trunc(x/y);
r=x-y*q;
if(r==0) {
break;
}
x=y;
y=r;
}
writeln("A legnagyobb közös osztó: "+y);
writeln("__________");
