C++ 算法：统计吉利数 - 优化后的代码示例

这篇文章将带您探索如何用 C++ 编写程序统计给定范围内满足特定条件的吉利数。我们将提供一个优化后的代码示例，并解释其原理。

题目描述

辰辰称一个数字是吉利的，当且仅当其满足以下性质：

• 不存在 4;
• 相邻两位数之和 ≠4。

例如，432, 133 就不是吉利数，而 666 就是吉利数。

求 L∼R 中有多少个吉利数。

输入

1 行 2 个整数 L, R。

输出

1 个整数表示 L∼R 中吉利数的个数。

样例

输入数据 1

3 15

输出数据 1

10

3, 5, 6, 7, 8, 9, 10, 11, 12, 15 是吉利数，而 4, 13, 14 不是吉利数。

数据范围

1≤L≤R≤1018，∣L−R∣≤5×106。

C++ 代码示例

#include <iostream>
using namespace std;
bool isLucky(int num) {
while (num > 0) {
if (num % 10 == 4) {
return false;
}
num /= 10;
}
return true;
}
int countLuckyNumbers(int L, int R) {
int count = 0;
for (int i = L; i <= R; i++) {
if (isLucky(i)) {
count++;
}
}
return count;
}
int main() {
int L, R;
cin >> L >> R;
cout << countLuckyNumbers(L, R) << endl;
return 0;
}

代码解析

1. isLucky(int num) 函数用来判断一个数字是否为吉利数。

• 使用循环遍历数字的每一位，判断是否包含 4。如果包含，则返回 false，表示该数字不是吉利数。
• 如果遍历完所有位都没有找到 4，则返回 true，表示该数字是吉利数。

2. countLuckyNumbers(int L, int R) 函数用来统计 L 到 R 之间的吉利数个数。

• 使用循环遍历 L 到 R 之间的每个数字。
• 对于每个数字，调用 isLucky() 函数判断是否为吉利数。
• 如果为吉利数，则计数器 count 加 1。
• 最终返回 count，即吉利数的个数。

3. main() 函数是程序的入口，负责接收输入，调用 countLuckyNumbers() 函数计算吉利数个数，并输出结果。

优化建议

以上代码示例中，isLucky() 函数的优化空间较小，主要是在 countLuckyNumbers() 函数中进行优化。

• 可以考虑使用二分查找法，将 L 到 R 之间的数字分成若干段，然后分别判断每一段中是否存在吉利数，从而减少遍历的次数。
• 还可以使用动态规划，将之前已经判断过的数字的结果保存起来，下次遇到相同的数字时可以直接使用，避免重复计算。

希望这篇文章能够帮助您更好地理解如何用 C++ 编写程序统计吉利数，并提供一些优化建议。