CCF CSP 2016.04 折点计数问题C++解决方案

"CCF CSP 2016.04 第7次题目答案解析代码提供了针对‘折点计数’问题的C++实现，包括三种解法：方法一、方法二和方法三。该认证是CCF CSP（中国计算机学会软件能力认证）的一部分，旨在考察编程者对软件能力的理解和应用。" 在CCF CSP 2016.04的第七次认证中，有一道题目要求计算给定正整数序列中的折点数量。折点定义为一个数，其左侧相邻数小于它且右侧相邻数大于它，或者反之，即由上升转为下降或由下降转为上升的点。以下是三种解法的详细说明： 1. 方法一： 这种方法需要两次遍历序列。首先计算相邻数之间的差值，以确定当前趋势（上升或下降）。然后再次遍历，比较相邻趋势的变化，统计折点数量。这种方法需要记住前一个数值和差值，但不需要额外的数组存储数据，可能会牺牲一些时间效率。 2. 方法二： 这种方法更为直观，只需要遍历一次序列。对于每个数，检查它是否同时大于左右两边的数（或同时小于），如果是，则为折点。这种方法同样不使用数组存储数据，可能会影响空间效率。 3. 方法三： 这种方法先将整个序列读入数组，然后按照方法二的思路进行折点判断和计数。虽然程序逻辑清晰，但需要额外的内存空间来存储数据。 在提供的代码中，有两个100分的C++实现，分别对应方法二和方法一。方法二的代码如下： ```cpp /*CCF201604-1折点计数*/ #include<iostream> using namespace std; int main() { int n, left, mid, right, sum = 0; // 输入n，输前２个数 cin >> n; if (cin >> left >> mid) { for (int i = 3; i <= n; i++) { // 输入第3至第n个数 cin >> right; // 判定是否为折点 if (left < mid && mid > right) sum++; else if (left > mid && mid < right) sum++; left = mid; mid = right; } } // 输出结果 cout << sum << endl; return 0; } ``` 方法一的代码虽然未给出完整，但通常会涉及更多的变量如`first`, `second`, `prearrow`, `arrow`来跟踪序列趋势和前一个数值。 这道题目的关键是理解和应用序列中的趋势变化，并有效地利用循环和条件判断来找到折点。三种方法各有优缺点，选择哪种取决于对时间和空间复杂性的权衡。在实际编程竞赛或认证中，参赛者需要根据具体要求和环境选择最合适的解决方案。