「算法」蛇形填数 & 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形填数
题目
不用多说,就是给一个数字(矩形的边长),然后打印出如图所示的规律的矩形。
思考
这是蛇形填数中最简单的一种,我们只需要按照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.三角蛇形(蓝桥杯)
题目
思考
这是蛇形填数中最复杂的一种,我们需要从左上角开始按斜S形对数组进行填数。
虽然看似复杂,但仔细观察还是有规律可循的,我们可以斜着看,将每每条斜着的一串数字看成是一次循环填充数字,循环的次数便是用户输入的n的大小。
我们依然定义i为循环次数,那么当i为0、2、4即偶数的时候,数字都是从左下向右上填充的;当i为1、3、5即奇数的时候,数字都是从右上向左下填充的。
因为循环次数i是从0开始的,所以每次循环填充的数字的个数就可以表示为i+1。
仍然可以套用之前的while代码
代码
方法一:
#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; }