[Java] Wahrheitstaffel rekursiv

[NemesisFS]

Hi,
ich habe die Aufgabe, Wahrheitstafeln wie diese:

true	true	true
true	true	false
true	false	true
true	false	false
false	true	true
false	true	false
false	false	true
false	false	false

Für ein beliebiges n durch ein Programm rekursiv auszugeben. Mir ist nach einigen Stunden Arbeit nurnoch die Lösung eingefallen, es durch eine Matrix zu lösen, ich gehe davon aus, es gibt eine sehr viel elegantere Lösung, sie will mir aber nicht einfallen...

Hier ist mein Code:

 public class Hue8_3 {
	public static void main(String[] args) {
		truethtable(4);
	}

	static void truethtable(int n) {
		boolean matrix[][] = new boolean [(int) Math.pow(2, n)][n];
		truethtable2(n, 0, (int) Math.pow(2, n), matrix);
		printBoolMatrix(matrix);
		
	}

	static boolean[][] truethtable2(int n, int a, int b, boolean[][] matrix) {
		int i;
		if(n == 0) return matrix;

		for(i = a; i < (a + b)/2; i++) {		//true schreiben
			matrix[i][n-1] = true;
		}
		truethtable2(n-1, 0, (a+b)/2, matrix);		//nächste Ebene aufrufen

		for(i = (a + b)/2; i < b; i++) {		//false schreiben
			matrix[i][n-1] = false;
		}
		truethtable2(n-1, (a+b)/2, b, matrix);		//nächste Ebene aufrufen

		return matrix;
	}

	static void printBoolMatrix(boolean[][] matrix) {
		for(int i = 0; i < matrix.length;i++) {
			for(int j = 0; j < matrix[0].length;j++) {
				System.out.print(matrix[i][j] + "\t");
			}
		System.out.println();
		}
	}
}

Die Ausgabe ist leider völlig falsch:

true        true        true        
true        true        true        
true        false        true        
false        false        true        
false        true        false        
false        true        false        
true        false        false        
false        false        false

Ich habe schon versucht mit Netbeans zu debugen, aber im Debug Modus kriege ich eine Fehlermeldung, obwohl das Programm problemlos ausgeführt werden kann... Kann mir wer helfen?

mfg nemesis

 

[knoxyz]

Irre ich mich, oder muss eine Folgerung mit Variablen und Verknüpfung (und, oder, nicht,...) gegeben sein,
damit Wahrheitstafeln Sinn macht/überprüft werden kann?

 

[johbon]

Viel zu kompliziert was du da machst! Ich würde sagen schau dir noch mal die Matrix an ich sage nur:
0
1
2
3
4
5
6
7

 

[NemesisFS]

Die Wahrheitstafel soll nur für n verschiedene Boolsche Variablen alle möglichen Kombinationen angeben.

@johbon: Ich verstehe leider nicht, was du mir sagen willst... =/

 

[Killkrog]

Schau dir mal die Bit-Darstellung an...
1: 0001
2: 0010
3: 0011
4: 0100
...

Na, dämmerts?

 

[NemesisFS]

so langsam

Das ganze soll ja aber rekursiv gelöst werden...

 

[ManOki]

hmm ... informatiker würden da sowas denken:

0 - false false false
1 - true false false
2 - false true false

überleg dir mal, wofür die einzelnen - nenn ich sie mal bits - stehen könnten
und wie man einfach von 1 auf die einzelnen "bits schlussfolgern" kann

EDIT: boah, bin ich lahm ... -.-

 

[johbon]

um es kurz zu machen und dir den spaß zu nehmen:

static void truethtable(int von,int bis){
  if (von>bis) return;
  System.out.print(!(von&4) + " " + !(von&2) + " " + !(von&1) + "\n"); // Weiß nicht ob das der Java Syntax entspricht
  ++von;
  truethtable(von,bis);
}

 

[Killkrog]

Und, gibts ne genau Vorgabe, was für ne rekursion?

myFor(int current, int max) {
if (current == max) {
return;
}
// Anweisung mit current als Integer zum berechnen der Bitstellen
myFor(current+1, max);
}

Ist auch rekursiv

 

[NemesisFS]

Nunja es gibt keine Vorraussetzungen für die Rekursion...
Wie lassen sich denn Integer zahlen in Java bitweise ausgeben?

 

[[GP] mino]

probier mal das:

public static void main(String[] args) {
	int2bitstr(7);
}

public static void int2bitstr(int in){
		System.out.println(Integer.toBinaryString(in));
		if (in > 0) int2bitstr(in-1);
}

 

[NemesisFS]

vielen Dank, für die Lösung, ich fasses nicht, dass ich das nicht gesehn habe...

 

[johbon]

Nunja es gibt keine Vorraussetzungen für die Rekursion...
Wie lassen sich denn Integer zahlen in Java bitweise ausgeben?

Schon mal was von den Bitoperator und gehört? Weiß leider nicht wie er in Java angewendet wird!
Aber damit kannst du kanns einfach nach schauen ob Binär Code einer Decimalzahl ein 4,2 oder 1 vorkommt.

 

[[GP] mino]

vielen Dank, für die Lösung, ich fasses nicht, dass ich das nicht gesehn habe...

kein thema hauptsache was neues dazugelernt

 

[1668mib]

Wenn mir jetzt noch jemand sagen könnte, welchen Sinn diese Art der Rekursion hat... bin mir nicht sicher, ob das wirklich so gemacht werden soll...

Ich meine wenn man sich die Fakultät mit Rekursion anschaut, dann sieht man, dass bei jedem rekursiven Aufruf das Problem ja ein wenig vereinfacht wird... statt Fakultät von 4 brauch ich nur noch die Fakultät von 3 zu benutzen, und das multipliziere ich mit 4... für die von 3 brauch ich nur noch die von 2, für die von 2 brauch ich gar nicht rechnen... das Problem wird sozusagen immer "einfacher".

Die hier verwendeten Rekursionen sind lediglich ein (schlechter) Ersatz von Schleifen (gut, bei der Fakultät ist es auch kein guter Ersatz für eine Schleife, man muss nur mal an den Stack-Bedarf denken...).

 

[johbon]

probier mal das:

public static void main(String[] args) {
	int2bitstr(7);
}

public static void int2bitstr(int in){
		System.out.println(Integer.toBinaryString(in));
		if (in > 0) int2bitstr(in-1);
}

Ist leider nicht ganz so richtig was hier steht die Ausgaben die da kommen sehen dann so aus:
1. 111 = 7
2. 011 = 6
3. 101 = 5
4. 001 = 4
...
und so soll es sein:
1. 111 = 7
2. 110 = 3
3. 101 = 5
4. 100 = 4
...

 

[Killkrog]

Schon mal was von den Bitoperator und gehört? Weiß leider nicht wie er in Java angewendet wird!
Aber damit kannst du kanns einfach nach schauen ob Binär Code einer Decimalzahl ein 4,2 oder 1 vorkommt.

Für die Vollständigkeit und weils einfach stimmt, dass man für das obige Problem Bit-Ops hernehmen sollte!

int i = 105;
System.out.println(((i & 128) != 0) + " " + ((i & 64) != 0) + " " + ((i & 32) != 0) + " " + ((i & 16) != 0) + " " + ((i & 8) != 0) + " " + ((i & 4) != 0) + " " + ((i & 2) != 0) + " " + ((i & 1) != 0));
// Ausgabe: false true true false true false false true

 

[[GP] mino]

@johbon
verwirr mich nicht..

true true true = 111= 7
true true false = 110 = 6
true false true = 101 = 5
true false false = 100 = 4
false true true = 011 = 3
false true false = 010 = 2
false false true = 001 = 1
false false false = 000 = 0

und genau das kommt auch raus..

static int bitlen = 0;
	public static void int2bit(int in)
	{
		int iTemp = Integer.toBinaryString(in).length();
		if (iTemp > bitlen)
		{
			bitlen = iTemp;
			iTemp = 0;
		}
		else
			iTemp = bitlen - iTemp;
		
		String sTemp = "";
		for (int i = 0; i < iTemp; i++)
		  sTemp = sTemp + "0";
					
		System.out.println(sTemp + Integer.toBinaryString(in));
		if (in > 0) int2bit(in - 1);
	}

ergibt:

111
110
101
100
011
010
001
000

 

[johbon]

@mino
Das problem ist
true true false = 110 != 6 sondern
true true false = 110 = 3
6 wäre
false true true = 011 = 6

 

[NemesisFS]

hier mal die lösung, die ich inzwischen gebastelt habe:

static void int2bitstr(int n) {
	int2bitstr((int) (Math.pow(2, n) - 1), (int) (Math.pow(2, n) - 1));
}
	static void int2bitstr(int n, int x) {
		String string = Integer.toBinaryString(1 + n + x);
			for(int i = 1; i <= string.length() - 1;i++){
			System.out.print((string.charAt(i) == 49) ? "true\t" : "false\t");
		}
			System.out.println();
		if(x > 0) int2bitstr(n, x-1);
}

um die vorhergehenden Nullen mit auszugeben, habe ich die Zahl einfach so erhöht, dass das nächste Bit aufjedenfall gesetzt ist.