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