首页 > > 程序设计 > C/C++ >

递归（五）：递归图形

2019-08-16 07:42:19来源：博客园阅读 ()

递归（五）：递归图形

【例1】递归三角形图案。

输入一个正整数n（n<=7），按图1的示例输出相应的由星号组成的三角形图案。

图1 n分别为2、3、4、5的三角形图案

（1）编程思路。

根据题目示例可知，度数为n的三角形图案，将占2^n-1行2^n-1列，可以用一个二维字符数组来存储图形中各个字符，因为n<=7，而2⁶=64，因此可以定义一大小为64*64的字符数组来存储度数不超过7的图形。

图2

度数n为4的三角形图案在二维数组中的存储情况如图2所示。由图2可知，度数为4的图案可以由度数为3的图案（图2中蓝色底纹所示）复制而来，即在其右方和正下方分别是一个度数为3的图案。

因此，度数为n的图形G(n)可以由以下递归式子表示：

G(n - 1) G(n - 1)

G(n - 1)

设递归函数void draw(int n,int x,int y)表示在（x，y）位置开始设置度数为n的图形，它由3个度数为n-1的图形组成，其起始位置分别为：（x，y）、（x，y+2^n-2）和（x+2^n-2，y）。

该递归函数的结束条件是：当n=1时（即度数为1的图形），只需在（x，y）位置设置一个字符'*'即可。

（2）源程序。

#include <iostream>

using namespace std;

#define N 64

void draw(char a[][N], int n, int row, int col)

{

if(n==1){

a[row][col] = '*';

return;

}

int w = 1;

int i;

for(i=1; i<=n-2; i++) w *= 2;

draw(a, n-1, row, col);

draw(a, n-1, row, col+w);

draw(a, n-1, row+w,col);

}

int main()

{

char a[N][N];

int n,w,i,j;

for(i=0;i<N;i++)

for(j=0;j<N;j++)

a[i][j] = ' ';

cin>>n;

w=1;

for(i=1; i<=n-1; i++) w *= 2;

draw(a,n,0,0);

for(i=0; i<w; i++)

{

for(j=0; j<w; j++)

cout<<a[i][j]<<" ";

cout<<endl;

}

return 0;

}

【例2】打印图形（2014年第5届蓝桥杯省赛试题）。

小明在X星球的城堡中发现了如下图形：

编写一个程序，实现该图形的打印。

（1）编程思路。

度数n为4的图案在二维数组中的存储情况如图3所示。由图3可知，度数为4的图案可以由3个度数为3的图案（图3中分别用绿色、浅绿色和黄色蓝色底纹所示）。

因此，度数为n的图形G(n)可以由以下递归式子表示：

G(n - 1)

G(n - 1) G(n - 1)

设递归函数void draw(int n,int x,int y)表示在（x，y）位置开始设置度数为n的图形，它由3个度数为n-1的图形组成，其起始位置分别为：（x，y+2^n-2）、（x+2^n-2，y）和（x+2^n-2，y+2^n-1）。

该递归函数的结束条件是：当n=1时（即度数为1的图形），只需在（x，y）位置设置一个字符'*'即可。

（2）源程序。

#include <stdio.h>

#define N 70

void f(char a[][N], int rank, int row, int col)

{

if(rank==1){

a[row][col] = '*';

return;

}

int w = 1;

int i;

for(i=0; i<rank-1; i++) w *= 2;

f(a, rank-1, row, col+w/2);

f(a, rank-1, row+w/2, col);

f(a, rank-1, row+w/2, col+w);

}

int main()

{

char a[N][N];

int i,j,x,w;

for(i=0;i<N;i++)

for(j=0;j<N;j++) a[i][j] = ' ';

scanf("%d",&x);

w=1;

for(i=0; i<x-1; i++) w *= 2;

f(a,x,0,0);

for(i=0; i<w; i++){

for(j=0; j<2*w; j++) printf("%c",a[i][j]);

printf("\n");

}

return 0;

}

【例3】打印图形（2018年第9届蓝桥杯省赛试题）。（原题是填空题）

编写一个程序，在控制台绘制分形图（就是整体与局部自相似的图形）。

当n=1,2,3的时候，输出如下：

（1）编程思路。

度数为n的图形，其大小是3ⁿ*3ⁿ，可以用字符数组来存储图形中各个字符。

度数为n的图形可以有以下递归式子表示：

B(n - 1)

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

B(n - 1)

设递归函数void draw(int n,int x,int y)表示在（x，y）位置开始设置度数为n的图形，它由5个度数为n-1的图形组成，其起始位置分别为：（x+s，y）、（x，y+s）、（x+s，y+s）、（x+2*s，y+s）和（x+s，y+2*s），其中s=3^(n-1)。

（2）源程序。

#include <iostream>

using namespace std;

#define N 729

void draw(char a[][N], int n, int row, int col)

{

if(n==0){

a[row][col] = 'O';

return;

}

int w = 1;

int i;

for(i=1; i<=n-1; i++) w *= 3;

draw(a,n-1, row+w, col);

draw(a,n-1, row, col+w);

draw(a,n-1, row+w,col+w);

draw(a,n-1, row+2*w, col+w);

draw(a,n-1, row+w,col+2*w);

}

int main()

{

char a[N][N];

int n,w,i,j;

for(i=0;i<N;i++)

for(j=0;j<N;j++)

a[i][j] = ' ';

cin>>n;

w=1;

for(i=1; i<=n; i++) w *= 3;

draw(a,n,0,0);

for(i=0; i<w; i++)

{

for(j=0; j<w; j++)

cout<<a[i][j];

cout<<endl;

}

return 0;

}

（3）蓝桥杯填空题给出的源程序。（请自己阅读体会）

#include <stdio.h>
#include <stdlib.h>
void show(char* buf, int w)
{
int i,j;
for(i=0; i<w; i++) {

for(j=0; j<w; j++) {

printf("%c", buf[i*w+j]==0? ' ' : 'o');
}
printf("\n");
}
}
void draw(char* buf, int w, int x, int y, int size){
if(size==1){
buf[y*w+x] = 1;
return;
}
int n = size/3 ; // 填空
draw(buf, w, x, y, n);
draw(buf, w, x-n, y ,n);
draw(buf, w, x+n, y ,n);
draw(buf, w, x, y-n ,n);
draw(buf, w, x, y+n ,n);
}
int main()
{
int N = 3;
int t = 1;
int i;
for(i=0; i<N; i++) t *= 3;
char* buf = (char*)malloc(t*t);
for(i=0; i<t*t; i++) buf[i] = 0;
draw(buf, t, t/2, t/2, t);
show(buf, t);
free(buf);
return 0;
}

【例4】Fractal（POJ 2083）。

Description

A fractal is an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales. The object need not exhibit exactly the same structure at all scales, but the same "type" of structures must appear on all scales.

A box fractal is defined as below :

A box fractal of degree 1 is simply

A box fractal of degree 2 is

X X

If using B(n - 1) to represent the box fractal of degree n - 1, then a box fractal of degree n is defined recursively as following

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

B(n - 1)

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

Your task is to draw a box fractal of degree n.

Input

The input consists of several test cases. Each line of the input contains a positive integer n which is no greater than 7. The last line of input is a negative integer −1 indicating the end of input.

Output

For each test case, output the box fractal using the 'X' notation. Please notice that 'X' is an uppercase letter. Print a line with only a single dash after each test case.

Sample Input

-1

Sample Output

X X X X

X X

X X X X

X X

X X X X

X X

X X X X

X X X X X X X X

X X X X

X X X X X X X X

X X X X

X X

X X X X

X X X X X X X X

X X X X

X X X X X X X X

X X X X

X X

X X X X

X X

X X X X

X X

X X X X

X X X X X X X X

X X X X

X X X X X X X X

X X X X

X X

X X X X

X X X X X X X X

X X X X

X X X X X X X X

（1）编程思路。

度数为n的图形，其大小是3^(n-1)*3^(n-1)，可以用字符数组来存储图形中各个字符，因为n<=7，而3^6=729，因此可以定义一大小为731*731的字符数组来存储度数不超过7的图形。

度数为n的图形可以有以下递归式子表示：

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

B(n - 1)

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

设递归函数void draw(int n,int x,int y)表示在（x，y）位置开始设置度数为n的图形，它由5个度数为n-1的图形组成，其起始位置分别为：（x，y）、（x，y+2*s）、（x+s，y+s）、（x+2*s，y）和（x+2*s，y+2*s），其中s=3^(n-2)。

该递归函数的结束条件是：当n=1时（即度数为1的图形），只需在（x，y）位置设置一个字符'X'即可。

（2）源程序。

#include<iostream>

#include<cmath>

using namespace std;

char map[731][731];

void draw(int n,int x,int y)

{

int size;

if(n==1)

{

map[x][y]='X';

return ;

}

size=pow(3.0,n-2);

draw(n-1,x,y); //左上角

draw(n-1,x,y+2*size); //右上角

draw(n-1,x+size,y+size); //中间

draw(n-1,x+2*size,y); //左下角

draw(n-1,x+2*size,y+2*size); //右下角

}

int main()

{

int i,j,n,size;

while(cin>>n && n!=-1)

{

size=pow(3.0,n-1);

for(i=1;i<=size;i++)

{

for(j=1;j<=size;j++)

map[i][j]=' ';

}

draw(n,1,1);

for(i=1;i<=size;i++)

{

for(j=1;j<=size;j++)

cout<<map[i][j];

cout<<endl;

}

cout<<"-\n";

}

return 0;

}

原文链接:https://www.cnblogs.com/cs-whut/p/11096348.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：关于拼写小助手的开发日记

下一篇：C++11智能指针原理和实现

IDC资讯：主机资讯注册资讯托管资讯 vps资讯网站建设

网站运营：建站经验策划盈利搜索优化网站推广免费资源

网站联盟：联盟新闻联盟介绍联盟点评网赚技巧

行业资讯：搜索引擎网络游戏电子商务广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器安全防护

软件技巧：其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识：网络协议网络安全网络管理组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条

最新资讯

热门关注

热门标签