如何使用递归构建螺旋方阵？ [英] how to build spiral square matrix using recursion?
本文介绍了如何使用递归构建螺旋方阵？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我想建立使用递归螺旋方阵。我能够建立螺旋方阵通过如下迭代方法：
I wanted to build a spiral square matrix using recursion. I am able to build spiral square matrix using iterative method as below:
void main()
{
int initial_direction = UP , n = MAX , p = 1 ; /* intial_direction
is set to UP because we need to start moving right */
int r ,c , a[MAX][MAX];
int row_right = 0 , column_down = n-1 , row_left = n-1 , column_up = 0 ;
clrscr ();
//Set all elements of the matrix to 0
for(r = 0 ; r < MAX ; r++)
{
for(c = 0 ; c < MAX ; c++)
a[r][c] = 0 ;
}
//Generate elements of the spiral matrix
while(p != n*n+1)
{
if(initial_direction == UP)
{
//Move RIGHT
r = row_right++ ;
for(c = 0 ; c < n ; c++)
{
if(a[r][c] == 0)
a[r][c] = p++;
}
initial_direction = RIGHT ;
}
else if(initial_direction == RIGHT)
{
//Move down
c = column_down-- ;
for(r = 0 ; r < n ; r++)
{
if(a[r][c] == 0)
a[r][c] = p++;
}
initial_direction = DOWN ;
}
else if(initial_direction == DOWN)
{
//Move left
r = row_left-- ;
for(c = n-1 ; c >= 0 ; c--)
{
if(a[r][c] == 0)
a[r][c] = p++;
}
initial_direction = LEFT ;
}
else if(initial_direction == LEFT)
{
//Move up
c = column_up++;
for(r = n-1 ; r >= 0 ; r--)
{
if(a[r][c] == 0)
a[r][c] = p++;
}
initial_direction = UP ;
}
}
//Print the matrix
printf("\n\n");
for(r = 0 ; r < MAX ; r++)
{
for(c = 0 ; c < MAX ; c++)
printf("%4d ",a[r][c]);
printf("\n");
}
}
我想用递归来创建相同的矩阵： 这里是code，我用：
I wanted to create the same matrix using recursion: Here is the code i used:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool s[5][5] = {0};
int counter;
typedef enum {
right = 0,
down,
left,
up
}c_flag;
c_flag flag;
int last;
int build_matrix(int a[5][5],int i,int j, c_flag flag)
{
int ret;
if (i < 0 || i>=5 || j < 0 || j >= 5)
{
if (last == right)
{
flag = down;
last = flag;
}
if (last == down)
{
flag = left;
last = flag;
}
if (last == left)
{
flag = up;
last = flag;
}
if (last == up)
{
flag = left;
last = flag;
}
return false;
}
if (s[i][j] == true)
{
if (last == right)
{
flag = down;
last = flag;
}
if (last == down)
{
flag = left;
last = flag;
}
if (last == left)
{
flag = up;
last = flag;
}
if (last == up)
{
flag = left;
last = flag;
}
return false;
}
if(s[i][j] == false)
{
s[i][j] = true;
a[i][j] = ++ counter;
}
if (flag == right)
{
ret = build_matrix(a,i,j+1,right);
//if (!ret)
// return false;
}
flag = down;
last = flag;
if (flag == down)
{
ret =build_matrix(a,i+1,j,down);
//if (!ret)
// return false;
}
flag = left;
last = flag;
if (flag == left)
{
ret = build_matrix(a,i,j-1,left);
//if (!ret)
// return false;
}
flag = up;
last = flag;
if (flag == up)
{
ret = build_matrix (a,i-1,j,up);
//if (!ret)
// return false;
}
flag = right;
last = flag;
return false;
}
int main()
{
int i, j, n = 5;
int k, ret;
//printf("Enter N to construct square matrix \n");
//scanf("%d",&n);
int a[5][5] = {0};
k = n/2 + n%2;
for (i = 0; i < k; i++)
{
ret = build_matrix(a,i,i,right);
}
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
printf("%d",a[i][j]);
printf("\n");
}
return 0;
}
我收到了放上面为：
I am getting out put for above as :
1 2 3 4 5
16 19 22 25 6
15 18 21 24 7
14 17 20 23 8
13 12 11 10 9
而不是
Problem is Flag is not setting proper, i dunno inside which recursion call flag is getting disturbed.
Please some one help implement using recursion.
但问题是标志没有设置正确的，我不知道该递归调用的标志是越来越不安中。 请有人帮助实现使用递归。
解决方案
推荐答案
#include <stdio.h>
void build_matrix(int msize, int a[msize][msize], int size, int value){
int i, row, col;
if(size < 1)
return;
row = col = (msize - size) / 2;
if(size==1){
a[row][col] = value;
return;
}
for(i=0;i<size-1;++i)
a[row][col++] = value++;//RIGHT
for(i=0;i<size-1;++i)
a[row++][col] = value++;//DOWN
for(i=0;i<size-1;++i)
a[row][col--] = value++;//LEFT
for(i=0;i<size-1;++i)
a[row--][col] = value++;//UP
build_matrix(msize, a, size-2, value);
}
int main(){
int size;
printf("input size : ");
scanf("%d", &size);
int a[size][size];
build_matrix(size, a, size, 1);
for(int r=0;r<size;++r){
for(int c=0;c<size;++c)
printf("%3d ", a[r][c]);
printf("\n");
}
return 0;
}
这篇关于如何使用递归构建螺旋方阵？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
