具體數(shù)學(xué) 第3章 整值函數(shù)(3.4節(jié)-3.5節(jié))

1、第第3章章 整值函數(shù)整值函數(shù)（Integer Functions）鞠成東鞠成東E-mail：M. P. ：152046793362022-1-3123.4 MOD: The Binary OperationMOD: 二元運(yùn)算2022-1-313MOD: 二元運(yùn)算 在正整數(shù)m除正整數(shù)n時，商可以用取整符號表示為 ，而余數(shù)則記成“n mod m”： 也就是 可將“余數(shù)”的計算推廣到負(fù)整數(shù)，乃至任意實(shí)數(shù)上： 因此mod是一個二元運(yùn)算，其中后面的數(shù)稱為模數(shù)，前面的數(shù)至今尚沒有命名。mn 余數(shù)商mnmmnnmodmmnnmn 商余數(shù)modyyxxyx 商余數(shù)mod2022-1-314MOD的直觀理解和例

2、子 當(dāng)x、y為正實(shí)數(shù)時，如何直觀理解x mod y的意義？假設(shè)有一個周長為y的圓，如果從某個點(diǎn)O開始在圓上繞著移動大小為x的距離，則結(jié)束點(diǎn)就是x mod y。而且移動過程中掃過O的次數(shù)為 。 如何理解當(dāng)x或y是負(fù)數(shù)時的x mod y？先來看一些例子：yx2 ) 3/(5) 3(5 3mod51 3/535 3mod51 ) 3/(5) 3(5 3mod52 3/535 3mod52022-1-315負(fù)整數(shù)模下的MOD 可以看到，如果模數(shù)y取不同的符號，x mod y的符號也不相同，但是值均在0和模數(shù)y之間： 若y = 0怎么辦？有人提出，為保持連續(xù)性而定義： ，可以證明： 但是上面的定義實(shí)際用

3、處不大。為保持完整性，CM中定義 ，也就是說x mod y與x之差總為y的倍數(shù)。0,mod00,mod0yyyxyyyx對于對于xx0mod0mod0modlim0 xyxy如何證明?00modx2022-1-316實(shí)數(shù)模下的MOD 如果將x分為整數(shù)部分和小數(shù)部分： ，可以發(fā)現(xiàn)，小數(shù)部分能夠表示成x mod 1，即注意：mod的運(yùn)算優(yōu)先級比+/-高。 能否對上取整函數(shù)定義類似mod的運(yùn)算？G-K-P給出了一個mumble的名字： 看看mumble在圓周模型下的意義：在繞著圓周前進(jìn)距離x后，為了再次到起始點(diǎn)還需要前進(jìn)的距離。 xxx 1modxxxxyxyyx mumble 2022-1-317

4、MOD的分配律 分配律是mod運(yùn)算的重要法則。對所有實(shí)數(shù)c、x和y有 如果約定mod的優(yōu)先級比乘法低，則右邊可以移去圓括號。分配律的正確性可由定義驗(yàn)證：容易驗(yàn)證模數(shù)為零時也成立。)mod()()mod(cycxyxccycxcycxcycxyxcycxyxyxcyxcmod/)/()mod(2022-1-318均勻分組問題 下面討論常遇到的實(shí)際問題：n個東西分到規(guī)模盡可能均等的m組。例如將n行文字排成m列，為整齊起見，列的長度依次遞減，任意兩列行數(shù)之差不超過1。例如37行排成5列，顯然右邊更美觀：3224160831231507302214063729211305362820120435271

5、911033426181002332517090158888行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行1608373023150736292214063528211305342720120433261911033225181002312417090177788行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行2022-1-319分組問題的要求 附加要求：按列優(yōu)先的順序排列各行文字：先放第1列，再放第2列、第3列等等，才符合閱讀習(xí)慣。 如果按行優(yōu)先排列各行文字，能夠得到右邊的排列結(jié)果（每列的行數(shù)是正確的），但是各行文字的順序不對。（列1將包

6、含行1、6、11、36而不是正確的行1、2、3、8。） 如果n不是m的倍數(shù)，每個較長的列應(yīng)該包含 行，而每個較短的列應(yīng)該包含 行；較長的列有n mod m個，而較短的列有n mumble m個。mn/mn/2022-1-3110分組問題的解決思路 下面用“東西”和“組”來代替“行”和“列”，即可得到對一般化問題的解決方法。 按照剛才的思路，首先，第1組應(yīng)包含 件東西。然后，接著要處理的問題就是把剩下的東西再“均勻地”分到m1組里面。很好，我們很容易想到這帶有“遞歸”的色彩。因此后面的分配也同樣每次僅考慮剩下的“第1組”。 重復(fù)下列過程：把余下的n = n - 個東西放入m= m - 1個其他組

7、中，直到m = 0為止。mn/mn/2022-1-3111分組問題的例子 例如對n = 314和m = 6，我們得到的分配方案如下： 顯然符合要求。也就是說，盡管模數(shù)一直在變，但是仍然取得了規(guī)模“平均”的分組方案。52152522104523156524208535261536314/組數(shù)東西數(shù)剩余組的數(shù)量剩余東西數(shù)量2022-1-3112MOD分組方法的正確性分析 假設(shè)n = qm + r，其中q = ，r = n mod m。a) 如果r = 0，先把q件東西放入第1組，再用n = n - q替換n，剩下的n = qm件東西放入余下的m = m 1組此后的分配也是每次放入q個東西。結(jié)果正確

8、。b) 如果r 0，先把 = q + 1件東西放入第1組，再用n = n q 1替換n，剩下n = qm + r 1件東西放入其余m = m 1組。對n和m，可驗(yàn)證新的余數(shù)為r = r 1，但是q未變。依次分配，可得到包含q + 1件東西的r個組，以及包含q個東西的m r個組。結(jié)果也正確。 怎樣快速計算第k組中有多少件東西？提示：按照k與r的大小關(guān)系分情況討論。mn/mn/mkn12022-1-3113MOD表示下的分組過程 根據(jù)我們得到的在k上的直接計算公式，可以用下面的等式表示出將n劃分成以大小遞減、且基本上均勻的m個部分的過程：事實(shí)上我們在前面已經(jīng)遇到過m2的情形： mmnmnmnn11

9、 22212nnnnn2022-1-3114遞增次序下的分組 如果希望分組的規(guī)模是遞增的，也就是說小組在大組之前，可以用相同的方法完成，只是在第一組中放入 件東西。相應(yīng)地，可以得到相同形式的等式如下 問題：如何證明下式成立？mn mmnmnmnn11 mmnmnmnmmnmnmn11112022-1-3115在實(shí)數(shù)上的推廣 來看一個讓人驚訝的美妙等式。如果用 替換前面的n，我們會得到一個關(guān)于所有實(shí)數(shù)x的等式： 驚訝不？我們知道，實(shí)數(shù)的下取整是它的整數(shù)近似值，等式左邊只有一個近似值，卻恰好等于右邊好多個近似值之和。 如果粗略地假設(shè) 約為x - 1/2，則左邊約為mx -1/2，右邊約為(x-1/

10、2)+(x-1/2+1/m)+(x-1/2+(m-1)/m) ，兩邊的粗略近似值恰好相等。mx mmxmxxmx11 x2022-1-3116在實(shí)數(shù)上的推廣之證明 回憶前面學(xué)到的知識（？），我們可以移去下取整符號內(nèi)部的下取整符號。這樣就證明了前面的等式： mmxmxxmmmxmmxmmxmmmxmmxmmxmx1111112022-1-31173.5 Floor/Ceiling Sums下取整/上取整的求和2022-1-3118下取整/上取整的求和 前一節(jié)已經(jīng)看到，對涉及取整符號的求和，有時可以得到封閉形式解（當(dāng)然，解有可能用取整符號表示）： 本節(jié)將探討若干情形下、涉及取整的求和問題。 對涉及

11、取整符號的大多數(shù)求和問題，一般的計算技巧是引入新的變量，以此去掉取整符號，并將取整求和轉(zhuǎn)化為普通的求和問題。 右側(cè)的求和問題有沒有封閉形式解？ mmxmxxmx11nkk02022-1-3119平方根取整求和：方法1 直接從含有取整符號的式子無法入手，讓我們嘗試引入新的變量。 方法1：首先引入變量 ，然后得到km mkmkmkmkmknkmnkmmnmkmmmkmnkmmkmnkmkmnkmk,022,022,022,0,00) 1() 1() 1(12022-1-3120平方根取整求和：方法1 兩個求和的分項都是依賴于n的。n的值決定了求和上下界，設(shè)有 ，此時第1個求和變?yōu)?301201202022,0222233232322) 1() 1(mmmmmmmmmmmmmmkmmmmmmkn2022-1-3121平方根取整求和：方法1 對第2個求和項 顯然有 ，因此求和可化簡為 最后，合并兩個求和項的值，即可得到總的求和2022,022) 1() 1(nnkmnkmmkmkmkmnkmm,022) 1(mnn這里,6