谈晶阁

  • 信息奥赛一本通函数题库解析: 回文三位数

    Jul 2, 2024 • algorithms, olympiad, functions

    原题链接:

    解题思路

    题目要求找出所有既是回文数又是素数的三位数。一个回文数是指从左到右读和从右到左读都相同的数。一个素数是指除了 1 和自身外没有其他因数的自然数。

    步骤

    1. 判断一个数是否为素数：编写一个函数 is_prime 来判断一个数是否为素数。
    2. 判断一个数是否为回文数：编写一个函数 is_palindrome 来判断一个数是否为回文数。
    3. 遍历所有三位数：从 100 到 999 遍历每个数，检查它们是否既是回文数又是素数，并输出结果。

    代码实现

    以下是实现上述步骤的 C++ 代码：

    #include <iostream>
#include <cmath>
using namespace std;

// 函数：判断一个数是否为素数
bool is_prime(int num) {
    if (num <= 1) return false; // 1 及以下的数不是素数
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) return false; // 如果找到因子，则不是素数
    }
    return true; // 如果没有找到因子，则是素数
}

// 函数：判断一个数是否为回文数
bool is_palindrome(int num) {
    int original = num, reversed = 0;
    while (num > 0) {
        reversed = reversed * 10 + num % 10;
        num /= 10;
    }
    return original == reversed;
}

int main() {
    // 遍历所有三位数
    for (int i = 100; i <= 999; ++i) {
        if (is_prime(i) && is_palindrome(i)) {
            cout << i << endl; // 输出既是回文数又是素数的三位数
        }
    }

    return 0;
}

    代码讲解

    1. is_prime 函数：用于判断一个数是否为素数。若数小于或等于1，则返回 false。否则，通过遍历从 2 到 (\sqrt{num}) 的所有整数，检查 num 是否能被整除。如果能被整除，则返回 false；否则返回 true。

       bool is_prime(int num) {
     if (num <= 1) return false;
     for (int i = 2; i <= sqrt(num); ++i) {
         if (num % i == 0) return false;
     }
     return true;
 }

    2. is_palindrome 函数：用于判断一个数是否为回文数。通过将数 num 反转并与原数 original 比较，若相同则为回文数。

       bool is_palindrome(int num) {
     int original = num, reversed = 0;
     while (num > 0) {
         reversed = reversed * 10 + num % 10;
         num /= 10;
     }
     return original == reversed;
 }

    3. 主程序：遍历所有三位数（100 到 999），对于每个数，使用 is_prime 和 is_palindrome 函数检查其是否既是回文数又是素数。如果是，则输出该数。

       int main() {
     for (int i = 100; i <= 999; ++i) {
         if (is_prime(i) && is_palindrome(i)) {
             cout << i << endl;
         }
     }
     return 0;
 }

    知识点总结

    1. 素数判断：通过判断一个数是否能被 2 到 (\sqrt{num}) 之间的数整除来判断其是否为素数。
    2. 回文数判断：通过反转数字并与原数字比较来判断其是否为回文数。
    3. 遍历和条件判断：遍历所有三位数并使用条件判断来筛选既是回文数又是素数的数。

    以上代码和讲解展示了如何有效地找出所有既是回文数又是素数的三位数并按要求输出结果。

  • 信息奥赛一本通函数题库解析: 绝对素数

    Jul 2, 2024 • algorithms, olympiad, functions

    原题链接:

    解题思路

    题目要求找出所有二位绝对素数。一个绝对素数是指它和它的数字对换后的数都是素数。比如 13 和 31 都是素数，所以 13 是绝对素数。

    步骤

    1. 判断一个数是否为素数：编写一个函数 is_prime 来判断一个数是否为素数。
    2. 判断一个数是否为绝对素数：编写一个函数 is_absolute_prime 来判断一个数和它的数字对换后的数是否都是素数。
    3. 遍历所有两位数：从 10 到 99 遍历每个数，检查它们是否为绝对素数，并输出结果。

    代码实现

    以下是实现上述步骤的 C++ 代码：

    #include <iostream>
#include <cmath>
using namespace std;

// 函数：判断一个数是否为素数
bool is_prime(int num) {
    if (num <= 1) return false; // 1 及以下的数不是素数
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) return false; // 如果找到因子，则不是素数
    }
    return true; // 如果没有找到因子，则是素数
}

// 函数：检查两个数是否为绝对素数
bool is_absolute_prime(int num) {
    int reversed_num = (num % 10) * 10 + (num / 10); // 对换数字位置
    return is_prime(num) && is_prime(reversed_num); // 判断原数和对换后的数是否都是素数
}

int main() {
    // 遍历所有两位数
    for (int i = 10; i <= 99; ++i) {
        if (is_absolute_prime(i)) {
            cout << i << endl; // 输出绝对素数
        }
    }

    return 0;
}

    代码讲解

    1. is_prime 函数：用于判断一个数是否为素数。若数小于或等于1，则返回 false。否则，通过遍历从 2 到 (\sqrt{num}) 的所有整数，检查 num 是否能被整除。如果能被整除，则返回 false；否则返回 true。

       bool is_prime(int num) {
     if (num <= 1) return false;
     for (int i = 2; i <= sqrt(num); ++i) {
         if (num % i == 0) return false;
     }
     return true;
 }

    2. is_absolute_prime 函数：用于判断一个数及其数字对换后的数是否都是素数。首先将数字对换位置，然后使用 is_prime 函数检查两个数是否为素数。

       bool is_absolute_prime(int num) {
     int reversed_num = (num % 10) * 10 + (num / 10);
     return is_prime(num) && is_prime(reversed_num);
 }

    3. 主程序：遍历所有两位数（10 到 99），对于每个数，使用 is_absolute_prime 函数检查其是否为绝对素数。如果是，则输出该数。

       int main() {
     for (int i = 10; i <= 99; ++i) {
         if (is_absolute_prime(i)) {
             cout << i << endl;
         }
     }
     return 0;
 }

    知识点总结

    1. 素数判断：通过判断一个数是否能被 2 到 (\sqrt{num}) 之间的数整除来判断其是否为素数。
    2. 数字对换：通过取余和除法运算对换两位数的数字。
    3. 遍历和条件判断：遍历所有两位数并使用条件判断来筛选绝对素数。

    以上代码和讲解展示了如何有效地找出所有二位绝对素数并按要求输出结果。

  • 信息奥赛一本通函数题库解析: 最大数max(x,y,z)

    Jul 2, 2024 • algorithms, olympiad, functions

    原题链接:

    解题思路

    题目要求我们计算 ( m ) 的值，公式为：

    [ m = \frac{\max(a, b, c)}{\max(a+b, b, c) \times \max(a, b, b+c)} ]

    其中， ( a, b, c ) 为输入的三个数。我们需要定义求最大值的函数，并利用它来计算公式中的最大值。最后，输出结果并保留三位小数。

    步骤

    1. 定义求最大值的函数：为了简化代码并提高可读性，我们定义一个函数来求三个数中的最大值。
    2. 输入处理：读取用户输入的三个数 ( a, b, c )。
    3. 计算 ( m ) 的值：利用公式计算 ( m )。
    4. 输出结果：按照题目要求，输出保留三位小数的结果。

    代码实现

    以下是实现上述步骤的 C++ 代码：

    #include <iostream>
#include <iomanip>
using namespace std;

// 定义函数：求三个数中的最大值
double max(double x, double y, double z) {
    return std::max(std::max(x, y), z);
}

int main() {
    double a, b, c;
    cin >> a >> b >> c; // 输入a, b, c

    // 计算 m
    double m = max(a, b, c) / (max(a + b, b, c) * max(a, b, b + c));

    // 输出结果，保留三位小数
    cout << fixed << setprecision(3) << m << endl;

    return 0;
}

    代码讲解

    1. max 函数：该函数使用标准库函数 std::max 来计算三个数中的最大值。我们首先计算 x 和 y 的最大值，然后再与 z 进行比较，得到最终的最大值。

       double max(double x, double y, double z) {
     return std::max(std::max(x, y), z);
 }

    2. 输入处理：读取用户输入的三个浮点数 a, b, c。

       double a, b, c;
 cin >> a >> b >> c;

    3. 计算 m 的值：根据公式计算 m 的值。

       double m = max(a, b, c) / (max(a + b, b, c) * max(a, b, b + c));

    4. 输出结果：使用 fixed 和 setprecision(3) 控制输出格式，保留三位小数。

       cout << fixed << setprecision(3) << m << endl;

    知识点总结

    1. 函数定义和调用：通过定义 max 函数，简化了代码并提高了可读性。
    2. 标准库函数：利用 std::max 函数计算两个数的最大值。
    3. 格式化输出：使用 fixed 和 setprecision 控制浮点数的输出格式。

    以上代码和讲解展示了如何高效地计算并输出保留三位小数的结果。

  • 信息奥赛一本通函数题库解析: 素数个数

    Jul 2, 2024 • algorithms, olympiad, functions

    原题链接: 素数个数

    解题思路

    这道题目要求我们计算从 2 到 n（其中 n 的最大值为 50000）之间的素数个数。素数是指除了 1 和自身以外不再有其他因数的自然数。解决这个问题我们可以使用 埃拉托色尼筛法（Sieve of Eratosthenes），这是一种高效的计算素数的算法。

    埃拉托色尼筛法解释

    埃拉托色尼筛法是一种古老的算法，用于寻找一个范围内的所有素数。其基本思想是从 2 开始，将每个素数的倍数标记为合数（即非素数）。具体步骤如下：

    1. 初始化：创建一个布尔数组 is_prime，大小为 n+1，并将所有元素初始化为 true。is_prime[i] 表示数 i 是否为素数。
    2. 标记合数：从 2 开始，对于每个数 i，如果 is_prime[i] 为 true，则将 i 的所有倍数标记为 false。
    3. 计数素数：遍历数组 is_prime，统计值为 true 的元素个数，这些元素对应的索引即为素数。

    算法的时间复杂度

    埃拉托色尼筛法的时间复杂度为 (O(n \log \log n))，对于 n 最大值为 50000 的情况，效率是非常高的。

    代码实现

    下面是使用埃拉托色尼筛法计算从 2 到 n 范围内素数个数的代码：

    #include <iostream>
#include <algorithm> // 引入算法库以使用 fill_n
using namespace std;

// 函数：使用埃拉托色尼筛法计算素数的个数
int count_primes(int n) {
    if (n < 2) return 0; // 如果 n 小于 2，则没有素数

    // 创建布尔数组并初始化
    bool is_prime[n + 1];
    fill_n(is_prime, n + 1, true); // 初始化数组为 true

    is_prime[0] = is_prime[1] = false; // 0 和 1 不是素数

    // 使用埃拉托色尼筛法
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false; // 标记 i 的倍数为非素数
            }
        }
    }

    // 统计素数的个数
    int count = 0;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            count++; // 如果是素数，计数加一
        }
    }

    return count; // 返回素数的总个数
}

int main() {
    int n;
    cin >> n; // 输入 n

    int prime_count = count_primes(n); // 计算素数的个数

    cout << prime_count << endl; // 输出素数的个数

    return 0;
}

    代码解析

    1. 初始化布尔数组：bool is_prime[n + 1]; 创建一个大小为 n+1 的布尔数组，并使用 fill_n(is_prime, n + 1, true); 初始化所有元素为 true。
    2. 特殊处理 0 和 1：is_prime[0] = is_prime[1] = false; 将 0 和 1 标记为非素数。
    3. 筛选素数：使用两层循环，外层循环从 2 到 (\sqrt{n})，内层循环从 i(^2) 开始，将每个素数 i 的所有倍数标记为 false。
    4. 统计素数：最后遍历数组 is_prime，统计所有为 true 的元素个数。

    这样就能高效地计算从 2 到 n 之间的素数个数并输出结果。

  • 信息奥赛一本通函数题库解析: 求正整数2和n之间的完全数

    Jul 2, 2024 • algorithms, olympiad, functions

    原题链接: 求正整数2和n之间的完全数

    根据题目描述和样例输入输出的要求，我们需要编写一个程序，找到 2 和 n 之间的完全数，并按升序输出。一个完全数是指它的所有真因子（不包括自身）之和等于它本身。

    以下是针对这道题的详细解题思路：

    1. 理解完全数的定义：完全数是一个正整数，它等于其所有真因子（包括 1，但不包括自身）的和。例如，6 是一个完全数，因为 6 = 1 + 2 + 3。

    2. 输入输出：输入一个整数 n (n <= 5000)，输出 2 到 n 之间的所有完全数，每行一个数，按从小到大的顺序排列。

    3. 解决方案：

      • 首先，我们需要一个函数来判断一个数是否为完全数。
      • 然后，我们遍历从 2 到 n 的所有整数，使用该函数判断是否为完全数。
      • 如果是完全数，将其存储在一个列表中。
      • 最后，按顺序输出列表中的所有完全数。

    以下是实现该方案的代码：

    #include <iostream>
using namespace std;

// 函数：判断一个数是否为完全数
bool is_perfect(int num) {
    if (num == 1) {
        return false; // 1 不是完全数
    }
    int sum = 1; // 1 是所有数的因子
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) {
            sum += i;
            if (i * i != num) { // 避免重复添加平方根
                sum += num / i;
            }
        }
    }
    return sum == num; // 如果因子和等于自身，则是完全数
}

int main() {
    int n;
    cin >> n; // 读入 n

    int perfect_numbers[5]; // 假设最多有 5 个完全数
    int count = 0; // 完全数的计数

    for (int i = 2; i <= n && count < 5; ++i) {
        if (is_perfect(i)) {
            perfect_numbers[count++] = i; // 如果 i 是完全数，加入数组
        }
    }

    for (int i = 0; i < count; ++i) {
        cout << perfect_numbers[i] << endl; // 输出所有的完全数
    }

    return 0;
}

    知识点总结：

    1. 因数分解：为了求一个数的所有真因子，我们需要遍历从 1 到这个数平方根之间的所有整数。如果某个整数是这个数的因子，那么它的对应因子也可以求出。例如，12 的因子包括 1, 2, 3, 4, 6 和 12，我们只需遍历到 sqrt(12) 即可。

    2. 数据存储和排序：使用数组或列表来存储找到的完全数，并按顺序输出。

    3. 复杂度分析：由于我们需要遍历从 2 到 n 的所有数，并对每个数进行因数分解，时间复杂度为 O(n * sqrt(n))，对于 n <= 5000 是可以接受的。

    这段代码可以有效解决这个问题，找出所有满足条件的完全数并输出。

    为什么 只需遍历到 sqrt(12) 即可

    只需遍历到 (\sqrt{n}) 是因为在查找一个数 (n) 的因子时，如果 (i) 是 (n) 的一个因子，那么 (\frac{n}{i}) 也是 (n) 的一个因子。具体来说，如果我们找到一个因子 (i)，那么我们可以直接确定另一个因子 (\frac{n}{i})。

    例如，对于 (n = 12)：

    • 因子对包括 (1, 12), (2, 6), 和 (3, 4)。
    • 如果我们从 1 遍历到 (\sqrt{12} \approx 3.46)，那么当我们找到因子 2 时，我们也可以确定 6 是因子（因为 (12 / 2 = 6)）。
    • 同样，当我们找到因子 3 时，我们也可以确定 4 是因子（因为 (12 / 3 = 4)）。

    这就意味着，我们只需遍历到 (\sqrt{n}) 就可以找到所有的因子对，因为对于每一个 (i \leq \sqrt{n})，对应的 (\frac{n}{i}) 都会被找到。

    这个方法大大减少了需要检查的数的数量，降低了时间复杂度。遍历到 (\sqrt{n}) 的时间复杂度是 (O(\sqrt{n}))，而不是遍历到 (n) 的 (O(n))，这对于较大的 (n) 来说是非常有效的。

    让我们再来看一遍代码中的这部分：

    for (int i = 2; i * i <= num; ++i) {
    if (num % i == 0) {
        sum += i;
        if (i * i != num) { // 避免重复添加平方根
            sum += num / i;
        }
    }
}

    这里的 i * i <= num 就是为了遍历到 (\sqrt{num})。如果 i 是 num 的因子，我们将 i 和 num / i 都加到因子和 sum 中。

    避免重复添加平方根的目的是处理完全平方数的情况。例如，16 的因子包括 1, 2, 4, 8 和 16，但我们不希望将 4 添加两次。

    通过这种方法，我们能够高效地找到所有因子并判断一个数是否为完全数。