华师一附中OI组

标题: 复杂字符图案 [打印本页]
作者: admin    时间: 2018-8-17 09:03
标题: 复杂字符图案
有些字符图案是找不到简单的字符和行号之间的关系的，比如杨辉三角，螺旋方针，幻方问题，cantor表等等，这样我们可以通过一个数组a[R][C]来寻找或者模拟字符和行列之间的关系，最后填满数组之后输出。强烈建议大家不要用x和y表示行和列，很容易引起误解，用r和c比较好。


输出程序段是非常好写的，每次输出一行后换行：

  1. void pp()
  2. {
  3.     int r,c;///平面图形输出千万不要用x和y
  4.     for (r=1; r<=n; r++)
  5.     {
  6.         for (c=1; c<=n; c++)  cout<<setw(4)<<a[r][c];
  7.         cout<<endl;
  8.     }
  9. }
复制代码
注意这里使用了一个setw函数控制输出列宽，这个函数在iomanip库里面，还有一个和他同样重要的函数 setprecision控制输出精度。
作者: admin    时间: 2018-8-17 09:04
比如杨辉三角，标准的应该是这样的：
                       1
                     1   1
                   1   2   1
                 1   3   3   1
               1   4   6   4   1
             1   5  10  10   5   1
           1   6  15  20  15   6   1
         1   7  21  35  35  21   7   1
       1   8  28  56  70  56  28   8   1
     1   9  36  84 126 126  84  36   9   1
但是我们知道，其实他是这样的，在输出的身后每行前面加上适当的空格就是了。本质上没有太大的区别。
   1
   1   1
   1   2   1
   1   3   3   1
   1   4   6   4   1
   1   5  10  10   5   1
   1   6  15  20  15   6   1
   1   7  21  35  35  21   7   1
   1   8  28  56  70  56  28   8   1
   1   9  36  84 126 126  84  36   9   1

很快的发现规律，
1、首尾都是1，
2、除此之外每个数字等于正上方和左上方的数字的和：a[r][c]=a[r-1][c-1]+a[r-1][c-1];
那么，立刻可以写出程序，先填满数组a[10][10]，然后打印输出：

  2.     int a[20][20];
  3.     int r,c;
  4.     for (r=0; r<=9; r++)  a[r][1]=a[r][r]=1;  ///首尾都是1

  6.     for (r=2; r<=9; r++)
  7.         for (c=1;c<=r-1; c++)
  8.             a[r][c]=a[r-1][c-1]+a[r-1][c]; ///填表过程

  10.     for (r=1; r<=9; r++)   ///输出过程
  11.     {
  12.         ///for (j=1; j<=10-r; j++) cout<<"  ";   ///这句话控制前面的空格数目
  13.         for (c=1; c<=r; c++)
  14.             cout<<setw(4)<<a[r][c];
  15.         cout<<endl
  16.     }

复制代码
然后在这个程序的输出部分加上一句控制行前空格的语句就可以把正三角形的变成斜三角形的。
  1. for (j=1; j<=10-r; j++) cout<<"  ";   ///这句话控制前面的空格数目
复制代码


作者: admin    时间: 2018-8-17 09:14
幻方问题，在n*n（n为奇数）的方框里面填上1-n*n的数字，使横竖和两主对角线上的n个的数字的和都是想等的。
比如 n=5;
17 24  1  8 15
23  5  7 14 16
  4  6 13 20 22
10 12 19 21  3
11 18 25  2  9
填法如下：
1、把1填在首行正中间2、计算下一个数字的位置：
    填在上一个数字的右上方，要是越界了，就按铺地砖的方式处理，也就是上面越界，就填在最下方，右边越界就填在最左边。
    若右上方有数字了，则填在正下方
3、重复直到n*n被填入
简单直观的做法：
  1. cin>>n;
  2.     r=0;c=n/2;k=1;a[r][c]=k;///1放在首行正中
  3.     while (k<n*n)
  4.     {
  5.        ///计算下一个
  6.        tr=r-1;  
  7.        tc=c+1;
  8.        ///越界处理
  9.        if (tr<0) tr=n-1;
  10.        if (tc==n) tc=0;
  11.        ///有数字的处理
  12.        if (a[tr][tc]>0) {tr=r+1;tc=c;}
  13.        ///填入
  14.        r=tr;c=tc;
  15.        k++;a[r][c]=k;
  16.     }
复制代码
更好的做法可以巧妙的处理这个越界，使用%自动来完成越界的处理，体会% 的用法。
  1.      cin>>n;
  2.      r=0;c=n/2;k=1;a[r][c]=k;
  3.      while (k<=n*n-1)
  4.      {
  5.         k++; //准备下一个数字
  6.         tr=(r-1+n)%n;tc=(c+1)%n; //计算右上方
  7.         //if (tr<0) tr=n-1;  //行越界处理
  8.         //if (tc>n-1) tc=0;//列越界处理
  9.         if (a[tr][tc]>0) {tr=r+1;tc=c;}  //有数字的处理
  10.         r=tr;c=tc;a[r][c]=k;
  11.      }

  13.     for (r=0; r<=n-1; r++)
  14.     {
  15.         for (c=0; c<=n-1; c++)
  16.             cout<<setw(3)<<a[r][c];
  17.         cout<<'\n';
  18.     }
复制代码



作者: admin    时间: 2018-8-22 17:56
螺旋方阵问题  打印出n*n的螺旋方阵
比如n=5
    1   2   3   4   5
  16  17  18  19   6
  15  24  25  20   7
  14  23  22  21   8
  13  12  11  10   9

n=6
   1   2   3   4   5   6
  20  21  22  23  24   7
  19  32  33  34  25   8
  18  31  36  35  26   9
  17  30  29  28  27  10
  16  15  14  13  12  11

这个题有很多的做法，每种做法都有一定的技巧，大家都可以认真做做，第一种做法，用udlr表示四个方向，四个方向按个数填充。
  1. int a[100][100],n;
  2. int u,d,l,r;  //u,d,l,r分别表示上下左右边界
  3. int i,j,k;
  4. void pp()
  5. {
  6.     int r,c;///平面图形输出千万不要用x和y
  7.     for (r=1; r<=n; r++)
  8.     {
  9.         for (c=1; c<=n; c++)  cout<<setw(4)<<a[r][c];
  10.         cout<<endl;
  11.     }
  12. }
  13. int main()
  14. {
  15.     cin>>n;
  16.     u=l=1;d=r=n;
  17.     k=1;
  18.     while (k<=n*n)
  19.     {
  20.         for (i=l; i<=r; i++) a[u][i]=k++; //沿着最上面从左到右；
  21.         u++; //上界变化
  22.         for (i=u; i<=d; i++) a[i][r]=k++; //沿着最右边从上到下；
  23.         r--; //右界变化
  24.         for (i=r; i>=l; i--) a[d][i]=k++; //沿着最下边从右到左；
  25.         d--; //上界变化
  26.         for (i=d; i>=u; i--) a[i][l]=k++; //沿着最上面从左到右；
  27.         l++; //上界变化
  28.     }
  29.     pp();
  30.     return 0;
  31. }
复制代码




作者: admin    时间: 2018-8-22 19:51
还有一个做法，就是在外圈设置一些标记，某些特殊的关键点设置为1，其余的地方都是0，从r=1 c=1开始填充这些0的区域，到达边界的地方就换方向，而换方向巧妙的使用了方向数组，这种方向数组在二维数组中很常用，体会这种做法，很精妙！
  1. #include <iostream>
  2. #include <iomanip>
  3. using namespace std;
  4. int a[100][100],n;
  5. int dr[]= {0,1,0,-1};
  6. int dc[]= {1,0,-1,0}; ///四个方向
  7. int i,j,r,c,k,d,tr,tc;
  8. int x;
  9. void pp()
  10. {
  11.     int r,c;///平面图形输出千万不要用x和y
  12.     for (r=1; r<=n; r++)
  13.     {
  14.         for (c=1; c<=n; c++)  cout<<setw(4)<<a[r][c];
  15.         cout<<endl;
  16.     }
  17. }
  18. int main()
  19. {
  20.     cin>>n;
  21.     a[1][n+1]=a[n+1][n]=a[n][0]=a[0][1]=1;///四个角标标记 第四个没意义
  22.     r=1;c=0;
  23.     k=1;d=0;
  24.     while (k<=n*n)
  25.     {
  26.         tr=r+dr[d],tc=c+dc[d];///计算下一个位置
  27.         if  (a[tr][tc]==0) ///能填的话
  28.             a[r=tr][c=tc]=k++;
  29.         else d=(d+1)%4; ///否则转向
  30.         ///pp();
  31.     }
  32.     pp();
  33.     return 0;
  34. }
复制代码






欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2