计算并输出n(包括n)以内所有能被5或9整除的自然数的倒数之和
时间: 2023-11-05 22:04:37 浏览: 60
算法1:暴力枚举
直接从1到n枚举每个自然数,判断是否能被5或9整除,如果能就将其倒数加入总和中。
时间复杂度:$O(n)$
C++ 代码
```
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
double sum = 0;
for (int i = 1; i <= n; i++) {
if (i % 5 == 0 || i % 9 == 0) {
sum += 1.0 / i;
}
}
printf("%.4f", sum);
return 0;
}
```
算法2:数学公式
将所有能被5或9整除的自然数分别列出来:
$5, 9, 10, 15, 18, 20, 25, 27, 30, 35, 36, 40, 45, 50, \ldots$
可以发现,它们的公倍数为:$5 \times 9 = 45$。
因此,我们只需要将n除以45得到能整除45的倍数m,然后根据等差数列求和公式计算出每个45的倍数中能被5或9整除的自然数的倒数之和,再将其乘以m,最后将剩余的自然数(小于45)暴力枚举即可。
时间复杂度:$O(1)$
C++ 代码
```
#include <iostream>
using namespace std;
double sum45(int n) { // 计算能被45整除的自然数的倒数之和
double a1 = 1.0 / 5, d = 1.0 / 45;
int m = n / 45;
double an = a1 + (m - 1) * d;
return m * (a1 + an) / 2;
}
int main() {
int n;
cin >> n;
double sum = 0;
sum += sum45(n); // 将能被45整除的自然数的倒数之和加入总和中
for (int i = 1; i <= n % 45; i++) { // 将剩余的自然数暴力枚举
if (i % 5 == 0 || i % 9 == 0) {
sum += 1.0 / i;
}
}
printf("%.4f", sum);
return 0;
}
```