循环结构与算法竞赛经典题解析-嵌云网-嵌入式AI开发资源站

循环结构与算法竞赛经典题解析

CodeWarrioress

1. 循环结构基础与常见算法题解析

作为一名参加过多次蓝桥杯的选手，我深知循环结构在算法竞赛中的重要性。今天我想分享几个经典的循环结构题目，这些题目不仅出现在洛谷的入门训练中，也是蓝桥杯等竞赛的常见题型。通过这几个题目，我们可以深入理解循环结构的各种应用场景。

1.1 极差计算问题

极差计算是统计学中最基础的概念之一，但在编程实现时需要考虑效率问题。题目要求我们找出n个整数中的最大值和最小值，然后计算它们的差。

最直观的做法是使用两个变量分别记录当前的最大值和最小值，通过一次遍历完成统计：

cpp复制int min_val = INT_MAX, max_val = INT_MIN;
for(int i=0; i<n; i++){
    if(a[i] < min_val) min_val = a[i];
    if(a[i] > max_val) max_val = a[i];
}
cout << max_val - min_val;

但题目给出的解法使用了排序：

cpp复制sort(a+1, a+1+n);
cout<<a[n]-a[1];

注意：虽然排序解法代码简洁，但时间复杂度是O(nlogn)，而直接遍历的解法是O(n)。在算法竞赛中，当n很大时（比如1e6），这种差异会非常明显。

1.2 最长连号问题

这个问题要求找出序列中最长的连续递增子序列的长度。例如序列[1,5,6,2,3,4,5,6,8,9]的最长连号是[2,3,4,5,6]，长度为5。

解题关键在于维护当前连号的长度，并在连号中断时更新最大长度：

cpp复制int max_len = 1, current_len = 1;
for(int i=1; i<n; i++){
    if(a[i] == a[i-1]+1){
        current_len++;
        max_len = max(max_len, current_len);
    }else{
        current_len = 1;
    }
}
cout << max_len;

题目给出的解法稍有不同，但思路一致。在实际编程中，处理边界条件（如空序列、单元素序列）也很重要。

2. 数学相关算法问题

2.1 质因数分解问题

这个问题要求我们对一个由两个质数相乘得到的数进行质因数分解，并输出较大的那个质数。

最直接的方法是找出n的最小质因数，然后用n除以它得到较大的质因数：

cpp复制for(int i=2; i*i<=n; i++){
    if(n%i == 0){
        cout << n/i;
        return 0;
    }
}

这个解法利用了题目中"n是两个不同质数的乘积"的条件。如果n可以是多个质数的乘积，就需要更复杂的分解算法。

提示：判断质数的函数可以单独提取出来，这在其他题目中也能复用：
cpp复制bool is_prime(int x){
    for(int i=2; i*i<=x; i++)
        if(x%i == 0) return false;
    return true;
}

2.2 储蓄计划问题

这个问题模拟了一个储蓄计划，需要考虑每月收支和储蓄规则。关键在于正确处理以下几个逻辑：

每月初获得300元
减去当月预算
如果剩余金额≥100，存储整百部分
检查是否出现赤字

cpp复制int cash = 0, saved = 0;
for(int month=1; month<=12; month++){
    cash += 300;
    cin >> budget;
    cash -= budget;
    if(cash < 0){
        cout << -month;
        return 0;
    }
    if(cash >= 100){
        int save = (cash/100)*100;
        saved += save;
        cash -= save;
    }
}
cout << saved*1.2 + cash;

这个题目很好地训练了循环结构和条件判断的综合运用能力。

3. 输出格式控制问题

3.1 数字三角形输出

这个问题要求我们按照特定格式输出数字矩阵和三角形。主要考察输出格式的控制能力。

对于正方形部分，需要注意：

数字从1开始递增
两位数以下要补前导零

cpp复制int count = 1;
for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        printf("%02d", count++);
    }
    printf("\n");
}

对于三角形部分，除了数字格式外，还需要控制空格数量来实现右对齐效果：

cpp复制int num = 1;
for(int i=1; i<=n; i++){
    // 打印前导空格
    for(int j=0; j<2*(n-i); j++) printf(" ");
    // 打印数字
    for(int j=0; j<i; j++) printf("%02d", num++);
    printf("\n");
}

注意：在算法竞赛中，输出格式必须严格符合题目要求，包括空格、换行等细节。建议先仔细阅读输出样例。

3.2 评委打分问题

这个问题要求去掉最高分和最低分后计算平均分。需要注意以下几点：

处理多个相同最高/最低分的情况（题目说明只需去掉一个）
输出保留两位小数
边界条件（如n=3时，去掉一个最高一个最低后只剩一个分数）

cpp复制int sum = 0, min_score = 11, max_score = -1;
for(int i=0; i<n; i++){
    int score;
    cin >> score;
    sum += score;
    if(score < min_score) min_score = score;
    if(score > max_score) max_score = score;
}
double avg = (sum - min_score - max_score) / (n-2.0);
printf("%.2f\n", avg);

在计算平均值时，将分母写成(n-2.0)可以确保进行浮点数除法而非整数除法。

4. 数学建模与算法优化

4.1 资金筹集问题

这个问题需要建立数学模型，找出满足条件的X和K。题目描述比较复杂，我们需要先理清题意：

每周存款模式为：

周一：X
周二：X+K
周三：X+2K
...
周日：X+6K

这样一周的存款总额为7X + 21K。52周的总存款为52*(7X + 21K) = 364(X + 3K) = N。

因此，我们需要解方程：X + 3K = N/364，其中X≤100，K>0，且X尽可能大，K尽可能小。

cpp复制int total = n / 364;
for(int k=1; ; k++){
    int x = total - 3*k;
    if(x <= 100 && x > 0){
        cout << x << endl << k;
        return 0;
    }
}

这个解法通过数学推导大大简化了问题。在算法竞赛中，很多看似复杂的问题都可以通过数学建模找到简单解法。

5. 编程技巧与注意事项

通过以上题目，我总结了一些重要的编程技巧：

边界条件处理：在最长连号问题中，需要考虑序列为空或只有一个元素的情况；在储蓄计划问题中，要处理第一个月就出现赤字的情况。
浮点数精度：在计算平均值时，要注意整数除法的问题。使用printf格式化输出可以方便地控制小数位数。
算法选择：极差计算问题展示了不同算法的时间复杂度差异。在数据量大时，O(n)算法明显优于O(nlogn)算法。
代码复用：质数判断是一个常用功能，可以提取为单独的函数供多处调用。
输出格式：数字三角形问题强调了输出格式的重要性。在竞赛中，格式错误会导致丢分，必须仔细检查。
数学建模：资金筹集问题展示了如何将实际问题转化为数学方程，从而简化解决方案。

在实际编程练习中，建议：

先仔细阅读题目，确保理解所有条件和要求
设计测试用例，包括边界情况
编写清晰、结构化的代码
添加必要的注释，特别是复杂的逻辑部分
测试各种可能的输入情况

这些题目虽然属于入门级别，但涵盖了算法竞赛中的许多基本概念和技巧。掌握它们将为解决更复杂的问题打下坚实基础。