C++信奥之径,锻炼思维,扎实算法——模拟与高精度算法(6)

摘要:根据题意,本题的核心在于模拟奇数边长方阵的顺时针与逆时针旋转后的结果,主要使用的算法为模拟,需要我们对数组旋转前的状态与旋转后的状态有所理解。

魔法少女小Scarlet

题目描述

算法解析

1、根据题意,本题的核心在于模拟奇数边长方阵的顺时针与逆时针旋转后的结果,主要使用的算法为模拟,需要我们对数组旋转前的状态与旋转后的状态有所理解。

2、由于旋转数组会让每个位置的值发生变化,因此需要开临时数组来存放旋转结果。

3、首先是顺时针旋转90度,假设方阵中心元素在第x行第y列,先取r=1,那么原始方阵可以画出:

其中,灰色行表示当前元素所在的行列数,白色行表示元素具体的值。当顺时针旋转过后:

可以发现,第x-1行的元素跑到了第y+1列,第x行的元素跑到了第y列,第x+1行的元素跑到了第y-1列。因此可以用4个变量,分别表示旋转前和旋转后的值所在位置,示例代码如下:

int a0=x-r,b0=y-r; //左上角第一个元素的初始位置int a1=x-r,b1=y+r;// 对应的旋转后位置for( a0 ; a0

在循环过程中,我们发现,每次都变化的是b0和a1,每趟变化一次的是a0和b1,因此,我们可以想办法每次将b0转化为a1,b1转化为a0,这样可以少用2个临时变量:

a1=x-y+b0b1=x+y-a0

从而将内循环的赋值语句更新为:

tmp[x-y+b0][x+y-a0] = a[a0][b0];

虽然比上面展示的代码难理解一点,但是如果作为读者的你也能想到这一层,那么恭喜!你对模拟算法的掌握进入一个新的层次!

4、结合顺时针的代码,同学们应该可以推导出逆时针旋转的两种代码形式,大家可以阅读完成后自行理解与编写。

【参考代码】

#includeusing namespace std;int a[505][505];int t[505][505];int n,m;inline void shun(int x,int y,int r){ for(int i=x-r;i>n>>m; int tmp=1; for(int i=1;i>x>>y>>r>>fx; if(fx==0) shun(x,y,r); else if(fx==1) ni(x,y,r); } for(int i=1;i

代码中的C++知识解读

内联函数inline

内联函数inline

在C++中,inline是函数定义的修饰符,添加的位置是直接在函数返回值前面加上inline。

在编译器遇到inline修饰的函数时,它会尝试将函数的代码带入到调用点,从而取代常规的函数调用。

但是编译器是否会带入代码,完全取决于编译器自身的选择,因为inline只是给编译器提供一个“建议”

运行结果

来源:佩佩课堂

相关推荐