詳解C語言通過遞歸與非遞歸實現蛇形矩陣

更新時間：2022年02月10日 15:09:35 作者：誠摯的喬治

蛇形矩陣（Snake matrix）是矩陣的一種，常被應用在編程題目與數學數列中，需要提取每條斜線里最小的數字，本篇文章將會通過遞歸和非遞歸來分別實現蛇形矩陣

前言：

本次蛇形矩陣我將以兩種方法來實現，即非遞歸和遞歸

非遞歸的實現：

#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的結果如下：