算法基础之枚举

╰+哭是因爲堅強的太久メ 2022-09-05 04:06 241阅读 0赞

## 算法基础之枚举（C++示例） ##

枚举  
枚举（Enumerate）是基于已有知识来猜测答案的一种问题求解策略。也称穷举法，效率不高，适用于没有明显规律的情况，但知道可能的答案都有哪些或者知道可能的答案在某个范围里面，从而一个个试验找到符合条件的解。  
枚举的思想是不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立。  
枚举的时候要想清楚：可能的情况是什么？要枚举哪些要素？

**例题1**一个数组中的数互不相同，求其中和为0的数对的个数。

//一个数组中的数互不相同，求其中和为0的数对的个数
    #include<stdio.h>
    int main()
    { 
    	int a[10] = { 10,-10,-20,3,5,-6,7,0,20,-3};
    	int i,n,j,ans;
    	n=10;
    	for (int i = 0; i < n; ++i)
      		for (int j = i+1; j < n; ++j)
      			if (a[i] + a[j] == 0) 
    			{ 
    				++ans;
        			printf("(%d, %d) \n",a[i],a[j]);
    			}
        		
    	printf("个数 %d \n",ans);
    }

运行结果如下：  
(10, -10)  
(-20, 20)  
(3, -3)  
个数 3

**例题2**、百钱买百鸡  
问题描述：  
公鸡每只5元，母鸡每只3元，三只小鸡1元，用100元买100只鸡，问公鸡、母鸡、小鸡各多少只？  
算法分析：  
利用枚举法解决该问题，以三种鸡的个数为枚举对象,分别设为mj,gj和xj，用三种鸡的总数 （mj+gj+xj=100）和买鸡钱的总数（1/3*xj+mj*3+gj\*5=100）作为判定条件，穷举各种鸡的个数。  
源码如下：

#include<iostream>
    using namespace std;
    int main()
    { 
    	int mj=0, gj=0, xj=0;     //定义变量分别表示母鸡、公鸡、小鸡并初始化
    	for (gj = 0; gj <= 20; gj++)		   //公鸡最多可买20个
    	{ 
    		for (mj = 0; mj <= 33; mj++)	   //母鸡最多可买33个
    		{ 
    			xj = 100 - gj - mj;			   //三种鸡的总数是100只
    			if (xj % 3 == 0 && 5 * gj + 3 * mj + xj / 3 == 100) //总花费100元。
    		    printf("公鸡为 %d 只，母鸡为 %d 只，小鸡为 %d 只！\n", gj, mj, xj);
    		}
    	}
    	return 0;
    }

运行结果如下：  
公鸡为 0 只，母鸡为 25 只，小鸡为 75 只！  
公鸡为 4 只，母鸡为 18 只，小鸡为 78 只！  
公鸡为 8 只，母鸡为 11 只，小鸡为 81 只！  
公鸡为 12 只，母鸡为 4 只，小鸡为 84 只！

**例题3、完美立方**  
形如a3=63 \+ 83 \+ 103 。编写一个程序，对任给的正整数N  
(N≤100)，寻找所有的四元组(a, b, c, d)，使得a3= b3 \+ c3 \+ d3，其中a,b,c,d 大于1 , 小于等于N，且b<=c<=d。  
输入  
一个正整数N (N≤100)。  
输出  
每行输出一个完美立方。输出格式为：  
Cube = a, Triple = (b,c,d)  
其中a,b,c,d所在位置分别用实际求出四元组值代入。  
要求a从小到大输出。　　  
代码如下：

// 完美立方
    # include <stdio.h>
     
    int main(void)
    { 
        int a,b,c,d;
        int N;
        //scanf("%d",&N);
        N=20;
        for (a=2; a<=N; a++)
            for (b=2; b<=a-1; b++)
                for (c=b; c<=a-1; c++)
                    for (d=c; d<=a-1; d++)
                        if (a*a*a == b*b*b + c*c*c + d*d*d)
                            printf("Cube = %d, Triple = (%d,%d,%d)\n",a,b,c,d);
         
        return 0;
    }

运行结果如下：  
Cube = 6, Triple = (3,4,5)  
Cube = 12, Triple = (6,8,10)  
Cube = 18, Triple = (2,12,16)  
Cube = 18, Triple = (9,12,15)  
Cube = 19, Triple = (3,10,18)  
Cube = 20, Triple = (7,14,17)