Christmas Tree Pattern

K

KennYblu3

Mitglied
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
 
Zuletzt bearbeitet:
S

SlaterB

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

KennYblu3

Mitglied
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?
 
Zuletzt bearbeitet:
S

SlaterB

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

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

Java: 
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..
 
A

Andi_CH

Top Contributor
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?
 
S

SlaterB

Gast
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
 
A

Andi_CH

Top Contributor
Ich hoffe dass es für mich hilfreich ist :D 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

Sonecc

Gesperrter Benutzer
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
 
S

SlaterB

Gast
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
 
Sonecc

Sonecc

Gesperrter Benutzer
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...
 
A

Andi_CH

Top Contributor
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.
 
X

XHelp

Top Contributor
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.
 
S

SlaterB

Gast
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..
 
X

XHelp

Top Contributor
Also wenn ich das so, wie ich es verstanden habe umsetze, dann kommt raus:
Code: 
n=1:
01

n=2:
  10
000111

n=3:
      00
    101101
  0000101010
00010101111111

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

SlaterB

Gast
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
Code: 
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
 
Zuletzt bearbeitet von einem Moderator:
K

KennYblu3

Mitglied
* | |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.
 
K

KennYblu3

Mitglied
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.
 
X

XHelp

Top Contributor
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.
 
S

SlaterB

Gast
@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?
 
X

XHelp

Top Contributor
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.
 
S

SlaterB

Gast
KennYblu3 hat gesagt.:
ich habs mit den regeln gebaut, deshalb frag ich ja ob es richtig ist ?
Zum Vergrößern anklicken....

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..
 
Zuletzt bearbeitet von einem Moderator:
K

KennYblu3

Mitglied
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
 
S

SlaterB

Gast
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 ;)
 
X

XHelp

Top Contributor
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)
Java: 
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;
		
	}
}
 
Zuletzt bearbeitet:
S

SlaterB

Gast
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:
Java: 
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
 
X

XHelp

Top Contributor
Da kommt ja sowas raus:
Code: 
          1010010101
          1001010110
     10000100011001110111
          1100011001
          0101011010
     01000010010101111011
          0110011100
     00100001010110111101
     00010001100111011110
000000000100011001110111111111
 
S

SlaterB

Gast
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 ;)
 
Zuletzt bearbeitet von einem Moderator:
S

SlaterB

Gast
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
 
X

XHelp

Top Contributor
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.
 

Aktuelle Jobs

Neue Themen


Oben