Gyakorlati alapok

A Pénzes-féle bináris skálakatalógus

 

Ezen fejezet előzménye a Pénzes-féle zenei módszertan egyik fontos eleme, a bináris skálakatalógus megalkotása. Ennek megértése, illetve annak felfedezése, hogy mennyiben volt újdonság ez a zeneelméletben, középszintű zeneelméleti ismereteket igényel, éppen ezért ezt most nem részletezem, hiszen a fentebb linkelt zenei honlapomon kellő mennyiségű és mélységű információ áll rendelkezésre. Helyette a probléma felvetéseként felteszek egy olyan jellegű kombinatorikai kérdést, amely hasonló a bináris skálakatalóguséhoz:

 

www.informatika-programozas.hu - Ezt most meg kell tanulni!

 

Adott 12 db tátongó biliárdlyuk. Hányféleképpen tudok beletenni 1 db biliárdgolyót, majd 2 db-ot, majd 3 db-ot, egészen 12 db-ig?

 

Ez valójában kombinatorikai kérdés, annak ismétlés variációs változata, ahol 12 db  biliárdlyukba 1-től 12 db golyót összesen 4096-féleképpen tehetek be, mert 212 = 4096.

 

Az előző, A kínai mintacsalád ültetési rendje című fejezet már tartalmazott ilyen jellegű Java-megoldást 3 elem esetére, amely során 3 db egymásba ágyazott for ciklust kellett felhasználnunk. Először nézzük meg tehát ezt a fajta megoldási utat, de megjegyzem, hogy nem lesz valami elegáns kód, hiszen 12 db for ciklust kell egymásba ágyaznunk, ennek ellenére lényegében célravezető, mert korrekt végeredményt szolgáltat:

 

www.informatika-programozas.hu - Futtatható Java-kód!

 

 

 

 

 

 

 


public class Main {
 public static void main(String[] args) {
  for (int a = 0; a <= 1; a++){
   for (int b = 0; b <= 1; b++){
    for (int c = 0; c <= 1; c++){
     for (int d = 0; d <= 1; d++){
      for (int e = 0; e <= 1; e++){
       for (int f = 0; f <= 1; f++){
        for (int g = 0; g <= 1; g++){
         for (int h = 0; h <= 1; h++){
          for (int i = 0; i <= 1; i++){
           for (int j = 0; j <= 1; j++){
            for (int k = 0; k <= 1; k++){
             for (int l = 0; l <= 1; l++){
              System.out.println (""+a+b+c+d+e+f+g+h+i+j+k+l+" ");
             }
            }
           }
          }
         }
        }
       }
      }
     }
    }
   }
  }
 }
}

 

Végeredmény:

Ez 4096 db számvariációt jelent, amely MS Word dokumentumban 68 oldalt tesz ki. Én külön HTML-fejezetben publikáltam. Íme az első néhány sora:

 

000000000000
000000000001
000000000010
000000000011
000000000100
000000000101
000000000110
000000000111
000000001000
000000001001

stb.
 

Ha csak számlistázásról lenne szó, akkor a megoldás rémegyszerű lenne: nincs más dolgunk, mint kilistázni a számokat bináris számformátumban 1 és 4096 között. Az átváltást a Numerikus egész című fejezetben érdekességként már ismertetett Integer.toBinaryString() metódus végzi el nekünk:

 

www.informatika-programozas.hu - Futtatható Java-kód!

 

 

 

 

 

 

 


public class Main {
    public static void main(String args[]){
    for(int i = 1 ; i < 4096; i++){
        System.out.println(Integer.toBinaryString(i));
        }
    }
}

 

Végeredmény (első néhány sor):

1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111

stb.

 

De azonnal észrevehetjük a gyenge pontot: az algoritmus nem 12 db, 0-ba ágyazott "1" kombinációt ír ki, hanem valóban decimális számok bináris értékeit (3decimális például = 11bináris), ezért a számkiírás változó hosszúságú. Kis kódmatatással az "üres" helyeket 0 értékekkel tudjuk feltölteni, bár ez sem lesz célravezető, a kód ettől nem javul meg:

 

www.informatika-programozas.hu - Futtatható Java-kód!

 

 

 

 

 

 

 


public class Main {
    public static void main(String args[]){
    String szamString = null;
    int aktualisHossz = 0;
    for(int i = 1 ; i < 4096; i++){
        szamString = Integer.toBinaryString(i);
        System.out.print(szamString);
        aktualisHossz = 13 - szamString.length();
        for(int j = 1; j < aktualisHossz; j++){
            System.out.print("0");
        }
        System.out.println();
        }
    }
}

 

Végeredmény (első néhány sor):

100000000000
100000000000
110000000000
100000000000
101000000000
110000000000
111000000000
100000000000
100100000000
101000000000
101100000000
110000000000
110100000000

stb.

 

www.informatika-programozas.hu - Ezt most meg kell tanulni!

 

Az "üres" helyek 0 értékekkel való feltöltésekor -mivel nem kombinatorikai, hanem pusztán listázó az algoritmus-, jelentős adatredundancia, azaz adattöbblet keletkezik, amely nem megengedett (az azonos sorok pirossal jelölve).

 

A megoldás természetesen többféleképpen lehetséges, az egyik valós, már kombinatorikai algoritmus előveszi a lusta programozók csodafegyverét, a rekurziót, azt a programozás-technikai eljárást, amely során a függvény mindig önmagát hívja meg (Rekurzió (A tiédet!) című fejezet). Ezzel még nem foglalkoztunk, így az alábbi futtatható Java-kódot csak érdekességképpen illesztettem be. A kód másik érdekessége, hogy int elemSzam változtatásával tudjuk a 0 és 1 ismétléses variációs hosszt változtatni, tehát például int elemSzam = 3; esetén 3 elemű lesz a kombinációs halmaz:

 

Végeredmény:

000
001
010
011
100
101
110
111

 

www.informatika-programozas.hu - Futtatható Java-kód!

 

 

 

 

 

 

 


public class Main {
    public static void kombinacio(int i, int elemSzam, char[]tarolo) {
    if(i < elemSzam) {
        tarolo[i] = '0';
        kombinacio(i+1,elemSzam,tarolo);
        tarolo[i] = '1';
        kombinacio(i+1,elemSzam,tarolo);
    }
    else System.out.println(String.valueOf(tarolo));
    }

public static void main(String[] args) {
    int elemSzam = 12;
    kombinacio(0,elemSzam,new char[elemSzam]);
    }
}

 

Végeredmény (első néhány sor):

000000000000
000000000001
000000000010
000000000011
000000000100
000000000101
000000000110
000000000111
000000001000
000000001001
000000001010
000000001011
000000001100
000000001101
000000001110
000000001111
000000010000
000000010001
000000010010

stb.