C++基础算法题解析：函数与结构体实战

1. 项目概述

今天我想和大家分享几个基础的C++编程题目，这些题目都来自洛谷的入门系列，主要涉及函数与结构体的基础应用。作为刚接触算法竞赛的新手，这些题目非常适合用来巩固基础编程能力。我会逐一分析每个题目的解题思路，并给出详细的代码实现和优化建议。

这几个题目涵盖了常见的编程基础知识点：

• 平面几何计算（三角形周长）
• 质数筛选算法
• 闰年判断逻辑
• 数组统计处理
• 阶乘计算

这些题目虽然基础，但包含了算法竞赛中常见的编程模式和思考方式。通过这几个例子，我们可以学习如何将数学概念转化为可执行的代码，以及如何优化常见的计算过程。

2. 题目详解与实现

2.1 P5735 距离函数与三角形周长计算

这个题目要求计算平面坐标系中三个点构成的三角形的周长。关键在于正确实现两点间距离的计算公式。

数学原理：
两点(x1,y1)和(x2,y2)之间的距离公式为：
√[(x2-x1)² + (y2-y1)²]

实现要点：

1. 需要定义一个专门计算距离的函数，提高代码复用性
2. 输入三个点的坐标
3. 分别计算三条边的长度
4. 求和并保留两位小数输出

优化建议：

• 使用hypot函数可以更简洁地计算两点距离
• 输入时可以封装成点结构体提高可读性

cpp复制#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

struct Point {
    double x, y;
};

double distance(Point a, Point b) {
    return hypot(a.x - b.x, a.y - b.y);
}

int main() {
    Point p1, p2, p3;
    cin >> p1.x >> p1.y;
    cin >> p2.x >> p2.y;
    cin >> p3.x >> p3.y;
    
    double perimeter = distance(p1, p2) + distance(p2, p3) + distance(p1, p3);
    cout << fixed << setprecision(2) << perimeter << endl;
    
    return 0;
}

2.2 P5736 质数筛

这个题目要求从一组数字中筛选出质数。质数判断是算法竞赛中的常见问题。

质数判断算法：

1. 试除法：检查2到√n之间是否有能整除n的数
2. 埃拉托斯特尼筛法（适合批量判断）

实现要点：

1. 实现一个判断质数的函数
2. 遍历输入数组，筛选质数
3. 输出结果

优化建议：

• 预处理质数表可以提高多次判断的效率
• 试除法只需要检查到√n即可

cpp复制#include <iostream>
#include <vector>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> primes;
    
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        if (isPrime(num)) {
            primes.push_back(num);
        }
    }
    
    for (int p : primes) {
        cout << p << " ";
    }
    
    return 0;
}

2.3 P5737 闰年展示

这个题目要求找出给定年份区间内的所有闰年。

闰年判断规则：

1. 能被4整除但不能被100整除，或者
2. 能被400整除

实现要点：

1. 实现闰年判断函数
2. 遍历年份区间，收集闰年
3. 输出结果

优化建议：

• 可以预计算闰年周期减少计算量
• 注意边界条件的处理

cpp复制#include <iostream>
#include <vector>
using namespace std;

bool isLeapYear(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

int main() {
    int start, end;
    cin >> start >> end;
    vector<int> leapYears;
    
    for (int year = start; year <= end; year++) {
        if (isLeapYear(year)) {
            leapYears.push_back(year);
        }
    }
    
    cout << leapYears.size() << endl;
    for (int year : leapYears) {
        cout << year << " ";
    }
    
    return 0;
}

2.4 P5738 歌唱比赛评分

这个题目要求计算选手的最终得分，规则是去掉最高最低分后取平均。

实现要点：

1. 对每个选手的分数数组进行排序
2. 去掉首尾元素
3. 计算剩余元素的平均值
4. 找出最高分

优化建议：

• 使用快速选择算法可以更高效地找到最大最小值
• 可以边输入边统计，减少存储空间

cpp复制#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

double calculateScore(vector<int>& scores) {
    sort(scores.begin(), scores.end());
    double sum = 0;
    for (int i = 1; i < scores.size() - 1; i++) {
        sum += scores[i];
    }
    return sum / (scores.size() - 2);
}

int main() {
    int n, m;
    cin >> n >> m;
    double maxScore = 0;
    
    for (int i = 0; i < n; i++) {
        vector<int> scores(m);
        for (int j = 0; j < m; j++) {
            cin >> scores[j];
        }
        double score = calculateScore(scores);
        maxScore = max(maxScore, score);
    }
    
    cout << fixed << setprecision(2) << maxScore << endl;
    return 0;
}

2.5 P5739 计算阶乘

这个题目要求计算n的阶乘，并挑战不使用循环语句。

实现方案：

1. 循环实现（基础）
2. 递归实现（无循环）
3. 模板元编程（编译期计算）

递归实现要点：

• 基准条件：0! = 1
• 递归关系：n! = n * (n-1)!

cpp复制#include <iostream>
using namespace std;

int factorial(int n) {
    return n <= 1 ? 1 : n * factorial(n - 1);
}

int main() {
    int n;
    cin >> n;
    cout << factorial(n) << endl;
    return 0;
}

3. 常见问题与优化技巧

3.1 浮点数精度处理

在计算几何题目中，浮点数精度是需要特别注意的问题。比如在三角形周长计算中：

提示：使用fixed和setprecision控制输出格式，避免浮点数精度问题导致输出不符合要求。

3.2 质数判断优化

质数判断有多种优化方法：

1. 预处理质数表
2. 只检查奇数（除2外）
3. 使用更高效的算法如Miller-Rabin测试

cpp复制// 优化的质数判断函数
bool isPrimeOptimized(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

3.3 递归与迭代的选择

阶乘计算展示了递归和迭代两种实现方式。需要注意：

• 递归有栈溢出风险（虽然本题n≤12不会）
• 迭代通常效率更高
• 递归代码通常更简洁

3.4 数组处理技巧

在歌唱比赛评分题目中，我们使用了排序来找到最大最小值。其他方法包括：

1. 遍历一次同时记录最大最小值
2. 使用nth_element算法

cpp复制// 不排序的评分计算方法
double calculateScoreWithoutSort(vector<int>& scores) {
    int minVal = scores[0], maxVal = scores[0];
    double sum = scores[0];
    
    for (int i = 1; i < scores.size(); i++) {
        sum += scores[i];
        minVal = min(minVal, scores[i]);
        maxVal = max(maxVal, scores[i]);
    }
    
    return (sum - minVal - maxVal) / (scores.size() - 2);
}

4. 扩展思考与练习建议

这些基础题目虽然简单，但包含了算法竞赛中常见的编程模式。建议进一步练习：

1. 尝试用不同的方法实现相同功能（如递归vs迭代）
2. 思考如何优化时间复杂度和空间复杂度
3. 处理更大规模的数据（如质数筛扩展到10^6）
4. 封装常用功能为可重用函数或类

对于想进一步提高的同学，可以尝试：

• 实现埃拉托斯特尼筛法
• 用动态规划优化阶乘计算
• 扩展歌唱比赛评分系统，支持更多统计功能

在实际编程中，我发现良好的代码组织和模块化设计非常重要。比如将常用的数学计算封装成独立函数，可以大大提高代码的可读性和复用性。另外，边界条件的测试也不容忽视，比如0和1这样的特殊输入值。