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ő mélységű és mennyisé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:
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:
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:
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:
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.
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
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.
Pénzes László