Számrendszerek, algoritmusok

Példák algoritmusokra

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:

Live code editor. Created by Bogdan Lyashenko.
https://bogdan-lyashenko.github.io/js-code-to-svg-flowchart/docs/live-editor/index.html (2022-10-02)

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.

Bináris szám átalakítása decimális számmá JavaScript program segítségével

Példa: 11012 = ?10

Megoldás:

számjegy helyi érték szorzat
1 23=8 8
1 22=4 4
0 21=2 0
1 20=1 1
Összesen 13

Eredmény:
11012 = 1310

Ellenőrzés:
1310 = 8 + 4 + 1 = 1*23 + 1*22 + 0*21 + 1*20 = 11012 (ok)

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 JS program (bin2dec) folyamatábrája

A fenti JavaScript programokban előforduló fontosabb programnyelvi szerkezetek rövid magyarázata:

// ...

var x="1101";

writeln("Bináris szám: "+x);

for(var i=1;i<x.length;i++) {...}

A 'for' ciklus egyik tipikus alkalmazása egy string karaktereinek egyenként történő feldolgozása (pl. kiírása egymás alá, külön sorokban): 

// egy string karaktereinek kiírása egymás alá

var x="1101";

for(var i=0;i<x.length;i++) {
 writeln(x[i]);
 }

writeln("___________");

Ezt a JavaScript programrészletet érdemes memorizálni.

A fenti példaprogramot módosíthatjuk úgy, hogy csak a string első szavát írjuk ki egy sorban. (Tétetezzük fel, hogy az első szó végét egy szóköz jelzi.) 

// egy string első szavának kiírása

var x="Hello Kata hogy vagy?";

for(var i=0;i<x.length;i++) {
 if(x[i]==" ") {
  break;
  }
 write(x[i]);
 }
writeln();

writeln("___________");

Ennek a példaprogramnak egy valamivel összetettebb variációja, hogy először keressük meg a string első szavát, majd a string első szó után következő karaktereit írjuk ki egy sorban. Tétetezzük fel, hogy az első szó végét most is egy szóköz jelzi. A program érdekessége a 'k' logikai változó, amelynek 'false' értéke azt jelzi, hogy még nem találtuk meg az első szót, 'true' értéke pedig azt, hogy megtaláltuk, és kezdődhet az első szó utáni karakterek kiírása. 

// egy string első szava _utáni_ részének kiírása

var x="Hello Kata hogy vagy?";

var k=false; // még _nem_ értünk a végére az első szónak

for(var i=0;i<x.length;i++) {
 if(x[i]!=" " && !k) {
  continue;
  }
 if(x[i]==" " && !k) {
  k=true; // az első szó végére értünk
  continue;
  }

 write(x[i]);
 }
writeln();

writeln("___________");

Jegyezzük meg, hogy a logikai változók kiválóan használhatók egy programban különböző események bekövetkezésének jelzésére.

if(x[i]=="1") {...} else {...}

x[i]=="1"

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

Megoldás:

számjegy helyi érték szorzat
1 2−1=1/2 1/2
1 2−2=1/4 1/4
0 2−3=1/8 0
1 2−4=1/16 1/16
Összesen 13/16

Eredmény:
0.11012 = 13/1610 = 0.812510

Ellenőrzés:
0.812510 = 0.5 + 0.25 + 0.0625 = 1*2−1 + 1*2−2 + 0*2−3 + 1*2−4 = 0.11012 (ok)

A fenti algoritmust megvalósító JavaScript program: 

// bináris törtszám átalakítása decimális törtszámmá (tizedestörtté)

/* feltétel: a bináris törtszám pozitív és 1-nél kisebb, azaz 0<x<1 teljesül */

var x="0.1101"; 

writeln("Bináris törtszám: "+x);
writeln();

var d=0;
var helyiertek=1/2;

for(var i=2;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 törtszám: "+d);

writeln("__________");

→ Tartalom
Boda István, 2023.