The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1941-The Sierpinski Fractal 感悟递归之美^_^

原题链接:http://162.105.81.212/JudgeOnline/problem?id=1941

解题方法:刚开始拿到这道题,我的第一反应是要一行一行的输出,不过做了几分钟之后发现:在题述意思下行与行之间似乎没有规律可言;
所以这种方法只能作罢;后来看了看discuss,有人提到用递归的方法来做这道题,这才恍然大悟:像种大问题嵌套类似之子问题的时候,递归不是最理想的方法么?
开一个很大的二维矩阵(因为不知道N的最大值有多大,矩阵尽量开大一点可以避免越界),然后给出中间某个点的坐标,让它成为整个图形的坐下点坐标,然后递归得“画出”三个子图形(当然还要注意一下递归出口O(∩_∩)O~),即可;当然在不知道这个题目n的最大值时,我们可以每次画图后刷新一边矩阵,不过为了优化速度,我只将n=10的图形画出,然后再由点与点之间的关系,求出各个参数的大小即可;
最后输出,这个没什么可说的了。。。

说句题外话,我交题的时候出现Access denied
幸好过年的时候也遇到过同样情况 用IP地址才可正常访问 大家注意下:

遇到Access denied的用户请通过http://162.105.81.212访问poj



#include<iostream>
#include
<cmath>
#include 
<cstdlib>
using namespace std;
#define MAX 100000000
#define MIN -100000000

char mymap[5000][5000];

int leftdot;
int rightdot;
int topdot;
int bottomdot;

void figure(int x,int y,int deep)
{

    
if(deep==1)
    
{

        mymap[x][y]
='/';
        mymap[x][y
+1]='_';
        mymap[x][y
+2]='_';
        mymap[x][y
+3]='\\';
        mymap[x
-1][y+1]='/';
        mymap[x
-1][y+2]='\\';
    }

    
else
    
{
        
int dis=(int)pow((double)2,deep);
        figure(x,y,deep
-1);
        figure(x,y
+dis,deep-1);
        figure(x
-dis/2,y+dis/2,deep-1);
    }

}



int main ()
{

    
int n;
    
int i,j;
    leftdot
=MAX;
    rightdot
=MIN;
    topdot
=MAX;
    bottomdot
=MIN;
    memset(mymap,
' ',sizeof(mymap));
    figure(
2500,2500,10);
    
    
while(scanf("%d",&n))
    
{

        
if(n==0)
            
break;

        topdot
=2500-(int)pow((double)2,10)+1;
        bottomdot
=topdot+(int)pow((double)2,n)-1;
        leftdot
=2500+(int)pow((double)2,10)-(int)pow((double)2,n);
        rightdot
=leftdot+(int)pow((double)2,n+1)-1;
        
for(i=topdot;i<=bottomdot;i++)
        
{

            
for(j=leftdot;j<=rightdot;j++)
            
{

                printf(
"%c",mymap[i][j]);
            }

            printf(
"\n");
        }

        printf(
"\n");
        
    }

    
return 0;
    system(
"pause");
}


posted on 2009-03-27 22:08 abilitytao 阅读(2414) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理