算法分析與設(shè)計(jì)

1、利用數(shù)組實(shí)現(xiàn)原始信息與處理結(jié)果的對(duì)應(yīng)存儲(chǔ)。編程統(tǒng)計(jì)身高(單位為厘米)。統(tǒng)計(jì)分150154； 155159； 160164； 165169； 170174； 175179及低于是150、高于是179共八檔次進(jìn)行?？紤]關(guān)系式身高/5-29與數(shù)組小標(biāo)的對(duì)應(yīng)關(guān)系#includeint main()int i,sg,a8;for(i=0;i179)a7=a7+1;else if (sg150)a0=a0+1;else asg/5-29=asg/5-29+1;scanf(%d,&sg);for (i=0;i=7;i=i+1)printf(%d field the number of people：%dn,

2、i+1,ai);return 0;二維趣味矩陣的應(yīng)用練習(xí)：編程打印形如下規(guī)律的n*n方陣。例如下圖：使左對(duì)角線和右對(duì)角線上的元素為0,它們上方 的元素為1,左方的元素為2,下方元素為3,右方元素為4,下圖是一個(gè)符合條件的階矩陣。 TOC o 1-5 h z 0111020104220 44主對(duì)角線元素i=j;副對(duì)角線元素：下標(biāo)下界為1時(shí)i+j=n+1,下標(biāo)下界為0時(shí)i+j=n-1；主上三角、元素：i =j；次上三角了元素：下標(biāo)下界為1時(shí)i +j=n+1,下標(biāo)下界為0時(shí)i+j=n+1,下標(biāo)下界為0時(shí)i+j=n-1；#includeint main()int ij,a100100,n;scanf(

3、%d,&n);fOr(i=1;i=n;i=i+1)for(j=1;j=n;j=j+1)if (i=j II i+j=n+1) a ij=0;if (i+jn+1 & ij) a ij=1;if (i+jj) a ij=2;if (i+jn+1 & ij) a ij=3;if (i+jn+1 & ij) a ij=4;for(i=1;i=n;i=i+1)printf(n);for( j=1j=n;j=j+1)printf(%4d,aij);printf(n);算法優(yōu)化技巧中算術(shù)運(yùn)算的妙用。練習(xí)開燈問題：有從1到n依次編號(hào)的n個(gè)同學(xué)和n盞燈。1號(hào)同學(xué)將所有的燈都關(guān)掉；2號(hào)同 學(xué)將編號(hào)為2的倍數(shù)的燈

4、都打開；3號(hào)同學(xué)則將編號(hào)為3的倍數(shù)的燈作相反處理(該號(hào)燈如 打開的，則關(guān)掉；如關(guān)閉的，則打開)以后的同學(xué)都將自己編號(hào)的倍數(shù)的燈，作相反處理。 問經(jīng)n個(gè)同學(xué)操作后，哪些燈是打開的？#includeint main() int n,a1000,i,k;printf(input a number:n);scanf(%d,&n);for( i=1;i=n;i+)ai=0;for( i=2;i=n;i+) k=1;while ( i*k=n) ai*k=1-ai*k;k=k+1;for( i=1;i=n;i+)printf( %4dn,ai);return 0;非數(shù)值問題的處理練習(xí)：警察局抓了 a，b，

5、c，d四名偷竊嫌疑犯，其中只有一人是小偷。審問中的描述如下：a說：“我不是小偷?！眀說：c是小偷?！眂說：“小偷肯定是d?！眃說：“c在冤枉人?！爆F(xiàn)在已經(jīng)知道四個(gè)人中三人說的是真話，一人說的是假話，問到底誰是小偷？提示：將以上信息數(shù)字化，用變量x存放小偷的編號(hào)，則x的取值范圍從1取到4,就假設(shè)了他們中的某人是小偷的所有情況。四個(gè)人所說的話就可以分別寫成：a說的話：x1b說的話：x=3c說的話：x=4d 說的話：x4 或 not(x=4) #include int main() int x;for(x=1;x1時(shí)，(a+b)n的中間各項(xiàng)系數(shù)是(a+b)n-i的相 應(yīng)兩項(xiàng)系數(shù)之和，如果把(a+b)

6、n的n+1的系數(shù)列為數(shù)組c，則除了 c(1)、c(n+1)恒為1夕卜，設(shè) (a+b)n的系數(shù)為c(i)，(a+b)n-1的系數(shù)設(shè)為c(i)。則有：c(i)=c，(i)+c，(i-1)而當(dāng)n=1時(shí)，只有兩個(gè)系數(shù)c(1)和c(2)(值都為1)。不難看出，對(duì)任何n, (a+b)n的二項(xiàng) 式系數(shù)可由(a+b)n-1的系數(shù)求得，直到n=1時(shí)，兩個(gè)系數(shù)有確定值，故可寫成遞歸子算法。#includevoid coeff(int a,int n);void coeff(int a,int n) int i;if(n=0) a1=1;else if (n=1) a1=1;a2=1;else coeff(a,n-

7、1);an+1=1;for (i=n;i=2;i-)ai=ai+ai-1;a1=1;int main()int a100=0,i,n;scanf(%d,&n);coeff(a,n);for(i=1;i=n+1;i=i+1)printf(%4d,ai);printf(n);return 0;分治算法的應(yīng)用練習(xí)3：求數(shù)列的最大子段和。給定n個(gè)整數(shù)(可能為負(fù)整數(shù))組成的序列a1,a2,.,an，求該序列連 續(xù)的子段，使其和為最大。如果該序列的所有元素都是負(fù)整數(shù)時(shí)定義其最大子段和為0。對(duì)于此問題可采用二分法逐步分解來完成。算法的設(shè)計(jì)思想如下：將所給的序列a1.n分為長(zhǎng)度相等的2段a1(n/2)和a(n

8、/2)+1n,分別求出這2段的最大子段和，則a1.n的最大子段和有3種情形。a1.n的最大子段和與a1.(n/2)的最大子段和相同；a1.n的最最大子段和與a(n/2)+1.n的最大子段和相同；a1.n的最大子段和為 ai:j,且 1WiW(n/2), (n/2)+1WjWn。情況1)和情況2)可分別遞歸求得。對(duì)于情況3) ,a(n/2)與a(n/2)+1一定在最大子段中，因此可以以伊2)為中心，分次求出i： (n/2), (n/2)+1： j兩子段的和，并相加返回。#include int maxSubSum(int a,int left,int right) int i,j,sum=0;i

9、f(left=right)/這是遞歸調(diào)用必須要有的終值情況。 sum=(aleft0?aleft:0); else int center=(left+right)/2;int leftSum=maxSubSum(a,left,center);/求出左序列最大子段和int rightSum=maxSubSum(a,center+1,right);/求出右序列最大子段和/求跨前后兩段的情況，從中間分別向兩端擴(kuò)展。從中間向左擴(kuò)展。這里注意，中 間往左的第一個(gè)必然包含在內(nèi)。int ls=0;int lefts=0;int tempi=center,tempj=center+1; for(i=cente

10、r;i=left;i-) lefts+=ai; if(leftsls) ls=lefts;int rs=0;int rights=0;fOr(j=+center;jrs) rs=rights;sum=ls+rs;/sum保存跨前后兩段情況的最大子段和求跨前后兩段的情況完成 if(sumleftSum)sum=leftSum;/記住，leftSum表示前段序列的最大子段和if(sum2算法可以用遞歸完成，下面是問題的遞歸算法。int main()int n, fn;printf(n=);scanf(%d”,&n);fn=f(n);int f(int x)if (x= 1 ) return(1);

11、if (x=2 ) return(2); elsereturn(f(x-1)+f(x-2);貪婪算法應(yīng)用練習(xí)2：?jiǎn)栴}描述：今天張麻子打算去約會(huì)。大家都知道張麻子是超級(jí)大帥哥，所以和他約會(huì)的MM也超 級(jí)多，她們每個(gè)人都和張麻子訂了一個(gè)約會(huì)時(shí)間。但是今天張麻子剛打算出門的時(shí)候才發(fā)現(xiàn)， 某幾個(gè)MM的約會(huì)時(shí)間有沖突。由于張麻子不會(huì)分身，還不能和多個(gè)MM同時(shí)約會(huì)，他只 能忍痛割愛拒絕掉某些MM。但是張麻子這個(gè)花心大蘿卜還是不死心，他想知道，他最多可 以和多少個(gè)MM約會(huì)。輸入：輸入的第一行包含一個(gè)正整數(shù)N(0N=1000)，表示和張麻子約會(huì)的MM數(shù)。接下去N 行，每行描述一個(gè)MM，格式為:Name sta

12、rttime endtime，表示在starttime,endtime)這個(gè)半開 區(qū)間是這個(gè)MM的約會(huì)時(shí)間，starttime endtime。名字由大寫或小寫字母組成，最長(zhǎng)不超 過15個(gè)字母，保證沒有兩個(gè)人擁有相同的名字，所有時(shí)間采用24小時(shí)制，格式為XX:XX， 且在06:00到23:00之間。輸出：輸出的第一行是一個(gè)整數(shù)M表示張麻子最多可以和多少個(gè)MM約會(huì)。接下來那一行就 是M個(gè)MM的名字，用空格隔開。您可以按照任意的順序輸出。如果存在多個(gè)答案，您可 以任選一個(gè)輸出。輸入示例：4Lucy 06:00 10:00Lily 10:00 17:00HanMeimei 16:00 21:00Ka

13、te 11:00 13:00輸出示例：3Lucy Kate HanMeimei算法分析：典型的任務(wù)選擇問題，可先按完成時(shí)間排序然后貪心選擇，即在可能的事件 a1a2an中選取在時(shí)間上不重疊的最長(zhǎng)序列。編程要點(diǎn)：1、誰結(jié)束時(shí)間早就選誰，因此要排序；2、進(jìn)行選擇時(shí)，還要考慮前一個(gè)被選人的結(jié)束時(shí)間與后一個(gè)開始時(shí)間是否有重疊。#include#include#include#includeusing namespace std;struct girlchar name20;int first,second; /約會(huì)的開始時(shí)間與結(jié)束時(shí)間;/此段函數(shù)即為sort函數(shù)對(duì)girl排序所用的排序規(guī)則，貪心算法為

14、盡可能多地選擇約會(huì)，因此要先對(duì)約會(huì)結(jié)束時(shí)間段按升序排列，/但有可能結(jié)束時(shí)間相等的，則考慮誰開始早誰排在前面，否則誰結(jié)束早誰排在前面。bool cmp(girl a,girl b)if(a.second=b.second)return a.firstb.first; return a.secondb.second;int main()int i, n,hour,min;char aa;girl gf1000;string str1000;scanf(%d,&n);for(i=0;in;i+)scanf(%s%d%c%d,&,&hour,&aa,&min); gfi.first=h

15、our*60+min;scanf(%d%c%d,&hour,&aa,&min); gfi.second=hour*60+min;sort(gf,gf+n,cmp); 對(duì)MM排序，sort為C+的函數(shù)，使用要包括頭文件 /要求sort使用cmp規(guī)則來對(duì)gf結(jié)構(gòu)體數(shù)組排序 str0=;int count=1;girl temp=gf0;for(i=1;i=temp.second) strcount+=;temp=gfi;coutcountendl;for(i=0;icount;i+) coutstri;return 0;動(dòng)態(tài)規(guī)劃算法求解數(shù)塔問題有形如圖4-1所示的一

16、個(gè)數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走， 一直走到底層，要求找出一條路徑，使路徑上的數(shù)值和最大。程序參考：#include main()int data5050;/存儲(chǔ)原始信息int decision5050;/存儲(chǔ)決策信息/*數(shù)組pathij存儲(chǔ)dataij選擇路徑，取值為0表示向左取值為1表示向右*/int path5050;int i,j,n; TOC o 1-5 h z /*輸入數(shù)塔有多少行*/printf(please input the number of rows:);scanf(%d,&n);/*輸入初始數(shù)據(jù)*/fOr(i=1;i=n;i+)for(j=1;j=

17、1;i=i-1)for(j=1;j=i;j=j+1)/* *左結(jié)合/* *左結(jié)合*/decisionij=decisioni+1j+decisionij;pathij=0;/* *右結(jié)合 */elsedecisionij=decisioni+1j+1+decisionij;pathij=1;/*動(dòng)態(tài)規(guī)劃過程結(jié)束decision11為最大值*/printf(max=%dn,decision11);/*根據(jù)pathij找出最優(yōu)解路徑*/j=1;for(i=1;i ,dataij);j=j+pathij;printf(%dn,datanj);10 .求兩個(gè)字符序列的最長(zhǎng)公共字符子序列。算法分析：設(shè)

18、A=a0, al,，am-1”，B=“b0, bl,，bn-1”，Z=z0,z1,.,zk-1”為它們的最長(zhǎng)公共子序列。有以下結(jié)論：1 ） 如 果 am-1=bn-1,貝zk-1=am-1=bn-1,且 “z0,z1,.,zk-2” 是 “a0,a1,.,am-2” 和 “b0,b1,.,bn-2 ”的一個(gè)最長(zhǎng)公共子序列；2）如果 am-1#bn-1，則若 zk-1#am-1，蘊(yùn)涵z0，z1， .， zk-1”是a0,a1,.,am-2”和 ”b0,b1,.,bn-1”的一個(gè)最長(zhǎng)公共子 序列；3） 如果 am-1bn-1，則若 zk-1bn-1，蘊(yùn)涵“z0，z1，.，zk-1”是“a0，a1，

19、.，am-1” 和“b0，b1，.，bn-2”的一個(gè)最長(zhǎng)公共子序列。定義cij為序列a0,a1,ai-2”和“b0,b1,bj-1 ”的最長(zhǎng)公共子序列的長(zhǎng)度，計(jì)算 cij 可遞歸地表述如下： cij=0如果 i=0 或 j=0；cij=ci-1j-1+1 如果 i,j0,且 ai-1=bj-1；cij=max(cij-1,ci-1j) 如果 i,j0,且 ai-1Nbj-1。參考程序：#include #include char a100,b100,str100;int c100100;int lcs_len(int i,int j)int t1,t2;if(i=0 | j=0) cij=0;elseif(ai-1=bj-1) cij=lcs_len(i-1J-1)+1;elset1=lcs_len(iJ-1); t2=lcs_len(i-1j); if(t1t2) cij=t1;else cij=t2;return cij;void build_lcs(int k, int i, int j