KNOWECON WIKI

ARTICLE

向下取整函数

向下取整函数（floor function）是数学中一类重要的取整函数。对于任意实数 x ，记作 x 或 floor(x) ，定义为不大于 x 的最大整数。即 x 是满足 x x < x + 1 的唯一整数。这一概念在数论、计算机科学和算法分析中应用广泛。 基本性质 设 x R ，则 x 是唯一的整数 n 满足 n x < n + 1 。例如： 负数的处理需

浏览 5 更新 2025-10-26

向下取整函数（floor function）是数学中一类重要的取整函数。对于任意实数 x x ，记作 ⌊x⌋ \lfloor x \rfloor 或 floor⁡(x) \operatorname{floor}(x) ，定义为不大于 x x 的最大整数。即 ⌊x⌋ \lfloor x \rfloor 是满足 ⌊x⌋≤x<⌊x⌋+1 \lfloor x \rfloor \le x < \lfloor x \rfloor + 1 的唯一整数。这一概念在数论、计算机科学和算法分析中应用广泛。

基本性质

设 x∈R x \in \mathbb{R} ，则 ⌊x⌋ \lfloor x \rfloor 是唯一的整数 n n 满足 n≤x<n+1 n \le x < n + 1 。例如：

⌊3.7⌋=3,⌊−2.3⌋=−3,⌊5⌋=5,⌊π⌋=3\lfloor 3.7 \rfloor = 3,\quad \lfloor -2.3 \rfloor = -3,\quad \lfloor 5 \rfloor = 5,\quad \lfloor \pi \rfloor = 3

负数的处理需特别注意：⌊−2.3⌋=−3 \lfloor -2.3 \rfloor = -3 ，这与向零取整（截断为 −2 -2 ）不同。

基本性质包括：（1）整数保持性：若 n∈Z n \in \mathbb{Z} ，则 ⌊n⌋=n \lfloor n \rfloor = n ；（2）平移性：⌊x+n⌋=⌊x⌋+n \lfloor x + n \rfloor = \lfloor x \rfloor + n 对任意整数 n n 成立；（3）恒等关系：⌊x⌋=x \lfloor x \rfloor = x 当且仅当 x∈Z x \in \mathbb{Z} ；（4）小数分解：x=⌊x⌋+{x} x = \lfloor x \rfloor + \{x\} ，0≤{x}<1 0 \le \{x\} < 1 。

与取余的关系

取模运算的标准定义为：

a mod n=a−n⌊an⌋a \bmod n = a - n \left\lfloor \frac{a}{n} \right\rfloor

该定义确保余数在 [0,n−1] [0, n-1] 范围内。Python 等语言的 \texttt{\%} 运算符正是基于此实现。

数论应用

勒让德公式（Legendre's formula）计算 n! n! 中素数 p p 的指数：

vp(n!)=∑k=1∞⌊npk⌋v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor

该公式在组合数计算和大数分解中不可或缺。埃尔米特恒等式（Hermite's identity）则揭示了取整与线性缩放的关系：

∑k=0n−1⌊x+kn⌋=⌊nx⌋\sum_{k=0}^{n-1} \left\lfloor x + \frac{k}{n} \right\rfloor = \lfloor nx \rfloor

在丢番图逼近和连分数理论中有重要应用。

计算机科学中的角色

算法分析中广泛使用向下取整函数：二分查找的比较次数为 ⌊log⁡2n⌋+1 \lfloor \log_2 n \rfloor + 1 ；堆排序的建堆复杂度由 ∑h=0⌊log⁡2n⌋⌊n/2h+1⌋ \sum_{h=0}^{\lfloor \log_2 n \rfloor} \lfloor n/2^{h+1} \rfloor 刻画；哈希表的除留余数法 h(k)=k mod m h(k) = k \bmod m 本质上依赖向下取整。在计算几何中，向下取整用于将连续坐标映射到像素网格；在操作系统分页中，虚拟地址到物理页框的转换也依赖该运算。

与向上取整的对偶

向上取整函数 ⌈x⌉ \lceil x \rceil 定义为不小于 x x 的最小整数，满足对偶关系：

⌈x⌉=−⌊−x⌋\lceil x \rceil = -\lfloor -x \rfloor

傅里叶展开

向下取整函数可展开为傅里叶级数：

⌊x⌋=x−12+1π∑k=1∞sin⁡(2πkx)k\lfloor x \rfloor = x - \frac{1}{2} + \frac{1}{\pi} \sum_{k=1}^{\infty} \frac{\sin(2\pi k x)}{k}

该展开将分段常数函数用正弦波叠加逼近，在信号处理中有理论意义。

解题技巧

常见技巧包括：（1）放缩法：利用 ⌊x⌋≤x<⌊x⌋+1 \lfloor x \rfloor \le x < \lfloor x \rfloor + 1 夹逼；（2）整数化：设 n=⌊x⌋ n = \lfloor x \rfloor ，x=n+θ x = n + \theta ，0≤θ<1 0 \le \theta < 1 ；（3）分段讨论：按整数区间将函数化为逐段常数；（4）求和技巧：利用勒让德公式或埃尔米特恒等式化简。

例如，证明 ⌊n+n+1⌋=⌊4n+2⌋ \lfloor \sqrt{n} + \sqrt{n+1} \rfloor = \lfloor \sqrt{4n+2} \rfloor 是经典竞赛题，需利用平方差和单调性精密放缩。

扩展

向下取整函数可推广到 p p 进赋值论中，vp v_p 本质上计算被 p p 整除的最大幂次。在连分数展开中，部分商通过反复取整 a0=⌊x⌋ a_0 = \lfloor x \rfloor 和取倒数得到，构成连分数算法的基础。

总之，向下取整函数形式简洁却内涵丰富，从数论中的精确计数到算法分析的复杂度估算，从基本算术到高级解析工具，它在数学各分支中发挥着基础性作用。掌握其性质和技巧，对深入理解离散数学与计算理论具有重要奠基意义。