C基礎(chǔ)程序設(shè)計趣味題競賽題

1、2012 年程序設(shè)計競賽基礎(chǔ)實訓(xùn)詳解試 1 不等式對指定的正整數(shù)m ，試求滿足不等式11253321mnnm的正整數(shù)n。輸入正整數(shù)m （1m10000 ）, 輸出正整數(shù)n 所在的區(qū)間。例如 m=2 ，輸出正整數(shù)n 的區(qū)間為： 4,8 測試數(shù)據(jù)：（1） m=1000 （2） m=2012 程序設(shè)計：/ 解不等式， t1 #include #include void main() long c,d,i,m; double s; printf( 請輸入 m: );scanf(%ld,&m); i=0;s=0; while(sm) i=i+1;s=s+sqrt(i)/(2*i-1); c=i;

2、 while(sm+1) i=i+1;s=s+sqrt(i)/(2*i-1); d=i-1; printf(n 滿足不等式的正整數(shù)n 為: %ld,%ld n,c,d); 數(shù)據(jù)測試：請輸入 m: 1000 滿足不等式的正整數(shù)n 為: 999550,1001549 請輸入 m: 2012 滿足不等式的正整數(shù)n 為: 4047237,4051260 變通：如果和式中增加有規(guī)律的“- ”號，如何求解？實訓(xùn) 1：解不等式nm161514131211其中 m為從鍵盤輸入的正整數(shù)，式中符號為二個“+”號后一個“ - ”號，即分母能被3整除時為“ - ” 。輸入正整數(shù)m ，輸出滿足不等式的n。測試數(shù)據(jù)： (

3、1) m=4 (2) m=7 試 2 不定方程試求四元二次不定方程2222wzyx在指定區(qū)間 a,b的正整數(shù)解。輸入正整數(shù)a,b （1ab10000）, 輸出方程在該區(qū)間a,b內(nèi)的正整數(shù)解x，y，z，w（約定 axyzwb）的組數(shù)。例如輸入a,b: 1,10 ；求得方程在 1,10有 2 組解： 1,4,8,9，2,3,6,7，輸出： 2。測試數(shù)據(jù)：（1） 600,1000 （2） 1000,2012 求解要點：設(shè)指定區(qū)間為a,b，一般設(shè)置4 重循環(huán)在指定區(qū)間內(nèi)窮舉x、y、z、w（xyz） ，若滿足方程式則用n統(tǒng)計級數(shù)。程序設(shè)計：/ 求指定區(qū)間內(nèi)不定方程解的組數(shù) t21 #include #i

4、nclude void main() long a,b,n,x,y,z,w; printf( 請輸入?yún)^(qū)間 a,b的上下限 a,b: ); scanf(%ld,%ld,&a,&b); n=0; for(x=a;x=b-3;x+) for(y=x+1;y=b-2;y+) for(z=y+1;z=b-1;z+) for(w=z+1;w=b;w+) if(x*x+y*y+z*z=w*w) / 滿足不定方程式時統(tǒng)計 n+; if(n=0) printf( 方程在該區(qū)間內(nèi)沒有解。n); else printf( 方程在 %ld,%ld內(nèi)有 %ld 組解。 n,a,b,n); 優(yōu)化循環(huán)參數(shù)：

5、/ 求指定區(qū)間內(nèi)不定方程解的組數(shù) t22 #include #include void main() long a,b,n,x,y,z,w; printf( 請輸入?yún)^(qū)間 a,b的上下限 a,b: ); scanf(%ld,%ld,&a,&b); n=0; for(x=a;x=sqrt(b*b/3);x+) for(y=x+1;y=sqrt(b*b-x*x)/2);y+) for(z=y+1;z=sqrt(b*b-x*x-y*y);z+) for(w=z+1;w=b;w+) if(x*x+y*y+z*z=w*w) / 滿足不定方程式時統(tǒng)計 n+; if(n=0) printf(

6、方程在該區(qū)間內(nèi)沒有解。n); else printf( 方程在 %ld,%ld內(nèi)有 %ld 組解。 n,a,b,n); 數(shù)據(jù)測試：請輸入?yún)^(qū)間 a,b的上下限a,b: 500,1000 方程在 500,1000內(nèi)有 131 組解。請輸入?yún)^(qū)間 a,b的上下限a,b: 1000,2012 方程在 1000,2012內(nèi)有 617 組解。精簡循環(huán)設(shè)計：設(shè)指定區(qū)間為a,b，精簡 w循環(huán)，設(shè)置3 重循環(huán)在指定區(qū)間內(nèi)窮舉x，y，z（ xyb或 w不滿足方程，返回；否則用n 統(tǒng)計級數(shù)。/ 求指定區(qū)間內(nèi)不定方程解的組數(shù)t23 #include #include void main() long a,b,d,n,x

7、,y,z,w; printf( 請輸入?yún)^(qū)間 a,b的上下限 a,b: ); scanf(%ld,%ld,&a,&b); n=0; for(x=a;x=sqrt(b*b/3);x+) for(y=x+1;y=sqrt(b*b-x*x)/2);y+) for(z=y+1;zb) break; if(w*w=d) n+; / 滿足方程式時統(tǒng)計 if(n=0) printf( 區(qū)間內(nèi)沒有勾股數(shù)組。n); else printf( 方程在 %ld,%ld內(nèi)有 %ld 組解。 n,a,b,n); 變通：可把要求統(tǒng)計解數(shù)變?yōu)檩敵瞿承┙猓蜉敵瞿承┝?。實?xùn) 2：求最大值設(shè)指定區(qū)間 a,b內(nèi)的正

8、整數(shù)x,y,z,w滿足2222wzyx其中 a xyzwb，試求 s=x+y+z+w 的最大值。輸入正整數(shù)a,b （ 1ab10000） , 輸出 s 的最大值。測試數(shù)據(jù)：（1）a=500,b=1000 （2）a=1000,b=2012 試 3 喝汽水某學(xué)院的 m個學(xué)生參加南湖春游，休息時喝汽水。南湖商家的公告：（1）買 1 瓶汽水定價1.40 元，喝 1 瓶汽水（瓶不帶走）1 元。（2）為節(jié)約資源，規(guī)定3 個空瓶可換回1 瓶汽水，或20 個空瓶可換回7 瓶汽水。（3）為方面顧客，可先借后還。例如借1 瓶汽水，還3 個空瓶；或借7 瓶汽水，還20 個空瓶問 m個學(xué)生每人喝1 瓶汽水，至少需多少

9、元？輸入正整數(shù)m(2m10000)，輸出至少需多少元（精確到小數(shù)點后第2 位） 。測試數(shù)據(jù)：（1） 1111 （2） 2012 設(shè)計要點：建立 x=0,1,2,int(m/20)循環(huán) : 1） 把 m人分為 x 個大組，每組20 人。每組買13 瓶汽水（借7 瓶汽水），飲完后還20個空瓶（即相當(dāng)于換回7 瓶汽水還給商家） ，兩清。2） 剩下 t=m-x*20 人，分為 y=t/3個小組， 每組 3 人。每組買 2 瓶汽水 （借 1 瓶汽水），飲完后還3 個空瓶（即相當(dāng)于換回1 瓶汽水還給商家） ，兩清。3） 剩下 t=m-x*20-y*3人，每人花1 元喝 1 瓶。對每一個x，所求得最低費用(

10、13*x+2*y)*1.40+t與最小值變量mi 比較，求得最低費用。程序設(shè)計：/ 喝汽水 t31 #include void main() long m,t,x,y;double p,mi; printf( 請輸入 m ：); scanf(%ld,&m); p=1.40;mi=2*m; / 最小值 mi 賦初值for(x=0;x=m/20;x+) / 分 x 個大組，每組買13 瓶汽水，借7 瓶 t=m-20*x; / 剩下大組外的t 人y=t/3; / 剩下 t 人分 y 個小組，每組買2 瓶汽水，借1 瓶t=m-20*x-3*y; / 剩下大小組外的t 人，每人花1 元喝 1 瓶

11、if (13*x+2*y)*p+tmi) / 比較求最小值 mi=(13*x+2*y)*p+t; printf( 喝%ld 瓶汽水，需 %.2f 元。 n,m,mi); 數(shù)據(jù)測試：請輸入 m ： 1111 喝1111瓶汽水，需 1011.40 元。請輸入 m ： 2012 喝2012瓶汽水，需 1831.20 元。設(shè)計求解優(yōu)化：（1）大組人數(shù)為20 人，買 13 瓶汽水 （借 7 瓶汽水， 還 20 個空瓶），花費 13*1.40 元，人均 13*1.40/200.91 元。（2）小組人數(shù)為3 人，買 2 瓶汽水（借1 瓶汽水，還3 個空瓶） , 花費 2*1.40 元，人均 2*1.40/3

12、0.93333 元。（3）零散人數(shù)可能為1 或 2 人，每人喝1 瓶汽水（瓶不帶走） ，各花費1元注意到 0.910.9333331 ，顯然大組優(yōu)先小組，小組優(yōu)先零散。改進程序設(shè)計：/ 喝汽水 t32 #include void main() long m,x,y,z; printf( 請輸入 m ：); scanf(%ld,&m); x=m/20; / 分x個大組，每組買13瓶汽水，借 7瓶y=(m-20*x)/3; / 剩下人分 y個小組，每組買2瓶汽水，借 1瓶z=m-20*x-3*y; / 剩下零散 z人，每人花 1元喝 1瓶printf( 喝%ld瓶汽水，需 %.2f 元。

13、n,m,(x*13+y*2)*1.40+z); 試 4 交通網(wǎng)岳陽新城區(qū)的方格交通網(wǎng)如圖1所示， 其中金鶚山占據(jù)了交通網(wǎng)中(3,2)、 (4,2) 與(4,3)這三個交叉點尚未開通，另有從（2,3 ）至（ 2,4 ）與（ 6,4 ）至（ 7,4 ）的兩條打“”路段正在維護，禁止通行。試統(tǒng)計從始點(0,0) 到終點 (m,n) 的不同最短路線( 路線中各段只能從左至右、從下至上 )的條數(shù)。圖 1 交通網(wǎng)格示意圖輸入正整數(shù)m,n （7m=20,5n=20） ， 輸出從始點 (0,0) 到終點 (m,n) 的最短路線的條數(shù)。測試數(shù)據(jù)：（1） m=10,n=8 （2） m=20,n=12 設(shè)計要點：如

14、果沒有障礙的方格交通網(wǎng)，每一條路線共m+n段，其中橫向m段，縱向n 段，每一條不同路線對應(yīng)從m+n個元素中取m個元素（以放置橫向段）的組合數(shù)。因而不同路線條數(shù)為1111nmmnmmncmnm。今設(shè)置了諸多障礙，試應(yīng)用遞推求解。設(shè) f(x,y)(0 xm,0yn) 為從始點 (0,0) 到終點 (x,y)的不同最短路線的條數(shù)。（1） 遞推關(guān)系 f(x,y)=f(x-1,y)+f(x,y-1) （2） 邊界條件 f(x,0)=1 (0 x m) f(0,y)=1 (0y n) （3） 障礙處理城區(qū)的一座山所占據(jù)網(wǎng)中的(3,2)、 (4,2)、 (4,3)三個交叉點，可令f(3,2)= f(4,2)

15、= f(4,3)=0; 從（ 2,3 ）至（ 2,4 ）段禁止通行，則對f(2,4)的賦值只有f(1,4)，即 f24=f14; 同理 f74=f73; 程序設(shè)計：/ 帶障礙的交通路線問題t41 #include void main() int m,n,x,y,f5050; printf( 請輸入正整數(shù)m,n: ); scanf(%d,%d,&m,&n); for(x=1;x=m;x+) fx0=1; for(y=1;y=n;y+) f0y=1; / 確定邊界條件for(x=1;x=m;x+) for(y=1;y=n;y+) / 實施遞推得目標(biāo)值f(m,n) if(x=3 &a

16、mp; y=2 | x=4 & y=2 | x=4 & y=3) fxy=0; else if(x=2 & y=4) fxy=fx-1y; else if(x=7 & y=4) fxy=fxy-1; else fxy=fx-1y+fxy-1; printf( 不同最短路線條數(shù)為: %d n,fmn); 數(shù)據(jù)測試：請輸入正整數(shù)m,n: 10,8 不同最短路線條數(shù)為: 11008 請輸入正整數(shù)m,n: 20,12 不同最短路線條數(shù)為: 70679215 附無障礙交通路線問題程序/ 無障礙完整交通路線問題t42 #include void main() int k,m

17、,n,x,y,z,f5050; printf( 請輸入正整數(shù)m,n: ); scanf(%d,%d,&m,&n); for(x=1;x=m;x+) fx0=1; for(y=1;y=n;y+) f0y=1; / 確定邊界條件for(x=1;x=m;x+) for(y=1;y=n;y+) / 實施遞推得目標(biāo)值f(m,n) fxy=fx-1y+fxy-1; printf( 不同最短路線條數(shù)為: %d n,fmn); z=1; for(k=1;km且 bn 時，從 (0,0)點至中轉(zhuǎn)站 (a,b)這一段允許經(jīng)過終點(m,n) 點）交通網(wǎng)格示意圖輸入非負整數(shù)a,b,m,n ，輸出從始點

18、(0,0)經(jīng)中轉(zhuǎn)站 (a,b)到終點 (m,n) 的最短路線的條數(shù)。測試數(shù)據(jù)：（1）a=9,b=7,m=20,n=12 （2）a=20,b=12,m=9,n=7 試 5 三角網(wǎng)格把一個正三角形的三邊n 等分， 分別與各邊平行連接各分點，得 n- 三角網(wǎng)格。 例如 n=6時 6- 三角網(wǎng)格如圖2 所示。對指定正整數(shù)n，試求n-三角網(wǎng)格中不同三角形（大小不同或方位不同）的個數(shù)，以及所有這些三角形的面積之和（設(shè)網(wǎng)格中最小的單位三角形的面積為1） 。圖 2 6- 三角網(wǎng)格輸入整數(shù)n(1n120) ，輸出 n- 三角網(wǎng)格中不同三角形的個數(shù)，所有這些三角形的面積之和。測試數(shù)據(jù)：(1)25 (2)100 統(tǒng)

19、計求解要點：1) 設(shè) n- 三角網(wǎng)格中所含單位三角形數(shù)為p(n),顯然從最上層開始的第1 層為 1 個，第 2 層 3 個，, ，底層為2n-1 個。因而有p(n)=1+3+ , +(2n-1) 一般地，設(shè)k- 三角網(wǎng)格中所含單位三角形數(shù)為p(k),則p(k)=1+3+ , +(2k-1) （k=1,2,3, ， n）計算出 p(1),p(2),p(n) ，為后續(xù)計算面積和時使用。2） 統(tǒng)計三角形數(shù)與面積和時，設(shè)三角形的水平邊為底，頂角在上或在下把所有三角形分為“正立”與“倒立”兩類。設(shè)正立三角形的個數(shù)為s1, 其面積之和為ss1。正立三角形從大到小統(tǒng)計：邊為 n 的三角形1 個，其面積為p(

20、n) ；邊為 n-1 的三角形1+2 個，每個面積為p(n-1) ；,邊為 1 的三角形1+2+,+n個，每個面積為p(1) 。s1=1+(1+2)+(1+2+3)+,+(1+2+,+n) ss1=1*p(n)+(1+2)*p(n-1)+, +(1+2+ ,+n)*p(1) 3) 設(shè)倒立三角形的個數(shù)為s2, 其面積之和為ss2。倒立三角形從小到大統(tǒng)計：邊為 1 的三角形1+2+,+(n-1) 個，每個面積為p(1) ；邊為 2 的三角形1+2+,+(n-3) 個，每個面積為p(2) ；,當(dāng) n 為偶數(shù)時，邊為n/2 的三角形1 個，每個面積為p(n/2) ；s2=1+(1+2+3)+ ,+(1

21、+2+ ,+(n-1) ss2=1*p(n/2)+(1+2+3)*p(n/2-1)+,+(1+2+ ,+(n-1)*p(1) 當(dāng) n 為奇數(shù)時，邊為(n-1)/2的三角形1+2 個，每個面積為p(n-1)/2)；s2=(1+2)+(1+2+3+4)+,+(1+2+,+(n-1) ss2=(1+2)*p(n-1)/2)+(1+2+3+4)*p(n-1)/2)+, +(1+2+ ,+(n-1)*p(1) 4) 所求 n- 三角網(wǎng)格中不同三角形的個數(shù)為s1+s2，所有這些三角形的面積之和（即所含單位三角形的個數(shù)之和）為ss1+ss2 。程序設(shè)計：/ n-三角網(wǎng)格中的不同三角形個數(shù)及面積之和 t51

22、#include void main() int k,m,n,u,p1000; long t,t1,t2,s1,s2,ss1,ss2; printf( 請輸入正整數(shù)n: ); scanf(%d,&n); for(t=0,k=1;k=n;k+) t=t+(2*k-1);pk=t; t1=t2=s1=s2=ss1=ss2=0; for(k=1;k=n;k+) / 求正立三角形個數(shù)及其面積之和 t1=t1+k; s1=s1+t1;ss1=ss1+t1*pn+1-k; m=(n%2=0?1:2); for(k=m;k=n-1;k=k+2) / 求倒立三角形個數(shù)及其面積之和 t2=t2+(k-1

23、)+k;u=(n+1-k)/2; s2=s2+t2;ss2=ss2+t2*pu; printf( 三角網(wǎng)格中共有三角形個數(shù)為：%ld n,s1+s2); printf( 三角網(wǎng)格中所有三角形面積之和為：%ld n,ss1+ss2); 數(shù)據(jù)測試：請輸入正整數(shù)n: 25 三角網(wǎng)格中共有三角形個數(shù)為：4303 三角網(wǎng)格中所有三角形面積之和為：244153 請輸入正整數(shù)n: 100 三角網(wǎng)格中共有三角形個數(shù)為：256275 三角網(wǎng)格中所有三角形面積之和為: 201941895 點評：難點在于統(tǒng)計“倒立”三角形時，需對k 分奇數(shù)與偶數(shù)兩種情形分別總結(jié)規(guī)律。另外，求三角形面積之和時，p數(shù)組的建立大大簡化了

24、計算。試 6 雙碼二部數(shù)雙碼二部數(shù)定義：由兩個不同數(shù)碼組成，每個數(shù)碼多于1 位時相連而不分開的正整數(shù)稱為雙碼二部數(shù)。顯然，10 是最小雙碼二部數(shù)，3335 是一個 4 位雙碼二部數(shù),477 是一個 3位雙碼二部數(shù)；而333 只有一個數(shù)碼，4474 的數(shù)碼 4 呈分開狀態(tài)，都不是雙碼二部數(shù)。對指定的正整數(shù)n，探求出 n 位雙碼二部數(shù)從小到大排序的序列中第m項。依次輸入n,m（2n100） ， 輸出 n 位雙碼二部數(shù)序列的第m項。測試數(shù)據(jù)：（1）10,500 （2）30,2012 求解要點：設(shè)雙碼二部數(shù)為a,ab,b（1 a9，0b9） ，其高部數(shù)字a 有 la 位，低部數(shù)字b有 lb 位，顯然有

25、 la+lb=n (1la n-1) 為了確保從小到大枚舉雙碼二部數(shù)，要注意枚舉循環(huán)的先后次序：首先，高部數(shù)字a 須從小到大，范圍為1 9；當(dāng) a 確定后，高部位數(shù)la 簡單地從小到大或從大到小都不能確保雙碼二部數(shù)從小到大變化，需配合b分以下 3 步完成。為便于理解，以le=4,a=4的遞增進程實施標(biāo)注。(1) la增長（ 1 le-2 ）段， lb=le-la，b 遞增（ 0 a-1 ）取值。4000 4111 4222 4333 (la=1,lb=3,b:0 3) 4400 4411 4422 4433 (la=2,lb=2,b:0 3) (2) la與 lb 取定值段， la=le-1,

26、lb=1， b 遞增（ 0 9）取值（當(dāng)b=a 時跳過）。 4440 4441 4442 4443 4445 4446 4447 4448 4449 (la=3,lb=1,b:0 9, 其中 b=4 時跳過 ) (3) la減?。?le-2 1）段， lb=le-la，b 遞增（ a+1 9）取值。4455 4466 4477 4488 4499 (la=2,lb=2,b:5 9) 4555 4666 4777 4888 4999 (la=1,lb=3,b:5 9) 以上 3 步驟中每一步驟中都是遞增的，且3 個步驟銜接中沒有重復(fù)與遺漏，從而可確保 la 位的雙碼二部數(shù)從小到大遞增，沒有重復(fù)與

27、遺漏。程序代碼：/ 探求 n 位雙碼二部數(shù)從小到大排序的第m個 t61 #include #include void main() int a,b,a0,b0,i,n,m,la,lb,la0,lb0,s; printf( 請依次輸入整數(shù)n,m: ); scanf(%d,%d,&n,&m); s=0; for(a=1;a=9;a+) / 高部數(shù)字a 從小到大枚舉 for(la=1;la=n-2;la+) / 高部位數(shù)la 分 3 步驟枚舉 lb=n-la; for(b=0;b=a-1;b+) s+; / 變量 s 統(tǒng)計個數(shù) if(s=m) / 記錄第 m個數(shù)的信息 a0=a;b0

28、=b;la0=la;lb0=lb; la=n-1;lb=1; for(b=0;b=1;la-) lb=n-la; for(b=a+1;b=9;b+) s+; if(s=m) a0=a;b0=b;la0=la;lb0=lb; if(m=s) printf( %d位雙碼二部數(shù)從小到大第%d個數(shù)為： , n,m); for(i=1;i=la0;i+) printf(%d,a0); for(i=1;i=lb0;i+) printf(%d,b0); printf( n); else printf( %d位雙碼二部數(shù)的個數(shù)不到%d個。 n,n,m); 數(shù)據(jù)測試：請依次輸入整數(shù)n,m: 10,500 10位

29、雙碼二部數(shù)從小到大第500 個數(shù)為： 7766666666 請依次輸入整數(shù)n,m: 30,2012 30位雙碼二部數(shù)從小到大第2012 個數(shù)為： 888888888888888888888888000000 設(shè)計改進：/ 探求 n 位雙碼二部數(shù)從小到大排序的第m個 t62 #include #include void main() int a,b,a0,b0,i,n,m,la,la0,lb0,s; printf( 請依次輸入整數(shù)n,m: ); scanf(%d,%d,&n,&m); a=1;b=0;la=1; s=1; while(lan-1 | a9 | b8) if(b=9

30、) / 此時 b 不能增 1, 有以下 2 種選擇 if(la=1)a+; b=0; / a 增 1 后， b 從 0 開始 else la-; b=a+1; / a 段長增 1 后， b 從 a+1 開始 else if(b!=a-1) b+; / a與 la 不變， b 增 1 else if(la!=n-1)la+;b=0; / a段長增 1 后， b 從 0 開始 else if(b8) b+=2; / b增 2 跳過 a=b 情形 s+; if(s=m) a0=a;b0=b;la0=la;lb0=n-la; if(m=s) printf( %d位雙碼二部數(shù)從小到大第%d個數(shù)為： ,n

31、,m); for(i=1;i=la0;i+) printf(%d,a0); for(i=1;im ，且 n=d+1 為“ - ” ，可得 n=d 為一個解；而 n=d+2 時 1.0/(n+3)為“ +” ，可得 s(d+2)m; 以后各項中， “- ”項小于其前面的“+”項，可知對于nd+2 有 s(n)m 成立。因而有區(qū)間解：nd （2）在 nd 時是否有解， 逐個求和檢驗確定離散解。這一步不能省， 否則出現(xiàn)遺解。程序設(shè)計 1：/ 解不等式： m1+1/2-1/3+1/4+1/5-1/6+.+-1/n #include void main() long d,n,m,k; double s;

32、 printf(n 請輸入 m: ); scanf(%d,&m); n=-2;s=0; while(s=m) n=n+3;s=s+1.0/n+1.0/(n+1)-1.0/(n+2); d=n+1; s=0; / 可確定區(qū)間解nd（1） for(k=1;k0) s=s+1.0/k; else s=s-1.0/k; if(sm) printf( n=%ld, ,k); / 逐個得離散解 printf(n=%ld n,d); 程序運行示例：請輸入 m: 4 n=10151, n=10153, n=10154 請輸入 m: 7 n=82273511, n=82273513, n=8227351

33、4 注意：要特別注意，不要把離散解遺失。思考：如果把后一個離散解寫入?yún)^(qū)間解中？設(shè)計要點2：為敘述方便，記nns161514131211)(1) 通過循環(huán)累加， 當(dāng)加到 s=s+1.0/n+1.0/(n+1)-1.0/(n+2);得 s(n+2)m ， 令 d=n+1,可知： nd 為解；(2) 此時， s(n) 有可能大于m,因而在原s 基礎(chǔ)上 s-1.0/d+1.0/(d+1)得 s(n): 若 s(n)m, 合并得區(qū)間解：nd-1 ；若 s(n)m, 區(qū)間解為： nd； （因可肯定s(n-1)m, 得一個離散解：n d-3 ；若 s(n-2)m, 沒有離散解。程序設(shè)計 2：/ 解不等式：

34、m1+1/2-1/3+1/4+1/5-1/6+.+-1/n #include void main() long d,n,m; double s; printf(n 請輸入 m: ); scanf(%d,&m); n=-2;s=0; while(sm) printf( n=%ld n,d-1); / 輸出區(qū)間解 else printf( n=%ld n,d); s=s+1.0/(d-2)-1.0/(d-1); / 得 s(n-2) if(sm) printf( n=%ld n,d-3); / 輸出一個離散解 數(shù)據(jù)測試：請輸入 m: 4 n=10153 n=10151 請輸入 m: 7 n

35、=82273513 n=82273511 程序設(shè)計 3：請判斷以下程序是否正確？/ 解不等式： m1+1/2-1/3+1/4+1/5-1/6+.+-1/n #include void main() double n,m,s; printf(n 請輸入 m: ); scanf(%lf,&m); n=0;s=3.0/2; while(sm) printf( n=%.0fn,d); / 可確定區(qū)間解nd（2） else printf( n=%.0fn,d+1); / ? (1) 首先 s(d)m ，n=d 為一個解；而 s(d-3)=m ，n=d-2 為“ - ”項，其絕對值大于n=d-1

36、的“ +”項，可得s(d-1)m ；且知 nd 時無解。同時由03121111nnnn，可得 s(d+1)m 時, 以后的“ - ”項絕對值小于其前面的“+”項，故得區(qū)間解nd; 當(dāng) s(n+4)m ； 但不能確定s(n+6)0,因而不能確定n d+1 為區(qū)間解！2 求最大值設(shè)指定區(qū)間 a,b內(nèi)的正整數(shù)x,y,z,w滿足2222wzyx其中 a xyzwb，試求 s=x+y+z+w 的最大值。輸入正整數(shù)a,b （ 1ab10000） , 輸出 s 的最大值。測試數(shù)據(jù)：（3）a=500,b=1000 （4）a=1000,b=2012 設(shè)計要點：對每一組滿足條件的解，通過比較求得最大值。程序設(shè)計：

37、/ 求最大值#include #include void main() long a,b,d,s,x,y,z,w,max; printf( 請輸入?yún)^(qū)間 a,b的上下限 a,b: ); scanf(%ld,%ld,&a,&b); max=0; for(x=a;x=sqrt(b*b/3);x+) for(y=x+1;y=sqrt(b*b-x*x)/2);y+) for(z=y+1;zb) break; if(w*w=d) / 滿足條件時統(tǒng)計 s=x+y+z+w; if(smax) max=s; printf( s的最大值為：%ld n,max); 數(shù)據(jù)測試：請輸入?yún)^(qū)間 a,b的上下

38、限a,b: 500,1000 s的最大值為：2728 請輸入?yún)^(qū)間 a,b的上下限a,b: 1000,2012 s的最大值為：5496 3 帶中轉(zhuǎn)站的交通路線在某城區(qū)的完整方格交通網(wǎng)中，中轉(zhuǎn)站 (a,b)與終點 (m,n) 為交通網(wǎng)中的任意兩交叉點，這里 a,b,m,n為非負整數(shù)。試統(tǒng)計從始點(0,0) 經(jīng)中轉(zhuǎn)點（ a,b ）到終點 (m,n) 的不同最短路線( 路線中各段只能靠近目標(biāo)點而不能遠離目標(biāo)點) 的條數(shù)。（注：若am且 bn 時，從 (0,0)點至 (a,b) 點這一段允許經(jīng)過 (m,n) 點）交通網(wǎng)格示意圖輸入非負整數(shù)a,b,m,n ，輸出從始點(0,0)經(jīng)(a,b)到終點 (m,n

39、) 的最短路線的條數(shù)。測試數(shù)據(jù)：（3）a=9,b=7,m=20,n=12 （4）a=20,b=12,m=9,n=7 設(shè)計要點：如果路線中沒有設(shè)指定的必經(jīng)點，從始點(0,0) 到終點 (m,n) 每一條路線共m+n段，其中橫向 m段，縱向n 段，每一條不同路線對應(yīng)從m+n個元素中取m個元素（以放置橫向段）的組合數(shù)，不同路線條數(shù)為1111nmmnmmncmnm今設(shè)置了路線中的必經(jīng)點(a,b) ，須分以下兩步統(tǒng)計。設(shè)從始點(0,0)到交叉點 (a,b)的不同路線條數(shù)為y, 從交叉點 (a,b)到終點 (m,n) 的不同路線條數(shù)為z。據(jù)乘法原理，從始點(0,0) 經(jīng)(a,b)到終點 (m,n) 的最短

40、路線的條數(shù)為yz。為了求 y, 分以下兩種情形計算：1） 若 a=0 或 b=0，即必經(jīng)點與起點在橫向或縱向同線，y1。2） 若 a0 且 b0，即 a,b 為正整數(shù)時，y=abac。為了求 z, 分以下兩種情形計算：1） 若 m=a或 n=b，即必經(jīng)點與終點在橫向或縱向同線，z1。2） 若 m a 且 nb，必經(jīng)點與終點在橫向相差am，在縱向相差bn，z=ambnamc。程序設(shè)計：/ 帶中轉(zhuǎn)站的最短路線#include #include void main() double a,b,c,d,m,n,k,y,z; printf( 請輸入正整數(shù)a,b: ); scanf(%lf,%lf,&

41、;a,&b); printf( 請輸入正整數(shù)m,n: ); scanf(%lf,%lf,&m,&n); y=1; if(a*b0) for(k=1;k=a;k+) y=y*(b+k)/k; / 計算 c(a+b,a) z=1; if(m-a)*(n-b)!=0) c=fabs(m-a);d=fabs(n-b); for(k=1;k=c;k+) z=z*(d+k)/k; / 計算 c(|m-a|+|n-b|,|m-a|) printf( 不同最短路線條數(shù)為: %.0f n,y*z); 數(shù)據(jù)測試：請輸入正整數(shù)a,b: 9,7 請輸入正整數(shù)m,n: 20,12 不同最短路線條

42、數(shù)為: 49969920 請輸入正整數(shù)a,b: 20,12 請輸入正整數(shù)m,n: 9,7 不同最短路線條數(shù)為: 986263125120 附無障礙無中轉(zhuǎn)站的交通路線問題程序：/ 無障礙完整交通路線問題#include void main() int k,m,n,x,y,z,f5050; printf( 請輸入正整數(shù)m,n: ); scanf(%d,%d,&m,&n); for(x=1;x=m;x+) fx0=1; for(y=1;y=n;y+) f0y=1; / 確定邊界條件for(x=1;x=m;x+) for(y=1;y=n;y+) / 實施遞推得目標(biāo)值f(m,n) fxy

43、=fx-1y+fxy-1; printf( 不同最短路線條數(shù)為: %d n,fmn); z=1; for(k=1;k=m;k+) z=z*(n+k)/k; printf( 不同最短路線組合數(shù)為: %d n,z); 請輸入正整數(shù)m,n: 7,10 不同最短路線條數(shù)為: 19448 4 雙碼二部數(shù)序列試求雙碼二部數(shù)升序序列的第m項。測試數(shù)據(jù)： m=2012；m=20124 設(shè)計 1： 把雙碼二部數(shù)升序序列的第m項換算為n 位的第 m0項。注意到 2 位雙碼二部數(shù)共9*981 個； 3 位雙碼二部數(shù)共2*9*9 2*81 個；,/ 求雙碼二部數(shù)升序序列的第m項#include #include vo

44、id main() int a,b,a0,b0,i,n,m,m0,la,lb,la0,lb0,s; printf( 請依次輸入整數(shù)m: ); scanf(%d,&m); s=0;n=0; while(sm) n+;s=s+n*81; m0=m-(s-n*81);n+;s=0; / 換算為 n 位的第 m0項for(a=1;a=9;a+) / 高部數(shù)字a 從小到大枚舉 for(la=1;la=n-2;la+) / 高部位數(shù)la 分 3 步驟枚舉 lb=n-la; for(b=0;b=a-1;b+) s+; / 變量 s 統(tǒng)計個數(shù) if(s=m0) / 記錄第 m個數(shù)的信息 a0=a;b0

45、=b;la0=la;lb0=lb; la=n-1;lb=1; for(b=0;b=1;la-) lb=n-la; for(b=a+1;b=9;b+) s+; if(s=m0) a0=a;b0=b;la0=la;lb0=lb; printf( 雙碼二部數(shù)升序序列的第%d個數(shù)為： ,m); for(i=1;i=la0;i+) printf(%d,a0); for(i=1;i=lb0;i+) printf(%d,b0); printf( n); printf( （式中 %d個%d ，%d個%d)n, la0,a0,lb0,b0); 設(shè)計 2： 從 n=2 位開始統(tǒng)計/ 求雙碼二部數(shù)從小到大排列的第m

46、個數(shù)#include void main() int a,b,a0,b0,i,m,n,p,la,la0,lb0; printf( 請輸入整數(shù)m: ); scanf(%d,&m); n=1;p=0; while(1) n+;p+;a=1;b=0;la=1; / 默認 n 位第 1 個為 1 后 n-1 個 0 if(p=m) a0=a;b0=b;la0=la;lb0=n-la0;break; while(lan-1 | a9 | b8) p+; if(b=9) / 此時 b 不能增 1, 有以下 2 種選擇 if(la=1)a+; b=0; / a 增 1 后， b 從 0 開始 els

47、e la-; b=a+1; / a 段長增 1 后， b 從 a+1 開始 else if(b!=a-1) b+; / a與 la 不變， b 增 1 else if(la!=n-1)la+;b=0; / a段長增 1 后， b 從 0 開始 else if(b8) b+=2; / b增 2 跳過 a=b 情形 if(p=m) a0=a;b0=b;la0=la;lb0=n-la0;break; if(p=m) break; printf( 第%d個雙碼二部數(shù)為：%d(%d)%d(%d)n,m,a0,la0,b,lb0); printf( 其中從小到大第%d個數(shù)為： ,m); for(i=1;i

48、=la0;i+) printf(%d,a0); for(i=1;i=lb0;i+) printf(%d,b0); printf( n); 數(shù)據(jù)測試：請依次輸入整數(shù)m: 2012 雙碼二部數(shù)升序序列的第2012個數(shù)為： 55999999 （式中 2個 5，6個9) 請依次輸入整數(shù)m: 20124 雙碼二部數(shù)升序序列的第20124個數(shù)為： 88882222222222222222222 （式中 4個 8，19個 2) 5 求代數(shù)和設(shè) n 為正整數(shù)，求和nns/12/114/ 13/12/1143/12/1132/1121式中各項符號為二正一負，分母符號為一正一負。正整數(shù) n 從鍵盤輸入，輸出和s

49、四舍五入精確到小數(shù)點后5 位。輸入 n=100 輸出：輸入 n=2012 輸出：/ 求代數(shù)和1 #include #include void main() long j,n; double ts,s; printf( 請輸入 n: ); scanf(%d,&n); j=0;ts=0;s=0; while(jn) j=j+1; if(j%2=0) ts=ts-(double)1/j; / ts為各項的分母 else ts=ts+(double)1/j; if(j%3=0) s=s-sqrt(j)/ts; / 求代數(shù)和s else s=s+sqrt(j)/ts; printf( s=%.5

50、f n,s); / 求代數(shù)和2 #include #include void main() double j,n,ts,s; printf( 請輸入 n: ); scanf(%lfd,&n); j=0;ts=0;s=0; while(jn) j=j+1; if(fmod(j,2)=0) ts=ts-1/j; / ts為各項的分母 else ts=ts+1/j; if(fmod(j,3)=0) s=s-sqrt(j)/ts; / 求代數(shù)和s else s=s+sqrt(j)/ts; printf( s=%.5f n,s); 請輸入 n: 100 s=324.74013 請輸入 n: 20

51、11 s=28924.48725 請輸入 n: 2012 s=28989.22300 變通：設(shè) 2n2012, 當(dāng) n 為何值時，和s 最接近 2012？6 合數(shù)世紀(jì)探求1. 問題的提出20世紀(jì)的 100個年號 1901 2000 中有 13 個素數(shù)，而 21世紀(jì)的 100個年號 2001 ， 2100中有 14 個素數(shù)。那么，是否存在一個世紀(jì)的100 個年號中一個素數(shù)都沒有？定義一個世紀(jì)的100 個年號中不存在一個素數(shù)，即100 個年號全為合數(shù)的世紀(jì)稱為合數(shù)世紀(jì)。設(shè)計程序探索第m （約定 m100 ）個合數(shù)世紀(jì)。測試數(shù)據(jù)：(1) m=1 (2) m=10 2. 設(shè)計要點應(yīng)用窮舉搜索，設(shè)置a

52、世紀(jì)的的50 個奇數(shù)年號 ( 偶數(shù)年號無疑均為合數(shù)) 為 b，用 k 試商判別 b 是否為素數(shù)，用變量s 統(tǒng)計這 50 個奇數(shù)中的合數(shù)的個數(shù)。對于 a 世紀(jì)，若 s=50，即 50 個奇數(shù)都為合數(shù)，找到a 世紀(jì)為合數(shù)世紀(jì)，用n 統(tǒng)計合數(shù)世紀(jì)的個數(shù)。當(dāng)n=m時打印輸出a 世紀(jì)。當(dāng) n=m時退出循環(huán)結(jié)束。3. 合數(shù)世紀(jì)程序設(shè)計/ 探求第 1 個與第 m個合數(shù)世紀(jì)#include #include void main() long a,b,k; int m,n,s,x; printf( 請確定 m: ); scanf(%d,&m); a=1;n=0; while (1) a+;s=0; /

53、檢驗 a 世紀(jì) for(b=a*100-99;b=a*100-1;b+=2) / 窮舉 a 世紀(jì)奇數(shù)年號b x=0; for(k=3;k=sqrt(b);k+=2) if(b%k=0) x=1;break; if(x=0)break; / 當(dāng)前為非合數(shù)世紀(jì)時，跳出循環(huán)進行下一個世紀(jì)的探求 s=s+x; / 年號 b 為合數(shù)時， x=1，s 增 1 if(s=50) / s=50，即 50 個奇數(shù)均為合數(shù) n+; if(n=m) printf( 第%d個合數(shù)世紀(jì)為：%ld 世紀(jì)。 n,n,a); if(n=m) break; 4. 程序運行示例請確定 m: 10 第 1 個合數(shù)世紀(jì)為： 1671

54、9世紀(jì)。第 10 個合數(shù)世紀(jì)為： 58453 世紀(jì)。16719 世紀(jì)盡管是最早的合數(shù)世紀(jì)，它的100 個年號為 1671801 ，1671900 全為合數(shù)。這是一個非常漫長的年代，可謂天長地久，地老天荒！7 分解質(zhì)因數(shù)整數(shù)分解質(zhì)因數(shù)是最基本的分解。例如，90=2*3*3*5, 1960=23*5*72，前者為質(zhì)因數(shù)乘積形式，后者為質(zhì)因數(shù)的指數(shù)形式。把指定區(qū)間上的所有整數(shù)分解質(zhì)因數(shù),? 每一整數(shù)表示為質(zhì)因數(shù)從小到大順序的乘積形式。如果被分解的數(shù)本身是素數(shù)，則注明為素數(shù)。例如 , 92=2*2*23, 91(素數(shù) !) 。分解：1671861 5845271（1） 設(shè)計要點對每一個被分解的整數(shù)i

55、，賦值給 b(以保持判別運算過程中i 不變 ) ，用 k( 從 2 開始遞增取值 ) 試商 : 若不能整除，說明該數(shù)k 不是 b 的因數(shù)， k 增 1 后繼續(xù)試商。若能整除，說明該數(shù)k 是 b 的因數(shù)，打印輸出k* ；b 除以 k 的商賦給b(b=b/k)?后繼續(xù)用 k 試商 ( 注意，可能有多個k 因數(shù) ) ，直至不能整除，k 增 1 后繼續(xù)試商。按上述從小至大試商確定的因數(shù)顯然為質(zhì)因數(shù)。循環(huán)取值 k 的終值如何確定，一定程度上決定了程序的效率。終值定為i-1或 i/2 ，無效循環(huán)太多。循環(huán)終值定為i的平方根sqrt(i)可大大精簡試商次數(shù)，此時如果有大于sqrt(i)的因數(shù) ( 至多一個

56、!)?, 在試商循環(huán)結(jié)束后要注意補上，不要遺失。如果整個試商后b 的值沒有任何縮減，仍為原待分解數(shù)i ，說明 i 是素數(shù)， 作素數(shù)說明標(biāo)記。（2） 質(zhì)因數(shù)分解乘積形式程序設(shè)計/ 質(zhì)因數(shù)分解乘積形式#includemath.h #include void main() long int b,i,k,m,n,w=0; printf(m,n中整數(shù)分解質(zhì)因數(shù)（乘積形式）.n); printf(請輸入 m,n:); scanf(%ld,%ld,&m,&n); for(i=m;i=n;i+) / i為待分解的整數(shù) printf(%ld=,i); b=i;k=2; while(k1) pri

57、ntf(%ld*,k); continue; / k為質(zhì)因數(shù) , 返回再試 if(b=1) printf(%ldn,k); k+; if(b1 & b0，說明整數(shù) t 中含有數(shù)字 7。如果 g=0，說明整數(shù) t 中不含數(shù)字 4。對每一個 m位整數(shù)，據(jù) f0 & t%70, s1作相應(yīng)統(tǒng)計。據(jù) f0 & t%70 & g=0, s2 作相應(yīng)統(tǒng)計。（2）程序設(shè)計/ 統(tǒng)計含數(shù)字 7 且不能被 7 整除的 m位整數(shù)的個數(shù)s1，其中不含數(shù)字4的個數(shù) s2 #include void main() int c,f,g,i,j,m; long b,d,s1,s2,t; pri

58、ntf( 請輸入位數(shù) m (2=m=9): ); scanf(%d,&m); b=1; s1=0;s2=0; for(i=2;i=m;i+) b=b*10; / 計算 m位數(shù)的起點 for(t=b;t=10*b-1;t+) / 枚舉每一個 m位數(shù) d=t; f=0;g=0; for(j=1;j0 & t%70) s1+; / 統(tǒng)計含數(shù)字 7 且不能被 7 整除數(shù)的個數(shù)if(f0 & t%70 & g=0) s2+; / 統(tǒng)計其中不含數(shù)字4的個數(shù) printf( s1=%ld ,s2=%ld n,s1,s2); （3） 程序運行示例請輸入位數(shù) m (2=k=9):

59、 5 s1=32152 ,s2=20412 請輸入位數(shù) m (2=k=9): 6 s1=366522 ,s2=208300 變通 1：試統(tǒng)計含有數(shù)字7 且能被 7 整除的沒有重復(fù)數(shù)字的m位整數(shù)的個數(shù)s1，并指出其中最大的一個數(shù)。為了比較是否存在重復(fù)數(shù)字，設(shè)置f 數(shù)組， f3=2為 2個數(shù)字“ 3” 。#include void main() int c,e,g,i,j,m,f10; long b,d,s1,t; printf( 請輸入位數(shù) m (2=m=9): ); scanf(%d,&m); b=1; s1=0; for(i=2;i=m;i+) b=b*10; / 計算 m位數(shù)的起點

60、 for(t=b;t=10*b-1;t+) / 枚舉每一個 m位數(shù) d=t; for(j=0;j=9;j+) fj=0; / 數(shù)組清零 for(j=1;j=m;j+) c=d%10; d=d/10; fc+; / 統(tǒng)計數(shù)字 c 的個數(shù) for(g=0,j=0;j1) g=1; / 存在重復(fù)數(shù)字標(biāo)注g=1 if(f70 & t%7=0 & g=0) s1+; e=t; / 統(tǒng)計個數(shù) , 并把滿足條件的數(shù)賦值給 e printf( s1=%ld ,e=%d n,s1,e); 請輸入位數(shù) m (2=m=9): 5 s1=1978 ,e=98763 請輸入位數(shù) m (2=m3 ）位整數(shù)的個數(shù) s1，并指出其中從小到大排序的第n 個數(shù)。 #include void main() int c,e,i,j,m,n,f10; long b,d,s1,t; printf( 請輸入 m,n: ); scanf(%d,%d,&m,&n); b=1; s1=0; for(i=2;i=m;i+) b=b*10; / 計算 m位數(shù)的起點 for(t=b;t=10*b-1;t+) / 枚舉每一個 m位數(shù) d=t; for(j=0;j=9