3.3　用递归算法求解问题

如果由问题可以给出初始状态、目标状态，且扩展子状态的规则和约束条件，则可以使用递归算法找出一个由初始状态至目标状态的求解方案。使用递归算法时需要注意：求解过程中每一步的状态由哪些参数组成？其中哪些参数需要主程序传入初始值？哪些参数不需要？因为这些参数在递归时需要计算新状态，而回溯时需要恢复递归前的状态。

对于不需要主程序传入初始值的参数，设为递归程序的局部变量，以免与同名的全局变量混淆；对于需要由主程序传入初始值的参数，则按照存储量分类。

·存储量小的参数，设为递归子程序的值参，由编译系统自动实现递归和回溯时的状态转换，即递归时值参入栈，回溯时值参出栈。

·存储量大的参数（例如数组），设为全局变量，以避免系统栈区溢出，但需在递归语句后（回溯位置）加入恢复递归前状态的语句。

【3.3.1　Fractal】

分形（fractal）是物体在数量上、内容上“自相似”的一种数学抽象。

一个盒分形（box fractal）定义如下。

·1度的盒分形为：

X

·2度的盒分形为：

X　　X

　X 

X　　X

·如果B(n-1)表示n-1度的盒分形，则n度的盒分形递归定义如下：

请画出n度的盒分形的图形。

输入

输入由若干测试用例组成，每行给出一个不大于7的正整数，最后一行以一个负整数-1表示输入结束。

输出

对于每个测试用例，输出用'X'标记的盒分形。注意'X'是大写字母。在每个测试用例后输出包含一个短横线的一行。

试题来源：ACM Shanghai 2004 Preliminary

在线测试：POJ 2083，ZOJ 2423

试题解析

n度的盒分形图的规模为3n-1，即n度的盒分形图是一个边长为3n-1个单位长度的正方形。因为n≤7，而36=729，所以定义一个731×731的二维字符数组map来存储度数不超过7的盒分形图。我们通过递归函数print(n,x,y)生成以(x,y)格为左上角的n度的盒分形图。

1）递归边界：若n=1，则在(x,y)格填一个'X'并返回。

2）若n>1，则分别在左上方、右上方、中间位置、左下方、右下方填5个n-1度的盒分形图，且n-1度的盒分形图的规模m=3n-2。

·对于左上方n-1度的盒分形图，其左上角的位置为(x,y)，递归print(n-1,x,y)生成；

·对于右上方n-1度的盒分形图，其左上角的位置为(x,y+2×m)，递归print(n-1,x,y+2×m)生成；

·对于中间位置n-1度的盒分形图，其左上角的位置为(x+m,y+m)，递归print(n-1,x+m,y+m)生成；

·对于左下方n-1度的盒分形图，其左上角的位置为(x+2×m,y)，递归print(n-1,x+2×m,y)生成；

·对于右下方n-1度的盒分形图，其左上角的位置为(x+2×m,y+2×m)，递归print(n-1,x+2×m,y+2×m)生成。

递归调用print(n,1,1)，即可生成n度的盒分形图。

参考程序

#include<iostream>
#include<cmath>
using namespace std;
char map[731][731];           //二维字符数组map用来存储度数不超过7的盒分形图
void print(int n,int x,int y) //print(n, x, y)生成以(x, y)格为左上角的n度的盒分形图
{
    int m;
    if(n==1)                  //递归边界
    {
        map[x][y]='X';
        return ;
    }
    m=pow(3.0,n-2);           // m=3n-2, n-1度的盒分形图的规模
    print(n-1,x,y);           //左上方
    print(n-1,x,y+2*m);       //右上方
    print(n-1,x+m,y+m);       //中间位置
    print(n-1,x+2*m,y);       //左下方
    print(n-1,x+2*m,y+2*m);   //右下方
}
int main(void)
{
    int i,j,n,m;              //n度的盒分形图
    while(scanf("%d",&n)!=EOF)
    {
        if(n==-1)
            break;
        m=pow(3.0,n-1);       //m=3n-1, n度的盒分形图的规模
        for(i=1;i<=m;i++)     //n度的盒分形图初始化
        {
            for(j=1;j<=m;j++)
                map[i][j]=' ';
        }
        print(n,1,1);         //print(n, 1, 1)，生成n度的盒分形图
        for(i=1;i<=m;i++)     //输出n度的盒分形图
        {
            for(j=1;j<=m;j++)
                printf("%c",map[i][j]);
            printf("\n");
        }
        printf("-\n");
    }
    return 0;
}

【3.3.2　Fractal Streets】

随着我们对城市现代化的渴望越来越强烈，对新街道设计的需求也越来越大。Chris是负责这些设计的城市规划师之一。每年的设计需求都在增加，今年他被要求完整地设计一个全新的城市。

Chris现在不希望做更多的工作，因为他非常懒惰。他非常亲密的朋友之一Paul是一名计算机科学家，Paul提出了一个让Chris在同龄人中成为英雄的绝妙想法：分形街道（Fractal Streets）。通过使用希尔伯特曲线（Hilbert curve），他可以很容易地填充任意大小的矩形图，而工作量很少。

一阶希尔伯特曲线由一个“杯形曲线”组成。在二阶的希尔伯特曲线中，这个杯形曲线的杯子被四个更小但相同的杯子和三条连接这些杯子的道路所代替。在三阶的希尔伯特曲线中，这四个杯子再依次被四个相同但更小的杯子和三条连接道路等所代替。在杯子的每个角落都有一条供住房使用的带邮箱的车道，并且每个角落有一个简单的连续编号。左上角的房子是1号，两个相邻的房子之间的距离是10米。

一阶、二阶和三阶希尔伯特曲线如图3.3-1所示。正如你所见，分形街道的概念成功地消除了烦人的街道网格，只需要我们做少许的工作。

为了表示感谢，市长在Chris新计划建造的许多社区中为他提供了一栋房子。Chris现在想知道这些房子中的哪一栋离当地城市规划办公室最近（当然每个新的社区都有一个）。幸运的是，他不必在街上开车，因为他的新“汽车”是一种新型的飞行汽车。这辆高科技的汽车使他可以直线行驶到新办公室。请你编写一个程序来计算Chris必要的飞行距离（不包括起飞和着陆的垂直距离）。

输入

输入的第一行给出一个正整数，表示测试用例的数量。

图　3.3-1

然后，对于每个测试用例，在一行中给出三个正整数n（n<16）、h和o（o<231），分别表示希尔伯特曲线的阶数，以及提供给Chris的房屋和当地城市规划办公室的房屋编号。

输出

对于每个测试用例，在一行中输出Chris飞到工作地点的距离，单位为米，四舍五入为最接近的整数。

试题来源：BAPC 2009

在线测试：POJ 3889

试题解析

本题给出一个分形图，输入给出3个数n、h、o，其中n为希尔伯特曲线的阶数（分形图的级数），h和o分别是提供给Chris的房屋和当地城市规划办公室的房屋编号。求在n阶希尔伯特曲线（n级分形图）的情况下，编号为h和o的两个点之间的欧几里得距离×10是多少？

其中，n阶希尔伯特曲线（n级分形图）的形成规则如下：

1）首先，在右下角和右上角复制n-1阶希尔伯特曲线（n-1级分形图）；

2）然后，将n-1阶希尔伯特曲线顺时针旋转90°，放到左上角；

3）接下来，将n-1阶希尔伯特曲线逆时针旋转90°，放到左下角；

4）编号是从左上角那个点开始计1，沿着道路计数。

设递归函数calc(int n,LL id,LL & x,LL & y)用于计算n级分形图的编号为id的点的坐标为(x,y)，分析如下。

递归边界：当n等于1时，即如图3.3-1a所示的1级分形图，分四种情况。当id等于1时，坐标(x,y)为(1,1)；当id等于2时，坐标(x,y)为(1,2)；当id等于3时，坐标(x,y)为(2,2)；当id等于4时，坐标(x,y)为(2,1)。

对calc(int n,LL id,LL & x,LL & y)的分析和递归定义如下：

1）当前编号id不大于上一级分形图（n-1级分形图）的编号的总数时，说明当前编号id是在n级分形图的左上角，而左上角分形图是n-1级分形图逆时针旋转90o得到的，所以在代入递归式时，需要将x和y互换，递归函数为calc(n-1,id,y,x)。例如，在1级分形图中，按点的编号，坐标的道路为(1,1)→(1,2)→(2,2)→(2,1)。而在1级分形图的左上角中，坐标的道路为(1,1)→(2,1)→(2,2)→(1,2)。在这两种情况中，x和y互换了。

2）当前编号id不大于上一级分形图（n-1级分形图）的编号的总数的2倍时，说明当前编号id在n级分形图的右上角；而当前编号id不大于上一级分形图（n-1级分形图）的编号的总数的3倍时，说明当前编号id在n级分形图的右下角。相应于n-1级分形图，这两种情况的分形图没有旋转，所以递归函数分别为calc(n-1,id-_id,x,y)和calc(n-1,id-2×_id,x,y)。

3）当前编号id不大于上一级分形图（n-1级分形图）的编号的总数的4倍时，说明当前编号id在n级分形图的左下角。而左下角分形图是n-1级分形图顺时针旋转90o得到的，通过比较坐标，x映射为(1<<n)+1-x，y映射为(1<<(n-1))+1-y，递归函数为calc(n-1,id-3×_id,y,x)。

参考程序

#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;                    //定义超长整型
void calc(int n, LL id, LL &x, LL &y){    //计算和返回n级分形图编号为id的点的坐标(x, y)
    if(n == 1){                          //处理递归边界
        if(id==1) x=1,y=1;
        if(id==2) x=1,y=2;
        if(id==3) x=2,y=2;
        if(id==4) x=2,y=1;
    }else{
        LL _id = (1<<(n-1))*(1<<(n-1));  //计算n-1级分形图的编号总数
        if(id <= _id){                   //编号id不大于n-1级分形图的编号总数时的情况
                                         //处理
            calc(n-1,id,y,x);
        }else if(id <= 2*_id){           //编号id不大于n-1级分形图的编号总数2倍时的
                                         //情况处理
            calc(n-1,id-_id,x,y);
            y += 1<<(n-1);               // y映射为y +2n-1
        }else if(id <= 3*_id){           //编号id不大于n-1级分形图的编号总数3倍时的
                                         //情况处理
            calc(n-1,id-2*_id,x,y);
            x += 1<<(n-1);               //x映射为x +2n-1, y映射为y +2n-1
            y += 1<<(n-1);
        }else{                           //编号id小于n-1级分形图的编号总数的4倍时的
                                         //情况处理
            calc(n-1, id-3*_id, y,x);
            x = (1<<n)+1-x;              //x映射为2n+1-x，y映射为2n-1+1-y
            y = (1<<n-1)+1-y;
        }
    }
}
int main(){
    int _w;  scanf("%lld", &_w);         //输入测试用例数
    while(_w--){                         //依次处理每个测试用例
        int n; LL h,o;
        scanf("%d%lld%lld", &n, &h, &o); //输入曲线阶数n、住房编号h和办公室编号o
        LL sx, sy, ex, ey;
        calc(n,h,sx,sy);                 //计算住房编号h的坐标（sx，sy）
        calc(n,o,ex,ey);                 //计算办公室o的坐标（ex，ey）
        printf("%.0f\n",sqrt((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey))*10);   
                             //输出h与o点间的距离
    }
    return 0;
}

使用递归算法求解的方式很多。下面将介绍其中应用非常广泛的一种方法——回溯法。

上一章目录下一章