本文最后更新于 327 天前，其中的信息可能已经有所发展或是发生改变。

题目

　　已知 A < B，A 和 B 均为正整数，且 A * B = 2698, 求 A + B 的最小值，以及取最小值时 A 和 B 的值

解析

做题先审题，提炼已知条件和所求内容。

审题

已知条件：

A < B
A 和 B 为正整数
A * B = 2698

所求内容：

A + B 的最小值
取最小值时 A 和 B 的值

思考

　　在这个题中，满足三个条件的 A + B 的值肯定为有限个，对于最小值我们并不知晓，但它有最小值就有最大值，最大值就显而易见了，A = 1，B = 2698，A + B = 2699
　　以此为突破口，可以通过循环来找到更小更优的 AB 组合，我们首先想到的方法即是穷举法。

穷举法顾名思义，把可能出现的情况一一列举测试，并判断是否符合条件。

　　思路：定义一个和值 sum 变量，并赋值已知最大值 2699，通过改变循环控制变量来一一测试满足条件(能被 2698 整除)的 A、B 的可能取值，满足条件再判断 A + B 的值是否比 sum 小，如小则改变 sum。循环结束后 sum 就是 A + B 的最小值。

做题

　　先用中文描述思路，再把思路翻译替换为程序语言。循环程序如下

#include <iostream>
using namespace std;

int main() {
    int A = 1, B = 2698, sum = 2699;

    // 由解析写出循环
    for (int b = 2; b < 2698; b++) {
        // 判断是否能被整除(条件 2 和 3)
        if (2698 % b == 0) {
            int a = 2698 / b;

            // 判断条件 1 以及 sum 是否有更优解
            if (a < b && sum > a + b) {
                A = a;
                B = b;
                sum = A + B;
            }
        }
    }

    // 输出结果
    cout << "min(A + B)=" << sum << endl;
    cout << "A=" << A << endl;
    cout << "B=" << B << endl;
    return 0;
}

　　穷举法的弊端就显示出来了，即使内部加上判断条件，这个循环的轮数永远有两千多轮，虽然对于计算机来说，这可能只耗费几百微秒甚至几十微秒，性能表现也并不明显。可如果穷举法的列项有十万，一百万，积少成多耗费的时间就开始突出了。
　　为养成良好的编程习惯，我们应保持代码的简洁、干净、质量等，此时就需要改进算法逻辑(减少循环轮数)、减少不必要语句等等来提升程序效率。

再思考

　　因为 A < B，A * B = 2698，所以 B^2 > 2698，所以 B > sqrt(2698) = 51.9......
　　又 B 为正整数, 即 B >= 52，于是上面程序的循环就可以改成 for (int b = 52; b < 2698; b++) {}。但好像还是差一点意思，循环轮数并没有减少多少。
　　换种思路想想，从 B 入手实在没办法减少循环轮数了，我们还可以看看 A 的范围。
　　因为 A = 2698 / B，A < B，所以当 B 取最小值时，A 可以取得最大值。所以综上所述，0 < A < sqrt(2698) < B

程序改进

#include <iostream>
#include <cmath>

#define N 2698

using namespace std;

int main() {
    int A = 1, B = 2698, sum = 2699;
    // 由解析写出循环
    for (int a = 2; a < sqrt(N); a++) {
        // 判断是否能被整除
        if (N % a == 0) {
            // A 逐渐递增，B 逐渐递减，且 abs(A - B) 越小， A + B 就越小
            // 故最后一次满足条件的循环所得即是最终结果，不用再加判断
            A = a;
            B = N / A;
            sum = A + B;
        }
    }

    // 输出结果
    cout << "min(A + B)=" << sum << endl;
    cout << "A=" << A << endl;
    cout << "B=" << B << endl;
    return 0;
}

　　咦，既然按照逐渐递增来考虑 A，最后一次满足条件的循环所得就是最终结果，那何不按照逐渐递减来考虑 A 呢？
　　经证，可以，第一次满足条件后就是最终结果，可以直接 break 退出

最终程序

#include <iostream>
#include <cmath>

#define N 2698

using namespace std;

int main() {
    for (int A = sqrt(N); A > 0; A--) {
        if (N % A == 0) {
            int B = N / A;
            int sum = A + B;

            // 输出结果
            cout << "min(A + B)=" << sum << endl;
            cout << "A=" << A << endl;
            cout << "B=" << B << endl;
            break;
        }
    }
    return 0;
}

　　代码经过删减，读者可适量增加注释或中间变量以便于理解。循环轮数从最开始的两千多轮一下减少到了十几轮，可喜可贺。

程序输出结果(答案)

min(A + B)=109
A=38
B=71

虽说程序能跑能达到目的就行，但能追求完美又何乐而不为呢