天天看點

算法面試題四

螺旋隊列問題2:

如矩陣:

1    2      3    4    5

16  17  18  19   6

15  24  25  20   7

14  23  22  21   8

13  12  11  10   9

找出規律,并列印一個NxN的矩陣,規律就是從首坐标開始順時針依次增大。

代碼如下,用到了算法面試題三裡面的函數(http://blog.csdn.net/crzy_sparrow/article/details/7429102):

代碼如下:

#include <iostream>
#include <stdio.h>
#include <iomanip>

using namespace std;
typedef struct{
	int x;
	int y;
}Point;

//獲得坐标對應值
int getValue(Point point){
	int r = abs(point.x)>abs(point.y)?abs(point.x):abs(point.y);//目前點x,y的最大絕對值
	int ri=2*r-1;//邊長比目前正方形小的正方形上最大數
	int distance;
	//根據上下左右方向計算該點到該所在正方形上初始點的距離
	//x正軸
	if(point.x==r&&point.y!=-r){
		distance=point.y-(1-r)+1;
	}
	//y正軸
	else if(point.y==r){
		distance=2*r-1+r-point.x+1;
	}
	//x負軸
	else if(point.x==-r){
		distance=2*r-1+2*r+r-point.y+1;
	}
	//y負軸
	else{
		distance=2*r-1+2*r*2+point.x+r+1;
	}
	return (distance+ri*ri);
}



int main(int argc, char* argv[])
{ 
	const int N=6;
	int a[N][N];
	Point point;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			//奇數陣
			if(N%2){
				point.x=N/2-j;
				point.y=i-N/2;
			}
			//偶數陣
			else{
				point.x=j-(N-1)/2;
				point.y=N/2-i;
			}
		    a[i][j]=N*N+1-getValue(point);
				cout<<setw(3)<<a[i][j]<<" ";
		}
		cout<<endl;
	}

	getchar();
	return 0;
}
           

結果測試:

算法面試題四
算法面試題四