枚举问题刷题

考研机试题目中的很多问题往往能通过暴力方法来求解，这些题目并不需要进行过多的思考，而只需枚举所有可能的情况，或者模拟题目中提出的规则，便可以得到解答。虽然说这种方法看上并不高明，但对于一些简单的题目来说却是行之有效的好策略。

枚举

枚举是指对每个可能的解进行逐一判断，直到找到符合题目要求的答案。枚举类的题目本身并不复杂，但在采取枚举策略之前， 一定要好好分析题目的枚举量，枚举量过大时， 需要选择其他解决方法。即使问题适合用枚举策略来求解，也最好对题目进行一定的分析，以便通过减少部分无效的枚举来使得程序更加简洁和高效。

下面通过几道例题来感受一下：

abc_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/912b15e237ef44148e44018d7b8750b6?tpId=60&tqId=29487&tPage=1&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking题解：

#include<iostream>
using namespace std;
int main()
{
	for (int a = 0; a <= 9; a++)
	{
		for (int b = 0; b <= 9; b++)
		{
			for (int c = 0; c <= 9; c++)
			{
				//abc+bcc=532
				if (a * 100 + b * 10 + c + b * 100 + c * 10 + c == 532)
				{
					cout << a <<" "<< b << " "<< c << endl;
				}
			}
		}
	}

	return 0;
}

反序数_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/e0d06e79efa44785be5b2ec6e66ba898?tpId=60&tqId=31035&tPage=2&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking图解求逆序数的过程：

方法一：

#include<iostream>
using namespace std;
int Reverse(int n) { //封装一个求逆序数的函数
    int remain = 0;
    int reverse = 0;
    while (true) {
        remain = n % 10;
        n = n / 10;
        reverse = reverse * 10 + remain;
        if (n == 0) {
            break;
        }
    }
    return reverse;
}
int main() {
    for (int a = 1; a <= 9; a++) {
        for (int b = 0; b <= 9; b++) {
            for (int c = 0; c <= 9; c++) {
                for (int d = 0; d <= 9; d++) {
                    int n = a * 1000 + b * 100 + c * 10 + d;
                    if (n * 9 == Reverse(n)) {
                        cout << a << b << c << d << endl;
                    }
                }
            }
        }
    }
    return 0;
}

方法二(有一点投机取巧)：

#include<iostream>
using namespace std;

int main()
{
	for (int a = 0; a <= 9; a++)
	{
		for (int b = 0; b <= 9; b++)
		{
			for (int c = 0; c <= 9; c++)
			{
				for (int d = 0; d <= 9; d++)
				{
					if ((a * 1000 + b * 100 + c * 10 + d) * 9 == (d * 1000 + c * 100 + b * 10 + a))
					{
						if (a == 0 && b==0 && c==0 && d==0)
						{
							;
						}
						else
						{
							cout << a << b << c << d << endl;
						}
					}
				}
			}
		}
	}

	return 0;
}

对称平方数1_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/a84d46d5321f4e20931cb725e6c74fad?tpId=60&tqId=31036&tPage=2&ru=%2Fkaoyan%2Fretest%2F1001&qru=%2Fta%2Ftsing-kaoyan%2Fquestion-ranking题解：

#include<iostream>
using namespace std;

int Reverse(int n) { //封装一个求逆序数的函数
    int remain = 0;
    int reverse = 0;
    while (true) {
        remain = n % 10;
        n = n / 10;
        reverse = reverse * 10 + remain;
        if (n == 0) {
            break;
        }
    }
    return reverse;
}
int main() {
    for (int i = 0; i <= 256; i++) {
        int n = i * i;
        if (n == Reverse(n)) { //通过if条件来判断这个数是否具有对称性
            cout << i << endl;
        }
    }
    return 0;
}

与7无关的数__牛客网 (nowcoder.com)https://www.nowcoder.com/questionTerminal/776d401bf86d446fa783f0bef7d3c096

#include <iostream>
using namespace std;
bool Is_a_seven(int i)//封装成函数判断一个数中是否含有7，这样做的好处是避免一个函数循环过大
{
    int remain = 0;
    while (i)
    {
        remain = i % 10;
        if (remain == 7)
        {
            return true;
        }
        i = i / 10;
    }
    return false;
}
int main() {
    int n = 0;
    int sum = 0;//表示和
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        //与7相关的数要满足的条件：
        //1.能被7整除
        if (i % 7 == 0)
        {
            continue;//只跳过本次循环，用continue跳出
        }
        //2.数中是否含有7
        if (Is_a_seven(i))
        {
            continue;
        }
        sum = sum + i * i;
    }
    //输出：所有小于等于n的与7无关的数的平方和
    cout << sum << endl;
}

http://t.cn/E9ldhruhttp://t.cn/E9ldhru

此题容易出错：

解法一：避免小数的出现会引发向下取整这样的错误，那么同时都×3

#include<iostream>
using namespace std;

int main() {
    int n = 0;
    cin >> n;
    for (int x = 0; x <= 100; x++) {
        for (int y = 0; y <= 100; y++) {
            for (int z = 0; z <= 100; z++) {
                主要是1/3搞不好会变为0
                //所以想着全部×3 避免1/3的出现
                if ((x + y + z == 100) && (15 * x + 9 * y + z <= 3 * n)) {
                    cout << "x=" << x << ",y=" << y << ",z=" << z << endl;
                }
            }
        }
    }

    return 0;
}

解法2：利用强制类型转换，转换为double类型

#include<iostream>
using namespace std;

int main() {
    int n = 0;
    cin >> n;
    for (int x = 0; x <= n / 5; x++) {
        for (int y = 0; y <= n / 3; y++) {
            for (int z = 0; z <= 3 * n; z++) {
                if ((x + y + z == 100) && (5 * x + 3 * y + (double)1 / 3 * z <= n)) {
                    cout << "x=" << x << ",y=" << y << ",z=" << z << endl;
                }
            }
        }
    }

    return 0;
}

解法3：分数用1.0/3来表示

#include<iostream>
using namespace std;

int main() {
    int n = 0;
    cin >> n;
    for (int x = 0; x <= n / 5; x++) {
        for (int y = 0; y <= n / 3; y++) {
            for (int z = 0; z <= 3 * n; z++) {
                if ((x + y + z == 100) && (5 * x + 3 * y + 1.0 / 3 * z <= n)) {
                    cout << "x=" << x << ",y=" << y << ",z=" << z << endl;
                }
            }
        }
    }

    return 0;
}

通过此题要知道一个常识:

如果这个题目在处理1/3这个地方的时候不将数据强制类型转换成浮点类型，那么1/3的结果永远都是0，以后在处理这类问题的时候一定要注意，1/3以后尽量都用1.0/3来表示最好

Old Bill__牛客网 (nowcoder.com)https://www.nowcoder.com/questionTerminal/17a30153e092493e8b4d13f321343927

#include <iostream>
using namespace std;

int main() {
	int n, x, y, z;
	int flag = 0;
	while (cin >> n >> x >> y >> z)
	{
		flag = 0;
		for (int i = 9; i >= 1; i--) //i是最高位，j是最低位，分别从9往下循环
		{
			for (int j = 9; j >= 0; j--)
			{
				if ((10000 * i + 1000 * x + 100 * y + 10 * z + j) % n == 0)确保单价是整数
				{
					flag = 1;//将flag位置为1，目的是让程序可以退出下一层循环
					cout << i << " " << j << " " << (10000 * i + 1000 * x + 100 * y + 10 * z + j) / n << endl;
					break;//退出内层for循环
				}
			}
			if (flag == 1)//如果flag位是1.说明以及找到一组最大的满足结果的数，直接退出循环
			{
				break;
			}
		}
		if (flag == 0)//如果标志位遍历完成后还是0，则输出0
		{
			cout << 0 << endl;
		}
	}
}