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.

Példák algoritmusokra:
1.1. bináris egész 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: 1101₂ = ?₁₀

• 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 2³=8, tehát a szorzat 1*8=8
  • a következő számjegy 1, helyi értéke 2²=4, tehát a szorzat 1*4=4
  • a következő számjegy 0, helyi értéke 2¹=2, tehát a szorzat 0*2=0
  • az utolsó számjegy 1, helyi értéke 2⁰=1, tehát a szorzat 1*1=1
• a kapott szorzatokat összeadjuk: 8+4+1=13

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:
1101₂ = 13₁₀

Ellenőrzés:
13₁₀ = 8 + 4 + 1 = 1*2³ + 1*2² + 0*2¹ + 1*2⁰ = 1101₂ (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 JavaScript programokban előforduló fontosabb programnyelvi szerkezetek rövid magyarázata megtalálható itt.

Példák algoritmusokra:
1.2. bináris törtszám átalakítása decimális számmá

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/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.1101₂ = ?₁₀

• 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/2, tehát a szorzat 1*1/2=1/2
  • a következő számjegy 1, helyi értéke 2⁻²=1/4, tehát a szorzat 1*1/4=1/4
  • a következő számjegy 0, helyi értéke 2⁻³=1/8, tehát a szorzat 0*1/8=0
  • az utolsó számjegy 1, helyi értéke 2⁻⁴=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

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.1101₂ = 13/16₁₀ = 0.8125₁₀

Ellenőrzés:
0.8125₁₀ = 0.5 + 0.25 + 0.0625 = 1*2⁻¹ + 1*2⁻² + 0*2⁻³ + 1*2⁻⁴ = 0.1101₂ (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("__________");

---

A bináris egész- és törtszámokat egy program segítségével is átalakíthatjuk bináris számokká. Az algoritmust megvalósító JavaScript program:

// bináris szám átalakítása decimális számmá 

var x="1101.101";

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

var d=0;
var helyiertek=1;

for(var i=1;i<x.length;i++) {
 if(x[i]==".") { break; }
 helyiertek*=2;
 }

for(var i=0;i<x.length;i++) {
 if(x[i]==".") { continue; }
 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;
 writeln("      Kumulált összeg: "+d);
 helyiertek/=2;
 }

writeln();

writeln("Decimális szám: "+d);

writeln("__________");

Példák algoritmusokra:
2. hexadecimális szám átalakítása decimális számmá^⇒

Szótár:
– hexadecimális számok = tizenhatos számrendszerbeli számok
– decimális számok = tízes számrendszerbeli számok

Példa: 24C₁₆ = ?₁₀

• az átváltandó tizenhatos számrendszerbeli szám (pl. 24C) minden számjegyét megszorozzuk a szám helyi értékével
  • balról az első számjegy 2, helyi értéke 16²=256, tehát a szorzat 2*256=512
  • a következő számjegy 4, helyi értéke 16¹=16, tehát a szorzat 4*16=64
  • az utolsó számjegy C (ez megfelel 12-nek), helyi értéke 16⁰=1, tehát a szorzat 12*1=12
• a kapott szorzatokat összeadjuk: 512+64+12=588

számjegy	helyi érték	szorzat
2	162=256	512
4	161=16	64
C	160=1	12
	Összesen	588

Eredmény:
24C₁₆ = 588₁₀

Ellenőrzés:
588₁₀ = 512 + 64 + 12 = 2*256 + 4*16 + 12* 1 = 2*16² + 4*16¹ + 12*16⁰ = 24C₁₆ (ok)

---

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("__________");

Két fontos megjegyzés:

• a hexadecimális szám karaktereit tárolhatjuk egy tömbben is, amit legegyszerűbben a
  var x=["2","4","C"];
  utasítással hozhatunk létre;
• a JavaScript parseInt(...) függvénye egy karakterlánc (string) formájában tárolt számot alakít át decimális számmá (azaz integer típusú adattá); a fenti programban használhattuk volna helyette a hosszabb
  switch(x[i]) {
  case "a":
  case "A": sz=10; break;
  case "b":
  case "B": sz=11; break;
  ...
  case "f":
  case "F": sz=15; break;
  case "0": sz=0; break;
  case "1": sz=1; break;
  case "2": sz=2; break;
  ...
  case "8": sz=8; break;
  case "9": sz=9; break;
  default:
      throw new Error("hibás számjegy ("+x[i]+")");
  }
  szerkezetet is, amely már a hibás számábrázolást is kezeli.

A fenti JavaScript program egyszerűsített és 'while' ciklussal megírt változata, valamint a program 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.

A program és ennek a folyamatábrája a következő:

// hexadecimális szám átalakítása decimális számmá (ver 3.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;
 if(x[i]=="a" || x[i]=="A") {
  sz=10;
  }
 else if(x[i]=="b" || x[i]=="B") {
  sz=11;
  }
 else if(x[i]=="c" || x[i]=="C") {
  sz=12;
  }
 else if(x[i]=="d" || x[i]=="D") {
  sz=13;
  }
 else if(x[i]=="e" || x[i]=="E") {
  sz=14;
  }
 else if(x[i]=="f" || x[i]=="F") {
  sz=15;
  }
 else {
  sz=parseInt(x[i]);  
  }
 var r=sz*helyiertek;
 d=d+r;
 helyiertek=helyiertek/16;
 i=i+1;
 }

writeln("Decimális szám: "+d);

writeln("__________");

---

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.

A program és ennek a folyamatábrája a következő:

// hexadecimális szám átalakítása decimális számmá (ver 4.0)

function hex2dec(hx) {
 if(hx=="a" || hx=="A") {
  return 10;
  }
 if(hx=="b" || hx=="B") {
  return 11;
  }
 if(hx=="c" || hx=="C") {
  return 12;
  }
 if(hx=="d" || hx=="D") {
  return 13;
  }
 if(hx=="e" || hx=="E") {
  return 14;
  }
 if(hx=="f" || hx=="F") {
  return 15;
  }
 return parseInt(hx);
 }

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;
 sz=hex2dec(x[i]);
 var r=sz*helyiertek;
 d=d+r;
 helyiertek=helyiertek/16;
 i=i+1;
 }

writeln("Decimális szám: "+d);

writeln("__________");

A 'hex2dec' függvény megvalósítható egymásba ágyazott if ... else ... utasításokkal, például a következőképpen:

// hexadecimális szám átalakítása decimális számmá (ver 5.0)

function hex2dec(h) {
 var sz;
 if(h=="a" || h=="A") {
  sz=10;
  }
 else if(h=="b" || h=="B") {
  sz=11;
  }
 else if(h=="c" || h=="C") {
  sz=12;
  }
 else if(h=="d" || h=="D") {
  sz=13;
  }
 else if(h=="e" || h=="E") {
  sz=14;
  }
 else if(h=="f" || h=="F") {
  sz=15;
  }
 else {
  sz=parseInt(h);
  }
 return sz;
 }

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;
 sz=hex2dec(x[i]);
 var r=sz*helyiertek;
 d=d+r;
 helyiertek=helyiertek/16;
 i=i+1;
 }

writeln("Decimális szám: "+d);

writeln("__________");

A 'hex2dec' függvény megvalósítható a korábban megismert switch ... case ... szerkezettel is:

// hexadecimális szám átalakítása decimális számmá (ver 5.1)

function hex2dec(h) {
 var sz;
 switch(h) {
  case "0": sz=0; break;
  case "1": sz=1; break;
  case "2": sz=2; break;
  case "3": sz=3; break;
  case "4": sz=4; break;
  case "5": sz=5; break;
  case "6": sz=6; break;
  case "7": sz=7; break;
  case "8": sz=8; break;
  case "9": sz=9; break;
  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: 
   throw new Error("Hibás számjegy: "+h);  
  }
 return sz;
 }

var x="24C";

write("Hexadecimal number: "+x);
writeln();

var d=0;
var h=1;

var i=1;
while(i<x.length) {
 h=h*16;
 i=i+1;
 }

i=0;
while(i<x.length) {
 var sz;
 sz=hex2dec(x[i]);
 var r=sz*h;
 d=d+r;
 h=h/16;
 i=i+1;
 }

writeln("Decimal number: "+d);

writeln("__________");

Ezeknek a megvalósításoknak az előnye, hogy a függvény bemenetét (h) és kimenetét (sz) egyértelműen egy-egy változóval tudjuk megadni. Az utolsó verzióban a függvény hibás számjegy esetén hibaüzenetet ad és megszakítja a program futását.