算法

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]='\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’字符串结束符。最后输出每个字符串就好了。

38

发表评论