2018年全国多校算法寒假训练营练习比赛（第一场）G-圆圈

时间：2023-02-13 12:59:20

本人关于此题的理解，首先look两眼这道题，可以想到的是用递归来解决的，那咱怎么解决呢？找，找有没有什么规律可以使得当前圆圈图形的和前一个的圆圈图形建立联系，细想一下，发现有很多可以彼此建立联系的枢纽，那这里咋就已每一个n所代表的中间位置为枢纽。举个栗子，n=3，那这个图形的中间位置就是x=3^(n-1)+3^(n-1)/2+1 （此处'/'是计算机整数相除的）  , y=x（这里y和x是相等的，我就不写那么长了哈）;即n==3的中间位置为（14，14），然后我们调用递归函数，再将这个中间位置拆分成四个更小的子图的中间位置，四个分别为（14，5），（14，23），（5，14），（23，14），此时n==2，一直递归，将每个中间位置跟上述一样处理为四个更小的子图的中间位置，一直到到n==1，这时只需将n==1的中间位置的上下左右都赋值为1（统一一下哈，什么值都可以，你开心就好！），然后我们历遍输出就行了。

 

 

链接：https://www.nowcoder.com/acm/contest/67/G



来源：牛客网
 

题目描述
 

 
 
 
  
    圈圈圆圆圈圈，lulu小朋友最近看喜羊羊看多了，老是受刺激就画圆圈，听到小于8的数字时，还会画出十分有规律的圆圈，现在你需要根据样例观察出规律，编写程序，根据输入的数字n（n<8）,输出对应的圆圈。
 
 
 
 
输入描述:
 
 
第一行是样例数T（T<9）
第2到2+T-1行每行有一个整数n（n<8），代表lulu听到的数字
 
 
输出描述:
 
 
听到对应数字时，输出对应样子的圆圈。
 
 
链接：https://www.nowcoder.com/acm/contest/67/G
来源：牛客网


 
 
 
  

    示例1 
  
 
  
 
   
 
    
输入
 
    
 
     
4
0
1
2
3
 
    
 
   
 
   
 
    
输出
 
    
 
     
O
 O
O O
 O
    O
   O O
    O
 O     O
O O   O O
 O     O
    O
   O O
    O
             O
            O O
             O
          O     O
         O O   O O
          O     O
             O
            O O
             O
    O                 O
   O O               O O
    O                 O
 O     O           O     O
O O   O O         O O   O O
 O     O           O     O
    O                 O
   O O               O O
    O                 O
             O
            O O
             O
          O     O
         O O   O O
          O     O
             O
            O O
             O
 
    
 
   
 
   
 
    
说明
 
    
 
     
当n=0时输出
O
当n=1时输出
*O
O*O
*O
当n=2时输出
****O
***O*O
****O
*O*****O
O*O***O*O
*O*****O
****O
***O*O
****O
上面的'O'是大写英文字母O，'*'代表空格，每一行最后一个O后面不带空格。
 
    
 
   
 
  
 
 
 
 
备注:
 
 
对于100%的数据，
0<T<9;
0<=n<8;
 
 
。
 
 
.
 
 
///每次找中间位置，依次递归到后一阶

#include<stdio.h>
#define maxs 2187+10
#include<math.h>
int e[maxs][maxs],n;    ///定义为全局变量
void dfs(int cur,int x,int y)
{
    int i,j,ti;
    if(cur==1)  ///在此处中间的上下左右都赋值为1
    {
        e[x][y-1]=1;
        e[x][y+1]=1;
        e[x-1][y]=1;
        e[x+1][y]=1;
        return;
    }
    else
    {
    ti=(int)pow(3,cur-1);  ///很容易得到规律，下一个的中间位置就是此处的横坐标或者纵坐标加或者减ti
        dfs(cur-1,x,y-ti);  ///4种情况都递归下一阶
        dfs(cur-1,x,y+ti);
        dfs(cur-1,x+ti,y);
        dfs(cur-1,x-ti,y);
        return;
    }
}
int main()
{
    int i,t,m,n,j,item,sum,u;
    scanf("%d",&sum);
    for(i=1; i<=sum; i++)
    {
        scanf("%d",&n);
        item=(int)pow(3,n);   ///数组的范围，很容易看出为3^n
        for(m=1; m<=item; m++) ///统一初始化为0
            for(j=1; j<=item; j++)
                e[m][j]=0;
        if(n==0)         ///如果n==0，直接输出
            printf("O\n");
        else
        {
            t=(int)pow(3,n-1)+((int)pow(3,n-1))/2+1; ///刚开始的中间位置

            dfs(n,t,t);  ///开始递归


            for(m=1; m<=item; m++) ///item是数组的范围
            {
                for(u=item;u>=1;u--)  ///应题目要求每行的最后一个O后面不带格，
                {                     ///那咱就从每一行的最后一个位置找起，
                                    ///找到数组值为1的位置，就是这一行需要输出的最后一个位置
                    if(e[m][u]==1) break;
                }
                for(j=1; j<=u; j++)  ///u就是第m行的最后一个位置
                {
//                    printf("%d ",e[m][j]);
                    if(e[m][j]==1)
                        printf("O");
                    else
                        printf(" ");
                }
                putchar('\n');
            }
        }

    }
    return 0;
}

 
 

 
 
 
 
。
 
 
怎样，是不是很通俗易懂，哈哈，我也觉得是，
 
 
现在是不是特想copy，哈哈，千万不要，要想真正理解，
 
 
需自己敲代码，不敲不行。就这样吧，你可以走了，去AC吧！
 



标签：
相关文章