《計算機常用算法與程序設(shè)計案例教程》習題解答

計算機常用算法與程序設(shè)計案例教程 習題解答提要 習題 1 1分數(shù)分解算法描述 把真分數(shù) a/1”的埃及分數(shù)之和： （ 1） 尋找并輸出小于 a/； （ 2） 若 c900000000，則退出； （ 3） 若 c 900000000，把差 a/c 整理為分數(shù) a/b，若 a/b 為埃及分數(shù)，則輸出后結(jié)束。 （ 4） 若 a/繼續(xù)（ 1）、（ 2）、（ 3）。 試描述以上算法。 解： 設(shè) )(這里 x)表示取正數(shù) ，注意到 1 )1( )1(11 db c=d+1，則 a,b) ) c=b/a)+1; if(c900000000) +); a=a*b=b*c; / a,選擇下一個 分母作準備 if(a=1) ); 1求出以下程序段所代表算法的時間復雜度 （ 1） m=0; k=1;k=1;m=m+j; 解：因 s=1+2+ +n=n(n+1)/2 時間復雜度為 O( （ 2） m=0; k=1;k=a*10099;b=2) x=0,k=1; +則 p(n)= =( ) i,j,n,a3030; 請確定方陣階數(shù) n: ); %d,&n); i=1;aij=j; / 方陣左部元素賦值 if(i+jn+1 & ij) aij=n+1 / 方陣下部元素賦值 if(i+jn+1 & i a,c,p,n; p=2011; c=1111;n=4; / 變量 c與 c!=0) / 循環(huán)模擬整數(shù) 豎式 除法 a=c*10+1; c=a%p; n=n+1; / 每試商一位 由 %d 個 1組成的整數(shù)能被 %d 整除。 n,n,p); 習題 2 2解不等式 設(shè) 不等式 2011/12/11 13/12/11 12/11 112010 n 解：上下限一般為鍵盤輸入的 a,b。 / 解不等式 : a # a,b,c,d,i; ts,s; 請輸入 a,b: ); %d,%d,&a,&b); i=0;s=0; s x; x=65; ) x=x+66; if(x%5=1 & x%7=4) 至少有兵 : %。 ,x); 2分解質(zhì)因數(shù) 對給定區(qū)間 m,n的正整數(shù)分解 質(zhì)因數(shù) , 每一整數(shù)表示為質(zhì)因數(shù)從小到大順序的乘積形式。如果被分解的數(shù)本身是素數(shù)，則注明為素數(shù)。 例如 , 2012=2*2*503, 2011=(素數(shù) !)。 解：對區(qū)間中的每一個整數(shù) i(b=i)，用 k(2 i)試商： 若不能整除，說明該數(shù) 后繼續(xù)試商。 若能整除，說明該數(shù) k 是 b 的因數(shù)，打印輸出 k*； b 除以 k 的商賦給 b(b=b/k) 后繼 續(xù)用 注意，可能有多個 ，直至不能整除， 后繼續(xù)試商。 按上述從小至大試商確定的因數(shù)顯然為質(zhì)因數(shù)。 如果有大于 n)的因數(shù) (至多一個 !) ,在試商循環(huán)結(jié)束后要注意補上，不要遺失。 如果整個試商后 b 的值沒有任何縮減，仍為原待分解數(shù) n，說明 n 是素數(shù)，作素數(shù)說明標記。 若 k是 格式輸出，然后 b=b/k。 若 后繼續(xù)。 若上述試商完成后 1 b,i,k,m,n,w=0; m,n中整數(shù)分解質(zhì)因數(shù)（乘積形式） .n); 請輸入 m,n:); %&m,&n); i=m; %,k); / 返回再試 if(b=1) %ldn,k); k+; if(b1 & b=1，即 (2 (2k+1)中至少有一個素數(shù)，實施“ +”； 否則，若 ak+ak+1=0，即 (2 (2k+1)中沒有素數(shù)，實施“ -”。 同時，設(shè)置最大值變量 小值變量 在循環(huán)中，每計算一個和值 s，與 較確定最大值，同時記錄此時的項數(shù) 時記錄此時的項數(shù) / 基 于素數(shù)的整數(shù)和 # t,j,n,k,k1,k2,a3000; s, 請輸入整數(shù) n: ); %d,&n); k=1;k=1) s+=(2*(2*k+1); / 實施代數(shù)和 2*(2*k+1); if(ss;k1=k; / 比 較求最大值 if(s1(k=0 9)，說明 回。 在不存在重復數(shù)字的情形下，檢測若 f0+f1+f4=0，說明 7 位平方數(shù) d 中沒有數(shù)字“ 0” ,“ 1” ,“ 4” ,印輸出。 / 組成沒有重復數(shù)字的 7位平方數(shù) # k,m,n,t,f10; a,b,c,d,w; n=0; b=356789);c=876532); a=b; m=w%10;fm+;w=w/10; t=0,k=1;t=1; / 測試三個平方數(shù)是否有重復數(shù)字 if(t=0 & f0+f1+f4=0) / 測試平方數(shù)中沒有數(shù)字 0,1,4 n+; %2d: ,n); % n,d,a); 共可組成 %位平方數(shù) .n,n); 2寫出例 2運行程序。 對稱方陣程序： # i,j,n,a3030; 請確定方陣階數(shù) n: ); %d,&n); i=1;aij=(n+1)/2; / 方陣左部元素賦值 if(i+j=n+1 & i=j) aij=; / 方陣下部元素賦值 if(i+jn+1 & i x,y,t,k,a,b,c,d,e,n=0; m6,f11; a=12;m1=a;m2=c;m3=e;m4=b;m5=d; x=0;x=y%10;fx=fx+1; y=(10; / 分離數(shù)字 t=0,x=1;x # a,b,k; s,x; a=1; 1) a+;s=0; / 檢驗 b=a*100區(qū)間 f+1,f+n中的 應用試商法求指定區(qū)間 c,d(約定起始數(shù) c=3， d=c+10000)上的所有素數(shù)。求出該區(qū)間內(nèi)的一個素數(shù) m，設(shè)前一個素數(shù)為 f, 判別： 若 n，則輸出結(jié)果 f+1,f+n后結(jié)束； 否則，作賦值 f=m，為求下一個素數(shù)作準備。 如果在區(qū)間 c,d中沒有滿足條件的解，則作賦值： c=d+2， d=c+10000，繼續(xù)試商下去，直到找出 所要求的解。 （ 2） 程序?qū)崿F(xiàn) / 求最小的連續(xù) # c,d,f,m,j; t,n; 求最小的 n); 請輸入 n:); %d,&n); c=3;d=c+10000; f=3; ) m=c; / 滿足條件即行輸出 最小的 %,n); % n,f+1,f+n); ; if(t=0) f=m; / 每求出一個素數(shù) f if(md) c=d+2;d=c+10000; / 每一輪試商后改變 c, 2和積 9數(shù)字三角形 求解和為給定的正整數(shù) s（ s 45）的 9個互不相等的正整數(shù)填入 9數(shù)字三角形，使三角 形三邊上的 4個數(shù)字之和相等（ 三邊上的 4個數(shù)字之積也相等（ 圖 2 數(shù)字三角形 （ 1）求解要點。 把和為 個正整數(shù)存 儲于 b(1)， b(9)中，分布如下圖所示。為避免重復，不妨約定三角形中數(shù)字“下小上大、左小右大”，即 b(1) # k,j,t,s,s1,s2,n,b10; 請輸入正整數(shù) s： ); %d,&s); n=0; b1=1;b1 k,n; b3000,s; 請輸入 n: ); %d,&n); b1=1;b2=2;s=3; k=3;k3*m( m(i)=3*m(1; 特別注意：兩隊列若出現(xiàn)相等時，給 排頭都要增 1。 *m(=3*m( m(i)=2*m(1; ; ; / 為避免重復項， （ 2） 程序設(shè)計 / 雙關(guān)系遞推 # n,p2,p3,i;s,m3000; m1=1;s=1; ; / 排頭 p2, 請輸入 n: ); %d,&n); i=2;i k,m,t,p2,p3, a,b,c,s,f100; 求數(shù)列的第 請輸入 m: ); %d,&m); f1=1; a=2;b=3;c=5;s=1; k=2;k k,n; t,s100; 請輸入冪指數(shù)和至多為 n:); %d,&n); t=1;s0=1; ; k=1;k t,k;g100; t:); %d,&t); g0=0; g1=3; / 確定初始條件 k=2;k i,j,c,d,h,v,m,n,s,a3030; m行 請確定 m,n: ); %d,%d,&m,&n); c=n; if(mi; / 一圈的右列從下至上遞增 s+; ahv=s; if(s=m*n) h=i; v=n+1-i;vi; / 一圈的上行從右至左遞增 s+; ahv=s; if(s=m*n) v=i; %n,m,n); i=1;i k; t1000; t10=1; / 確定初始條件 k=9;k=1; / 逆推計算 t(1) tk=2*(tk+1+1); 第 1 天摘桃 %n,t1); k=1;k d,k,m,n; t1000; 請確定正整數(shù) m,n,d: ); %d,%d,%d,&m,&n,&d); tn=d; / 確定初始條件 k=k=1; / 逆推計算 t(1) tk=2*(tk+1+m); 第 1 天摘桃 %n,t1); k=1;k k; s,f50; f1=1;f2=1; s=f1+f2; / 數(shù)組元素與和變量賦初值 k=3;k k; a,b,s; a=1;b=1;s=a+b; / 迭代變量 a,b, k=2; 設(shè)計求 n!的遞歸函數(shù)，調(diào)用該函數(shù)求 !1!21!111 解： 定義 n!的遞歸函數(shù) f(n),在求和的 k(1 n)循環(huán)中實施求和 s+=(k); 程序設(shè)計： #f(n) g; if(n=1) g=1; g=n*f( g); k,n; s=1; 請輸入 n: );%d,&n); k=1;k f(n) g; if(n=1 | n=2) g=1; g=f(f( g); k,n; s=0; 請輸入 n: );%d,&n); k=1;k b(n) g; if(n=1) g=1; if(n=2) g=2; g=3*b(2*b( g); k,n; s=0; 請輸入 n: );%d,&n); k=1;k a(n) g; if(n=1) g=1; if(n%2=0) g=a(n/2)+1; g=a(2)+a(n+1)/2); g); k,n; s=0; 請輸入 n: );%d,&n); k=1;k=2;ai=ai+a a1=1; # i,j,k,n,a100; 請輸入楊輝三角的行數(shù)： ); %d,&n); j=0;j # i,j,c,d,h,v,m,n,s,a3030; m行 請確定 m,n: ); %d,%d,&m,&n); c=n; if(m=i+1; s+;ahv=s; / if(s=m*n) i=d; / 賦值完成即行退出 h=m+1-i;h=i+1; s+;ahv=s; / if(s=m*n) i=d; %n,m,n); i=1;i m,n,a2020=0; h,v,b,s,d; 數(shù)陣為 m行 確定 m,n： ); %d,%d,&m,&n); s=m; if(mn) s=n; b=1;d=1; t(b,s,d); / 遞歸函數(shù)說明 t(b,s,d); / 調(diào)用遞歸函數(shù) %d % n,m,n); h=1;hm*n) j=1;jm*n) / 另一遞歸出口 t(b+1,d); / 調(diào)用內(nèi)一圈遞歸函數(shù) 4應用遞歸設(shè)計 實現(xiàn) 有 排列 。 解： 設(shè)置遞歸函數(shù) p(k)， 1 k m+n，元素 ak取值為 0或 1。 當 k=m+變量 0”的個數(shù)。若 h=用 后回溯返回，繼續(xù)。 當 k m,n,r,a30; s=0; p(k); n,m: ); %d,%d,&n,&m); %與 %的排列 :n,n,m); p(1); / 從第 1個數(shù)開始 n s=%n,s); / 輸出排列的個數(shù) / 排列遞歸函數(shù) #p(k) h,i,j; if(k g,i,k,u,t,a10; m1,m2,i=1;a1=1; 1) g=1; k=k=1;if(ai=ak) g=0; / 兩數(shù)相同 ,標記 g=0 if(i=9 & g=1 & a11 & a71) m1=a2*10+a3; m2=a5*10+a6; m3=a8*10+a9; t=0,u=2; / 往前回溯 if(ai=9 & i=1) ai+; / 至第 1個數(shù)為 9結(jié)束 5兩組均分 參加拔禾比賽的 12個同學的體重如下： 48， 43， 57， 64， 50， 52， 18， 34， 39， 56， 16， 61 為使比賽公平，要求參賽的兩組每組 6個人，且每組同學的體重之和相等。 請設(shè)計算法解決這 “兩組均分”問題。 （ 1） 求解要點 一般地，對已知的 2n(個整數(shù)，確定這些數(shù)能否分成 2個組，每組 每組數(shù)據(jù)的和相等。 我們可采用回溯法逐步實施調(diào)整。 對于已有的存儲在 求出總和 這 2顯然無法分組 )。把這 2每組 方便調(diào)整 , 設(shè)置數(shù)組 a(i):1 2n。 考察 b(1)所在的組 ,只 要另從 b(2) b(2n)中選取 數(shù)。即定下 a(1)=1, 其余的a(i)(i=2, ,n)在 2 2組合與順序無關(guān) ,不妨設(shè) 2 a(2) # n,m,aN,b2*N,i,j,t; s1,s=0; 把 2每組 n); t=)%1000;t); / 隨機數(shù)發(fā)生器初始化 n :); %d,&n); s=0,i=1;ai+; if(m0) 共有以上 %,m); 無法實現(xiàn)二堆均分 . ); 5指定低逐位整除數(shù)探求 試求出所有 最高位為 3的 24位低逐位整除數(shù)（除個位數(shù)字為“ 0”外 ,其余各位 數(shù)字 均不得為“ 0”）。 / 最高位為 3的 整除 # i,j,n,r,t,a100; s=0; 逐位整除 確定 n： ); %d,&n); 所求 %的右逐位整除數(shù)： n,n); j=1;j=1; / 檢測 i r=r*10+aj; r=r%i; if(r!=0) ai=ai+1;t=1; / 余數(shù) r!=0時 ai增 1,t=1 ai9 & i1) ai=1; / 回溯 ai=ai+1; t=0; / 余數(shù) r=0時 ,t=0 if(t=0 & i=n) if(an=3) s+; %,s); j=n;j=1;%d,aj); n); ai=ai+1; if(s0) 最高位為 3的 %,n,s); 未找到 ,n); 5枚舉求解 8項素數(shù)和環(huán)，與回溯結(jié)果進行比較。 (1) 設(shè)計要點 為簡化輸出，環(huán)序列簡化為一般序列輸出，為避免重復，約定首項為“ 1”。 環(huán)中的每一項為一個數(shù)字，相連的 8項構(gòu)成一個 8位數(shù)。因而設(shè)置 1”開頭的 8位數(shù) 812345678 18765432中 枚舉 。注意到所有 1 8沒有重復數(shù)字的 8位數(shù)的數(shù)字和為 9 的倍數(shù)，該數(shù)也為 9的倍數(shù)，為此， 枚舉 循環(huán)步長可取 9，以精簡 枚舉 次數(shù)。 為操作與判斷方便，設(shè)置 3個數(shù)組： 位數(shù) f3=2，即 個數(shù)字“ 3”。 位數(shù) g4=6，即 位數(shù)為數(shù)字“ 6”。 b13=1，標識“ 1”表示 13為素數(shù)，標識“ 0”為非素數(shù)。 枚舉 實施： 1） 注意到 8項中每相鄰兩項之和不超過 15,對 15以內(nèi)的 5個素數(shù)用 1” ,其余均為“ 0”。 2） 在 8位數(shù)的 a 循環(huán)中，對 次求余分離出各個數(shù)字 x，應用 fx+統(tǒng)計數(shù)字用 g9數(shù)字。 3） 設(shè)置 k(1 8)判斷循環(huán)： 若 fk!=1 ，表明數(shù)字 回。 若 bgk+gk+1!=1，表明相鄰的第 k+1項之和不是素數(shù)，返回。順便說明，為判斷方便，首項“ 1”先行賦值給 g9，以與 g8相鄰，在 4） 通過以上判斷篩選的 a，其各個數(shù)字即為所求的 8項素數(shù)環(huán)的各項，打印輸出。 (2) 枚舉 實現(xiàn) 8項素數(shù)和環(huán) / 8項素數(shù)和環(huán) 枚舉 求解 # t,k,s,x,g10,f10,b18;a,y; k=1;k #n,a2000,b1000;s=0; t,j,k; p(k); 前 輸入整數(shù) n: ); %d,&n); k=1;k p(k) i,j,u; if(k d,i,j,s,t,u,v,a20,b300; s=31;s=28; s=%2d： n,s); v=0; / a0=0;a1=1;a6=s; a2=a1+1;a20) 5 枚舉 探索 4階 德布魯金 環(huán)， 并 與 德布魯金 環(huán)的回溯程序運行結(jié)果進行比較。 求解由 16個 0或 1組成的環(huán)序列，形成的由每相連 4個數(shù)字組成的 16個二進制數(shù)恰好在環(huán)中都出現(xiàn)一次。 (1) 枚舉 設(shè)計要點 約定序列由 0000開頭，第 5個數(shù)字與第 16個數(shù)字顯然都為 1(否則會出現(xiàn) 00000)。余下10個數(shù)字應用 枚舉 探求。 設(shè)置一維 約定 0000開頭，即 a(0) a(3)均為 0； a(4)=1,a(15)=1。其余 10個數(shù)字 a(5) a(14)通過 枚舉 探求。因為是環(huán)序列， a(16) a(18)即為開頭的 0。 分析 10個數(shù)字 0、 1組成的二進制數(shù)，高位最多 2個 0（否則出現(xiàn) 0001或 0000重復），即循環(huán)的初值可定為 7。同時，高位不會超過 4個 1（否則出現(xiàn) 11111超界），即循環(huán)的終值可定為 9+28+27+26。 對區(qū)間 n1,的每一個整數(shù) n(為不影響循環(huán)，賦值給 b)，通過除以 2取余轉(zhuǎn)化為 10個二進制數(shù)碼。用變量 的個數(shù)，若 i 6返回，確保 16 個數(shù) 字中有 8個 1時轉(zhuǎn)入下面的檢驗：計算 m1,驗 a(0) a(18)中每 4個相連數(shù)字組成的二進制數(shù)若有相同，顯然不能滿足題意要求，標記 t=1退出。若所有由 4個相連數(shù)字組成的 16個二進制數(shù)沒有相同的，滿足 德布魯金 環(huán)序列條件，作打印輸出。 （ 2） 4階 德布魯金 環(huán)序列 枚舉 實現(xiàn) # b,m,m1,m2,n,n1,n2,i,j,k,t,a20; m=0; 28; 12+256+128+64; / 確定 枚舉 范圍 n=n1;n=5; / 正整數(shù) n(即 b)轉(zhuǎn)化為二進制數(shù) ak=b%2; b=b/2; i+=ak; if(i!=6) / 確保 8個 1轉(zhuǎn)入以下 檢驗 t=0,k=0;k i,j,n,m,a100; s=0; n (ai+; n 總數(shù)為 :%n,s); / 輸出 C(n,m)的值 5 回溯實現(xiàn)復雜排列 應用回溯法探索 從 同元素中 取 m（約定 1 m n） 個 元素與另外 （ 1）算法設(shè)計要點 引入變量 的個數(shù)， 當 k ai=0，元素需從 0開始取 值；否則， 0的個數(shù)已達 ai=1，即從 1開始取值。這樣處理， 使 0的個數(shù)不超過 少一些無效操作，提高了回溯效率 。 按以上所描述的回溯的參量： n,m(m n) 元素初值： a1=0，數(shù)組元素取初值 0。 取值點：當 k ai=0，需從 0開始取值；否則， ai=1，即從 1開始取值。 回溯點： ai=n，各元素取值至 約束條件 1： ak!=0 & ai=ak | ai*ak 0 & ai-ak)=(其中 i k)，排除同 一列或同對角線上出現(xiàn) 2個皇后。 約束條件 2： i=n & h=& b111, 當取值達 n 個，其中 零，且棋盤全控時輸出一個解。 （ 2）復雜 排列 回溯優(yōu)化設(shè)計 # 30 i,j,h,k,n,m,t,aN; s=0; n (if(ai=0) / 改變?nèi)≈禐?0的元素值前先把 0的個數(shù) ai+; n s=%ldn,s); 58對夫婦特殊的拍照 一對夫婦邀請了 7對夫婦朋友來家餐聚，東道主夫婦編為 0號，其他各對按先后分別編為 1， 2， 7號。 餐聚后拍照，攝影師要求這 8對夫婦男左女右站在一排，東道主夫婦相鄰排位 在 橫排的正中央，其他各對排位， 1號夫婦中間安排 1個人 ,2號夫婦中間安排 2個人 ,依此類推。 共有多少種拍照排隊方式？ 1. 設(shè)計要點 在 個相同元素（相當于 ， 取到 2 數(shù)為 0的為 0號 （即東道主） ，余數(shù)為 1的為 1號，余數(shù)為 例如， n=4，數(shù)組元素為 0與 4，對 4同余，為一對“ 0”； 1與 5對 4同余，為一對“ 1”； 一般地， +同余，為一對 i,(i=0,1,2,3)。 返回條件修改為（當 ja(i) or a(j)+1!=其中 a(j)=a(i)，為使 a(j)%n=a(i)%n a(j)a(i)，避免同一對取余相同的數(shù)左邊大于右邊，導致重復； a(j)%n=a(i)%n a(j)+1!=免同一對數(shù)位置相差不滿足題意相間要求。 例如， a(j)=0時，此時 a(i)=n，為 0號情侶，位置應相差 1（即中間 沒有 人），即 。 a(j)=1時，此時 a(i)=n+1，為 1號情 侶，位置應相差 2（即中間有 1人），即 。 這些都應滿足條件 a(j)+1=果 a(j)+1!=滿足要求，返回。 設(shè) m=2n， 若滿足條件 (g0 i=m a(1)%n # i,j,g,n,m,s,a20; n (2ai | aj+1!= g=0; / 出現(xiàn)相同元素或同余小在后時返回 if(g & i=m & a1%ai+; n 共有解 s=%n,s); 習題 6 6 設(shè)矩陣 A為 p行 陣 B為 q行 矩陣乘積 試求 n（ n2） 個矩陣 ),2,1( 的乘積21的最少乘法次數(shù)。其中 數(shù)1, ii 解： 注意1是1樣才能確保 多個矩陣相乘，滿足乘運算結(jié)合律。 例如，求321 求前兩個矩陣的乘積321 )( 是先求后兩個的乘積 )(321 是可以的，但兩者的乘法次數(shù)不一定相等，我們要求最少乘法次數(shù)。 設(shè) m(i,j)是求乘積12的最少乘法次數(shù)，則有遞推關(guān)系 )2()1()()1,( (i+1=j) )1()1()(),1(),(m ),( (i k j,i d,n,i,j,k,t,r100,m100100; 請輸入矩陣的個數(shù) n :); %d,&n); 請輸入第 1個矩陣的行數(shù) :); %d,&r1); i=1;iairi aij=aj+dj; aij=airi %d,anm); 所求左上角頂點到右下角頂點的最大路程即最優(yōu)值為 a(n,m)。 6求解 邊數(shù)值 三角形 的最短路徑 已知邊數(shù)值三角形每兩點間距離如圖 7一個點可向左或向右兩個去向，求三角形頂點到底邊的最短路徑。 圖 7角形 邊數(shù)值數(shù)據(jù) 1) 算法設(shè)計 設(shè)邊數(shù)值三角形為 不包含作為邊終止點的三角形底邊 )，每點為 (i， j)， i=1,2,，n； j=1,2,， i,j)向左的邊長記為 l(i,j)，點 (i,j)向右的邊長記為 r(i,j)。記a(i,j)為點（ i,j） 到底邊的最短路程。顯然 a(i,j)=a(i+1,j)+l(i,j),a(i+1,j+1)+r(i,j) st(i,j)= l , r 應用逆推求解，所求的頂點 a(1,1). 2) 邊數(shù)值三角形最短路徑搜索 # n,i,j,t,s; a5050,l5050,r5050;050; t=%1000;t); / 隨機數(shù)發(fā)生器初始化 請輸入數(shù)字三角形的行數(shù) n:); %d,&n); i=1;i=1; / 逆推求取最短路徑 j=1;說明前面為 b(i,j)賦值不對 ,作修改 : b(i,j)=yb+ b(i+1,j),則 i,j)=D,否則 i,j)=R 這樣反推所得 b(1,1)即為所求的最小路徑數(shù)字和。 為了打印最小路徑 ,利用 先打印 a(1,1),i=1,j=1. 若 i,j)=R 則 ,即 j=j+1,然后打印 右邊整數(shù) a(i,j); 若 i,j)=D 則 ,即 i=i+1,然后打印 下面整數(shù) a(i,j); 若 i,j)=O 則 i,j 均增 1,即 i=i+1,j=j+1,然后打印 斜向右下整數(shù)a(i,j); 依此類推 ,直至打印到終點 a(n,m)。 6西瓜分堆 已知的 把這堆西瓜分成兩堆，每堆的個數(shù)不一定相等，使兩堆西瓜重量之差為最小。 (1） 設(shè)計要點 兩組數(shù)據(jù)之和不一定相等，不妨把較少的一堆稱為第 1堆。設(shè) b(i)之和為 s，則第 1堆數(shù)據(jù)之和 s/2，這里 x為 問題要求在滿足 s/2前提下求 大值 樣兩堆數(shù)據(jù)和之差的最小值為 為了求 用動態(tài)規(guī)劃設(shè)計，按分每一個瓜為一個階段，共分為 一個階段都面臨兩個決策：選與不選該瓜到第 1組。 1） 建 立遞推關(guān)系 設(shè) m(i,j)為 第 1堆距離 s/2還差重量 為 j， 可取 瓜編號 范圍為 ： i,i+1, ,。則 當 0 j=1; / 逆推計算 m(i,j) j=0;j=b(i) & m(i+1,j)m(i+1, （其中 i=1,2, n1） 第 1堆分 b(i); 不分 b(i); if(m(1,sb=b(n) 則第 1堆分 b(n)。 （ 2）求解 兩組數(shù)據(jù)和之差的最小值 程序設(shè)計 / 求解 兩組數(shù)據(jù)和之差的最小值 # 40 n,c1,i,j,s,t,cb,sb,bN,mN10*N; n: ); %d,&n); s=0; i=1;i=1; / 逆推計算 m(i,j) j=0;j=bi & mi+1jmi+1 bi;bi; %3d,bi); bi=0; / b(i)分后賦 0,為輸出第 2堆作準備 if(m1bn) %3d,bn); bn; bn=0; (%d)n, 第 2堆 : ); ,i=1;bi; %3d,bi); (%d)n, 6 應用遞推實現(xiàn)動態(tài)規(guī)劃求解 序列的 最小子段和 應用遞推實現(xiàn)動態(tài)規(guī)劃求解：給定 能為負整數(shù)）組成的序列12, , , na a a，求該序列形如 段和的最小值。 遞推實現(xiàn)動態(tài)規(guī)劃求解： 1） 動態(tài)規(guī)劃算法設(shè)計 設(shè) qj為序列前 )1(m 1 j 由 qj的定義 ,得 qj的遞推關(guān)系 : )1(01 011 初始條件： Q0=0 (沒有項時，其值自然為 0)。 （ 2） 動態(tài)規(guī)劃程序?qū)崿F(xiàn) / 動態(tài)規(guī)劃求最小子段和 # i,j,k,t,n,s,q1000,a1000; t=)%1000;t); / 隨機數(shù)發(fā)生器初始化 序列中 請確定 n:); %d,&n); 序列的 %n ,n); i=1;i=0) qj=aj