递归绘制Thue-Morse模式

Question

这是网络练习3.1.63。从“计算机科学”一书中看塞奇威克和韦恩的跨学科方法：

编写一个程序，读取命令行输入N，并绘制N到N的Thue-Morse模式.下面是N= 4，8和16的Thue-Morse模式.

这是我的节目：

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是本书作者编写的一个简单的API。我检查了我的程序就行了。以下是它的一个实例：

输入:n= 256

输出：

有什么办法可以改进我的计划吗？

感谢您的关注。

Answer 1

有什么办法可以改进我的计划吗？

是:)

一个很好的线索，看看你的程序是否可以改进，是当有很多重复的代码。通常有避免重复的方法，尽管它们有时会变得相当复杂。然而，由于两个非常重要的原因，避免重复是有用的：

• 复制/粘贴通常会导致“哑”错误。
• 如果你想改变一件事，你需要在十亿个地方改变它，使它更有可能你会忘记一个。

老实说，我正在尽可能多地阅读您的代码，但我不明白在那里发生了什么，所以很难对您正在做的事情进行回顾，但这也表明代码不够清晰，无法被试图理解它的人理解(在本例中是我)。

我们能做些什么呢？

• 使用全面的名称(用于方法、变量、所有真正的东西)
• 正确地间隔代码(你有没有读过一本复杂的论文/书，其中所有的文本都被压缩了？)你有没有读过另一本有好间距的书？它创造了一个与众不同的世界！
• 避免注释代码(为什么有注释代码？)是个错误吗？应该不予评论吗？评论了多久了？为什么？)
• 最后，当这些提示都不够时，您应该对代码进行注释，但是要小心不要“过度注释”。注释应该足够长，以便有人能够理解为什么您这样做。没有必要在StdDraw.setPenColor(StdDraw.BOOK_BLUE);上解释诸如“我正在改变钢笔颜色”之类的东西

现在，我认为有一件事可以帮助代码的可读性。现在，您的代码既计算“模式”，又打印它。如果您首先生成了一个适合当前问题的二进制2D数组，并且有另一个打印这个数组的函数，那该怎么办？

以您给出的N=4案例为例，数组可以如下所示：

0110
1001
1001
0110

将算法与打印分离也会让您看到如何改进代码。

例如，我们可以注意到row_i和col_i之间存在对称性，这意味着我们只需要找到网格的一半的值就可以找到所有的值(对于一个N值较大的问题来说，这将是一个有价值的优化)。

现在，如果我看一下你给我们的链接，我就会发现：

令人惊讶的是，Thue-Morse序列可以从替换系统生成:0 -> 01和1 -> 10，递归地生成.

让我们来看看您给我们的N=8示例的第一行。我们需要这个替换序列的log_2(8)=3迭代：0->01->0110->01101001。让我们用以下内容填充我们的2D数组：

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

现在，让我们填充第二行，知道第一个值是1：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

为了完成，让我们完成第三行，剩下的留给您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

我想你知道事情的结局了吧。这导致了一种非常具有表现力的代码方法，应该非常容易理解。然后，您可以有一个函数paintThueMorse，给它这个2D数组，并画蓝色的1，白色的0或逆。