爵士OIer查看:1021 回复:28 评论:13 创建时间:2021-01-28T21:41:48用户:爵士OIer查看:1021 回复:28 评论:13 创建时间:2021-01-28T21:41:48
大家好！这里是Kitten进阶教程与实战的第二期。相信跟着爵士来，大家的Kitten创作水平会大大提高。
我们将在这些教程里学习一些适合进阶深造的算法和技巧。
之前说要介绍深度优先搜索，觉得大家基础可能不够，所以先讲坐标系之类的东西了。
本期内容非常常见，平均每2块积木要用到一次。所以听好了！
注：已调大文字响应护眼活动
目录
符号与模型
数轴
什么是坐标系
坐标系简单用途
有关坐标系若干公式、定理
直线、抛物线、圆、椭圆的方程
幂函数，对指函数，三角函数
Kitten实现技巧0：坐标系的实现，Kitten函数的介绍
Kitten实现技巧1：跟随鼠标变速移动
Kitten实现技巧2：从三角函数到飞机路径
示例作品
比官方设置的三角函数还精准！泰勒展开的用途
附：C++中的函数
符号与模型
其实这玩意是学化学的时候学的，但忘了
为了负责一点，我搬运一下教材全解（雾
符号
概念：具有一定意义的图形、文字
用途：（1）简单明了地表示事物；
（2）避免由于事物外形不同引起混乱；
（3）避免由于语言文字的不同引起的混乱。
举例：比如“禁止鸣笛”路牌，电路图中的原件。
模型
举例：磁感线；地表水分含量图；地图；电路图；溶解度变化曲线；欧姆定律的公式表达。
原因 / 作用：帮助认识和理解一些无法直接观察到的事物。
数轴
在小学和初中阶段接触到的一般是实数轴。
一条数轴代表了全体的实数。数轴的0所在位置即为原点；数轴有一个箭头，表示正方向。一般向右指。
位置越往正方向移动，其数值就越大。
如图为一根数轴。其中，原点为O代表0，向右为正方向，一并且画出了一个单位长度的大小。
数轴三要素：原点、正方向、单位长度。
什么是坐标系
在一个平面上，我们随便取一个点作为原点，以通过这个点的两条互相垂直的直线分别作为x和y轴。
这样，我们就建立了坐标系。
上面这张图就是简单的平面直角坐标系xOy。
其中，x轴上的坐标成为横坐标，y轴称为纵坐标。
平面直角坐标系可看作两条垂直的数轴。
其他常见坐标系：直线坐标系（数轴）；空间直角坐标系；极坐标系；复平面坐标系（小学和初中难以接触）。
坐标系和模型有什么关联？
请各位思考，建立坐标系xOy属于建立模型吗？
坐标系的简单应用
坐标
坐标是坐标系中的有序数对 (a1,a2,a3,...,an)。
在平面直角坐标系中，我们用数对 (a,b) 表示一个点在坐标系中的位置。
有了坐标，那么我们坐标系就能够表示一个地方的位置。
如图，我们可以通过坐标表示食堂的位置。
地图
地图是一种模型。
地图三要素：比例尺，图例和注记，指向标。
世界地图中，我们必然会看到经纬网。
经纬网就是一种坐标系。比如杭州 (120°E, 30°N) 在东半球、北半球。
东喵的区分在本初子午线：子午线以东180°为东经。
南北纬和南北半球的区分都在赤道上。
东西半球的划分不同于东喵，东西半球的划分是20°W和160°E组成的经线圈。
如图，深蓝色为南北回归线、南北极圈，浅蓝色为赤道，红色所截平面为黄道面。
之所以会有这样的差别是由于自转轴与公转夹角为67.5°。
有关坐标系若干公式、定理
两点之间距离公式
众所周知的勾股定理，在直角三角形中，a^2+b^2=c^2
我们在坐标系中也可以运用以上定理，得到了两点之间的距离公式。
随便举个例子，有如下两点，求距离
我们作过两点的直线分别垂直于x轴和y轴，交点显然为直角。
因此我们可以放心大胆地用勾股定理啦qaq
我们将其推广到一般情况，能得到两点之间距离公式：
中点公式
回忆数轴，我们如何表示数轴上两个点的中点？
答案是这两个数的平均数。
我们能否予以推广，得到平面直角坐标系上的中点公式？
还是以那两个点为例：
我们似乎得到了一个惊人的事实：坐标系上两点的中点就等于两者横、纵坐标分别取平均数！
其实这也是较好理解的。我们用中位线想一想就知道了。
直线、抛物线、圆、椭圆的方程
幂函数，对指函数，三角函数
这些都先略过（因为关系不大）
更多的是数学的内容，大家可以看看慕斯和我（我是屑比慕斯差远了）的教程
https://shequ.codemao.cn/community/358280
https://shequ.codemao.cn/community/314925
https://shequ.codemao.cn/community/316232
https://shequ.codemao.cn/community/357318
Kitten实现技巧0：坐标系的实现，Kitten中函数的介绍
Kitten函数介绍
函数有参数（可以为空）、返回值（可以没有）。
参数就是函数在运行中需要参与运行的变量。为了更好地理解参数的作用和传递，我们看一下下面这个很简单的函数，这个函数只有一个参数：步数。
以下是调用函数以及参数传递的积木：
它表示运行函数“跑步”，其中步数为5。以上函数及其调用的效果等同于
返回值是函数计算后得到的结果，该结果会返回到调用它的语句中。
当你的函数出现返回值的时候，会多出这么个积木：
这个积木的含义是获取函数“跑步(0)”的返回值。
在对上面的“跑步(步数)”函数增添返回值，可以这么写：
我们还是使用以下语句
传入参数5，然后可以用
来获取返回值。
为了显示返回值，我们可以用变量“返回”来存储返回值，积木如下：
最终得到的返回值为
两点之间的距离
我们如何实现求出两点之间的距离？
首先因为编程猫没有“平方”函数，所以我们手写
这之后，我们根据距离公式，调用函数
中点公式
上面讲过的中点公式。
我们需要实现瞬移到两个角色的中间位置，这个时候可以：
Kitten实现技巧1：跟随鼠标变速移动
不知道大家在做飞机大战或其他作品的时候，是否需要让一个角色跟随鼠标移动？
这是很容易实现的。
那么让我们接着思考：为了让效果看起来更自然，我们需要做到当角色离鼠标越远的时候，向鼠标移动的速度越快，并且希望角色不改变外观上的方向。
这该怎么做？
我想大家经过上面的学习肯定已经知道了如何表示两点之间的距离。
其实我们并不需要那么麻烦。我们只需让角色重复执行将自己的位置变为原先坐标到鼠标坐标路径中的等分点即可。
我们想到了什么？
没错，中点公式就是上述的一个特殊情况（二等分点）！
因此我们只需将瞬移中点的积木略作修改即可！
Kitten实现技巧2：从三角函数到飞机路径
现在让我们回顾三角函数。
大家可以看看我和慕斯的四期教程
https://shequ.codemao.cn/community/357061
https://shequ.codemao.cn/community/357142
https://shequ.codemao.cn/community/358907
https://shequ.codemao.cn/community/359072
其中如下：
看图像，我们能否对飞机的运行路径做一些适当的处理，使它看上去很自然？
一个很好的想法就是：将飞机路径设置为正弦波！
如何实现？这是个好问题。
然而这并非很难的事。我们设置一个时间变量，让它每次增加一点点；同时，我们让纵坐标移动的量不变，横坐标的增量设置为余弦函数 cos 即可。
示例作品
https://shequ.codemao.cn/work/53478829
比官方设置的三角函数还精准！泰勒展开的用途
2020年初慕斯做了一个三角函数的运算，比官方自己设置的精确1000到10000倍左右。
这是如何做到的？
回顾泰勒公式：
这里勘误一下，慕斯只迭代了十四次。这足以证明其精确性。
这里的积木给一个参考，因为我并不确定有没有达到实际效果（逃
众所周知泰勒公式是近似，所以我们要先把输入的变量放在可控的范围内。然后我们要转弧度制。
像这样即可：
然后我们把这个“弧度x”放到泰勒公式里面去。
这就好啦qaq！！
附：C++中的函数
这里主要是一些实用的，比如FFT、NTT、Mul、Inv、Ln、Exp之类的多项式算法。
FFT
void FFT(Complex *f,int flag){
for(int i=0;i<n;i++){
if(i<tr[i])swap(f[i],f[tr[i]]);
}
for(int p=2;p<=n;p<<=1){
int len=(p>>1);
Complex wn(cos(2*PI/p),sin(2*PI/p));
if(!flag)wn.y*=-1;
for(int k=0;k<n;k+=p){
Complex buf(1,0);
for(int i=k;i<k+len;i++){
Complex tmp=buf*f[len+i];
f[len+i]=f[i]-tmp;
f[i]=f[i]+tmp;
buf=buf*wn;
}
}
}
}
NTT
void NTT(ll *f,int flag){
for(int i=0;i<n;i++){
if(i<tr[i])swap(f[i],f[tr[i]]);
}
for(int p=2;p<=n;p<<=1){
int len=(p>>1);
ll wn=qpow(flag?G:invG,(mod-1)/p);
for(int k=0;k<n;k+=p){
ll buf=1;
for(int i=k;i<k+len;i++){
ll tmp=buf*f[len+i]%mod;
f[len+i]=ck(f[i]-tmp+mod);
f[i]=ck(f[i]+tmp);
buf=buf*wn%mod;
}
}
}
if(!flag){
ll invn=qpow(n,mod-2);
for(int i=0;i<n;i++){
f[i]=f[i]*invn%mod;
}
}
}
Mul
就是NTT中的主函数部分啦qaq
Inv
void Inv(ll *f,ll *g,int m){
if(m==1){
g[0]=qpow(f[0],mod-2);return;
}
Inv(f,g,(m+1)>>1);
int n=1;
while(n<(m<<1))n<<=1;
for(int i=0;i<n;i++){
tr[i]=((tr[i>>1]>>1)|((i&1)?n>>1:0));
w[i]=f[i];
}
for(int i=m;i<n;i++)w[i]=0;
NTT(w,1,n),NTT(g,1,n);
for(int i=0;i<n;i++)
g[i]=(2-w[i]*g[i]%mod+mod)*g[i]%mod;
NTT(g,0,n);
for(int i=m;i<n;i++)g[i]=0;
}
Ln
void Ln(ll *f,ll *g,int n){
WeiFen(f,ff,n);
Inv(f,_f,n);
Mul(ff,_f,_g,n,n);
JiFen(_g,g,n);
}
结语
本期教程就到这里了。
我们学会了函数的入门、坐标系的入门到精通，学会了各种坐标系和运算、函数的奇妙技巧。
如果你认真学习了我在帖子中放出的其他教程链接，你会跟着把数学也学会很多。
接下来一期，我们将真正开始学习搜索算法了（下期还不教就d喵我）
爵士OIer往期教程：【第一期】https://shequ.codemao.cn/community/359743
示例作品：【第二期】https://shequ.codemao.cn/work/53478829（如果认为有帮助珂以点一个赞）
点赞0
评论
冰糖葫芦_两点之间的距离要加绝对值
点赞0
评论
呵呵呵呵呵
根号不需要绝对值。
而且平方没有负数。
我是说那个减的地方要加绝对值，不然有可能是负数。
Kitten的
你怕不是眼瞎。
你是看不到套了一个平方吗。
根号下 (x1-x2)^2+(y1-y2)^2 因为根号内的两项均为实数的平方，不可能出现负数。所以不需要绝对值。
建议先学学幂和二次根式。
根号的双重非负性。
