Drawing a Thue-Morse pattern recursively
This is web exercise 3.1.63. from the book Computer Science An Interdisciplinary Approach by Sedgewick & Wayne:
Write a program that reads in a command line input N and plots the N-by-N Thue-Morse pattern. Below are the Thue-Morse patterns for N = 4, 8, and 16.
Here is my program:
public class ThueMorse
{
public static void drawThueMorse1(int n, double x, double y, double size)
{
if (n == 0) return;
double x1 = x - size/2, x2 = x + size/2;
double y1 = y - size/2, y2 = y + size/2;
StdDraw.setPenColor(StdDraw.BOOK_BLUE);
StdDraw.filledRectangle(x+(3*size/4),y,size/4,size/2);
//StdDraw.pause(300);
StdDraw.filledRectangle(x-(3*size/4),y,size/4,size/2);
//StdDraw.pause(300);
StdDraw.filledRectangle(x,y+(3*size/4),size/2,size/4);
//StdDraw.pause(300);
StdDraw.filledRectangle(x,y-(3*size/4),size/2,size/4);
//StdDraw.pause(300);
StdDraw.setPenColor(StdDraw.WHITE);
StdDraw.filledSquare(x,y,size/2);
//StdDraw.pause(300);
StdDraw.filledSquare(x+(3*size/4),y+(3*size/4),size/4);
//StdDraw.pause(300);
StdDraw.filledSquare(x+(3*size/4),y-(3*size/4),size/4);
//StdDraw.pause(300);
StdDraw.filledSquare(x-(3*size/4),y-(3*size/4),size/4);
//StdDraw.pause(300);
StdDraw.filledSquare(x-(3*size/4),y+(3*size/4),size/4);
//StdDraw.pause(300);
drawThueMorse1(n-1, x1, y1, size/2);
drawThueMorse2(n-1, x1, y2, size/2);
drawThueMorse2(n-1, x2, y1, size/2);
drawThueMorse1(n-1, x2, y2, size/2);
}
public static void drawThueMorse2(int n, double x, double y, double size)
{
if (n == 0) return;
double x1 = x - size/2, x2 = x + size/2;
double y1 = y - size/2, y2 = y + size/2;
StdDraw.setPenColor(StdDraw.WHITE);
StdDraw.filledRectangle(x+(3*size/4),y,size/4,size/2);
//StdDraw.pause(300);
StdDraw.filledRectangle(x-(3*size/4),y,size/4,size/2);
//StdDraw.pause(300);
StdDraw.filledRectangle(x,y+(3*size/4),size/2,size/4);
//StdDraw.pause(300);
StdDraw.filledRectangle(x,y-(3*size/4),size/2,size/4);
//StdDraw.pause(300);
StdDraw.setPenColor(StdDraw.BOOK_BLUE);
StdDraw.filledSquare(x,y,size/2);
//StdDraw.pause(300);
StdDraw.filledSquare(x+(3*size/4),y+(3*size/4),size/4);
//StdDraw.pause(300);
StdDraw.filledSquare(x+(3*size/4),y-(3*size/4),size/4);
//StdDraw.pause(300);
StdDraw.filledSquare(x-(3*size/4),y-(3*size/4),size/4);
//StdDraw.pause(300);
StdDraw.filledSquare(x-(3*size/4),y+(3*size/4),size/4);
//StdDraw.pause(300);
drawThueMorse1(n-1, x1, y1, size/2);
drawThueMorse2(n-1, x1, y2, size/2);
drawThueMorse2(n-1, x2, y1, size/2);
drawThueMorse1(n-1, x2, y2, size/2);
}
public static int log2(int x)
{
return (int) (Math.log(x)/Math.log(2));
}
public static void main(String[] args)
{
int n = Integer.parseInt(args[0]);
n = log2(n)-1;
drawThueMorse1(n, 0.5, 0.5, 0.5);
}
}
StdDraw is a simple API written by the authors of the book. I checked my program and it works. Here is one instance of it:
Input: N = 256
Output:
Is there any way that I can improve my program?
Thanks for your attention.
Antworten
Is there any way that I can improve my program?
Yes :)
Ein guter Anhaltspunkt, um zu sehen, ob Ihr Programm verbessert werden kann, ist, wenn der Code viele Wiederholungen enthält. Es gibt normalerweise Möglichkeiten, Wiederholungen zu vermeiden, obwohl sie manchmal ziemlich komplex werden können. Das Vermeiden von Wiederholungen ist jedoch aus zwei sehr wichtigen Gründen nützlich:
- Kopieren / Einfügen führt normalerweise zu "dummen" Fehlern
- Wenn Sie etwas ändern möchten, müssen Sie es an einer Milliarde Stellen ändern, damit es wahrscheinlicher wird, dass Sie eines vergessen.
Ich bin sehr ehrlich, ich lese Ihren Code so oft ich kann, aber ich verstehe nicht, was dort passiert, daher wird es schwierig sein, einen Überblick darüber zu geben, was Sie tun, aber es ist auch so ein Hinweis darauf, dass der Code nicht klar genug ist, um von jemandem verstanden zu werden, der versucht, ihn zu verstehen (in diesem Fall von mir).
Was kann man dagegen tun?
- Verwenden Sie umfassende Namen (das gilt für Methoden, Variablen, alles wirklich)
- Platzieren Sie den Code richtig (Haben Sie jemals ein kompliziertes Papier / Buch gelesen, in dem der gesamte Text eng war? Haben Sie jemals ein anderes gelesen, in dem der Abstand gut war? Es macht einen großen Unterschied!)
- Vermeiden von kommentiertem Code (Warum ist er dort? Ist es ein Fehler? Sollte er nicht kommentiert werden? Wie lange wurde er kommentiert? Warum?)
- Wenn keiner dieser Tipps ausreicht, sollten Sie Ihren Code kommentieren, aber vorsichtig sein, um nicht zu "überkommentieren". Kommentare sollten gerade lang genug sein, damit jemand verstehen kann, warum Sie so codiert haben, wie Sie es getan haben. Es ist nicht nötig, Dinge wie "Ich ändere die Stiftfarbe" zu erklären
StdDraw.setPenColor(StdDraw.BOOK_BLUE);
Nun, es gibt eine Sache, von der ich denke, dass sie die Lesbarkeit des Codes erheblich verbessern würde. Im Moment berechnet Ihr Code das "Muster" und druckt es aus. Was wäre, wenn Sie zuerst ein binäres 2D-Array generiert hätten, das zum vorliegenden Problem passt, und eine andere Funktion hätten, die dieses Array druckt?
Anhand eines Beispiels für den von Ihnen angegebenen Fall N = 4 könnte das Array folgendermaßen aussehen:
0110
1001
1001
0110
Wenn Sie den Algorithmus vom Druck trennen, können Sie auch sehen, wie Sie Ihren Code verbessern können.
Zum Beispiel können wir feststellen, dass es eine Symmetrie zwischen dem \ gibt$row_i\$und \$col_i\$Dies bedeutet, dass wir nur den Wert der Hälfte des Gitters finden müssen, um alle Werte zu finden (dies wäre eine wertvolle Optimierung für ein Problem mit einem großen NWert).
Wenn ich mir nun den Link ansehe, den Sie uns gegeben haben, sehe ich Folgendes:
Erstaunlicherweise kann die Thue-Morse-Sequenz rekursiv aus dem Substitutionssystem erzeugt werden: 0 -> 01 und 1 -> 10.
Schauen wir uns dies mit der ersten Zeile des Beispiels N = 8 an, das Sie uns gegeben haben. Wir brauchen \$log_2(8)=3\$Iterationen dieser Substitutionssequenz : 0->01->0110->01101001. Füllen wir unser 2D-Array damit:
0 1 1 0 1 0 0 1
1 X X X X X X X
1 X X X X X X X
0 X X X X X X X
1 X X X X X X X
0 X X X X X X X
0 X X X X X X X
1 X X X X X X X
Füllen wir nun die zweite Zeile aus und wissen, dass der erste Wert 1 ist: 1 -> 10 -> 1001 -> 10010110
0 1 1 0 1 0 0 1
1 0 0 1 0 1 1 0
1 0 X X X X X X
0 1 X X X X X X
1 0 X X X X X X
0 1 X X X X X X
0 1 X X X X X X
1 0 X X X X X X
Lassen Sie uns zum Abschluss die dritte Reihe machen, und den Rest überlasse ich Ihnen 10 -> 1001 -> 10010110
0 1 1 0 1 0 0 1
1 0 0 1 0 1 1 0
1 0 0 1 0 1 1 0
0 1 1 X X X X X
1 0 0 X X X X X
0 1 1 X X X X X
0 1 1 X X X X X
1 0 0 X X X X X
Ich denke du siehst wo das endet. Dies führt zu einem ziemlich performanten Ansatz mit Code, der ziemlich einfach zu verstehen sein sollte. Danach könnten Sie eine Funktion paintThueMorsehaben, ihr dieses 2D-Array geben und blau für 1, weiß für 0 oder umgekehrt malen.