菜雞蒟蒻想在博客中記錄一些算法學(xué)習(xí)的心得體會(huì)，會(huì)持續(xù)更新C/C++方面的題解，方便理清思路和日后復(fù)習(xí)。如果還能結(jié)識(shí)一起敲代碼的小伙伴的話(huà)就更好啦嘿嘿，因?yàn)閷?shí)在是太弱了，肯定免不了錯(cuò)誤百出。歡迎批評(píng)指正，期待共同成長(zhǎng)！

題目描述

給出一個(gè)不大于 9 的正整數(shù) n，輸出 n×n 的蛇形方陣。

從左上角填上 1 開(kāi)始，順時(shí)針?lè)较蛞来翁钊霐?shù)字，如同樣例所示。注意每個(gè)數(shù)字有都會(huì)占用 3 個(gè)字符，前面使用空格補(bǔ)齊。

輸入樣例

輸入

4

輸出

  1  2  3  4
 12 13 14  5
 11 16 15  6
 10  9  8  7

題解部分

涉及算法：模擬。
各位讀者有聽(tīng)說(shuō)過(guò)“建模”一詞嗎？所謂“建模”，就是把事物進(jìn)行抽象，根據(jù)實(shí)際問(wèn)題來(lái)建立對(duì)應(yīng)的數(shù)學(xué)模型。“抽象”并不意味著晦澀難懂；相反，它提供了大量的便利。計(jì)算機(jī)很難直接去解決實(shí)際問(wèn)題，但是如果把實(shí)際問(wèn)題建模成數(shù)學(xué)問(wèn)題，就會(huì)大大地方便計(jì)算機(jī)來(lái)“理解”和“解決”。

思路

1.首先我們可以把題目抽象成數(shù)學(xué)問(wèn)題，題目可以理解成為在一個(gè)方格里按一定規(guī)律填自然數(shù)，規(guī)律如下圖。

(畫(huà)的丑各位輕噴）
可以看出"小蛇"的走向是右、下、左、上、反復(fù)循環(huán)。

2.建模完畢之后，我們可以把這個(gè)矩陣用二維數(shù)組來(lái)表示，每填一個(gè)數(shù)就相當(dāng)于x或者y變化。
注意這個(gè)坐標(biāo)系的建立是根據(jù)二維數(shù)組的特性建立的x代表行、y代表列。

int map[15][15];
//雖然題目要求數(shù)據(jù)最大是9*9，但為了避免內(nèi)存會(huì)爆一般會(huì)把數(shù)組空間開(kāi)大一點(diǎn)。
for(i=1;i<=n*n;i++)
map[x][y]=i;

3.那如何控制方向呢？其實(shí)只需要再定義一個(gè)二維數(shù)組就可以啦。

int pos[4][2]={
 		{0,1), //向右填數(shù)
 		{1,0},//向下填數(shù)
 		{0,-1},//向左填數(shù)
 		{-1,0}};//向上填數(shù)

注意順序一定要按小蛇的走向規(guī)律填寫(xiě)。
為了方便大家理解，可以來(lái)看下面這張圖，正好與上面的源碼對(duì)應(yīng)。

通過(guò)這個(gè)方向數(shù)組，我們就很容易獲得下一步的坐標(biāo)。這里可以用tx，ty來(lái)表示。

int tx=x+t[d][0]；
int ty=y+t[d][1];
///通過(guò)改變d來(lái)改變方向。

4.如何判斷下一步要不要換方向呢？這時(shí)，tx，ty就派上用場(chǎng)了。
我們需要判斷tx、ty是否超出邊界，來(lái)決定是否轉(zhuǎn)向。

for(i=1;i<=n*n;i++)
{
map[x][y]=i;
tx=x+pos[d][0],ty=y+pos[d][1];
if(tx>n||ty>n||tx<1||ty<1||map[tx][ty]>0)
	d=(d+1)%4;//因?yàn)橹挥兴膫€(gè)方向所以d++時(shí)需要%4,使得d只能是0，1，2，3。
	x=x+pos[d][0],y=y+pos[d][1];//判斷完畢后就可以知道下一步填哪啦。
}

矩陣的大小為n*n，故邊界為[1，n]。
所以一旦tx，ty，超出邊界，就需轉(zhuǎn)向。
需要注意的是遇到之前已經(jīng)填過(guò)數(shù)字的方格也需要轉(zhuǎn)向。

ok核心部分已經(jīng)講解完畢，下面奉上完整代碼。

完整代碼

C語(yǔ)言版

#include<stdio.h>
int map[15][15];//需要定義在全局變量，好處是初始化默認(rèn)值都是0。
int pos[4][2]={0,1,1,0,0,-1,-1,0};
int main()
{
	int n;
	int i,j;
	scanf("%d",&n);
	int x=1,y=1,d=0;
	for(i=1;i<=n*n;i++)
	{
		map[x][y]=i;
		int tx=x+pos[d][0],ty=y+pos[d][1];
		if(tx>n||ty>n||tx<1||ty<1||map[tx][ty]>0)
		d=(d+1)%4;
		x=x+pos[d][0],y=y+pos[d][1];
	}
	for(i=1;i<=n;i++)
	{
	for(j=1;j<=n;j++)
	printf("%3d",map[i][j]);
	printf("\n");
	}
	return 0;
}

C++版

#include<bits/stdc++.h>
using namespace std;
int map2[15][15];//因?yàn)閏++類(lèi)庫(kù)太多，定義名為map編譯器會(huì)產(chǎn)生歧義，所以在后面加個(gè)2就ok了。
int pos[4][2]={0,1,1,0,0,-1,-1,0};
int main()
{
	int n;
	cin>>n;
	int i,j;
	int x=1,y=1,d=0;
	for(i=1;i<=n*n;i++)
	{
		map2[x][y]=i;
		int tx=x+pos[d][0],ty=y+pos[d][1];
		if(tx>n||ty>n||tx<1||ty<1||map2[tx][ty])
		d=(d+1)%4;
		x=x+pos[d][0],y=y+pos[d][1];
	}
	for(i=1;i<=n;i++)
	{
	for(j=1;j<=n;j++)
	printf("%3d",map2[i][j]);
	cout<<endl;
	}
	return 0;
}

最近剛接觸的c++，不過(guò)單從這題來(lái)看好像也差不多（捂臉）。

到此這篇關(guān)于C/C++實(shí)現(xiàn)蛇形矩陣的示例代碼的文章就介紹到這了,更多相關(guān)C/C++ 蛇形矩陣內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論