# Christmas Tree Pattern



## KennYblu3 (7. Dez 2010)

Hi,

ich muss eine Aufgabe in der Uni lösen leider versteh ich den Algorithmus überhaupt nicht. Kann mir da jemand helfen? versuch schon paar Tage mit Papier und Stift den Algorithmus zu verstehen, aber irgendwie macht es einfach nicht click. Der Algorithmus heist Christmas Tree Pattern. Im Internet find ich dazu nichts, im Buch von Don Knuth Art of Programming ist auch nichts zu finden.

Ich hab mal das Aufgabenblatt hochgeladen. 

Kostenloser Bilder Upload Service - Gratis Bilder hochladen / uploaden ohne Anmeldung


----------



## Andi_CH (7. Dez 2010)

Und wie ist dieser Algoritmus definiert? (Meine Glaskugel ist immer noch in Reparatur)


----------



## KennYblu3 (7. Dez 2010)

Hab den post editiert  Aufgabenblatt ist oben


----------



## ARadauer (7. Dez 2010)

zeig mal was du schon hast


----------



## SlaterB (7. Dez 2010)

ganz kontret gefragt: was ist das Muster der Ordnung 2? verstehst du wie es aus dem Muster der Ordnung 1, nämlich 01 entsteht?


----------



## KennYblu3 (7. Dez 2010)

also bei n =2  ist das Muster ja:
     10
00  01 11

oder ?

bei n =3 ist doch S2 = 01; S3=11 und S1 = 00 richtg?


----------



## SlaterB (7. Dez 2010)

> bei n =2 ist das Muster [..]

das scheint mir korrekt,
jetzt fange an so eine Methode zu schreiben, die das liefert, damit


```
public static void main(String[] args) {
  System.out.prinln(next("01"));
}
```
funktioniert,
ob der Rückgabewert der Methode ein String[] oder ein String mit Zeilenumbruch sein sollte ist ganz egal,
mach wie du denst nur dass es vorangeht,
baue also diese Methode, trenne den Parameter in einzelne Zeilen und Zeichen auf, 
baue Schritt für Schritt, Regel für Regel, den neuen Wert zusammen,

wenn dir beim Programmieren konkrete Probleme entgegentreten, dann poste die hier,
aber nur generell 'wie geht das' ist schlecht, auch wenn es wie so oft zumindest für die Tipps reicht, die ich jetzt hier geschrieben habe,
aber sind das wirklich schon neue Infos?

------

> bei n =3 ist doch S2 = 01; S3=11 und S1 = 00 richtg? 

groß S1 kenne ich gar nicht, meinst du s1..st wie in der Aufgabe genannt?
dann muss man erstmal festhalten, dass es nun zwei Zeilen gibt, die getrennt zu zerlegen sind, die erste Zeile ähnlich dem allerersten Schritt,
die zweite Zeile besteht aus 6 Zeichen, es gibt s1 bis s6, jedes s steht für eine Ziffer, meiner Interpretation nach

wobei der Zusatz (für t = 1 entfällt die erste Zeile) komisch ist, eine Zeile mit nur einer Ziffer gibts doch gar nicht..


----------



## Andi_CH (7. Dez 2010)

Ich versteh die Notation der Rekursion nicht

S10 S11...St-11 St1

Sollte die rote 1 nicht eine 2 sein?

und was heisst überhaupt S10 ???
Zeile 1 alles 0?


----------



## SlaterB (7. Dez 2010)

ist es hilfreich wenn du deine Unwissenheit hier einbringst? 

bedeutet eben dass das erste s doppelt hingeschrieben werden soll, meiner Meinung nach, ob das was bringt zeigt sich vielleicht wenn man einen größeren Baum erstellt,
wenn es gut aussieht, dann bestimmt so gemeint, ansonsten kann man nach Alternativen suchen, wobei ich da nichts anderes mögliches sehe

s1 0 ist genau s1 und 0


----------



## Andi_CH (7. Dez 2010)

Ich hoffe dass es für mich hilfreich ist  oder soll ich für meine Fragen (ich hoffe ja was zu lernen) einen eigenen Thread aufmachen?

Zeile S1 ist "0"
Zeile S1 ist "1"
Zeile S2 ist "1"

Das kann ich vorerst noch nicht glauben


----------



## Sonecc (7. Dez 2010)

IMHO ist die Aufgabe inkorrekt gestellt, da t nie definiert wird. Ich persönlich kann da nur raten, was t sein soll. Kann aber auch sein, dass ich ein Brett vorm Kopf habe


----------



## SlaterB (7. Dez 2010)

es gibt kein S1 mit großem S, es gibt s1, eine Ziffer eines Bitwortes (10101110..),
ein Bitwort ist eine Zeile, bestehend aus mehreren einzelnen s,
eine Ornung ist besteht aus mehreren Zeilen

> Zeile S1 ist "0"
macht da keinen Sinn, eher
Zeile 10 besteht aus s1=1 und s2=0


----------



## Andi_CH (7. Dez 2010)

Sonecc hat gesagt.:


> IMHO ist die Aufgabe inkorrekt gestellt, da t nie definiert wird. Ich persönlich kann da nur raten, was t sein soll. Kann aber auch sein, dass ich ein Brett vorm Kopf habe



t ist IMHO die Anzahl Zeilen die gezeichnet werden soll


----------



## Sonecc (7. Dez 2010)

Ich deute aus t die Anzahl der Zeilen der Ordnung n (also der vorhergehenden Ordnung).
t könnte aber auch die Länge der Zeile der vorhergehenden Ordnung sein, da in Aufgabenteil 1 si als ein Bitstring der Länge n definiert wurde.
Alles sehr schwammig und ungenau definiert meiner Meinung nach...


----------



## Andi_CH (7. Dez 2010)

Hab ich schon mal gesagt, dass ich CaseSensitive Sprachen hasse!

Also sed /S/s/ - alles klar?

Egal aber wir alle hier (sind aktuell 5 Personen ;-) ) möchte dann schon gerne die Lösung sehen um zu verstehen wie man die Schreibweise implementieren muss.


----------



## XHelp (7. Dez 2010)

Es sieht nicht gerade nach einem geeignetem Beispiel für die Rekursion.
Außerdem ist am Anfang nur 1 Zeile da. Wenn eine Zile gibt, dann wird dir auch nur durch 1 Zeile ersetzt (für t=1 entfällt die erste Zeile), also bleibt es immer bei einer Zeile, wenn man es versucht rückwärts aufzubauen.
Äußerst komische Aufgabe.


----------



## SlaterB (7. Dez 2010)

t wird vorher in s1...st verwendet, für mich ist das klar die Länge an Zeichen in einer Zeile (5 in 01000),
die Bedingung spielt dann wie gesagt keine Rolle, weil es keine Zeile mit nur einer Ziffer gibt,

ganz dumm ist sie nicht, denn die Regeln setzen ja zum Teil t > 1 voraus, damit passt es es logisch etwas besser..


----------



## XHelp (7. Dez 2010)

Also wenn ich das so, wie ich es verstanden habe umsetze, dann kommt raus:

```
n=1:
01

n=2:
  10
000111

n=3:
      00
    101101
  0000101010
00010101111111
```

Aber so richtig mustermäßig sieht es nicht aus.


----------



## SlaterB (7. Dez 2010)

stimmt, und das Gerede der Darstellung von allen 2^n Bitwörtern der Länge n passt auch überhaupt nicht,
für n = 3 gibt es 8 Bitwörter, manuell ideal dargestellt als

```
000
100
001
010
110
011
101
111
```
aber auch kein schöner Baum und hat mit der Aufgabe wenig zu tun.., ist wohl für schlauere Menschen gedacht


----------



## KennYblu3 (7. Dez 2010)

* |    |100 |101 |      * 3
* |    |010 |110 |      * 3
* |000 |001 |011 |111   * 3


das kommt doch raus fuer n =3 ? oder ? ich dreh durch mit diesem scheiss ;P
3 Zeilen, und 2^3 Strings.


----------



## SlaterB (7. Dez 2010)

wie kommst du auf diese 2^3 Strings?, das wär ja ideal


----------



## KennYblu3 (7. Dez 2010)

steh doch da :

Es
beschreibt eine systematische Anordnung dieser 2n Strings von n Bits. Im Folgenden
bezeichnet si immer einen Bitstring der Länge n.

Oder versteh ich das auch falsch ?

Wie soll ich das den programmieren wenn ich den algo nicht mal richtig versteh dum di dum.


----------



## XHelp (7. Dez 2010)

Ne, es muss schon etwas baumartiges rauskommen, da du ja eine Zeile mit x zeichen durch 2 Zeilen mit 2*(x-1) und 2*(x+1)-Zeichen ersetzt.


----------



## SlaterB (7. Dez 2010)

@KennYblu3
dass es für n=3  acht verschiede Bitwörter gibt, klar, 
nur hast du die jetzt wie ich in meinem Posting von 17:46 einfach beliebig aufgeschrieben 
oder hast du sie mit dem Regeln aus der Aufgabe berechnet?


----------



## KennYblu3 (7. Dez 2010)

ich habs mit den regeln gebaut, deshalb frag ich ja ob es richtig ist ?


----------



## XHelp (7. Dez 2010)

Es müssen Zeilen rauskommen, Sterne und Ziffern >1 sind nicht dabei genau so wie "|", von daher bin ich mir ziemlich sicher, dass es falsch ist.


----------



## KennYblu3 (7. Dez 2010)

100 101 
010 110 
000 001 011 111

dann halt so ? ;P
mir gehts um die Bits ob die in der richtigen reinfolge sind.......


----------



## SlaterB (7. Dez 2010)

KennYblu3 hat gesagt.:


> ich habs mit den regeln gebaut, deshalb frag ich ja ob es richtig ist ?



wie du vielleicht erahnen könntest verzweifeln wir anderen alle daran, also erkläre doch bitte WIE du das mit den Regeln gemacht hast,
Schritt für Schritt, zu jedem Bit warum es dahinkommt,
wieviele Zeilen und ob | dazwischen oder nicht, das stört gar nicht mal

edit: aber ich glaube so langsam habe ich es auch

n=2 ist
10
00 01 11

und je zwei Bit zusammen sind dann ein s, t ist dann 3 für die zweite Zeile,
Leerzeichen sind also doch wichtig..

si soll ja auch ja auch ein Bitstring der Länge n sein, nicht ein Bit, tjaja..


----------



## KennYblu3 (7. Dez 2010)

Also da das Muster 2^1 vorgegeben ist "0 1"

ist s1=0 und s2=1

wenn man sich das jetzt fuer 2^2 abbildet. Muss man nur s1 und s2 in die 
s2"0" . . . st"0"
s1"0" s1"1" . . . st−1"1" st"1"
Aussagen einfügen.

Also ist 2^2
10  (s2"0" ; s2=1;also 10)
00  01  11

4 Strings und 2 Zeilen


ich hoffe ich hab das so richtig verstanden


----------



## SlaterB (7. Dez 2010)

für n=2 war das schon bekannt, liest du eigentlich was alles auf Seite 1 an Postings stehen? 
bzw. hast du ja selber um 13:56 geschrieben, nix neues,
für n=3 wirds interessanter, habe ich nun aber auch verstanden, siehe mein edit oben, 

---

so, nur noch programmieren


----------



## XHelp (7. Dez 2010)

Das wäre mein Vorschlag. Es sollte definitiv nicht so übernommen werden und mindestens nachvollzogen wäre (zumal für meinen Geschmack ein paar Abfragen fehlen. Also die Lösung könnte falsch sein, aber anders kann ich den Algo nicht deuten:
(der Code ist wohl eher an SlaterB gerichtet, ob er es auch so verstanden hat)

```
public class Strange {
	public static void main(String[] args) {
		for (int n=1;n<4;n++) {
			List<String> res = getStrangeShit(n);
			System.out.println("n="+n+":");
			int maxLength = res.get(res.size()-1).length();
			for(String line:res) {
				for (int i=0;i<(maxLength-line.length())/2;i++) {
					System.out.print(" ");
				}
				System.out.println(line);
			}
		}
	}
	
	public static List<String> getStrangeShit(int n) {
		List<String> result = new ArrayList<String>();
		if (n<=1) {
			result.add("01");
		} else {
			List<String> tmp = getStrangeShit(n-1);
			for (String currentLine:tmp) {
				String newLine = "";
				for (int j=1;j<currentLine.length();j++) { //ab S2
					newLine+=currentLine.charAt(j)+"0"; //Sj0
				}
				if (!newLine.isEmpty()) { //wenn t>1 ist, wobei diese Regel nie eintritt
					result.add(newLine);
				}
				newLine = "";
				for (int j=0;j<currentLine.length();j++) { //ab S1
					newLine+=currentLine.charAt(j)+"1"; //Sj1
				}
				newLine = currentLine.charAt(0)+"0"+newLine; //S0+'0' am Anfang
				result.add(newLine);
			}
		}
		return result;
		
	}
}
```


----------



## SlaterB (7. Dez 2010)

ja, inzwischen haben ich/wir ja (dank Hilfe des ursprünglichen Fragestellers  ) ein anderes Verständnis,
si ist wie gesagt nicht ein Bit sondern gleich n Bits

damits schnell vorangeht, so sieht das Programm dann aus:

```
public class Test {
    public static void main(String[] args)  {
        for (int n = 1; n < 6; n++)    {
            List<String> res = getStrangeShit(n);
            System.out.println("n=" + n + ":");
            int maxLength = res.get(res.size() - 1).length();
            for (String line : res)    {
                for (int i = 0; i < (maxLength - line.length()) / 2; i++)   {
                    System.out.print(" ");
                }
                System.out.println(line);
            }
        }
    }

    public static List<String> getStrangeShit(int n)  {
        List<String> result;
        if (n <= 1)  {
            result = new ArrayList<String>();
            result.add("01");
        }  else    {
            List<String> tmp = getStrangeShit(n - 1);
            result = new ArrayList<String>();
            for (String currentLine : tmp) {
                int width = n - 1;
                int t = currentLine.length() / width;
                String newLine = "";
                if (t > 1)  {
                    for (int j = 1; j < t; j++)  { // ab S2
                        newLine += sub(currentLine, j, width) + "0"; // Sj0
                    }
                    result.add(newLine);
                }
                newLine = "";
                for (int j = 0; j < t; j++) { // ab S1
                    newLine += sub(currentLine, j, width) + "1"; // Sj1
                }
                newLine = sub(currentLine, 0, width) + "0" + newLine; // S0+'0' am Anfang
                result.add(newLine);
            }
        }
        return result;
    }

    private static String sub(String st, int j, int width)  {
        return st.substring(j * width, (j + 1) * width);
    }


}
```
Umsetzung in Swing noch schwer genug


----------



## XHelp (7. Dez 2010)

Da kommt ja sowas raus:

```
1010010101
          1001010110
     10000100011001110111
          1100011001
          0101011010
     01000010010101111011
          0110011100
     00100001010110111101
     00010001100111011110
000000000100011001110111111111
```


----------



## SlaterB (7. Dez 2010)

ist doch schick, die 0en und 1en haben keine Bedeutung, die grobe Form finde ich durchaus passend als Tannenbaum,
kein Dreieck aber besser als gar nichts, ist ja nicht einfach das in so einer Aufgabe einzubauen,,

mit höheren n siehts erstmal aus..,  sehr hoher Baun der nicht besonders breit wird,
hoch ist aber auch nur n=10, 12 usw., n=100 oder 10.000 sollte man lieber nicht probieren


----------



## KennYblu3 (7. Dez 2010)

FAIL 

der Baum soll bei n=4 so aussehen:

Kostenloser Bilder Upload Service - Gratis Bilder hochladen / uploaden ohne Anmeldung

jetzt versteh ich garnichts mehr JUHU


----------



## SlaterB (7. Dez 2010)

das ist n=8 und in meinem Programm sieht es auch genau so aus, von Leerzeichen mal abgesehen, die zu ergänzen ist eine gute Aufgabe für dich


----------



## XHelp (7. Dez 2010)

Bist du sicher, dass es wirklich bei n=4 sein soll? Es sollen ja in dem Baum alle Möglichkeiten von n-Stelligen Binärzahlen dargestellt werden, und dein Baum sieht verdächtig nach 8-stelligen Zahlen aus.


----------

