Hilbert 曲线

题目:写一段程序, 可以画出左图曲线. 语言不限, 输出形式不限(可以输出到屏幕, 输出到一个位图文件, 或是你能想到的表达方式).

云风写了一个参考程序可以观看绘制的过程, 请 下载(27k)

注:  SPACE 跳过绘制过程
     F8    截图
     ESC   退出

提示：这个是一条 Hilbert 曲线, 我们来看看 1 阶曲线见左下图, 二阶见中下图, 三阶见右下图. 发现规律了吗?

这一次的活动, 得到了大家的支持, 在此表示感谢 :-) 按收到的解答的时间次序, 依次有:

• FGF, 用 VB 写的版本, 很漂亮 ;-) 大家可以去他的主页看看.
• haplo, 这里有他用 MFC 写的版本(20k) (由于主页空间紧张, 我删去了 exe 文件, 只留下源码)
• 小熊猫, 一个 java 的版本(8k), 运行版本我放在这里了, 应该可以直接用浏览器观看, 不过我的 Netscape 好象不支持 :-(

实际上, 理解了这个图形的含义, 程序并不难写. 曲线是递归定义的, 每个曲线是由 4 个同样的曲线 (方向有所不同) 构成, 之间用短直线连接. 收到的代码大致相同, 只需要在程序中处理 4 个方向的曲线, 然后用递归绘制就 OK 了.

这里, 我看了朋友们寄来的代码, 从效率上, 有一点我觉得有一点应该改进. 收到的所有代码都将曲线的 4 个方向放在一个函数中处理, 典型的是 FGF 朋友的代码. 这从人的思维角度讲没有错, 但云风天生喜欢从速度上考虑编码. 这里, 如果将各种方向的处理用 if...then...else 或 switch...case 结构, 势必造成大量的分支跳转, 程序优化的一个重点在于避免分支, (当然这个程序, 另一个优化策略在于消除递归, 这里较麻烦, 略去不提) 所以我个人的建议是为每个方向的 曲线做一个单独的函数.云风自己的代码如下:

#include "windsoul.h"

#define WIDTH 14
#define color 0xffffff

int x,y;

void draw_1(int n);
void draw_2(int n);
void draw_3(int n);
void draw_4(int n);

#define LEFT hline(screen,x,y,x-WIDTH,color);x-=WIDTH
#define RIGHT hline(screen,x,y,x+WIDTH,color);x+=WIDTH
#define UP vline(screen,x,y,y-WIDTH,color);y-=WIDTH
#define DOWN vline(screen,x,y,y+WIDTH,color);y+=WIDTH

void draw_1(int n)
{
	if (n==0) return;
	draw_4(n-1);
	LEFT;
	draw_1(n-1);
	DOWN;
	draw_1(n-1);
	RIGHT;
	draw_2(n-1);
}

void draw_2(int n)
{
	if (n==0) return;
	draw_3(n-1);
	UP;
	draw_2(n-1);
	RIGHT;
	draw_2(n-1);
	DOWN;
	draw_1(n-1);
}

void draw_3(int n)
{
	if (n==0) return;
	draw_2(n-1);
	RIGHT;
	draw_3(n-1);
	UP;
	draw_3(n-1);
	LEFT;
	draw_4(n-1);
}

void draw_4(int n)
{
	if (n==0) return;
	draw_1(n-1);
	DOWN;
	draw_4(n-1);
	LEFT;
	draw_4(n-1);
	UP;
	draw_3(n-1);
}

int wsInit()
{
	install(draw);
	install(input);
	clear_bitmap_ex(screen,0);
	x=500,y=WIDTH;
	draw_1(5);
	return 0;
}

int wsMain()
{
	if (keystat[KEY_ESC]) return 1;
	if (keystat[KEY_F8]) save_bmp(screen,"screen.bmp");
	update_screen();
	return 0;
}

void wsExit()
{
}