关注公众号【算法码上来】,每日算法干货马上就来!

首先声明一下,最近这段时间忙毕设,没时间更新博客了,大家见谅。
今天这节课开始讲解取整相关知识,主要是数论相关的了。
符号定义
向下取整函数$\left\lfloor x \right\rfloor $定义为小于等于$x$的最大整数。
向上取整函数$\left\lceil x \right\rceil $定义为大于等于$x$的最小整数。
<!–swig6–>
性质
性质1
<!–swig7–>
性质2
取整函数范围:
<!–swig8–>
性质3
负数的取整:
<!–swig9–>
性质4
取整函数中的整数可以提取出来:
<!–swig10–>
应用
应用1
证明:
<!–swig11–>
更一般的,我们还可以证明,对于任意连续、递增的函数$f(x)$,如果它满足
<!–swig13–>
那么有
<!–swig14–>
我们证明第2个式子,第1个同理可证。
如果$x = \left\lceil x \right\rceil $,显然成立。
否则$x < \left\lceil x \right\rceil $,因为$f(x)$递增,所以有
<!–swig18–>
两边同时取整,有
<!–swig19–>
要证左右两边相等,那么只要证
<!–swig20–>
不成立即可。假设上式成立,那么由中间值定理,一定存在$x \le y < \left\lceil x \right\rceil $,使得
<!–swig22–>
敲黑板!!这里是怎么来的呢?
由下图可以看出,当下面式子成立时,满足中间值定理
<!–swig23–>
但是在这里,我们假设是
<!–swig24–>
那么由$\left\lceil {f(x)} \right\rceil < \left\lceil {f(\left\lceil x \right\rceil )} \right\rceil $能否推出$\left\lceil {f(x)} \right\rceil < f(\left\lceil x \right\rceil )$呢?当然是可以的。
<!–swig27–>
所以
<!–swig28–>
又因为$x \le y < \left\lceil x \right\rceil $,所以不存在整数$y$,矛盾!
所以证得
<!–swig31–>
另一个特殊的例子是
<!–swig32–>
其中$m$和$n$都是整数,并且$n$是正整数。
应用2
接着介绍区间相关的性质。
求1到1000中使得下列式子成立的$n$一共有多少个?
<!–swig37–>
求解方法如下:
<!–swig38–>
继续推广,求1到$N$中使得上面式子成立的$n$有多少个?
令
<!–swig41–>
也就是小于等于$\left\lfloor {\sqrt[3]{N}} \right\rfloor $的最大整数。
所以
<!–swig43–>
渐进地等于
<!–swig44–>
应用3
定义一个实数的谱为:
<!–swig45–>
很容易证明如果两个实数$\alpha \ne \beta $,那么
<!–swig47–>
假设$\alpha < \beta $,那么令
<!–swig49–>
所以
所以集合$Spec(\beta )$中小于$\left\lfloor {m\alpha } \right\rfloor $的元素个数小于$m$。而集合$Spec(\alpha )$中小于$\left\lfloor {m\alpha } \right\rfloor $的元素个数大于等于$m$。所以两个集合不相等。
谱有很多奇妙的性质,例如下面两个谱:
<!–swig57–>
可以发现,这两个谱正好划分了正整数集。
证明方法也很简单,只要证明对任意正整数$n$,两个集合中小于$n$的元素个数之和为$n$,过程如下:
<!–swig61–>
所以第一个集合中小于$n$的元素个数为
<!–swig63–>
同理第二个集合中小于$n$的元素个数为
<!–swig65–>
所以总个数为
<!–swig66–>
得证。