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:
Online JavaScript Interpreter by Peter Jipsen, Chapman University (January 2013).
http://math.chapman.edu/~jipsen/js/ (2020-11-19)
Megjegyzés:
Ha a fenti link valamilyen oknál fogva nem működik, használjuk az
alábbi linket.
A JavaScript programok folyamatábráját megjeleníthetjük az alábbi webes alkalmazás segítségével:
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:
3.1. decimális egész 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á (ver. 1.0)
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:
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("__________");
A fenti program végtelen szakaszos kettedestört esetén maximum 50 bináris számjegyet számol ki. Írassuk ki a 2-vel való szorzások törtrészét x=0.68 esetén:
Figyeljük meg, hogy tizedestörtek esetén a szorzás nem pontos, és a legkisebb helyiértékeken minél több szorzást hajtunk végre, annál nagyobb hibát kapunk. Emiatt a szorzatok törtrészének ismeretében nem tudjuk teljes bizonyossággal eldönteni, hogy eljutottunk-e egy ismétlődő szorzathoz (ahonnan a bináris számjegyek már ismétlődni fognak).
A fenti példában például négy tizedesjegyet vizsgálva megtalálhatjuk az ismétlődő szakaszokat. (De jegyezzük meg, hogy elvileg az ismétlődő szakaszok bármilyen hosszúak lehetnek, ezért ez a megoldás csak az egyszerűbb példák esetén működik.) Az ezt megvalósító JavaScript program (kiegészítő anyag):
// tizedestört átalakítása véges vagy végtelen szakaszos kettedestörtté (tömb használatával)
function formaz(x,n) {
var s=""+x;
var t="";
if(s.length>n+2) {
for(var i=0;i<n+2;i++) {
t=t+s[i];
}
}
else {
t=s;
while(t.length<n+2) {
t=t+"0";
}
}
return t;
}
function talal(s) {
var k=-1;
for(var i=0;i<ptr;i++) {
if(s==tomb[i]) {
k=i;
break;
}
}
return k;
}
var x=0.1;
writeln("A törtszám: "+x);
writeln();
var maxi=50;
var s="";
var tomb=new Array();
var ptr=0;
var k=-1; // ism. szakasz kezdete
var i=1;
while(x>0 && i<=maxi) {
var t=formaz(x,4);
var k=talal(t);
if(k>=0) {
break;
}
tomb[ptr]=t;
ptr++;
x*=2;
write(" szorzat: "+formaz(x,4));
var b;
if(x<1) {
b="0";
}
else {
b="1";
x=x-1;
}
s+=b;
writeln(", számjegy: "+b);
i++;
}
writeln();
writeln("A tört (első "+maxi+" kettedesjegy): 0."+s);
if(k>=0) {
write("Ismétlődő szakasz: 0.");
for(var i=0;i<s.length;i++) {
if(i==k) {
write("[");
}
write(s[i]);
}
writeln("]");
}
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).⇒
Esetünkben a=5, b=7, q=5/7. Hajtsuk végre ezekkel a számokkal az algoritmust:
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 algoritmusból az is látszik, hogy például 7-tel való osztás esetén legfeljebb 7 különböző maradék lehetséges. Ha az algoritmusban egy maradék (azaz a "tört rész" oszlopban levő szám) megismétlődik, onnantól kezdve a tört számjegyei ismétlődni fognak, tehát végtelen szakaszos tizedetört esetén 7-tel való osztás esetén a szakaszok hossza nem lehet 7-nél nagyobb.
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é (verem alkalmazásával)
/* 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("__________");
