ACM/ICPC 之 分治法入门(画图模拟:POJ 2083)
2024-10-07 22:53:28
题意:大致就是要求画出这个有规律的Fractal图形了= =
例如 1 对应 X
2 对应 X X
X
X X
- 这个题是个理解分治法很典型的例子(详情请参见Code)
- 分治法:不断缩小规模,以致把整个大问题分解为若干个可以直接处理的小问题,一般通过递归调用实现,可以用极简代码完成高复杂的工作,但空间与时间占用也相对较大。
//分治法画图
//Memory:880K Time:16 Ms
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; #define MAX 1000 //╮(╯▽╰)╭,毕竟图形处理是硬伤,只能用数组模拟画布了= =
char fig[MAX][MAX]; //figure
int scale; void dfs(int n,int size,int x,int y)
{
if(n==)
fig[x][y] = 'X';
else
{
//规模缩小一倍
size /= ; /*分治画五个分区域*/
dfs(n-,size,x,y);
dfs(n-,size,x+size*,y);
dfs(n-,size,x,y+size*);
dfs(n-,size,x+size,y+size);
dfs(n-,size,x+size*,y+size*);
}
} int main()
{
int n,i,j;
while(~scanf("%d",&n), n != -)
{
//计算当前规模所产生的尺寸
scale = ;
for(i=;i<=n;i++)
scale *= ;
//初始化画布
for(i=;i<=scale;i++)
{
for(j=;j <= scale;j++)
fig[i][j] = ' ';
fig[i][j] = '\0';
} dfs(n,scale,,);
for(i=;i<=scale;i++)
printf("%s\n",&fig[i][]);
printf("-\n");
} return ;
}
最新文章
- scala 的内部类
- Android --差缺补漏之 Intent&;putExtra()
- BlockingQueue深入分析
- ExtJS4.2学习(四)Grid表格中文排序问题(转)
- java BingInteger生成2进制String循环移位时长度自动缩减
- java基础->;循环
- 设计模式学习(四): 1.简单工厂 (附C#实现)
- 笔记︱支持向量机SVM在金融风险欺诈中应用简述
- 实验-使用VisualVM或JConsole进行对程序进行性能分析
- Javascript中构造函数的返回值问题和new对象的过程
- [LeetCode] 724. Find Pivot Index_Easy tag: Dynamic Programming
- Ubuntu 16.04下安装网络流量分析工具 Wireshark
- ASP.NET MVC 学习笔记-1.ASP.NET MVC 基础
- 使用RequireJS并实现一个自己的模块加载器 (二)
- PIL中文文档
- openstack多region介绍与实践---转
- SERVER 2008 R2 SP1下的内存虚拟盘(支持32位,64位的所有windows版本)
- linux系统中-E,-S,-c的区别和作用(怎么讲代码转化为机器识别的语言)
- 将setter方法与itemClick: 进行类比
- android开发游记:meterial design 5.0 开源控件整套合集 及使用demo