pascal中級(jí)教程第四章分治

1、第四章第四章分治分治4.1取余運(yùn)算取余運(yùn)算源程序名mod.（pasccpp）可執(zhí)行文件名mod.exe輸入文件名mod.in輸出文件名mod.out【問題描述】輸入b，p，k的值，求bpmodk的值。其中b，p，kk為長整型數(shù)?！緲永縨od.inmod.out21092^10mod9=7【知識(shí)準(zhǔn)備】進(jìn)制轉(zhuǎn)換的思想、二分法?！舅惴ǚ治觥勘绢}主要的難點(diǎn)在于數(shù)據(jù)規(guī)模很大(bp都是長整型數(shù))，對(duì)于bp顯然不能死算，那樣的話時(shí)間復(fù)雜度和編程復(fù)雜

2、度都很大。下面先介紹一個(gè)原理：abmodk＝(amodk)(bmodk)modk。顯然有了這個(gè)原理，就可以把較大的冪分解成較小的，因而免去高精度計(jì)算等復(fù)雜過程。那么怎樣分解最有效呢顯然對(duì)于任何一個(gè)自然數(shù)P，有p＝2pdiv2pmod2，如19＝219div2十19mod2＝291，利用上述原理就可以把b的19次方除以k的余數(shù)轉(zhuǎn)換為求b的9次方除以k的余數(shù)，即b19=b291＝bb9b9，再進(jìn)一步分解下去就不難求得整個(gè)問題的解。這是一個(gè)典

3、型的分治問題，具體實(shí)現(xiàn)的時(shí)候是用遞推的方法來處理的，如p=19，有19=291，9=241，4=220，2=210，1＝201，反過來，我們可以從0出發(fā)，通過乘以2再加上一個(gè)0或1而推出1，2，4，9，19，這樣就逐步得到了原來的指數(shù)，進(jìn)而遞推出以b為底，依次以這些數(shù)為指數(shù)的自然數(shù)除以k的余數(shù)。不難看出這里每一次乘以2后要加的數(shù)就是19對(duì)應(yīng)的二進(jìn)制數(shù)的各位數(shù)字，即1，0，0，1，1，而19＝(10011)2，求解的過程也就是將二進(jìn)制數(shù)還

4、原為十進(jìn)制數(shù)的過程。具體實(shí)現(xiàn)請(qǐng)看下面的程序，程序中用數(shù)組binary存放p對(duì)應(yīng)的二進(jìn)制數(shù)，總位數(shù)為len，binary[1]存放最底位。變量rest記錄每一步求得的余數(shù)。771661583852881【知識(shí)準(zhǔn)備】分治思想和遞歸程序設(shè)計(jì)?！舅惴ǚ治觥磕玫竭@個(gè)問題后，便有一種遞歸重復(fù)的感覺。首先對(duì)最簡(jiǎn)單的情況(即k＝1)進(jìn)行分析：公主只會(huì)在4個(gè)方格中的一個(gè)：左上角：則使用3號(hào)毯子補(bǔ)，毯子拐角坐標(biāo)位于(22)；下面就簡(jiǎn)稱為毯子坐標(biāo)左下角：則使

5、用2號(hào)毯子補(bǔ)，毯子拐角坐標(biāo)位于(12)；右上角：則使用1號(hào)毯子補(bǔ)，毯子拐角坐標(biāo)位于(21)；右下角：則使用4號(hào)毯子補(bǔ)，毯子拐角坐標(biāo)位于(11)；其實(shí)這樣不能說明什么問題，但是繼續(xù)討論就會(huì)有收獲，即討論k＝2的情況(如圖41)：###●#○###○○#####我們假設(shè)公主所在的位置用實(shí)心圓表示，即上圖中的(14)，那么我們就可以把1號(hào)毯子放在(23)處，這樣就將(13)至(24)的k＝1見方全部覆蓋(#表示地毯)。接下來就是3個(gè)k=1的見

6、方繼續(xù)填滿，這樣問題就歸結(jié)為k＝1的情況了，但是有一點(diǎn)不同的是：沒有“公主”了，每一個(gè)k=1的小見方都會(huì)留下一個(gè)空白(即上圖中的空心圓)，那么空白就有：13＝3個(gè)，組合后便又是一個(gè)地毯形狀。好了，現(xiàn)在有感覺了吧，我們用分治法來解決它！對(duì)于任意k1的宮殿，均可以將其化分為4個(gè)k2大小的宮殿，先看一下公主站的位置是屬于哪一塊，因?yàn)楦鶕?jù)公主所在的位置，我們可以確定中間位置所放的毯子類型，再遞歸處理公主所站的那一塊，直到出現(xiàn)邊界條件k＝1的情況