C++分形递归

c++分形递归例题。 分形，具有以非整数维形式充填空间的形态特征。通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质 。

一个盒状分形定义如下： 度为1的盒分形为：

 X 

度为2的盒分形为：

X X
 X
X X

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

B(n - 1)        B(n - 1)

        B(n - 1)

B(n - 1)        B(n - 1)

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

输入格式:

输入一系列度，每行给出一个不大于7的正整数。输入的最后一行以-1表示输入结束

输出格式:

对于每个用例，输出用’X’标记的盒状分形。在每个测试用例后输出包含一个短划线“-”的一行。

输入样例:

1
2
3
4
-1

输出样例:

注意：每行的空格请输出完整。

X
-
X X
 X 
X X
-
X X   X X
 X     X 
X X   X X
   X X   
    X    
   X X   
X X   X X
 X     X 
X X   X X
-
X X   X X         X X   X X
 X     X           X     X 
X X   X X         X X   X X
   X X               X X   
    X                 X    
   X X               X X   
X X   X X         X X   X X
 X     X           X     X 
X X   X X         X X   X X
         X X   X X         
          X     X          
         X X   X X         
            X X            
             X             
            X X            
         X X   X X         
          X     X          
         X X   X X         
X X   X X         X X   X X
 X     X           X     X 
X X   X X         X X   X X
   X X               X X   
    X                 X    
   X X               X X   
X X   X X         X X   X X
 X     X           X     X 
X X   X X         X X   X X
-

解题算法

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n[1000];
char a[1000][1000];
int mypow(int d)
{
    int ans=1;
    for(int i=1;i<=d;i++)
        ans*=3;//为什么乘3呢？因为图形是3*3的
    return ans;
}

void dfs(int cur,int x,int y)
{
    if(cur==1)
    {
        a[x][y]='X';
        return ;
    }
    int s=mypow(cur-2);
    dfs(cur-1,x,y);//打出左上的X应该变为的图形；
    dfs(cur-1,x,y+2*s);//打出右上的X应该变为的图形；
    dfs(cur-1,x+s,y+s);//打出中间的X应该变为的图形；
    dfs(cur-1,x+2*s,y);//打出左下的X应该变为的图形；
    dfs(cur-1,x+2*s,y+2*s);//打出右下的X应该变为的图形；
}

int main()
{
    int k=0;
    while(~scanf("%d",&n[k])){
        if(n[k]==-1){
            break;
        }
        k++;
    }
    k=0;
    while(n[k]!=-1)
    {
        memset(a,' ',sizeof(a));
        dfs(n[k],1,1);
        int s=mypow(n[k]-1);
        for(int i=1;i<=s;i++)//横着的长度为3的n-1次方，纵着的长度为3的n-1次方
        {
            a[i][s+1]='
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n[1000];
char a[1000][1000];
int mypow(int d)
{
int ans=1;
for(int i=1;i<=d;i++)
ans*=3;//为什么乘3呢？因为图形是3*3的
return ans;
}
void dfs(int cur,int x,int y)
{
if(cur==1)
{
a[x][y]='X';
return ;
}
int s=mypow(cur-2);
dfs(cur-1,x,y);//打出左上的X应该变为的图形；
dfs(cur-1,x,y+2*s);//打出右上的X应该变为的图形；
dfs(cur-1,x+s,y+s);//打出中间的X应该变为的图形；
dfs(cur-1,x+2*s,y);//打出左下的X应该变为的图形；
dfs(cur-1,x+2*s,y+2*s);//打出右下的X应该变为的图形；
}
int main()
{
int k=0;
while(~scanf("%d",&n[k])){
if(n[k]==-1){
break;
}
k++;
}
k=0;
while(n[k]!=-1)
{
memset(a,' ',sizeof(a));
dfs(n[k],1,1);
int s=mypow(n[k]-1);
for(int i=1;i<=s;i++)//横着的长度为3的n-1次方，纵着的长度为3的n-1次方
{
a[i][s+1]='\0';//在3的n-1次方后面没有多余的空格
}
for(int i=1;i<=s;i++)
{
printf("%s\n",a[i]+1);
}
printf("-\n");
k++;
}
system("pause");
return 0;
}
';//在3的n-1次方后面没有多余的空格
        }
        for(int i=1;i<=s;i++)
        {
            printf("%s\n",a[i]+1);
        }
        printf("-\n");
        k++;
    }
    system("pause");
    return 0;
}

这是一个递归算法，因为每次只能输出一行，所以预先创建了一个大数组存放图形。dfs的作用为递归输出每个小单元，mypow计算小单元之间的距离。由于使用了memset初始化数组为‘ ’，在主程序中把3的n-1次方后更换为‘\0’字符串结束符。最后输出每个字符串就好了。

---