算法设计与分析实用教程杨克昌 第2章 枚举

《算法设计与分析实用教程杨克昌 第2章 枚举》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学要求了解枚举算法的概念与枚举设计要领应用枚举求解统计求和、整数搜索、解方程与不等式、数式、数组、数列与数阵等基本案例本章重点对某些枚举算法进行改进与优化掌握枚举算法时间复杂度分析第2章枚举2.1枚举概述1.枚举的概念(1)枚举法（Enumerate）也称为列举法、穷举法，是蛮力策略的体现，又称为蛮力法。(2)枚举是一种简单而直接地解决问题的方法，其基本思想是逐一列举问题所涉及的所有情形。(3)应用枚举时应注意对问题所涉及的有限种情形进行一一列举，既不能重复，又不能遗漏。2.枚举的框架描述（1）区间枚举n=0;for(k=<区间下限>;k<=<区间上限>;

2、k++){<运算操作序列>;if(<约束条件>){printf(<满足要求的解>);n++;}}printf(<解的个数>);（2）递增枚举k=<枚举起点>while(1){k++;<运算操作序列>;if(<约束条件>){printf(<满足要求的解>);return;}}3.枚举的实施步骤（1）根据问题的具体情况确定枚举量（简单变量或数组）；（2）根据问题的具体实际确定枚举范围，设置枚举循环；（3）根据问题的具体要求确定筛选（约束）条件；（4）设计枚举程序并运行、调试，对运行结果进行分析与讨论。2.2统计与求和2.2.1同码小数s(d,n)=0.d+0.dd+

3、0.ddd+…+0.dd…dw(d,n)=0.d+2×0.dd+3×0.ddd+…+n×0.dd…d（两和式为n项之和，其中第k项小数点后有k个数字d，加权和第k项的权系数为k）依次输入整数d(1≤d≤9)，n(1≤n<10000)，计算并输出和s(d,n)与w(d,n)（四舍五入精确到小数点后6位）。求和的精度并不高，只要设置双精实变量s,w实施累加即可。设置j(1——n)循环枚举和式的每一项，设s的当前项为t，其后一项显然为t=t/10+0.1*d;加权和w的每一项在t的基础上乘加权系数j，即累加t*j。1.枚举设计要点2.枚举设计描述scanf("%d,%

4、d",&d,&n);t=s=w=0;for(j=1;j<=n;j++){t=t/10+0.1*d;s+=t;w+=t*j;//累加求和}printf("s(%d,%d)=%.6f",d,n,s);printf("w(%d,%d)=%.6f",d,n,w);对于给定的同码小数的和：s(d,n)=0.d+0.dd+0.ddd+…+0.dd…dw(d,n)=0.d+2×0.dd+3×0.ddd+…+n×0.dd…d输入正整数d(1≤d≤9)，n(1≤n<10000)，试精确求和s(d,n)与w(d,n)。同时统计：在s(d,n)与w(d,n)的n个小数位中，共

5、有多少个小数位s与w对应位的数字相同？3.问题引申（1）枚举设计要点设置一维数组s，s[j]表和的小数点后第j位，s[0]为和的整数部分；同理设置一维数组w，w[j]表加权和的小数点后第j位，w[0]为加权和的整数部分。1）对应位累加求和2）从后向前进位s[j-1]=s[j-1]+s[j]/10;s[j]=s[j]%10;3）按对应位比较s与w数字相同4）输出和s与w（2）枚举设计描述for(t=0,j=n;j>=1;j--)//对S，W分位求和{t=t+j;s[j]=(n+1-j)*d;w[j]=t*d;}for(j=n;j>=1;j--)//从后往前逐一进位

6、{s[j-1]=s[j-1]+s[j]/10;s[j]=s[j]%10;w[j-1]=w[j-1]+w[j]/10;w[j]=w[j]%10;}m=0;for(j=1;j<=n;j++)//比较s与w数字相同的位数if(s[j]==w[j])m++;2.2.2三角网格对指定正整数n，试求n-三角网格中所有不同三角形（大小不同或方位不同）的个数，以及所有这些三角形的面积之和。重点：（1）分“正立”与“倒立”两类分别统计求和（2）建立p数组简化求三角形面积之和的计算。难点:统计“倒立”三角形时，需对k分奇数与偶数两种情形分别总结规律并实施求和。2.3整数搜索2.3.

7、1整数对案例提出：设b是正整数a去掉一个数字后的正整数，对于给出的正整数n，寻求满足和式a+b=n的所有正整数对a,b。设计要点：（1）根据给出的n设置整数a的枚举循环，对每一个a,计算b=n-a。（2）设计条件循环，由赋值表达式d=a/(t*10)*t+a%t;生成a的各个去数字数。这些去数字数d逐个与b=n-a进行比较并决定取舍。2.3.2基于s的双和数组把一个偶数2s分解为6个互不相等的正整数a,b,c,d,e,f，然后把这6个正整数分成(a,b,c)与(d,e,f)两个三元组，若这两组数具有以下两个相等特性：则把数组(a,b,c)与(d,e,f)称为基于

8、s的双和数组(约定a