2017.12.15 计算机算法分析与设计 枚举

计算机常用算法------第二章 枚举

（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个素组n",m);
                    if(m>0)
                    printf("一个最大全素组为:%d+%d+%d=%ldn",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个。n",m);
        printf("其和s=%.5fn",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.n");
    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",n);
            printf("x = %.0f,y = %.0fn",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<=%ldn",c,d);
    }
}