这两题怎么写呢,希望能给出过程,谢谢了
我就帮你详细说一题吧,另外一题稍微提及一下,你自己也试试分析分析。
螺旋矩阵
---让数字从左上角开始往里螺旋回转,直到数组被填满。
说说常见的解题思路,首先分析旋转的方式。
可以看出它的旋转方式(右->下->左->上)
再仔细点分析一下
从左上角起往右走到边界
到达右方边界后接着往下走到边界
到达下方边界后,往左走到边界
最后往上走到边界,并结束一圈
好了,接下来看看我们怎么模拟这个过程。
首先,我的方法是把每一圈当做是一个独立的循环。那么通过计算可以得知n阶的矩阵最多会有n/2(向下取整)圈,于是乎5阶矩阵被我拆分成两圈(红色标记为“目前”矩阵的左上角及右下角):
第一圈:
第一圈完毕后可以把矩阵规模往内缩,因为这一圈已经处理完毕。
第二圈:
中心做特殊处理即可。
-----------------------------------------------
那么如何模拟呢?同样的按照之前分析的分为4步,也就是4个循环。
Tx、Ty代表左上角的x、y;Bx、By代表右下角的x、y。
第一步,往右走:也就是y不变,x从Tx->Bx;
第一步完毕之后可以视为顶部行已经处理完毕,于是乎Ty往下挪。
第二步,往下走:也就是x不变,y从Ty->By;
同理,第二步完毕之后可以视为右侧一列处理完毕,所以Bx往左挪
第三步,往左走:也就是y不变,x从Bx->Tx;
同理,完毕之后可以视为底部一行处理完毕,所以By往上挪
第四部,往上走,关闭一圈:也就是x不变,y从By->Ty;
同理,完毕最后视为左侧列处理完毕,所以Tx往右挪。
至此一圈处理完毕,Tx、Ty、Bx、By也到了下一圈应到的位置上。
内圈我相信你已经会了。说实话我不希望你照抄,我希望你能按照自己理解写一遍。但我还是给出我的实现代码给你参考一下,由于你问题分区不对无法排版代码就只能上传图了。
下面说说第二题
猴子选大王
这题理解分析起来非常容易,无非就是你有n个人形成的队列,他们按顺序报数,报到第m个出列,循环直至队列仅剩一人。
这个问题最适合使用链表或者是循环数组实现,链表方式就不说了,做法显而易见。
循环数组的做法你应该懂,如arr[0,1...n],当到了n的时候使指针(位置指示器)回到0则为循环数组。
实现思路就是将数组初始化为猴子的编号,并且数组中的数值为负数则代表该位已出列。
循环不断数出(跳过负值,因已出列)应当出列的猴子,输出即可。
int main()
{
int a[100][100];
int n, i, j, x, y, f, x1, y1;
scanf("%d", &n);
for(i=0; i<n; i++)
for(j=0; j<n; j++)
a[i][j]=0;
// printf("aaaaaaaaaa\n");
for(i=0, x=0, y=0, f=0; i<n*n; i++)
{
// printf("%d\n", i);
f=f%4;
a[x][y]=i+1;
x1=x; y1=y;
printf("a[%d][%d]=%d\n", x, y, i+1);
if(f==0) { y++; if(y>n-1||a[x][y]!=0) { y--; x++; f++;}}
else if(f==1) { x++; if(x>n-1||a[x][y]!=0) {x--; y--; f++;}}
else if(f==2) { y--; if(y<0||a[x][y]!=0) {y++; x--; f++;}}
else if(f==3) { x--; if(x<0||a[x][y]!=0) {x++; y++; f++;}}
}
// printf("xxxxxxxxxxx\n");
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
printf("%d ", a[i][j]);
}
printf("\n");
}
}
#include<stdio.h>
int main()
{
int a[10000];
int m;
int n;
int x;
int count;
int i;
scanf("%d",&m);
scanf("%d",&n);
for(i=1;i<=m;i++)
a[i]=i;
count=m;
x=0;
for(i=0;count>1;i++)
{
if(a[i%m+1]!=-1)
{
x++;
}
if(x==n && a[i%m+1]!=-1)
{
a[i%m+1]=-1;
count--;
x=0;
}
}
for(i=1;i<=m;i++)
if(a[i]!=-1)
printf("%d\n",i);
return 0;
}