2301_80775030 2023-12-05 20:24 采纳率: 0%
浏览 12
已结题

求减少这个c++程序内存的解决方案

有没有办法减少一下这个程序的内存,提交代码显示内存超限了,这个代码的大致意思是对一组数字中任意两个数求最大公约数并用其将两个数替换,这样为一次操作,经过输入的指定操作数后,求出可能得出的数组和的最大值


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int GreatestCommonDivisor(int a, int b) {
    int n1 = max(a, b);
    int n2 = min(a, b);
    int nt;
    while (n2!=0)
    {
        nt = n1;
        n1 = n2;
        n2 = nt % n2;
    }
    return n1;
}
vector<vector<int> > Perform(vector<int> inputv) {
    vector<vector<int> > outputv;
    vector<int> trans;
    int div;
    for (int i = 0; i < inputv.size(); i++)
    {
        for (int j = i + 1; j < inputv.size(); j++)
        {
            trans = inputv;
            div = GreatestCommonDivisor(trans[i], trans[j]);
            trans[i] = div;
            trans.erase(trans.begin() + j);
            outputv.push_back(trans);
        }
    }
    return outputv;
}
vector<vector<int> > Generate(vector<vector<int> >inputv) {
    vector<vector<int> > outputv;
    vector<vector<int> > trans;
    for (int i = 0; i < inputv.size(); i++)
    {    
        trans = Perform(inputv[i]);
        outputv.insert(outputv.end(), trans.begin(), trans.end());
    }
    return outputv;
}
int sum(vector<int> inputv) {
    int output = 0;
    for (int value : inputv) {
        output += value;
    }
    return output;
}

int main() {
    int n,k;
    cin >> n >> k;
    int inputn;
    vector<vector<int> > initialnum;
    vector<vector<int> > trans;
    vector<int> firstvector;
    vector<int> sumvector;
    for (int i = 0; i < n; i++)
    {
        cin >> inputn;
        firstvector.push_back(inputn);
    }
    initialnum.push_back(firstvector);
    for (int i = 0; i < k; i++)
    {
        trans = Generate(initialnum);
        initialnum = trans;
    }
    for (vector<int> valuevector : initialnum) {
        sumvector.push_back(sum(valuevector));
    }
    int maxsum = sumvector[0];
    for (int i = 1; i < sumvector.size(); i++)
    {
        maxsum = max(sumvector[i], maxsum);
    }
    cout << maxsum;
}
  • 写回答

17条回答 默认 最新

  • 专家-赤兔[在线] 2023-12-05 20:25
    关注
    获得0.60元问题酬金

    引自强大而免费的微信小程序:皆我百晓生

    为了减少程序的内存占用,可以考虑以下几个方面的优化:

    1. 减少不必要的数据复制:在Perform函数中,每次需要对输入数组进行复制后再进行操作。可以改为直接在原数组上进行操作,避免额外的内存开销。

    2. 减少不必要的数据存储:在Generate函数中,每次对中间结果进行存储,最后再合并结果。可以改为每次直接将结果加入到最终结果中,避免中间存储的开销。

    3. 优化循环遍历:在main函数中,使用vector的range-based for循环会产生临时的迭代器对象,增加了额外的内存开销。可以改为使用传统的for循环进行遍历。

    4. 减少不必要的内存分配:在sum函数中,对每个数字都进行了一次内存分配,影响了性能。可以将循环中的内存分配移出到循环之前,避免重复分配。

    经过以上优化,可以降低程序的内存占用。以下是优化后的代码:

    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    int GreatestCommonDivisor(int a, int b) {
        int n1 = max(a, b);
        int n2 = min(a, b);
        int nt;
        while (n2 != 0) {
            nt = n1;
            n1 = n2;
            n2 = nt % n2;
        }
        return n1;
    }
    
    void Perform(vector<int>& inputv, vector<vector<int>>& outputv) {
        int div;
        for (int i = 0; i < inputv.size(); i++) {
            for (int j = i + 1; j < inputv.size(); j++) {
                div = GreatestCommonDivisor(inputv[i], inputv[j]);
                inputv[i] = div;
                outputv.push_back(inputv);
                inputv[i] = div;
                inputv[j] = inputv.back();
                inputv.pop_back();
            }
        }
    }
    
    void Generate(vector<vector<int>>& inputv, vector<vector<int>>& outputv) {
        vector<vector<int>> trans;
        for (int i = 0; i < inputv.size(); i++) {
            Perform(inputv[i], trans);
            outputv.insert(outputv.end(), trans.begin(), trans.end());
        }
    }
    
    int sum(const vector<int>& inputv) {
        int output = 0;
        for (int value : inputv) {
            output += value;
        }
        return output;
    }
    
    int main() {
        int n, k;
        cin >> n >> k;
        vector<int> firstvector;
        for (int i = 0; i < n; i++) {
            int inputn;
            cin >> inputn;
            firstvector.push_back(inputn);
        }
        vector<vector<int>> initialnum;
        initialnum.push_back(firstvector);
        vector<vector<int>> trans;
        for (int i = 0; i < k; i++) {
            Generate(initialnum, trans);
            initialnum = trans;
        }
        vector<int> sumvector;
        for (int i = 0; i < initialnum.size(); i++) {
            sumvector.push_back(sum(initialnum[i]));
        }
        int maxsum = sumvector[0];
        for (int i = 1; i < sumvector.size(); i++) {
            maxsum = max(sumvector[i], maxsum);
        }
        cout << maxsum;
    }
    
    评论 编辑记录

报告相同问题?

问题事件

  • 系统已结题 12月13日
  • 创建了问题 12月5日

悬赏问题

  • ¥20 请问这种量表怎么用spss量化分析(作为中介模型的因变量
  • ¥55 AD844 howland电流源如何驱动大额负载
  • ¥15 C++ /QT 内存权限的判断函数列举
  • ¥15 深度学习GFnet理解问题
  • ¥15 单细胞小提琴堆叠图代码
  • ¥50 升级strust2版本到2.3.15.1后使用ognl3.0.6.jar windows环境中没有问题,但部署到linux环境报错
  • ¥15 vue页面,node封装接口
  • ¥15 求TMS320F280039C工程模板!
  • ¥15 delphi+fastreport实现分组补空打印问题
  • ¥15 使用python把两台mysql数据库服务器数据导出和导入