「算法」蛇形填数 & 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;
}


相关文章
|
6月前
【每日一题Day297】LC1444切披萨的方案数 | 动态规划+二维前缀和
【每日一题Day297】LC1444切披萨的方案数 | 动态规划+二维前缀和
64 0
|
算法 测试技术 C++
C++二分算法习题:判断是否是完全平方数[容易]和排列箱子[容易]
C++二分算法习题:判断是否是完全平方数[容易]和排列箱子[容易]
|
6月前
|
算法 测试技术 C++
【状态压缩 容斥原理 组合数学】3116. 单面值组合的第 K 小金额
【状态压缩 容斥原理 组合数学】3116. 单面值组合的第 K 小金额
【状态压缩 容斥原理 组合数学】3116. 单面值组合的第 K 小金额
|
6月前
|
人工智能 算法
前缀和算法题(区间次方和、小蓝平衡和、大石头的搬运工、最大数组和)
前缀和算法题(区间次方和、小蓝平衡和、大石头的搬运工、最大数组和)
|
6月前
每日一题(最大连续1的个数,完全数计算)
每日一题(最大连续1的个数,完全数计算)
30 0
|
6月前
【每日一题Day165】LC1039多边形三角剖分的最低得分 | 区间dp
【每日一题Day165】LC1039多边形三角剖分的最低得分 | 区间dp
55 0
|
算法 C++
剑指offer(C++)-JZ11:旋转数组的最小数字(算法-搜索算法)
剑指offer(C++)-JZ11:旋转数组的最小数字(算法-搜索算法)
|
机器学习/深度学习 算法 NoSQL
【基础算法】浅浅刷个小题 # 反转字符串 # 反转字符串 II # 三个数的最大乘积 #
【基础算法】浅浅刷个小题 # 反转字符串 # 反转字符串 II # 三个数的最大乘积 #
每日三题-最大正方形 、完全平方数 、目标和
每日三题-最大正方形 、完全平方数 、目标和
86 2
每日三题-最大正方形 、完全平方数 、目标和
|
人工智能 算法 C++
[**算法**]关于数字反转的两道例题的分析思考
两个题目看着很像,但是细节不太一样,一个是去处理浮点,(其中有用STL大法的和将小数点前后和小数点分开进行输入的还有利用字符串的读写来处理的)还有一个是去处理整数
152 0