计算机常用算法------第二章 枚举
（1）枚举概述
枚举法也称为列举法、穷举法，使蛮力策略的具体表现，又称为蛮力法。
枚举是一种简单而直接解决问题的方法.
（2）枚举的基本思想是：
逐一列举问题所涉及的所有清醒，并根据问题提出条件的条件检验哪些是问题的解，那些应予以排除。
枚举法常用于解决“是否存在”或“有多少种可能”等问题。
（3）枚举的特点是
算法设计比较简单，只要一一列举问题所涉及的所以情形即可。
（4）枚举模式
实施枚举通常是应用循环结构来实现
有两种：
1.区间枚举
区间枚举:通过枚举循环的上下限控制枚举区间，而在循环体中完成各个运算操作，然后根据所求解的具体条件，应用选择结构实施判别与筛选，求得所要求的解。
区间枚举设计的框架描述：
框架描述：
n = 0;
for(k = <区间下限>;k<=<区间上限>;k++){ //根据实际情况控制枚举范围
<运算操作序列>;
if(<约束条件>){ //根据约束条件实施筛选
printf(<满足要求的解>); //逐一输出问题的解
n++; //统计解的个数
}
}
printf(<解的个数>); //输出解的个数
**2.递增枚举：**
有些问题没有明确的范围限制，可根据问题的具体情况试探地从某一起点开始增值枚举，对每一个数进行操作与判别，若满足条件即输出结果
递增枚举设计的框架描述：
k = 0;
while(1){
k++; //设置循环，枚举变量k递增；
<运算操作序列>;
if(<约束条件>){ //根据约束条件实施筛选与结束
printf(<满足要求的解>); //输出问题的解
return ; //返回结束
}
}
枚举实施步骤：
（1）根据问题的具体情况确定枚举量（简单变量或数组）
（2）根据问题的具体情况确定枚举范围，设置枚举循环
（3）根据问题的具体要求确定筛选条件
（4）设计枚举并运行、调试，对运行结果进行分析与讨论。
（5）统计与求和
全素组
···素数又称为质数，是不能被1以外的其他整数整除的整数。如2，3，5，7 2也是偶素数
···合数又称为复数，一个整数如果能被除1与本身以外的整数整除。
···注意：1既不是质数也不是偶数
例题：例如输入n=15，输出 3+5+11=19为素数 则 3 5 11称为一个基于15的全素组
//统计求和 应用试商判别素数
#include<stdio.h>
#include<math.h>
int main(){
int i,j,k,i2,j2,k2,n,s,t,w,z,max,p[9000],q[1500];
long m;
printf("请输入一个整数n：");
scanf("%d",&n);
for(int i= 0;i<= 3*n;i = i+2){
t = 1;
z = (int)sqrt(i);
for(int j = 3;j<= z;j++){
if(i%j==0){
t = 0;
break;
}
if(t == 1){ //奇数i为素数时标记p[i]=1
p[i] = 1;
}
w = 0;
for(int i = 3;i<= n;i=i+2){
if(p[i] == 1){
w++;
q[w] = i; //共有w个不大于n的奇素数赋给q数组
}
}
}
}
m = 0;
max = 0;
for(int i = 1;i<= w-2;i++) //设置三重循环枚举所有三个素数数组
for(int j = i+1;j<= w-1;k++)
for(int k = j+1;k<=w;k++){
s = q[i]+q[j]+q[k]; //统计三个元素之和
if(p[s] == 1){
m++;
if(s>max){ //比较并记录最大全素组
max = s;
i2 = q[i];
k2 = q[k];
}
}
}
printf("共有%ld个素组
",m);
if(m>0)
printf("一个最大全素组为:%d+%d+%d=%ld
",i2,j2,k2,max);
}
最简真分数（分子小于分母，且分子分母无公因数）
#include<stdio.h>
#include<math.h>
int main(){
int a,b,i,j,t,u;
long m = 0;
double s;
printf("最简真分母在[a,b]内，请确定a、b:");
scanf("%d,%d",&a,&b);//输入区间上下限
s = 0;
for(int j = a;j<= b;j++) //枚举分母
for(int i = 1;i<= j-1;i++){ //枚举分子
for(t = 0,u = 2;u<= i;u++){ //枚举因数
if(j%u == 0 && i%u == 0){
t = 1;
break; //分子分母有公因数，舍去
}
if(t == 0)
{
m++;//统计最简真分数个数
s+=(double)i/j; //求最简真分数的和
}
}
}
printf("最简真分数共m=%ld个。
",m);
printf("其和s=%.5f
",s);
}
（6）解方程
佩尔方程
x^2+ny=1(其中n为非平方正整数)
常把x、y中有一个为零的解称为平凡解
x、y满足方程的最小正数的解又称为基本解
程序设计：
#include<stdio.h>
#include<math.h>
void main(){
double a,m,n,x,y;
printf("解佩尔方程：x^2-ny^2=1.
");
printf("请输入非平方整数n:");
scanf("%lf",&n);
m = floor(sqrt(n+1));
if(m*n == n){
printf("n为平方数，方程无正整数解");
return;
}
y = 1;
y++;
a = n*y*y;
x = floor(sqrt(a+1));
if(x*x == a+1){
printf("方程x^2-%.0fy^2 = 1的基本解为：
",n);
printf("x = %.0f,y = %.0f
",x,y);
break;
}
}
}
（7）解不等式
程序设计：
#include<stdio.h>
#include<math.h>
int main(){
long c,d,i,m1,m2;
double s;
printf("请输入正整数m1，m2（m1<m2）:");
scanf("%ld,%ld",&m1,&m2);
i = 0;
s = 0;
while(s<= m1){
i = i+1;
s = s+sqrt(i)/(i+1);
}
c = i;
do{
i = i+1;
s = s+sqrt(i)/(i+1);
}
while(s<=m2){
d = i-1;
printf("满足不等式的正整数n为:%ld<=n<=%ld
",c,d);
}
}