今天在训练的时候,我在做题打表的时候意外发现我们的三角函数和710这个数字有着千丝万缕的不解之缘。查阅资料无果后经过推导我发现了背后的奥妙。今天就让我们来看看关于三角函数和710的那些事吧。

先从一道题目开始

这是ICPC 2019-2020 North-Western Russia Regional Contest的B题,题目大意如下:

Treap是一种在二叉搜索树中存储一组结构体的数据结构。树的每个节点都是一对包含(x,y)的结构体。

节点的 x 值是存储的是数据的 key 值。在Treap中,x 值遵循“二叉搜索树规则”:即对于任意一个节点,节点的左子树中的所有 x 值小于其 x 值,节点右子树中的所有 x 值大于其 x 值。

节点的 y 值遵循“堆规则”:即对于任意节点,节点的 y 值小于或等于其父节点的 y 值。一般来说 y 值都是直接随机出来的.Treap的结构如下图:

SJ1.png

现在我们规定,对于给定的 key 值也就是 x 值,其节点的 y 值为 y = sin x

给定你n(n ≤ 5e4),让你输出 n 个整数的 x 值(在int范围内),使得这棵Treap呈现链状。

这题乍一看好像是神仙题,但仔细一想在什么情况下我们的Treap会轻而易举的形成链状呢?显然如果当我们把我们n个x 值排序后,如果我们的 y 值也具有单调性,那么我们的Treap一定呈现链状,如果我们假设a1 < a2 < …… < an,那么我们就有:

SJ2.png

如上图,当 x 单调递增时, y 也单调递增时,我们就会得到左边这条链;而当 x 单调递增时, y 单调递减时,我们这会得到有边这条链。

那我们如何构造出 n 个int范围内的整数x[i],使他们从小到大排列后sin(x[i])也具有单调性呢?毫无头绪的情况下我重拾旧业,开始打表:

既然sinx是关于原点对称的,所以我就假定在y轴左边找到n/2个,在y轴右边找到n/2个,再加上原点就完美实现了。但是一个一个数枚举还是不现实,所以我们假设最后得到的答案的任意相邻两数的间隔是一定的,最后决定在1000以内枚举间隔。接着我打了下面这样一个表:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
long long num, n, flag;
double ans[22000];
int main() {
    n = 1000;
    num = 0;
    for(int i = 1; i <= 10000; i++) { //寻找间隔 
        flag = 0;
        for(long long j = 1; j <= n; j++) {
            ans[j] =  sin((long long)i * j - n * i / 2);//关于y轴对称 
            if(j >= 3) {
                if(ans[j] > ans[j - 1] && ans[j - 1] < ans[j - 2]){
                    flag = 1;
                    break;
                }
                if(ans[j] < ans[j - 1] && ans[j - 1] > ans[j - 2]){
                    flag = 1;
                    break;
                }
            }//判断单调性 
        }
        if(!flag) printf("%d\n", i);//如果具有单调性 
    }

    return 0;
}

输出结果710,没错今天的主角登场了:

SJ3.png

接着我就提交了酱紫一个程序:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
long long num, n;
int main() {
    scanf("%lld", &n);
    num = 0;
    for(long long i = 1; i <= n; i++) printf("%lld\n", (long long)710 * i - (long long)710 * (long long)n/ (long long) 2);//关于y轴对称 
    return 0;
}

就直接AC了……接着报着好奇的心理,我输出了n = 20时的情况:

SJ4.png

现在可能还看不出什么,我再输出他对应的正弦值:

SJ5.png

可见它生成了较为密集且具有单调递增性质的sin值。可能这还看不出来,我们看一下50000的:

SJ6.png

可见生成的sin值基本涵盖[-1, 1]且相当密集。

换言之,对于x是整数的情况,sin(710 * x)可以生成密集的具有单调性的正弦函数。这就非常有意思了啊:

SJ7.png

我们的sin(710 * x)的图像难道会是上图这样的吗?

只有710吗

在好奇心的驱使下我开始探究,如果对于整数 x ,当x递增时,想让 sin(c * x) 也具有单调性,那么 c 一定要是 710 吗?

所以我把之前的打表程序的范围进行了修改,把搜索范围扩大到了一万:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
long long num, n, flag;
double ans[22000];
int main() {
    n = 1000;
    num = 0;
    for(int i = 1; i <= 10000; i++) { //寻找间隔 
    //间隔的搜寻范围扩大到10000 
        flag = 0;
        for(long long j = 1; j <= n; j++) {
            ans[j] =  sin((long long)i * j - n * i / 2);//关于y轴对称 
            if(j >= 3) {
                if(ans[j] > ans[j - 1] && ans[j - 1] < ans[j - 2]){
                    flag = 1;
                    break;
                }
                if(ans[j] < ans[j - 1] && ans[j - 1] > ans[j - 2]){
                    flag = 1;
                    break;
                }
            }//判断单调性 
        }
        if(!flag) printf("%d\n", i);//如果具有单调性 
    }

    return 0;
}

一看输出结果,哟 710 的倍数一家都来了呢:

SJ8.png

换言之只要是710的倍数都具有类似的性质。那么为什么是710呢?

为什么是710

我苦苦搜寻了一大圈的资料,但却无果。没办法只好自己手动去推导了。

首先第一个问题是,既然710的倍数可以,那它的一半355为什么不可以呢?

我修改了一下之前的提交程序:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
long long num, n;
int main() {
    scanf("%lld", &n);
    num = 0;
    for(long long i = 1; i <= n; i++) printf("%lf\n", sin((long long)355 * i - (long long)355 * (long long)n / (long long) 2));
    return 0;
}

输出结果我们发现:

SJ9.png

但看绝对值还是和刚刚一样都是先下降再上升,但是这次1符号却不是0的左边全是负号,右边全是正号,而是正号负号交叉进行。那可能是什么原因呢?

“周期性”,对于sinx,如果让他变化一个很小的数 λ ,并且加上一些周期我们就会发现 sin(x + λ) = sin(x + λ + 2Π) = -sin(x + λ + Π)

换言之,加上半个周期,符号就会改变,再加上半个周期,其符号就会变回来。是不是发现了什么?

没错我们可以把355看成是半个周期,而710就是一个周期,这样就解释的通为什么710的倍数也具有一样的性质。

接下来又回归到了最开始的问题,为什么是710?

接下来我试探性的打了下面这样一个程序,去寻找10000内距离距离它最近的Π的倍数最小的七个数和他们分别的距离:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const double pi = asin(1) * 2;
double a[1100000];

double check(double x) {
    return(min(ceil(x) - x, x - floor(x)));
} 

int main() {
    int n = 10000;
    for(int i = 1; i <= n; i++) a[i] = check(i / pi);//寻找距离 
    sort(a + 1, a + n + 1);

    for(int o = 1; o <= 7; o++) {
        for(int i = 1; i <= n; i++) {
            if(check(i / pi) == a[o]) {
                printf("%d %lf\n", i, a[o]);
                break;
            }
        }
    }
    return 0;
}

最后发现果不其然,还是710那一家老小:

SJ10.png

那道理就很好解释了,710/Π≈226,误差在小数点后第五位,也就是说我们可以把710近似地看成226Π,那么如果是sin(c x) = sin(x 226Π)的话,那么sin这个结果会一直是0对吧。但是这个1e-5的误差虽然很小,但是依然存在,这个误差就提供了一丝偏移,每一次我们的sin 都在加上了226个周期后都朝着同一个方向偏移了很小很小的一点点,所以这就是我们能用sin(710 * x)在int范围内生成单调的sin值的原因。

所以我们真正的sin(710*x)的图像应该是这样:

SJ7.5.png

其一个周期大概为1000000左右,换句话说如果题目数据范围再大,我们直接输出710的倍数就可能跨过单调区间,不输出的答案就一定是单调的了。

这也进一步解释了为什么sin(355 x)会出现一个正一个负的情况。其原因就是335 / Π = 113,是个奇数。所以即便是sin(x 113Π),原本的符号就是+1,-1,+1,-1的,所以恰好出现了正负号交叉进行的情况。

到这里关于关于正弦函数和七百一十的那些事就基本梳理出来了。那只有710的倍数有这样的性质吗?当然不是,当我们的生成范围变成long long,搜索范围变成1000000时:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const double pi = asin(1) * 2;
double a[1100000];

double check(double x) {
    return(min(ceil(x) - x, x - floor(x)));
} 

int main() {
    int n = 1000000;//扩大范围
    for(int i = 1; i <= n; i++) a[i] = check(i / pi);//寻找距离 
    sort(a + 1, a + n + 1);

    for(int o = 1; o <= 7; o++) {
        for(int i = 1; i <= n; i++) {
            if(check(i / pi) == a[o]) {
                printf("%d %lf\n", i, a[o]);
                break;
            }
        }
    }
    return 0;
}

我们就发现这次的主力军变成了10348一家老小:

SJ11.png

它们与kΠ之间的差距达到了1e-6,也就是说用它们来当sin(c * x)中的c,可以生成出更加稠密的具有单调性的sin序列。更小的误差值带来的是更大的周期,这就解决了当 n 更大时,使用710构造输出序列的正弦值不是单调的问题。

那其他三角函数呢

那这次题目是x单调,要求正弦函数单调,那下次搞个余弦或者正切怎么办?没事我们一个一个搞定。

正切函数

首先是正切,正切是很好搞定的,因为在关于0对称的一个单调区间内,正切的单调性和正弦是基本相一致的,所以直接抄正弦的生成就好了:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
long long num, n;
int main() {
    scanf("%lld", &n);
    num = 0;
    for(long long i = 1; i <= n; i++) printf("%lld\n", (long long)710 * i - (long long)710 * (long long)n/ (long long) 2);//关于y轴对称 
    return 0;
}

此时若输出20个数对应的tan值:

SJ12.png

就可以发现其和sin一样单调且密集。

余弦函数

余弦函数比较特殊,它的单调区间并不关于y轴对称,所以我们考虑只要y轴右半部分的单调区间即可:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
long long num, n;
int main() {
    scanf("%lld", &n);
    num = 0;
    for(long long i = 1; i <= n; i++) printf("%lld\n", (long long)710 * i);//只要y轴右半边 
    return 0;
}

此时若输出20个数对应的cos值,而由于开始时导数值较小,所以区间取到7100时才有比较明显的下降,可以在具体操作时可以视情况选择间距(在此输出以7100间距为例):

SJ13.png

就可以发现也是单调且密集。若想要随着x的递增单调递增的可以选取y轴的左半部分,这里就不赘述了。

结语

通过这篇BLOG,相信你已经完全了解了三角函数和七百一十的那些事,希望能在今后的学习生活中对你有所启发。最后希望你喜欢这篇BLOG!

Last modification:March 21st, 2020 at 12:17 am
If you think my article is useful to you, please feel free to appreciate