我需要编写一个Pascal程序,使数组成为螺旋形式,类似于这样:
(7) (8) (9) (10)
(6) (1) (2) (11)
(5) (4) (3) (12)
(16)(15)(14)(13)
从1开始,一直到36,但这并不是很重要。
经过3天的思考,我不知道如何实现这个问题。
问题不在于语言语法或数组,而在于算法。
你能否帮我提供任何想法、链接、伪代码或任何编程语言的程序代码?
我需要编写一个Pascal程序,使数组成为螺旋形式,类似于这样:
(7) (8) (9) (10)
(6) (1) (2) (11)
(5) (4) (3) (12)
(16)(15)(14)(13)
从1开始,一直到36,但这并不是很重要。
经过3天的思考,我不知道如何实现这个问题。
问题不在于语言语法或数组,而在于算法。
你能否帮我提供任何想法、链接、伪代码或任何编程语言的程序代码?
在迭代矩阵时,有一个巧妙的想法可以用来改变方向。看看下面的表格。输入(dX,dY)是增量值中的先前方向,输出(cwdx,cwdy)是下一个顺时针方向,输出(ccwdx,ccwdy)是下一个逆时针方向(坐标(0,0)位于左上角):
dx dy | cwdx cwdy | ccwdx ccwdy
-------------------------------
1 0 | 0 1 | 0 -1
0 1 | -1 0 | 1 0
-1 0 | 0 -1 | 0 1
0 -1 | 1 0 | -1 0
所以,如果给定顺时针旋转的方向(dx,dy),则需要方向(-dy,dx)来顺时针旋转,而要逆时针旋转,则需要方向(dx,-dy)。这意味着您不需要在代码中使用开关来改变方向,只需要通过三行代码来实现:
temp = dx; // this is for clockwise turn
dx = -dy;
dy = temp;
这里有一段来自Java程序的代码片段,用于执行螺旋矩阵访问。它通过跟踪方向变化来感知需要进行多少次访问以在任何给定方向上行进。简化此问题的模式是,在沿着任何给定方向行进时,下次访问该方向时需要进行的访问次数会减少一个。更简单地说,如果第一次您在水平方向行进时要进行6次访问,那么下一次您在水平方向行进时将进行5次访问。还应注意,水平和垂直访问是分别进行跟踪的。下面的单个方程式已用于计算在需要改变方向后给定方向的访问次数。该方程式通过从总方向更改次数中推导出垂直或水平,并使用mod作为选择器来选择。最后,将访问视为在矩阵上移动的蛇,我将步骤表示为行/列的变化作为速度(dy和dx)。正如另一个人指出的那样,有一种可以使用的模式,并且在dy和dx的公式中表达出来。
int[][] matrix = { { 1, 2, 3, 4, 5, 6, 7, 8 },
{ 24, 25, 26, 27, 28, 29, 30, 9 },
{ 23, 40, 41, 42, 43, 44, 31, 10 },
{ 22, 39, 48, 47, 46, 45, 32, 11 },
{ 21, 38, 37, 36, 35, 34, 33, 12 },
{ 20, 19, 18, 17, 16, 15, 14, 13 } };
int n = matrix.length;
int m = matrix[0].length;
int row = 0;
int col = 0;
int dx = 1;
int dy = 0;
int dirChanges = 0;
int visits = m;
for (int i = 0; i < n * m; i++) {
System.out.print(matrix[row][col] + " ");
visits--;
if (visits == 0) {
visits = m * (dirChanges %2) + n * ((dirChanges + 1) %2) - (dirChanges/2 - 1);
int temp = dx;
dx = -dy;
dy = temp;
dirChanges++;
}
col += dx;
row += dy;
}
这个程序的输出是:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
考虑将nxn矩阵分割成2x2、4x4等同心子矩阵。在你的情况下,我们会有外部子矩阵(元素5到16)和内部子矩阵(元素1到4)。
现在针对每个级别,应该迭代四个边缘,并填充所需的元素。可以从内到外或从外到内。我选择从外向内。我们保持一个计数器,初始值为n*n
(在我们的示例中为16)。
对于从1
到n/2
的 i :
首先取底边(外层级别的元素16-13)。我们从x[n-i+1][i]
到x[n-i+1][n-i+1]
并进行填充(对于第一级别,这将是16、15、14、13,对于第二级别为4和3)。
然后我们取右边(外层级别的元素12-10)。我们从x[n-i][n-i+1]
到x[i][n-i+1]
(外层级别的元素12、11、10)。
然后我们取顶部边缘(外层元素9-7)。我们从x[i][n-i]
到x[i][i]
(外层元素9、8、7)。
最后,我们取左侧边缘(外层元素6-5)。我们从x[i+1][i]
到x[n-i][i]
并填充该侧(这将是外层元素6、5)。
如果n
为奇数,则最后还有中间元素。然后,您只需要分配x[n/2+1][n/2+1] = 1
。
我希望我已经清楚地表达了这个想法;如果有什么不明白的,请问。
此外,我没有实现解决方案,因为我假设您遇到的问题只是想法,而不是实现
最简单的想法是从螺旋的末尾开始,然后往回走。
有四个变量(left
、top
、right
、bottom
),告诉你每一边已经填充了多少。
创建一个适当大小的矩阵。
将left = top = 0
初始化,并将right
和bottom
初始化为最后一列和行索引。
从左
到右
填充底部
行。将底部
减一。
从底部
到顶部
填充右侧
。将右侧
减一。
从右侧
到左侧
填充顶部
。将顶部
加一。
从顶部
到底部
填充左侧
。将左侧
加一。
迭代直到填满整个矩阵。
用右手定则(就像解迷宫一样)如何?
考虑每个走过的单元格会成为墙壁。
以下是用 PHP 写的递归解决方案。
<?php
header('Content-type: text/plain');
function fill($x, $y, $dir, $leftInDir, $index, $stepSize, $stop){
global $out;
// set the value for the current item //
$out[$y][$x] = $index;
// everything that comes after this point is computing for the parameters of the next call //
// activate this for debugging //
//echo $x, ',', $y, ',', $dir, ',', $leftInDir, ',', $index, ',', $stepSize, ',', $stop, "\n";
// decrease the number of steps left to take in the current direction //
$leftInDir--;
// check if this is the last item //
if($index == $stop)
return;
// we're going up for the next item //
if($dir == 'U')
$y--;
// we're going right for the next item //
if($dir == 'R')
$x++;
// we're going down for the next item //
if($dir == 'D')
$y++;
// we're going left for the next item //
if($dir == 'L')
$x--;
// if this was the last step in this direction we need to change the direction //
if($leftInDir == 0){
// after two direction changes we need to increase the numbers of steps to take //
if($dir == 'D' || $dir == 'U'){
$stepSize++;
}
// update the direction clockwise //
if($dir == 'U')
$dir = 'R';
else if($dir == 'R')
$dir = 'D';
else if($dir == 'D')
$dir = 'L';
else if($dir == 'L')
$dir = 'U';
// set the number of steps left as the step size //
$leftInDir = $stepSize;
}
// increase the number to put in the cell //
$index++;
// call for the next item //
fill($x,$y,$dir,$leftInDir,$index,$stepSize,$stop);
}
// set the size //
$size = 100;
// start the process from the center of the matrix //
fill((int)$size/2, (int)$size/2, 'R', 1, 1, 1, $size*$size);
// just output //
ksort($out);
foreach($out as $row){
ksort($row);
foreach($row as $item){
echo str_pad($item, 7);
}
echo "\n";
}
?>
1
的位置开始走。1 RIGHT,1 DOWN,2 LEFT,2 UP,3 RIGHT,等等,直到达到 n*n
。至#1
我写了这个程序,但结果看起来像这样:
00000
10000
11000
11100
.....
我不知道,也许是我没有理解你的算法或者其他问题发生了。 这是代码:
n:=16;
x:=1;
For i:=1 to (n div 2) do
begin
For p:=i to n-i+1 do
begin
a[n-i+1,p]:=x;
end;
For q:=n-i to i do
begin
a[q,n-i+1]:=x;
end;
For o:=n-i to i do
begin
a[i,o]:=x;
end;
For u:=i+1 to n-i do
begin
a[u,i]:=x;
end;
end;
所以我尝试将 PHP 编写的 #2 程序转换为 Pascal,它可以工作。 现在我将修复它,使其按顺时针方向编写数字,并从数组中心开始。
非常感谢大家。
CurValue = n * n;
终点是最下方的左侧点。
我们将从终点到第一个点进行访问(我们在访问时分配值)
每个单元格在开始时都具有零值。
x = n-1;
y = 0;
arr[x][y] = CurValue;
while ( CurValue greater than zero )
{
keep going right until you face a cell that has non-zero value or until you reach the most right cell
keep going top until you face a cell that has non-zero value or until you reach the most top cell
keep going left until you face a cell that has non-zero value or until you reach the most left cell
keep going down until you face a cell that has non-zero value or until you reach the most down cell
}
note: with each cell you visit then do the following :
CurValue --;
Assign CurValue to the current visited cell;
我希望上面的算法很清楚易懂。
import java.util.Scanner;
class CircularMatrixFromInnerClockwise
{
Scanner sc= new Scanner(System.in);
void main()
{
System.out.println("Enter size.");
int n=sc.nextInt();
int a[][]= new int [n][n];
int r1,c1,r2,c2;
if(n%2==0)
{
r1=n/2-1;
c1=n/2-1;
r2=n/2-1;
c2=n/2-1;
}
else
{
r1=(n+1)/2-1;
c1=(n+1)/2-1;
r2=(n+1)/2-1;
c2=(n+1)/2-1;
}
int k=1;
do
{
if(c2<n-1&&r2<n-1)
{
r2++;
c2++;
}
for(int i=c1;i<=c2;i++)
a[r1][i]=k++;
if(k>=n*n)
break;
for(int i=r1+1;i<=r2;i++)
a[i][c2]=k++;
if(k>=n*n)
break;
if(c1>0&&r1>0)
{
c1--;
r1--;
}
for(int i=c2-1;i>=c1;i--)
a[r2][i]=k++;
if(k>=n*n)
break;
for(int i=r2-1;i>=r1+1;i--)
a[i][c1]=k++;
if(k>=n*n)
break;
}while(k<=n*n);
System.out.println("Circular matrix");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
System.out.print( a[i][j]+"\t");
}
System.out.println();
}
}
}
你的意思是它必须从左到右,从上到下打印数字吗?要制作平方数,可以将连续的奇数相加-1 + 3 + 5 + 7 + 9 + 11 = 36。
在这个螺旋中,左侧边缘很简单...除了底部行。因此,一种方法是将算法编写为如果螺旋形状再大一圈,但不要打印第一行和第一列以及最后一列。