资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

算法基础——枚举

创作时间:

作者:

@小白创作中心

算法基础——枚举

引用

CSDN

https://m.blog.csdn.net/2301_79571285/article/details/143867451

枚举算法，也叫穷举算法，是一种通过一一列举出问题所有可能的解，并在逐一列举的过程中，将它们逐一与目标状态进行比较以得出满足问题要求的解的算法。本文将详细介绍枚举算法的基本概念、解题思路，并通过三个具体的例题帮助读者掌握枚举算法的应用。

一、枚举算法简介

枚举算法，也叫穷举算法，通过一一列举出问题所有可能的解，并在逐一列举的过程中，将它们逐一与目标状态进行比较以得出满足问题要求的解。在列举的过程中，既不能遗漏也不能重复。

主要应用于没有公式能够解决某个题。例如：求小于N的最大素数——找不到公式可以直接计算

从N-1开始循环，找到第一个素数，就可以返回这个数。到2（包括2）既可以终止循环，如果一个
[N-1,2]之间要么是素数，要么不是素数，没有第3中可能了
求最大符合条件的素数，这里的关键点在于判断一个数是不是素数
质数(素数)是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
不是素数
如果一个数能被另一个数整除，那么这个数 <= 另一个数/2

public static int getPrime(int n) {
    // 求小于n的最大素数
    for (int i = n - 1; i > 1; i--){
        // 判断i是不是指数： i只能被它本身和i整除： 除数j = [i-1, 2)
        // 又因为如果被除数大于除数的一半，就一定不可能被整除： 除数
        boolean flag = false;
        for (int j = i / 2 ; j > 1; j--){
            if (i % j == 0){ // 不是素数
                flag = true;
                break;
            }
        }
        if (!flag){
            return i;
        }
    }
    return -1;
}

二、主要解题思路

1.解题方法路线

根据问题的具体情况确定枚举对象→ 根据问题的具体要求确定枚举范围、设置枚举循环→
根据问题的具体要求确定判断条件→考虑提高枚举算法的效率，减少时间复杂度

2.解题注意事项

三、例题

1.百钱买百鸡

1.题目：公鸡每只5元，母鸡每只3元，三只小鸡1元，用100元买100只鸡，问公鸡、母鸡、小鸡各多少只？

2.解题思路：通过列举公鸡，母鸡，小鸡的只数来找到符合条件的结果，公鸡最少0只，最多20只；母鸡最少0只，最多33只，小鸡最少0只，最多300只。

3.解题条件：

（1） x+y+z=100

（2）5x+3y+z/3=100

（3）z/3可以整除

4.解题代码

#include<stdio.h>  
int main(){  
int x,y,z;  
for(x=0;x<20;x++){  
for(y=0;y<33;y++){  
for(z=0;z<300;z++){  
if(x+y+z==100&&(5*x+3*y+z/3)==100&&z%3==0){  
printf("公鸡有%d只，母鸡有%d只，小鸡有%d只\n",x,y,z);  
}  
}  
}  
}  
return 0;  
}

2.特别数的和

1.题目：

小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

请问，在 1 到 n 中，所有这样的数的和是多少？

输入格式：输入一行包含两个整数 n（1≤n≤104）

输出格式：输出一行，包含一个整数，表示满足条件的数的和。

输入

输出

574

2.解题思路：

遍历1到n的所有数，找出含2、0、1、9的所有数，并把它们相加，输出最后的和。在确定数字i中是否含有指定数字，可以通过while循环，不断判断i%10是否满足，若不满足，则i=i/10；若满足，则停止判断。

3.解题代码：

#include <stdio.h>
int main(){
  int n,i;
  scanf("%d",&n);
  int sum=0;
  for(i=1;i<=n;i++){
    int j=i;
    while(j){
      if(j%10==2||j%10==0||j%10==1||j%10==9){
        sum+=i;
        break;
      }
      j=j/10;
    }
  }
  printf("%d",sum);
  return 0;
}

3.k倍区间

1.题目：给定一个长度为N的数列，A1, A2,'.An，如果其中一段连续的子序列 Ai, A;+1,..・Aj(i<j) 之和是K的倍数，我们就称这个区间[i,j]是K倍区间。你能求出数列中总共有多少个K倍区间吗?

输入描述：第一行包含两个整数N 和K(1<N,K<105 )。以下N行每行包含一个整数A;(1<A;<10°)

输出描述：输出一个整数，代表K倍区间的数目。

2.解题思路：

这个题本身就是在给的N个数里面任选(小于N个数)组合，并进行求和，判断他们的和是否是给定数K的倍数，最后计算一共有多少个这样的组合。为确保所有组合都能计算的到不遗漏，本题用了两个for循环，第一个fou循环里的i是组合数的起始，第二个fou循环里的j是组合数的末尾。通过遍历所有组合和来确定最后结果。

3.解题代码：

#include <stdio.h>
#define N 10000000
int main(){
  long long n,k;
  long long a[N];
  int i,j;
  scanf("%lld %lld",&n,&k);
  for(i=0;i<n;i++){
    scanf("%lld",&a[i]);
  }
  long long count=0;
  for(i=0;i<n;i++){
    long long  sum=0;
    for(j=i;j<n;j++){
      sum=sum+a[j];
      if(sum%k==0){
        count++;
      }
    }
  }
  printf("%lld",count);
  return 0;
}