當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

上下取整函数的关系以及一些重要性质(附证明)

發布時間：2024/3/13 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了上下取整函数的关系以及一些重要性质(附证明) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

tags: DSA Combinatorics Mathematics

寫在前面

今天(2022.12.7)的lc每日一題, 雖然是中等但也有很多需要注意的點, 看到了0x3f大佬的題解才發現自己知識點的太多不足, 比如下面這個式子:(出自具體數學練習3.12)
$\left\lceil \frac{n}{m} \right\rceil = \left\lfloor \frac{n+m-1}{m} \right\rfloor = \left\lfloor \frac{n - 1}{m} \right\rfloor + 1.$
本文主要給出取整函數的一些內容, 包括幾個重要的取整函數以及上下取整函數之間的關系等.

參考了具體數學¹, Wikipedia²以及³.

基本概念

這里的一些定義, 記號等均參考了具體數學.

取整函數

上取整(ceil):

\lceil x\rceil

, 表示大于等于

x

的最小整數;

下取整(floor):

\lfloor x\rfloor

, 表示小于等于

x

的最大整數;

取整(等價于下取整):

[x]

, 同下取整.

數的表示

設 $x\in\mathbb R$ , 則

$\lfloor x\rfloor$ 表示 $x$ 的整數部分(integer part)

${x\}$ 表示 $x$ 的分數部分(fractional part), (不與單元素集合混淆的情況下)

關系:
$x=\lfloor x\rfloor+\{x\}\iff\{x\}=x-\lfloor x\rfloor.$

取余運算

(下取整表示)設 $m,n\in\mathbb N^*$ , 則
$n=m\cdot\underbrace{\lfloor n/m \rfloor}_{\text{商}}+\underbrace{n\bmod m}_{\text{余數}}\tag{1}$
其中, $n\bmod m\in[0, m)$ .

性質

取余運算

范圍

由 $(1)$ , 得
$n\bmod m=n-m\lfloor n/m \rfloor$
推廣:(設 $x,y\in\mathbb R$ )
$x\bmod y=x-y\lfloor x/y \rfloor,\ y\ne0.$
于是:
$\begin{cases} x\bmod y\in [0,y),&y>0\\ x\bmod y\in (y,0],&y<0 \end{cases}$

另外, 定義
$x\bmod 0=x.\tag{2}$

類似, 定義一個新的運算 $\rm mumble$ , 用上取整表示數:
$x=y\cdot \lceil x/y\rceil-x\ \rm{mumble}\ y, \ y\ne0.$

分配律

$\forall c,x,y\in \mathbb R$ ,
$c(x\bmod y)=(cx)\bmod(cy).$

證明:

$\forall cy\ne0$ ,
$\begin{aligned} c(x\bmod y) &=c(x-y\lfloor x/y\rfloor)\\ &=cx-cy\lfloor cx/cy\rfloor\\ &=(cx)\bmod(cy). \end{aligned}$
當 $y = 0$ 時, 根據定義 $(2)$ , 分配律依然成立.

數的表示

用取余重寫數的表示(整數部分, 分數部分)
$x=\lfloor x\rfloor+x\bmod 1.$

關系

冪等性

$\begin{aligned} \Big\lfloor \lfloor x \rfloor \Big\rfloor &= \lfloor x \rfloor, \\ \Big\lceil \lceil x \rceil \Big\rceil &= \lceil x \rceil, \\ \Big\{ \{ x \} \Big\} &= \{ x \}. \end{aligned}$

并有:(只關注內層作用)
$\begin{aligned} \Big\lfloor \lceil x \rceil \Big\rfloor &= \lceil x \rceil, \\ \Big\lceil \lfloor x \rfloor \Big\rceil &= \lfloor x \rfloor, \end{aligned}$

互反律

$\begin{aligned} \lfloor x \rfloor +\lceil -x \rceil &= 0, \\ -\lfloor x \rfloor &= \lceil -x \rceil, \\ -\lceil x \rceil &= \lfloor -x \rfloor. \end{aligned}$

并且:
$\lfloor x \rfloor + \lfloor -x \rfloor = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ -1,&\text{ 若 }\ x\not\in \mathbb{Z}, \end{cases} \\[5pt] \lceil x \rceil + \lceil -x \rceil = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}$
針對小數部分( $\{x \} = x - \lfloor x \rfloor$ ):
$\{ x \} + \{ -x \} = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}$

與整數的關系

$\lceil x\rceil\geqslant x$ ; $\lfloor x\rfloor\leqslant x$ ; $\lfloor x \rfloor \leqslant \lceil x \rceil$ .

$\lfloor x\rfloor=x\iff x\in \mathbb Z\iff \lceil x\rceil=x$ ;

If $x\notin \mathbb Z$ , then $\lceil x\rceil-\lfloor x\rfloor=[x\ \text{not an integer}]=1$ .
另一種表述:
$\lceil x \rceil - \lfloor x \rfloor = [x\text{是否為整數}]= \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}$

$x-1<\lfloor x\rfloor$ , $x+1>\lceil x\rceil$ , so we have:
$x-1<\lfloor x\rfloor\leqslant x\leqslant \lceil x\rceil<x+1.$

設 $n\in\mathbb Z,\ x\in \mathbb R$ , 則有:
$\begin{cases} \lfloor x\rfloor=n\iff n\leqslant x<n+1\\ \lfloor x\rfloor=n\iff x-1<n\leqslant x\\[10pt] \lceil x\rceil=n\iff n-1<x\leqslant n\\ \lceil x\rceil=n\iff x\leqslant n<x+1\\ \end{cases}$
并有, 整數項移出取整號:
$\begin{cases} \lfloor x+n\rfloor=\lfloor x\rfloor+n,\\ \tag{*} \lceil x+n\rceil=\lceil x\rceil+n, \end{cases}$
不等式的轉換:
$\begin{cases} \lfloor x\rfloor<n \iff x<n\\ \lfloor x\rfloor\geqslant n\iff x\geqslant n \\[10pt] \lceil x\rceil>n\iff x> n\\ \lceil x\rceil\leqslant n\iff x\leqslant n\\ \end{cases}$

與函數的關系

設 $f (x)$ 是任意一個具有如下性質且在一個實數區間內連續的單調遞增函數, 即:
$f(x)=\text{integer}\Longrightarrow x=\text{integer}.$
則有(若函數 $f(x),f(\lfloor x\rfloor),f(\lceil x\rceil)$ 有定義)
$\lfloor f(x)\rfloor=\lfloor f(\lfloor x\rfloor)\rfloor,\quad \lceil f(x)\rceil=\lceil f(\lceil x\rceil)\rceil.$

證明:(反證)

當 $x=\lceil x\rceil$ , 顯然成立.
當 $x<\lceil x\rceil$ 時, 根據函數 $f (x)$ 單調性得到:
$f(x)<f(\lceil x\rceil),$
根據上取整函數非降性質, 又可得到:
$\lceil f(x)\rceil\leqslant \lceil f(\lceil x\rceil)\rceil,$
- 若 $\lceil f(x)\rceil< \lceil f(\lceil x\rceil)\rceil$ , 由 $f$ 連續性, 必定存在數 $y$ , 使得 $x\leqslant y<\lceil x\rceil$ , 以及 $f(y)=\lceil f(x)\rceil$ . 由于 $f$ 定義, $y\in\mathbb Z$ , 但是不存在介于 $\lfloor x\rfloor$ 和 $\lceil x\rceil$ 之間的整數, 矛盾, 由此得證.

由此得到一個特例:

$\forall m\in \mathbb Z$ , $n\in\mathbb N^*$ , 有
$\left\lceil \frac {x+m}n\right\rceil=\left\lceil \frac {\lceil x\rceil+m}n\right\rceil,\ \left\lfloor \frac {x+m}n\right\rfloor=\left\lfloor \frac {\lfloor x\rfloor+m}n\right\rfloor.\tag{**}$

恒等式

每組近似分配(埃爾米特恒等式的特例)

將 $n$ 個物品分成 $m$ 組, 按照非增次序排列且盡可能相等的部分的劃分:
$n=\left\lceil \frac nm\right\rceil+\left\lceil \frac {n-1}m\right\rceil+\cdots+\left\lceil \frac {n-m+1}m\right\rceil.\tag{3}$

證明: (構造)

設 $n = q m + r$ , 其中 $q=\lfloor n/m\rfloor$ , $r=n\bmod m, 0\leqslant r<m$ , 則:

當 $r = 0$ , 此時將 $q=\lfloor n/m\rfloor$ 件物品放入第一組, 并且用 $n^{'} = n ? q$ 替換 $n$ , 讓 $n^{'} = q m^{'}$ 件物品放入剩下的 $m^{'} = m ? 1$ 組中, 重復這個操作直到物品都被分組.
當 $r > 0$ , 將 $\lceil n/m\rceil=\lfloor n/m\rfloor+1= q+1$ 件物品放進第一組, 用 $n^{'} = n ? q ? 1$ 替換 $n$ ,

$n'=n-q-1=qm+r-q-1=q(\underbrace{m-1}_{m'})+\underbrace{r-1}_{r'}$

即 $n^{'} = q m^{'} + r ? 1$ 件物品留給后面的分組. 此時新的余數為 $r^{'} = r ? 1$ , 但 $q$ 保持不變.
當余數 $r$ 減到 $0$ 時, 此時情況同上, 所以有
$n件商品:\begin{cases} \qquad r個組:q+1件物品\\ m-r個組:q件物品 \end{cases}$

那么在第 $k$ 組( $1\leqslant k\leqslant m$ )中有多少物品?

應該是:
$\left\lceil \frac {n-k+1}m\right\rceil$

證明:

將 $n = q m + r$ 代入上式, 得到:
$\left\lceil \frac {n-k+1}m\right\rceil=\left\lceil \frac {qm+r-k+1}m\right\rceil\stackrel{(*)}{=}q+\left\lceil \frac {r-k+1}m\right\rceil$
應用邊界條件: $1\leqslant k\leqslant m,\ 0\leqslant r<m$ , 得到
$\left\lceil \frac {r-k+1}m\right\rceil=[k\leqslant r]$
上面的 $[k\leqslant r]$ 表示當滿足 $k\leqslant r$ 時, 取 $1$ , 否則取 $0$ , 這正好滿足我們上面給出的構造分組的方法.

將其寫成累加形式, 則有:
$\begin{aligned} n&=\left\lceil \frac nm\right\rceil+\left\lceil \frac {n-1}m\right\rceil+\cdots+\left\lceil \frac {n-m+1}m\right\rceil\\ &=\sum_{i=0}^{m-1}\left\lceil \frac {n-i}m\right\rceil=qm+\sum_{i=0}^{m-1}\left\lceil \frac {r-i}m\right\rceil\\ &=qm+\sum_{i=0}^{r-1}\left\lceil \frac {r-i}m\right\rceil=qm+r\\ \end{aligned}$

同理, 根據各個部分按照非減的次序排列, 小的組放在前面, ( $\lfloor n/m\rfloor$ 在第一組)就得到:
$n=\left\lfloor \frac nm\right\rfloor+\left\lfloor \frac {n+1}m\right\rfloor+\cdots+\left\lfloor \frac {n+m-1}m\right\rfloor.\tag{3'}$
針對上面得到的結論, 還可以進行推廣:

利用 $\lfloor mx\rfloor$ 替換 $(3^{'})$ 式中的 $n$ , 并用 $(? ?)$ 式去掉下取整函數中的下取整函數可以得到:
$\lfloor mx\rfloor=\left\lfloor x\right\rfloor+\left\lfloor x+\frac 1m\right\rfloor+\cdots+\left\lfloor x+\frac{m-1}m\right\rfloor.$
上式就是埃爾米特恒等式.

$\bigstar$ 上下取整轉換

下面介紹前言部分提到的一個重要的關系, 利用這個式子可以方便的轉換上取整和下取整, 因為計算機編程語言中常用下取整.
$\left\lceil \frac{n}{m} \right\rceil = \left\lfloor \frac{n+m-1}{m} \right\rfloor = \left\lfloor \frac{n - 1}{m} \right\rfloor + 1.\tag{***}$
以及:
$\left\lfloor \frac{n}{m} \right\rfloor = \left\lceil \frac{n-m+1}{m} \right\rceil = \left\lceil \frac{n + 1}{m} \right\rceil - 1.$

證明:(方法1)

直接由埃爾米特恒等式的特例 $(3)$ 的第一項等于 $(3^{'})$ 式的第二項, 即為本結論, 需要從組合意義角度出發. (分組方法)

證明:(方法2)

對 $(*\!*\!*)$ 兩端同時減去 $\left\lfloor \dfrac nm\right\rfloor$ , 得到:

左邊:(利用與整數的關系之3)
$\left\lceil \frac{n}{m} \right\rceil-\left\lfloor \dfrac nm\right\rfloor=\left\lceil\frac{n\bmod m}{m}\right\rceil=\begin{cases} 0,&\text{ 若 }n\bmod m=0,\\ 1,&\text{ 若 }n\bmod m>0. \end{cases}$
右邊:
可設 $n = m q + r$ , 并有 $q=\lfloor n/m \rfloor,0\leqslant r=n\bmod m<m$ , 則
$\begin{aligned} \left\lfloor \frac{n+m-1}{m} \right\rfloor-\left\lfloor \frac nm\right\rfloor &=\left\lfloor \frac{mq+m+r-1}{m} \right\rfloor-\left\lfloor \frac {mq+r}m\right\rfloor\\ &=\left\lfloor \frac{r+m-1}{m} \right\rfloor-\left\lfloor \frac {r}m\right\rfloor\\ &=\left\lfloor \frac{r+m-1}{m} \right\rfloor\\ &=\left\lfloor \frac{n\bmod m+m-1}{m} \right\rfloor\\ &=\begin{cases} 0,&\text{ 若 }n\bmod m=0,\\ 1,&\text{ 若 }n\bmod m>0. \end{cases} \end{aligned}$

即得結論.

當然, 還有通過廣義Ramsey定理證明的方法(鴿巢原理的推廣), 可以參見³.

總的來看, 這個結論通過上面的近似分組問題就可以解釋了.

ref

具體數學; ??

取整函數 - 維基百科，自由的百科全書 (wikipedia.org); ??

上取整與下取整的轉換 - flyor - 博客園 (cnblogs.com); ?? ??

總結

以上是生活随笔為你收集整理的上下取整函数的关系以及一些重要性质(附证明)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： spring boot高校二手教材管理平
下一篇：机器学习面试题（转）

编程问答

上下取整函数的关系以及一些重要性质(附证明)

tags: DSA Combinatorics Mathematics

寫在前面

基本概念

取整函數

數的表示

取余運算

性質

取余運算

范圍

分配律

數的表示

關系

冪等性

互反律

與整數的關系

與函數的關系

恒等式

每組近似分配(埃爾米特恒等式的特例)

★ \bigstar ★上下取整轉換

ref

總結

$\bigstar$ 上下取整轉換