详解C语言通过递归与非递归实现蛇形矩阵

Coral ·

更新时间:2024-11-14

· 116 次阅读

前言：

本次蛇形矩阵我将以两种方法来实现，即非递归和递归

非递归的实现：


#define right 1
#define down 2
#define left 3
#define up 4
#define n 5     //控制矩形的大小
#include<stdio.h>
int main()//设计一个蛇形矩形图案 顺时针
{
int m = 1; int x = 1; int y = 1; int direct; int i = 0;
int j = 0;
int arr[n + 1][n + 1];
for (x = 1; x < (n + 1); x++)
{
for (y = 1; y < (n + 1); y++)
{
arr[x][y] = 100;//随机但是不能定为零
}
}
x = 1; y = 1; direct = right;
while (m <= n * n)
{
arr[x][y] = m++;
switch (direct)
{
case right:
if (arr[x][y + 1] == 100)
{
y++;
}
else
{
direct = down;
x++;
}break;
case down:
if (arr[x + 1][y] == 100)
{
x++;
}
else
{
direct = left;
y--;
}break;
case left:
if (arr[x][y - 1] == 100)
{
y--;
}
else
{
direct = up;
x--;
}break;
case up:
if (arr[x - 1][y] == 100)
{
x--;
}
else
{
direct = right;
y++;
}break;
}
}
//显示矩形
for (x = 1; x <= n; x++)
{
for (y = 1; y <= n; y++)
{
printf("%2d ", arr[x][y]);
}
printf("\n");
}
return 0;
}

非递归的解题思想：定义一个数组，这个数组的大小是（N+1）*（N+1），目的是形成一个边框，便于调整方向，其次就是当x与y跑到边框的位置就实现拐弯。

拐弯的思想就是上到下，下到左，左到上，上再到右，实现从外围向内包围，直至m <= n * n。

递归的实现：


#define right 1
#define down 2
#define left 3
#define up 4
#define n 7          //控制大小
int arr[n][n];
#include<stdio.h>
void snake(int x, int y, int m, int direct)
    {
      arr[x][y]=m;
  if (m == n * n)
return;
 switch (direct)
{
case right:
 if ((y+1) == (n+1) || arr[x][y+1] > 0)
{//到达右边边界或者右边有数字，不能再往右
direct = down; //改变方向，向下
x++; //向下移动一格
}
else     //可以向右填写
   y++; //向右移动一格
break;
case down:
if ((x + 1) == (n+1) || arr[x + 1][y] > 0)
{
direct = left;
y--;
}
else
x++;
break;
case left:
if ((y + 1) == (n+1) || arr[x][y - 1] > 0)
{
direct = up;
x--;
}
else
y--;
break;
case up:
if ((y + 1) == (n+1) || arr[x-1][y] > 0)
{
direct = right;
y++;
}
else
x--;
break;
}
    snake(x, y, ++m, direct); //填写下一个数
}
int main()//用递归填写这个矩形蛇形图案
 {
int x = 1; int y = 1; int m = 1;
 snake(x, y, m, right);
//显示矩形
for (x = 1; x <= n; x++)
{
 for (y = 1; y <= n; y++)
{
 printf("%2d ", arr[x][y]);//这里有个二，别忘了
 }
printf("\n");
}
return 0;
}

递归的实现大体思路跟非递归的实现类似，从外面到内部

但递归的每一个元素是单独在一个函数里来定义的，直至最后的m==n*n，然后再main函数里实现最终的模型。

其中的n是来控制大小，例如当n为5和9的结果如下：