算法分析与设计

1、利用数组实现原始信息与处理结果的对应存储。编程统计身高(单位为厘米)。统计分150154； 155159； 160164； 165169； 170174； 175179及低于是150、高于是179共八档次进行。考虑关系式身高/5-29与数组小标的对应关系#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;二维趣味矩阵的应用练习：编程打印形如下规律的n*n方阵。例如下图：使左对角线和右对角线上的元素为0,它们上方 的元素为1,左方的元素为2,下方元素为3,右方元素为4,下图是一个符合条件的阶矩阵。 TOC o 1-5 h z 0111020104220 44主对角线元素i=j;副对角线元素：下标下界为1时i+j=n+1,下标下界为0时i+j=n-1；主上三角、元素：i =j；次上三角了元素：下标下界为1时i +j=n+1,下标下界为0时i+j=n+1,下标下界为0时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);算法优化技巧中算术运算的妙用。练习开灯问题：有从1到n依次编号的n个同学和n盏灯。1号同学将所有的灯都关掉；2号同 学将编号为2的倍数的灯

4、都打开；3号同学则将编号为3的倍数的灯作相反处理(该号灯如 打开的，则关掉；如关闭的，则打开)以后的同学都将自己编号的倍数的灯，作相反处理。 问经n个同学操作后，哪些灯是打开的？#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;非数值问题的处理练习：警察局抓了 a，b，

5、c，d四名偷窃嫌疑犯，其中只有一人是小偷。审问中的描述如下：a说：“我不是小偷。”b说：c是小偷。”c说：“小偷肯定是d。”d说：“c在冤枉人。”现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？提示：将以上信息数字化，用变量x存放小偷的编号，则x的取值范围从1取到4,就假设了他们中的某人是小偷的所有情况。四个人所说的话就可以分别写成：a说的话：x1b说的话：x=3c说的话：x=4d 说的话：x4 或 not(x=4) #include int main() int x;for(x=1;x1时，(a+b)n的中间各项系数是(a+b)n-i的相 应两项系数之和，如果把(a+b)

6、n的n+1的系数列为数组c，则除了 c(1)、c(n+1)恒为1夕卜，设 (a+b)n的系数为c(i)，(a+b)n-1的系数设为c(i)。则有：c(i)=c，(i)+c，(i-1)而当n=1时，只有两个系数c(1)和c(2)(值都为1)。不难看出，对任何n, (a+b)n的二项 式系数可由(a+b)n-1的系数求得，直到n=1时，两个系数有确定值，故可写成递归子算法。#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;分治算法的应用练习3：求数列的最大子段和。给定n个整数(可能为负整数)组成的序列a1,a2,.,an，求该序列连 续的子段，使其和为最大。如果该序列的所有元素都是负整数时定义其最大子段和为0。对于此问题可采用二分法逐步分解来完成。算法的设计思想如下：将所给的序列a1.n分为长度相等的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)可分别递归求得。对于情况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)/这是递归调用必须要有的终值情况。 sum=(aleft0?aleft:0); else int center=(left+right)/2;int leftSum=maxSubSum(a,left,center);/求出左序列最大子段和int rightSum=maxSubSum(a,center+1,right);/求出右序列最大子段和/求跨前后两段的情况，从中间分别向两端扩展。从中间向左扩展。这里注意，中 间往左的第一个必然包含在内。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);贪婪算法应用练习2：问题描述：今天张麻子打算去约会。大家都知道张麻子是超级大帅哥，所以和他约会的MM也超 级多，她们每个人都和张麻子订了一个约会时间。但是今天张麻子刚打算出门的时候才发现， 某几个MM的约会时间有冲突。由于张麻子不会分身，还不能和多个MM同时约会，他只 能忍痛割爱拒绝掉某些MM。但是张麻子这个花心大萝卜还是不死心，他想知道，他最多可 以和多少个MM约会。输入：输入的第一行包含一个正整数N(0N=1000)，表示和张麻子约会的MM数。接下去N 行，每行描述一个MM，格式为:Name sta

12、rttime endtime，表示在starttime,endtime)这个半开 区间是这个MM的约会时间，starttime endtime。名字由大写或小写字母组成，最长不超 过15个字母，保证没有两个人拥有相同的名字，所有时间采用24小时制，格式为XX:XX， 且在06:00到23:00之间。输出：输出的第一行是一个整数M表示张麻子最多可以和多少个MM约会。接下来那一行就 是M个MM的名字，用空格隔开。您可以按照任意的顺序输出。如果存在多个答案，您可 以任选一个输出。输入示例：4Lucy 06:00 10:00Lily 10:00 17:00HanMeimei 16:00 21:00Ka

13、te 11:00 13:00输出示例：3Lucy Kate HanMeimei算法分析：典型的任务选择问题，可先按完成时间排序然后贪心选择，即在可能的事件 a1a2an中选取在时间上不重叠的最长序列。编程要点：1、谁结束时间早就选谁，因此要排序；2、进行选择时，还要考虑前一个被选人的结束时间与后一个开始时间是否有重叠。#include#include#include#includeusing namespace std;struct girlchar name20;int first,second; /约会的开始时间与结束时间;/此段函数即为sort函数对girl排序所用的排序规则，贪心算法为

14、尽可能多地选择约会，因此要先对约会结束时间段按升序排列，/但有可能结束时间相等的，则考虑谁开始早谁排在前面，否则谁结束早谁排在前面。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); 对MM排序，sort为C+的函数，使用要包括头文件 /要求sort使用cmp规则来对gf结构体数组排序 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;动态规划算法求解数塔问题有形如图4-1所示的一

16、个数塔，从顶部出发，在每一结点可以选择向左走或是向右走， 一直走到底层，要求找出一条路径，使路径上的数值和最大。程序参考：#include main()int data5050;/存储原始信息int decision5050;/存储决策信息/*数组pathij存储dataij选择路径，取值为0表示向左取值为1表示向右*/int path5050;int i,j,n; TOC o 1-5 h z /*输入数塔有多少行*/printf(please input the number of rows:);scanf(%d,&n);/*输入初始数据*/fOr(i=1;i=n;i+)for(j=1;j=

17、1;i=i-1)for(j=1;j=i;j=j+1)/* *左结合/* *左结合*/decisionij=decisioni+1j+decisionij;pathij=0;/* *右结合 */elsedecisionij=decisioni+1j+1+decisionij;pathij=1;/*动态规划过程结束decision11为最大值*/printf(max=%dn,decision11);/*根据pathij找出最优解路径*/j=1;for(i=1;i ,dataij);j=j+pathij;printf(%dn,datanj);10 .求两个字符序列的最长公共字符子序列。算法分析：设

18、A=a0, al,，am-1”，B=“b0, bl,，bn-1”，Z=z0,z1,.,zk-1”为它们的最长公共子序列。有以下结论：1 ） 如 果 am-1=bn-1,贝zk-1=am-1=bn-1,且 “z0,z1,.,zk-2” 是 “a0,a1,.,am-2” 和 “b0,b1,.,bn-2 ”的一个最长公共子序列；2）如果 am-1#bn-1，则若 zk-1#am-1，蕴涵z0，z1， .， zk-1”是a0,a1,.,am-2”和 ”b0,b1,.,bn-1”的一个最长公共子 序列；3） 如果 am-1bn-1，则若 zk-1bn-1，蕴涵“z0，z1，.，zk-1”是“a0，a1，

19、.，am-1” 和“b0，b1，.，bn-2”的一个最长公共子序列。定义cij为序列a0,a1,ai-2”和“b0,b1,bj-1 ”的最长公共子序列的长度，计算 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