本题可以直接模拟填数字,也可以直接计算结果。
代码一:(这个代码,缺陷在于数组太大,浪费内存啊。另外,循环次数也不少。总之,时间空间的消耗都不小。)
/*===============================================================
本段代码是模拟往数组填数字的过程。
每填写一个值就判断该位置是否(i,j)。若寻到目标位置,
则输出答案。
=================================================================*/
#include<stdio.h>
int a[][]={};//这个大小的静态数组尚可申请,但假如是放在函数内部声明却不行了的。这个大小大概是9MB,但距离30000*30000的大小实在是太远了。
int main()
{
int n,i,j;
int m;//m表示总共的层数
int k,p,q;//循环变量
int flag=;//标志性变量:等于0表示尚未循环到目标元素(i,j)
int t;
int len; scanf("%d%d%d",&n,&i,&j);
m=(n+)/; //m表示总共的层数
t=; //t表示要填进数组的数字
for(k=;k<=m&&flag==;k++)
{
p=k,q=k; //(k,k)是第k层左上角坐标点
len=n-*(k-);//表示当前层中每一条边的元素个数
for(;q<=(k+len-);q++)//填充当前层的顶边
{
a[p][q]=t;
if(p==i&&q==j)
{
printf("%d\n",a[p][q]);
return ;
}
t++;
}
q--;
p++;
for(;p<=(k+len-);p++)//填充当前层的右边
{
a[p][q]=t;
if(p==i&&q==j)
{
printf("%d\n",a[p][q]);
return ;
}
t++;
}
p--;
q--;
for(;q>=k;q--)//填充当前层的下边
{
a[p][q]=t;
if(p==i&&q==j)
{
printf("%d\n",a[p][q]);
return ;
}
t++;
}
q++;
p--;
for(;p>k;p--)//填充当前层的左边
{
a[p][q]=t;
if(p==i&&q==j)
{
printf("%d\n",a[p][q]);
return ;
}
t++;
}
}
return ;
}
代码二:(这个代码缺陷在于循环时间没减少……)
/*===============================================================
本段代码也是模拟往数组填数字的过程。但没有申请数组内存来存储数据。
而是只用一个变量表示每一次要填写的数字。
毕竟题目只要输出(i,j)位置的值,故不用保存整个数组。
只需要判断每一次模拟到的位置是否是(i,j)即可。
=================================================================*/
#include<stdio.h>
int main()
{
int n,i,j;
int m;//m表示总共的层数
int k,p,q;//循环变量
int flag=;//标志性变量:等于0表示尚未循环到目标元素(i,j)
int t;
int len; scanf("%d%d%d",&n,&i,&j);
m=(n+)/; //m表示总共的层数
t=; //t表示要填进数组的数字
for(k=;k<=m&&flag==;k++)
{
p=k,q=k; //(k,k)是第k层左上角坐标点
len=n-*(k-);//表示当前层中每一条边的元素个数
for(;q<=(k+len-);q++)//填充当前层的顶边
{
if(p==i&&q==j)
{
printf("%d\n",t);
return ;
}
t++;
}
q--;
p++;
for(;p<=(k+len-);p++)//填充当前层的右边
{
if(p==i&&q==j)
{
printf("%d\n",t);
return ;
}
t++;
}
p--;
q--;
for(;q>=k;q--)//填充当前层的下边
{
if(p==i&&q==j)
{
printf("%d\n",t);
return ;
}
t++;
}
q++;
p--;
for(;p>k;p--)//填充当前层的左边
{
if(p==i&&q==j)
{
printf("%d\n",t);
return ;
}
t++;
}
}
return ;
}
代码三:(这个代码应该算是比较完美了,时间空间都降下来了,而且是O(1)时间的算法。)
/*===============================================================
本段代码不是模拟填写数字的过程,而是直接根据i和j的值计算(i,j)所在的层k。
然后计算第k层左上角(k,k)位置处的元素值。
接下来呢,要寻到 (i,j)处的值,可以有两种方法:
(1)模拟填数字的过程环绕一圈寻找(i,j)。
(2)根据i,j的值依次计算(k,k)距离(i,j)的几个段的距离即可得到答案。
这里使用第二个方案。
=================================================================*/
#include<stdio.h>
int main()
{
int n,i,j;
int k,t;
freopen("matrix10.in","r",stdin);
freopen("matrix10.txt","w",stdout);
scanf("%d%d%d",&n,&i,&j);
//根据i判断(i,j)所在层数k
t=(n+)/;
if(i<=t)
{
if(j<=t) k=(i<=j?i:j);//(i,j)在左上部分
else k=(i<(n+-j)?i:(n+-j)); //(i,j)在右上部分
}
else
{
if(j<=t) k=(n+-i)<j?(n+-i):j; //(i,j)在左下部分
else k=(n+-i)<(n+-j)?(n+-i):(n+-j); //(i,j)在右下部分
}
//计算第k层左上角坐标为(k,k)的数t
k--;
t=n*n-(n-*k)*(n-*k)+;//注意:n-2k表示剥去k层之后剩余部分的行数和列数.(i,j)所在层没被剥掉,故而要先执行k--。
k++;
if(i==k) //(i,j)在第k环的上边线
t=t+(j-k);
else if(j==k+n-*(k-)-) //(i,j)在环的右边.
t=t+(n-*(k-)-)+(i-k);
else if(i==k+n-*(k-)-)//(i,j)在环的下边
t=t+(n-*(k-)-)+(n-*(k-)-)+((k+n-*(k-)-)-j);
else t=t+(n-*(k-)-)+(n-*(k-)-)+(n-*(k-)-)+((k+n-*(k-)-)-i);
printf("%d\n",t);
return ;
}
关于计算层数的代码:
其实是把整个数组分为左上、右上、左下和右下四个区域分别处理。
#include<stdio.h>
int main()
{
int n,i,j,k,t;
scanf("%d",&n);
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
t=(n+)/;
if(i<=t)
{
if(j<=t) k=(i<=j?i:j);//(i,j)在左上部分
else k=(i<(n+-j)?i:(n+-j)); //(i,j)在右上部分
}
else
{
if(j<=t) k=(n+-i)<j?(n+-i):j; //(i,j)在左下部分
else k=(n+-i)<(n+-j)?(n+-i):(n+-j); //(i,j)在右下部分
}
printf("%d ",k);
}
printf("\n");
}
return ;
}
关于计算(i,i)处的值:
n*n-(n-2*k)*(n-2*k)+1
其中,n*n是数字总的个数,k是表示被剥去的层数(注意:假如(i,j)在第k层,则被剥去的是(k-1)层。)
(n-2*k)*(n-2*k)表示剥去之后,剩余部分的元素的个数。
如何理解n-2*k呢?其实啊,就是“每剥去一层,行和列的数量都会减少2,于是总共减少的数量就是2*k。剩余的部分自然就是n-2*k了。”