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

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

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

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

=n

-個(gè)東西放入m’=m

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

=314和m

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

=qm

+r，其中q

=，r

=nmodm。如果r

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

=n

-q替換n，剩下的n’

=

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

=m

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

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

=n

–q

–1替換n，剩下n’

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

=m

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

=r

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

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

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

事實(shí)上我們?cè)谇懊嬉呀?jīng)遇到過(guò)m＝2的情形：2023/2/314遞增次序下的分組如果希望分組的規(guī)模是遞增的，也就是說(shuō)小組在大組之前，可以用相同的方法完成，只是在第一組中放入件東西。相應(yīng)地，可以得到相同形式的等式如下問(wèn)題：如何證明下式成立？2023/2/315在實(shí)數(shù)上的推廣來(lái)看一個(gè)讓人驚訝的美妙等式。如果用替換前面的n，我們會(huì)得到一個(gè)關(guān)于所有實(shí)數(shù)x的等式：驚訝不？我們知道，實(shí)數(shù)的下取整是它的整數(shù)近似值，等式左邊只有一個(gè)近似值，卻恰好等于右邊好多個(gè)近似值之和。如果粗略地假設(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é)到的知識(shí)（？），我們可以移去下取整符號(hào)內(nèi)部的下取整符號(hào)。這樣就證明了前面的等式：2023/2/3173.5Floor/CeilingSums

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