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

第3章整值函數(shù)

（IntegerFunctions）鞠成東E-mail：juchd@M.P.：152046793362023/2/323.4‘MOD’:TheBinaryOperation

‘MOD’:二元運(yùn)算2023/2/33MOD:二元運(yùn)算在正整數(shù)m除正整數(shù)n時，商可以用取整符號表示為，而余數(shù)則記成“nmodm”：也就是可將“余數(shù)”的計算推廣到負(fù)整數(shù)，乃至任意實(shí)數(shù)上：因此mod是一個二元運(yùn)算，其中后面的數(shù)稱為模數(shù)，前面的數(shù)至今尚沒有命名。2023/2/34MOD的直觀理解和例子當(dāng)x、y為正實(shí)數(shù)時，如何直觀理解xmody的意義？假設(shè)有一個周長為y的圓，如果從某個點(diǎn)O開始在圓上繞著移動大小為x的距離，則結(jié)束點(diǎn)就是xmody。而且移動過程中掃過O的次數(shù)為。如何理解當(dāng)x或y是負(fù)數(shù)時的xmody？先來看一些例子：2023/2/35負(fù)整數(shù)模下的MOD可以看到，如果模數(shù)y取不同的符號，xmody的符號也不相同，但是值均在0和模數(shù)y之間：若y=0怎么辦？有人提出，為保持連續(xù)性而定義：，可以證明：但是上面的定義實(shí)際用處不大。為保持完整性，CM中定義，也就是說xmody與x之差總為y的倍數(shù)。如何證明?2023/2/36實(shí)數(shù)模下的MOD如果將x分為整數(shù)部分和小數(shù)部分：，可以發(fā)現(xiàn)，小數(shù)部分能夠表示成xmod1，即

注意：mod的運(yùn)算優(yōu)先級比+/-高。能否對上取整函數(shù)定義類似mod的運(yùn)算？G-K-P給出了一個mumble的名字：

看看mumble在圓周模型下的意義：在繞著圓周前進(jìn)距離x后，為了再次到起始點(diǎn)還需要前進(jìn)的距離。2023/2/37MOD的分配律分配律是mod運(yùn)算的重要法則。對所有實(shí)數(shù)c、x和y有如果約定mod的優(yōu)先級比乘法低，則右邊可以移去圓括號。分配律的正確性可由定義驗證：

容易驗證模數(shù)為零時也成立。2023/2/38均勻分組問題下面討論常遇到的實(shí)際問題：n個東西分到規(guī)模盡可能均等的m組。例如將n行文字排成m列，為整齊起見，列的長度依次遞減，任意兩列行數(shù)之差不超過1。例如37行排成5列，顯然右邊更美觀：2023/2/39分組問題的要求附加要求：按列優(yōu)先的順序排列各行文字：先放第1列，再放第2列、第3列等等，才符合閱讀習(xí)慣。如果按行優(yōu)先排列各行文字，能夠得到右邊的排列結(jié)果（每列的行數(shù)是正確的），但是各行文字的順序不對。（列1將包含行1、6、11、···、36而不是正確的行1、2、3、···、8。）如果n不是m的倍數(shù)，每個較長的列應(yīng)該包含行，而每個較短的列應(yīng)該包含行；較長的列有nmodm個，而較短的列有nmumblem個。2023/2/310分組問題的解決思路下面用“東西”和“組”來代替“行”和“列”，即可得到對一般化問題的解決方法。按照剛才的思路，首先，第1組應(yīng)包含件東西。然后，接著要處理的問題就是把剩下的東西再“均勻地”分到m–1組里面。很好，我們很容易想到這帶有“遞歸”的色彩。因此后面的分配也同樣每次僅考慮剩下的“第1組”。重復(fù)下列過程：把余下的n’

=n

-個東西放入m’=m

-1個其他組中，直到m=0為止。2023/2/311分組問題的例子例如對n

=314和m

=6，我們得到的分配方案如下：顯然符合要求。也就是說，盡管模數(shù)一直在變，但是仍然取得了規(guī)模“平均”的分組方案。2023/2/312MOD分組方法的正確性分析假設(shè)n

=qm

+r，其中q

=，r

=nmodm。如果r

=0，先把q件東西放入第1組，再用n‘

=n

-q替換n，剩下的n’

=

qm‘件東西放入余下的m’

=m

–1組……此后的分配也是每次放入q個東西。結(jié)果正確。如果r>0，先把=q

+1件東西放入第1組，再用n’

=n

–q

–1替換n，剩下n’

=qm’+r–1件東西放入其余m’

=m

–1組。對n’和m’，可驗證新的余數(shù)為r’

=r

–1，但是q未變。依次分配，可得到包含q+1件東西的r個組，以及包含q個東西的m

–r個組。結(jié)果也正確。怎樣快速計算第k組中有多少件東西？

提示：按照k與r的大小關(guān)系分情況討論。2023/2/313MOD表示下的分組過程根據(jù)我們得到的在k上的直接計算公式，可以用下面的等式表示出將n劃分成以大小遞減、且基本上均勻的m個部分的過程：

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

-1/2，則左邊約為mx

-1/2，右邊約為(x-1/2)+(x-1/2+1/m)+···+(x-1/2+(m-1)/m)，兩邊的粗略近似值恰好相等。2023/2/316在實(shí)數(shù)上的推廣之證明回憶前面學(xué)到的知識（？），我們可以移去下取整符號內(nèi)部的下取整符號。這樣就證明了前面的等式：2023/2/3173.5Floor/CeilingSums

下取整/上取整的求和2023/2/318下取整/上取整的求和前一節(jié)已經(jīng)看到，對涉及取整符號的求和，有時可以得到封閉形式解（當(dāng)然，解有可能用取整符號表示）：本節(jié)將探討若干情形下、涉及取整的求和問題。對涉及取整符號的大多數(shù)求和問題，一般的計算技巧是引入新的變量，以此去掉取整符號，并將取整求和轉(zhuǎn)化為普通的求和問題。右側(cè)的求和問題有沒有封閉形式解？2023/2/319平方根取整求和：方法1直接從含有取整符號的式子無法入手，讓我們嘗試引入新的變量。方法1：首先引入變量，然后得到2023/2/320平方根取整求和：方法1兩個求和的分項都是依賴于n的。n的值決定了求和上下界，設(shè)有，此時第1個求和變?yōu)?023/2/321平方根取整求和：方法1對第2個求和項