22 枚举

理论说明

枚举是最简单也是最直白的搜索方式，它依次尝试搜索空间中所有的解，测试是否符合条件，若符合则输出答案，否则继续测试下一组解。 但是在使用枚举这种相对比较暴力的算法来解题时，我们对其时间复杂度要做特别的关注。枚举问题的时间复杂度往往需要与需要枚举的情况个数有关，因为我们必须不遗不漏的枚举每一种可能成为答案的情况。所以搜索空间越大，枚举的时间复杂度越高。所以，我们对某一问题进行枚举时，必须保证其时间复杂度在题目时限可以接收的范围内。

题目来源和说明

2009年哈尔滨工业大学计算机研究生机试真题

题目描述

用小于等于n元去买100只鸡，大鸡5元/只，小鸡3元/只，还有1/3元每只的一种小鸡，分别记为x只，y只，z只。编程求解x,y,z所有可能解。

输入说明

测试数据有多组，输入n

输出说明

对于每组输入，请输出x,y,z所有可行解，按照x,y,z依次增大的顺序输出。

样例展示

输入：
40

输出：
x=0,y=0,z=100
x=0,y=1,z=99
x=0,y=2,z=98
x=1,y=0,z=99

C++代码

#include<iostream>
using namespace std;
int n;

int main() {
    while(scanf("%d",&n)!=EOF) {
        for(int x=0;x<=100;x++) {
            for(int y=0;y<=100-x;y++) {
                int z=100-x-y;
                if(x*5*3+y*3*3+z<=n*3) { //考虑到一只小小鸡的价格为1/3,为了避免除法带来的精度损失，这里采用了对不等式两端所有数字都乘3的操作，这也是避免除法的常用技巧
                    printf("x=%d,y=%d,z=%d\n",x,y,z);
                }
            }
        }
    }
    return 0;
}

abc

设a、b、c均是0到9之间的数字，abc、bcc是两个三位数，且有：abc+bcc=532。求满足条件的所有a、b、c的值。

C++代码

#include<iostream>
using namespace std;

int main() {
    int a,b,c;
    for(a=1;a<=9;a++) {
        for(b=1;b<=9;b++) {
            for(c=0;c<=9;c++) {
                if(a*100+b*10+c+b*100+c*10+c == 532) {
                    printf("%d %d %d\n",a,b,c);
                }
            }
        }
    }
    return 0;
}

Old Bill

C++代码