枚举算法——①基础

本文主要是介绍枚举算法——①基础，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

枚举算法：
**定义：
根据提出问题，列出该问题的所有可能的解，并在逐一列出的过程中，检验每个可能解是否是问题的真正解(如果是，则采纳这个解，否则继续判断下一个)。
**应用：
枚举法往往适合解决较简单的题目，这类题目的特点：
1）枚举范围是有穷的；
2）检验条件是确定的；
**代码结构：
枚举范围循环+条件判断语句
Tips：
在程序中，可以通过多层for循环的方式来实现枚举多个变量。

例子1：年龄判断

完整代码

#include<iostream>
using namespace std;
int main(){
	int tot=0;//记录可能解的个数
	for(int i=10;i<=99;i++){//枚举年龄的范围 
		if(i-(i%10*10+i/10)==27){//判断条件 //%取余时取个位数，/取最高位数 
			tot++;
		}
	} 
	cout<<tot<<endl;
	return 0;
} 

例子2：水仙花数

完整代码

#include<iostream>
#include<cmath>
using namespace std;
int main(){
	int cnt=0;
	for(int i=100;i<=999;i++){
		double a=i%10;//获取个位数字；
		double b=i%100/10;//获取十位数；    //'/'去取最高位，'%'去取最低位 
		double c=i/100;//获取百位数字；
		double num=pow(a,3)+pow(b,3)+pow(c,3);//double pow(double x,double y) x的y次幂 
		if(num==i){
			cnt++;
			cout<<num<<" "; 
		} 
	}
	cout<<endl;
	cout<<cnt;
	return 0;
} 

Tips：
1）本题结构：预处理+枚举+判断
2）用到了cmath头文件中的函数：pow(double x,double y) x的 y次幂 。
例子3：四叶玫瑰

完整代码

#include <iostream>
using namespace std;
int pow(int n) {
    return n * n * n * n;
}
bool rose(int x){
	//**分别为个、十、百、千位**
    int a=x%10;
    int b=x/10%10;
    int c=x/100%10;
    int d=x/1000;
    return pow(a)+pow(b)+pow(c)+pow(d)==x;
}
int main() {
    int n;
    cin >> n;
    if(n<1000||n>9999){
       cout<<"error!";
    } else {
        for(int i=1000;i<=n;i++){
            if(rose(i)){
                cout<<i<<endl;
            }
        }    
    }
    return 0;
}

例子4：滑雪课程设计

完整代码

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int a[1005];
int main() {
    freopen("ski.in", "r", stdin);
    freopen("ski.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 1e9;  // 表示 10 的 9 次方，是一个很大的数
    for (int low = 0; low + 17 <= 100; low++) {
        int high = low+17;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] < low) {
                sum += (low - a[i]) * (low - a[i]);
            }
            if(a[i]>high){
				sum+=(high-a[i])*(high-a[i]);
			}
            // 这里需要添加合适的代码
            
        }
        if(sum<ans)ans=sum;// 这里需要添加合适的代码
    }
    cout << ans << endl;
    return 0;
}

例子5：子数整除



完整代码

#include <iostream>
using namespace std;
int main() {
    freopen("divide.in", "r", stdin);
    freopen("divide.out", "w", stdout);
    int k;
    cin >> k;
    bool ok = false;
    for (int i = 10000; i <= 30000; i++) {
        int a = i/100;
        int b = i/10%1000;
        int c = i%1000;
        if (a % k == 0 && b % k == 0 && c % k == 0) {
            ok = true;
            cout << i << endl;
        }
    }
    if (!ok) {
        puts("No");
    }
    return 0;
}

例子6：(多个枚举变量)方程的解

完整代码

#include <cmath>
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    for(int a=0;a*a<=n;a++){
    	for(int b=a;a*a+b*b<=n;b++){//让b初始化为a，是因为题目的条件是a<=b<=c!!!
            /*for(int c=b;a*a+b*b+c*c<=n;c++){
                if(a*a+b*b+c*c==n){
                    cout<<a<<" "<<b<<" "<<c<<endl;
                }
            }*/
            int c=sqrt(n-a*a-b*b);
            if(c>=b&&a*a+b*b+c*c==n){
                cout<<a<<" "<<b<<" "<<c<<endl;
            }
        }
    }
    
    return 0;
}

例子7：扔骰子


思路：
用到前面数组下标应用中的计数排序的思想。
完整代码

#include <cstdio>
#include <iostream>
using namespace std;
int cnt[100];
int main() {
    freopen("dice.in", "r", stdin);
    freopen("dice.out", "w", stdout);
    int a, b, c;
    cin >> a >> b >> c;
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            for (int k = 1; k <= c; k++) {
                int temp=i+j+k;
                cnt[temp]++;
            }
        }
    }
    int ans = 1;
    for (int i = 1; i<=a+b+c; i++) {
        if (cnt[ans]<cnt[i]) {
            ans = i;
        }
    }
    cout << ans << endl;
    return 0;
}

例子8：回文数


完整代码

#include <iostream>
#include <cstdio>
using namespace std;
//bool k=false;
int main() {
    freopen("palindrome.in", "r", stdin);
    freopen("palindrome.out", "w", stdout);
    int n,flag=0;//标志flag
    cin >> n;
    for(int i=10000;i<=99999;i++){
        int a=i/10000;
        int b=i/1000%10;
        int c=i/100%10;
        int d=i/10%10;
        int e=i%10;
        if(a==e&&b==d&&(n==(a*2+b*2+c))){
            cout<<i<<endl;
            flag=1;
        }
    }
    for(int i=100000;i<=999999;i++){
        int a=i/100000;
        int b=i/10000%10;
        int c=i/1000%10;
        int d=i/100%10;
        int e=i/10%10;
        int f=i%10;
        if(a==f&&b==e&&c==d&&(n==(a*2+b*2+c*2))){
			cout<<i<<endl;
            flag=1;
		}
    }
    if(flag==0)
        cout<<-1;
    /*if(!ok){
        cout<<-1<<endl;
    }*/
    return 0;
}

Tips：
本题用到了一个标志flag，其值初始化为0，当满足条件时，将其置为1。
例子9：和数


思路：
双重循环(游标移动)，第三层循环(即最内层循环)计算并判断

完整代码

#include <iostream>
#include <cstdio>
using namespace std;
int a[105];
int main(){
	freopen("sum.in", "r", stdin);
    freopen("sum.out", "w", stdout);
    int n,i,count=0;
    cin>>n;
    //int a[n];
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    for(i=0;i<n;i++){
        int flag=0;
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                if(a[i]==a[j]+a[k]&&k!=j){//自己+自己！=自己 
                    flag=1;
                    count++;//同一个数可能有多组数相加可以得到
                    break;
                }     
            }
            if(flag==1)
                break;
        }
    }
    cout<<count;
    return 0;
}

这篇关于枚举算法——①基础的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！