第5章精巧求解剖析

精巧求解，是指，巧解、精解，巧和精結(jié)合求解，凝聚數(shù)學(xué)的精華，彰顯出編程的卓越。

?

5.1和與積巧算

?

5.1.1互積和

【編程題】

給定n個(gè)整數(shù)，對這n個(gè)整數(shù)求任意2個(gè)數(shù)之積，任意3個(gè)數(shù)之積，......，直至所有n個(gè)整數(shù)之積。把所有這些積求和稱為這些整數(shù)的互積和m。

【妙思巧解】

巧妙構(gòu)造多項(xiàng)式化互積為多項(xiàng)式積。

n個(gè)整數(shù)記為a1、a2、a3、......、an

m = (1+a1)(1+a2)...(1+an) - (a1+a2+...+an) - 1

這樣，用循環(huán)就一個(gè)積，就可以巧妙的求解整數(shù)的互積和。

?

5.1.2嵌套根式和

設(shè)計(jì)要點(diǎn)：處理根號(hào)嵌套，要逆向處理循環(huán)，從最內(nèi)層根號(hào)開始，直至最外層根號(hào)。

?

5.2同碼數(shù)匯趣

由同一個(gè)數(shù)碼組成的數(shù)稱為同碼數(shù)。如5555是同碼整數(shù)；0.77777是同碼小數(shù)。

?

5.2.1同碼數(shù)整除

【編程題】探求同碼數(shù)能被p整除。

采用模擬豎式除法。

?

5.2.2同碼數(shù)求和

【編程題】求同碼整數(shù)和。S(d, n) = d + dd + ddd + dddd + ... + dd...d(n個(gè)d)

s用數(shù)組存儲(chǔ)，數(shù)組每個(gè)單元存儲(chǔ)一位數(shù)字。

從個(gè)位開始，相加和進(jìn)位。

?

5.3統(tǒng)計(jì)的智慧

5.3.1巧妙建模

【編程題】

對于給定的正整數(shù)和s，對于3個(gè)變量x, y, z的不定方程x+y+z = s，試統(tǒng)計(jì)x, y, z取自區(qū)間[c, ?d](0 ≤?c < d, 3c ≤?s)整數(shù)解的組數(shù)。

?

設(shè)計(jì)要點(diǎn)：循環(huán)，依次探求即可

?

5.3.2三角網(wǎng)格統(tǒng)計(jì)

把一個(gè)正三角形的三邊分成n等份，分別與各邊平行連接各分點(diǎn)，得n-三角網(wǎng)格。

【編程題】

對于指定正整數(shù)n，試求n-三角形網(wǎng)格中所有不同三角形（大小不同或方位不同）的個(gè)數(shù)，以及所有這些三角形的面積之和（約定網(wǎng)格中最小的單位三角形的面積為1）

?

設(shè)計(jì)要點(diǎn)：從最上層得單位三角形開始，推導(dǎo)計(jì)算公式。

?

5.3.3交通方格網(wǎng)

用典型的矩形方格網(wǎng)表示交通網(wǎng)。

【編程題】

給定一個(gè)交通方格網(wǎng)，其中有路障禁止通行，（路線中各段只能從左至右，從下至上），求從起始點(diǎn)（0，0）到終點(diǎn)（m，n）的最短路線的條數(shù)。

?

設(shè)計(jì)要點(diǎn)，用遞推求得點(diǎn)(x, y)和前點(diǎn)(x-1, y)與(x, y-1)的關(guān)系

?

5.4游戲中的素?cái)?shù)概率

5.4.1從搖骰子到抽數(shù)牌

【編程題】抽數(shù)牌之和為素?cái)?shù)的概率。

有n張數(shù)字牌，數(shù)字牌上分別標(biāo)有整數(shù)1，2，3，……，n。

輸入牌的張數(shù)n（10<n<1000），分別計(jì)算抽取2張與抽取3張牌，這兩種抽牌整數(shù)之和為素?cái)?shù)的概率，并分別指出出現(xiàn)概率最高的素?cái)?shù)（精確到小數(shù)點(diǎn)后3位）。

?

設(shè)計(jì)要點(diǎn)：注意循環(huán)枚舉時(shí)設(shè)置正確，以免出現(xiàn)遺漏或重復(fù)；用試商判別法判別素?cái)?shù)。

涉及概率計(jì)算，必須統(tǒng)計(jì)事件的總體數(shù)與滿足指定條件事件個(gè)數(shù)，這是概率計(jì)算的基礎(chǔ)。

?

5.4.2抽撲克牌

【編程題】撲克牌，除取大小王，有四種花色牌，每種花色有A，2，3，4，...，10，J，Q，K（約定A為數(shù)碼為1，J，Q，K分別為11，12，13），即每種花色有13個(gè)數(shù)碼牌。

分別計(jì)算抽取2張與抽取3張牌，這兩種抽牌整數(shù)之和為素?cái)?shù)的概率。

?

設(shè)計(jì)要點(diǎn)，用數(shù)組依次存儲(chǔ)四種花色的牌，其他同5.4.1

?

5.5梅齊里亞克砝碼問題

梅齊里亞克砝碼問題

一位商人有一個(gè)40磅的砝碼，由于跌落在地而碎成4塊.后來，稱得每塊碎片的重量都是整磅數(shù)，而且可以用這4塊來稱從1至40磅之間的任意整數(shù)磅的重物.問這4塊砝碼碎片各重多少？

此類問題后來拓展成數(shù)學(xué)中一類“稱重問題”，引起人們廣泛關(guān)注。

?

5.5.1單砝碼盤稱重

單砝碼天平，規(guī)定只能在砝碼盤放砝碼，而稱重盤只能放物品不能放砝碼。

【編程題】

一人要用整數(shù)m克材料制作n個(gè)砝碼，可以用這n個(gè)砝碼在單碼盤天平上稱1~m克的任意整數(shù)克質(zhì)量。

輸入整數(shù)m及指定整數(shù)質(zhì)量t（m≤1000，t≤m），輸出砝碼至少個(gè)數(shù)n及這n個(gè)砝碼的質(zhì)量，并輸出在天平商稱重t的砝碼配置方案。

?

設(shè)計(jì)要點(diǎn)，當(dāng)n塊砝碼質(zhì)量分別為1，2，2^2，... ，2^(n-1)時(shí)，

m = 1+2+2^2+... +2^(n-1) = 2^n - 1

可在單碼盤天平上實(shí)現(xiàn)稱1~m的任意整數(shù)質(zhì)量。

?

5.5.2雙砝碼盤稱重

雙砝碼盤，天平的兩個(gè)盤都能放砝碼。

【編程題】

一人要用整數(shù)m克材料制作n個(gè)砝碼，可以用這n個(gè)砝碼在雙碼盤天平上稱1~m克的任意整數(shù)克質(zhì)量。

輸入整數(shù)m及指定整數(shù)質(zhì)量t（1<t<m），輸出砝碼至少個(gè)數(shù)n及這n個(gè)砝碼的質(zhì)量。

?

設(shè)計(jì)要點(diǎn)，當(dāng)n塊砝碼質(zhì)量分別為1，3，3^2，... ，3^(n-1)時(shí)，

m = 1+3+3^2+... +3^(n-1) = (3^n - 1)/2

可在雙碼盤天平上實(shí)現(xiàn)稱1~m的任意整數(shù)質(zhì)量。

?

5.60-1串積與多碼串積

5.6.1探求0-1串積

【編程題】

輸入整數(shù)b，試尋找最小的整數(shù)a，使得a x b為0-1串積。

?

設(shè)計(jì)要點(diǎn)，不要枚舉整數(shù)a來探求，工作量非常大，而通過枚舉串積來探求，工作量相對要小得多。從小到大搜索0-1串積（要看作十進(jìn)制數(shù)），從中找出最小的能被b整除的0-1串積。

?

5.6.2指定多碼串積

【編程題】

輸入兩個(gè)數(shù)碼v, u（約定0 ≤?v < u ≤?9），對指定的正整數(shù)b，試探求最小的正整數(shù)a，使得a x b全由數(shù)字v與u組成。

?

設(shè)計(jì)要點(diǎn)：應(yīng)用求余數(shù)判別指定n碼串積。

?

5.7精妙的尾數(shù)前移

【編程題】

整數(shù)n的尾數(shù)q（可為多位）移到n的前面所得的數(shù)為n的p倍，記為n(q, p)。這里正整數(shù)p不大于前移尾數(shù)q的首位。對于指定的尾數(shù)q與倍數(shù)p，求解n(q, p)。

?

設(shè)計(jì)要點(diǎn)：用數(shù)組存儲(chǔ)整數(shù)的各位數(shù)字，應(yīng)用模擬豎式除法計(jì)算。

?

?

5.8伯努利裝錯(cuò)信封問題

排列的定義：從n個(gè)不同元素中，任取m(m≤n,m與n均為自然數(shù),下同）個(gè)不同的元素按照一定的順序排成一列，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列；從n個(gè)不同元素中取出m(m≤n）個(gè)元素的所有排列的個(gè)數(shù)，叫做從n個(gè)不同元素中取出m個(gè)元素的排列數(shù)，用符號(hào)A(n,m)。

?

組合的定義：從n個(gè)不同元素中，任取m(m≤n）個(gè)元素并成一組，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)組合；從n個(gè)不同元素中取出m(m≤n）個(gè)元素的所有組合的個(gè)數(shù)，叫做從n個(gè)不同元素中取出m個(gè)元素的組合數(shù)。用符號(hào) C(n,m) 表示。

?

5.8.1實(shí)現(xiàn)排列組合

【編程題】

輸入正整數(shù)n，m，實(shí)現(xiàn)排列A(n,m)與組合C(n,m)，并輸出。

?

設(shè)計(jì)要點(diǎn)：應(yīng)用回溯法設(shè)計(jì)

?

5.8.2全錯(cuò)位排列

某人想邀請朋友來家中聚會(huì)，寫好了n封請柬，需要裝入n個(gè)信封，結(jié)果因?yàn)榇中陌颜埣砣垦b錯(cuò)了信封。請問：裝錯(cuò)的可能會(huì)有多少種呢？

?

設(shè)計(jì)要點(diǎn)，可以用枚舉法，或者用遞推數(shù)列法

?

5.9兩個(gè)“幽靈”e和π

e和π都是無限不循環(huán)小數(shù)，試超越數(shù)，在數(shù)學(xué)上稱為幽靈。

?

5.9.1自然對數(shù)的底e

【編程題】

試設(shè)計(jì)程序計(jì)算自然對數(shù)的底e，精確到小數(shù)點(diǎn)后指定的x位。

設(shè)計(jì)要點(diǎn)：選擇計(jì)算自然對數(shù)的底e的公式，確定計(jì)算項(xiàng)數(shù)，模擬豎式除法

?

5.9.2圓周率π

【編程題】

試設(shè)計(jì)程序計(jì)算圓周率π，精確到小數(shù)點(diǎn)后指定的x位。

?

【讀者體會(huì)】

這一章介紹了一些精巧求解例題。

編程設(shè)計(jì)要點(diǎn)。找到巧妙的求解公式。