向量折叠算法运行结果不符预期，求问题分析与解决

原代码 #

#include<iostream>
#include<fstream>
#include<vector>

using namespace std;

int main() {
    vector<int> vector1;
    vector<int> nr_notate_separat;
    int n;
    int nr;

    cin>>n;

    for(int i = 0; i < n; i++)
    {
        cin>>nr;
        vector1.push_back(nr);
    }

    while(vector1.size() > 1)
    {
        if(vector1.size() % 2 == 1)
        {
                nr_notate_separat.push_back(vector1[vector1.size() - 1]);
                vector1.pop_back();
        }

        vector<int> vector2;

        for(int i = 0; i < vector1.size() / 2; i++)
            {
                    vector2.push_back(vector1[i] + vector1[vector1.size() - 1 - i]);
            }

        vector1 = vector2;
    }

    nr_notate_separat.push_back(vector1[0]);

    for(int i = 0; i < nr_notate_separat.size(); i++)
    {
        cout<<nr_notate_separat[i]<<endl;
    }


    return 0;

}

需求说明 #

需求：
给定一个包含n个自然数的向量，需多次执行折叠操作，直到向量仅剩一个元素。每次折叠操作时，最后一个元素与第一个元素重合，倒数第二个与第二个重合，依此类推。若n为奇数，最中间的元素无法折叠，需提取并单独记录。新向量的元素个数为n/2，每个元素为重合的两个元素之和。对新向量重复折叠操作，直至仅剩一个元素，该元素也需单独记录。需确定所有单独记录的数字。

示例：
输入：
11
2 3 4 7 5 6 2 1 9 4 6

输出：
6 13 30

解释：
初始向量元素个数为奇数，因此中间元素6被单独记录。折叠后新向量为：8 7 13 8 7。该向量元素个数仍为奇数，中间元素13被单独记录。折叠后得到向量15 15，元素个数为偶数，无需单独记录，折叠后得到元素30，将其单独记录后停止操作。

问题诊断 #

你的代码输出为6, 11, 32，与示例结果不符，核心错误在于：当向量长度为奇数时，错误地提取并删除了最后一个元素，而非需求要求的中间元素。

比如示例中初始向量长度11，正确的中间元素是索引5的6，但你的代码取的是最后一个元素（索引10的6）——这次碰巧值相同，但后续步骤就会出错：

1. 初始向量删除最后一个元素后，剩余元素折叠得到的是[6,12,5,9,11]，而非示例中的[8,7,13,8,7]；
2. 后续处理这个错误向量时，又会提取最后一个元素11记录，最终导致结果偏差。

修正后的代码 #

#include<iostream>
#include<vector>

using namespace std;

int main() {
    vector<int> vector1;
    vector<int> nr_notate_separat;
    int n;
    int nr;

    cin >> n;

    for(int i = 0; i < n; i++)
    {
        cin >> nr;
        vector1.push_back(nr);
    }

    while(vector1.size() > 1)
    {
        if(vector1.size() % 2 == 1)
        {
            // 提取并删除中间元素
            int mid_idx = vector1.size() / 2;
            nr_notate_separat.push_back(vector1[mid_idx]);
            vector1.erase(vector1.begin() + mid_idx);
        }

        vector<int> vector2;
        int len = vector1.size();
        for(int i = 0; i < len / 2; i++)
        {
            vector2.push_back(vector1[i] + vector1[len - 1 - i]);
        }

        vector1 = vector2;
    }

    nr_notate_separat.push_back(vector1[0]);

    // 按示例格式输出空格分隔的结果
    for(size_t i = 0; i < nr_notate_separat.size(); i++)
    {
        if(i > 0) cout << " ";
        cout << nr_notate_separat[i];
    }
    cout << endl;

    return 0;
}

修正说明 #

1. 核心修复：将奇数长度时提取最后一个元素的逻辑，改为提取并删除中间元素（通过vector1.size()/2计算中间索引，用erase方法删除该位置元素）；
2. 输出优化：调整输出格式为空格分隔，与示例一致（原代码是每行一个元素）；
3. 冗余清理：移除了未使用的<fstream>头文件，增加len变量避免重复计算向量长度。

测试示例输入，修正后的代码会输出正确的6 13 30。

内容的提问来源于stack exchange，提问作者David Stroia