「算法」蛇形填数 & S型填数

简介: 这一篇将接着利用上一次的打印模板,来破解其他类型的模拟题目。

「算法」蛇形填数 & S型填数


这一篇将接着利用上一次的打印模板,来破解其他类型的模拟题目。教你打遍天下无敌手(bushi

模板👇

//向下走 
while(x + 1 <= n && !res[x + 1][y]) {
        res[++x][y] = ++count;
}
//向左
while(y - 1 > 0 && !res[x][y - 1]) {
        res[x][--y] = ++count;
}
//向上
while(x - 1 > 0 && !res[x - 1][y]) {
        res[--x][y] = ++count;
}
//向右
while(y + 1 <= n && !res[x][y + 1]) {
        res[x][++y] = ++count;
} 

接下来就医S型填数以及蓝桥杯比赛中出现的题,三角蛇形打印为例,继续套用我们的打印模板。


1.S形填数


题目

1.png

不用多说,就是给一个数字(矩形的边长),然后打印出如图所示的规律的矩形。


思考


这是蛇形填数中最简单的一种,我们只需要按照S形的方法填充数字即可。\

我们可以发现如果我们定义一个二维数组,那么二维数组的第0列、第2列、第4列,即偶数列,数字都是从上往下依次填充的;而第1列、第3列、第5列,即奇数列,数字都是从下到上依次填充的。


所以,


初始化数字类型数组int arr[100][100] = { 0 };

但是字符串数组不能这么初始化...字符串要用memset函数

数字往下走就是

//向下走 
while(x + 1 <= n && !res[x + 1][y]) {
        res[++x][y] = ++count;
}

往上走就是

while(x - 1 >= 0 && !res[x - 1][y]) { 
    res[x--][y] = ++count; 
}

代码


核心代码:

vector<vector<int>>  res(n + 2, vector<int>(n + 2,0));
int count = 1;
res[1][1] = 1;
int x = 1;
int y = 1;
while(count < n *n) {
        //向下走 
        while(x + 1 <= n && !res[x + 1][y]) {
                res[++x][y] = ++count;
        }
        y++;
        //向上
        while(x - 1 >= 0 && !res[x - 1][y]) {
                res[x--][y] = ++count;
        }
        y++;
}

完整代码:

#include<stdio.h>
int main()
{
  int n = 0;
  int arr[100][100] = { 0 };  //初始化。建议memset(arr,0,sizeof(arr))
  scanf("%d", &n);       //输入需要填充的数组的大小,arr[n][n]
  //填充数组
  int i = 0;
  int num = 1;
  for (i = 0; i < n; i++)//需要打印n列数字
  {
    if (i % 2 == 0)//偶数列填充
    {
      int x = 0;
      int y = i;
      for (x = 0; x <= n-1; x++)
      {
        arr[x][y] = num;
        num++;
      }
    }
    else//奇数列填充
    {
      int x = n - 1;
      int y = i;
      for (x = n - 1; x >= 0; x--)
      {
        arr[x][y] = num;
        num++;
      }
    }
  }
  //打印数组
  int j = 0;
  for (i = 0; i < n; i++)
  {
    for (j = 0; j < n; j++)
    {
      printf("%-3d ", arr[i][j]);
    }
    printf("\n");
  }
  return 0;
}

2.三角蛇形(蓝桥杯)


题目

1.png

思考


这是蛇形填数中最复杂的一种,我们需要从左上角开始按斜S形对数组进行填数。


虽然看似复杂,但仔细观察还是有规律可循的,我们可以斜着看,将每每条斜着的一串数字看成是一次循环填充数字,循环的次数便是用户输入的n的大小。


我们依然定义i为循环次数,那么当i为0、2、4即偶数的时候,数字都是从左下向右上填充的;当i为1、3、5即奇数的时候,数字都是从右上向左下填充的。


因为循环次数i是从0开始的,所以每次循环填充的数字的个数就可以表示为i+1。


仍然可以套用之前的while代码

1.png

代码


方法一:
#include <bits/stdc++.h> 
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<vector<int>>  res(n + 2, vector<int>(n + 2,0));
  int count = 1;
  res[1][1] = 1;
  int x = 1;
  int y = 1;
  while(count < n * (n + 1) / 2) {
    y++;  //向左 
    //斜向下走 
    while(x != 0 && y != 0 && !res[x + 1][y - 1]) {
      res[x++][y--] = ++count;
    }
    y++;  //向下
    //斜向上走
    while(x != 0 && y != 0 && !res[x - 1][y + 1]) {
      res[x--][y++] = ++count;
    }
                //跳回到输出的矩阵内,好继续后面的while循环
    x++;
    y--;
  }
        for(int i = 1; i <= n; i++) {
          for(int j = 1; j <= n - i + 1; j++) {
        cout << res[i][j];
        if(j != n - i + 1) { cout << " ";} 
                else { cout << endl;}
      }
  }
  return 0;
}
方法二:
#include<stdio.h>
int main()
{
  int n = 0;
  int arr[100][100] = { 0 };
  scanf("%d", &n);//输入需要填充的数组的大小,arr[n][n]
  //填充数组
  int i = 0;
  int num = 1;
  for (i = 0; i < n; i++)
  {
    if (i % 2 == 0)//i为偶数时,数字从左下向右上填充
    {
      int x = i;
      int y = 0;
      while (x+1)//每次循环填充的数字个数为i+1即x+1个
      {
        arr[x][y] = num;
        num++;
        x--;
        y++;
      }
    }
    else//i为奇数时,数字从右上向左下填充
    {
      int x = 0;
      int y = i;
      while (y+1)//每次循环填充的数字个数为i+1即y+1个
      {
        arr[x][y] = num;
        num++;
        x++;
        y--;
      }
    }
  }
  //打印数组
  int j = 0;
  for (i = 0; i < n; i++)
  {
    for (j = 0; j < n; j++)
    {
      printf("%-3d ", arr[i][j]);
    }
    printf("\n");
  }
  return 0;
}


相关文章
|
机器学习/深度学习 算法
【算法基础】筛质数
【算法基础】筛质数
81 0
|
9月前
|
算法 测试技术 C#
【菲蜀定理 子序列】1250 检查「好数组」
【菲蜀定理 子序列】1250 检查「好数组」
|
8月前
线性代数——(期末突击)行列式(上)-行列式计算、行列式的性质
线性代数——(期末突击)行列式(上)-行列式计算、行列式的性质
227 7
|
8月前
线性代数——(期末突击)行列式(下)-行列式按行展开、范德蒙行列式、克拉默法则
线性代数——(期末突击)行列式(下)-行列式按行展开、范德蒙行列式、克拉默法则
275 7
|
人工智能 算法
算法提高:组合数学| 容斥原理常见应用
容斥原理常见的问题如下。 (1) 篮球、羽毛球、网球三种运动,至少会一种的有22人,会篮球的有15人,会羽毛球的有17人,会网球的有12人,既会篮球又会羽毛球的有11人,既会羽毛球又会网球的有7人,既会篮球又会网球的有9人,那么三种运动都会的有多少人? (2) 《西游记》《三国演义》《红楼梦》三大名著,至少读过其中一本的有20人,读过《西游记》的有10人,读过《三国演义》的有12人,读过《红楼梦》的有15人,读过《西游记》《三国演义》的有8人,读过《三国演义》《红楼梦》的有9人,读过《西游记》《红楼梦》的有7人。问三本书全都读过的有多少人?
205 0
算法提高:组合数学| 容斥原理常见应用
|
C语言
【C语言刷题】喝汽水问题、上三角矩阵判定以及矩阵相等判定
【C语言刷题】喝汽水问题、上三角矩阵判定以及矩阵相等判定
102 0
【C语言刷题】喝汽水问题、上三角矩阵判定以及矩阵相等判定
|
C语言
C语言【海伦公式 求三角形面积】
C语言【海伦公式 求三角形面积】
498 0
|
机器学习/深度学习 算法 索引
算法步步为营(1)-两数之和
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。可以按任意顺序返回答案。
98 0
|
存储 算法 vr&ar
算法步步为营(02)-两数之和
两个非空链表,表示两个非负整数。它们每位数字都是逆序存储,且每个节点只能存储一位数字。 将两个数相加,并以相同形式返回一个表示和的链表。除了数字 0 之外,这两个数都不会以 0 开头。
114 0
|
算法 C语言
【有营养的算法笔记】基础算法 —— 整数二分与浮点二分
【有营养的算法笔记】基础算法 —— 整数二分与浮点二分
178 0
【有营养的算法笔记】基础算法 —— 整数二分与浮点二分