论坛 › C\C++交流 › 求教怎么用vector实现数塔问题

狂野的小黄花 发表于 2021-3-31 18:34:20

求教怎么用vector实现数塔问题

/*因为最近在学STL库，所以想用vector代替二维数组实现数塔问题
输入如下
5
5
8 3
12 7 16
4 10 11 6
9 5 3 9 4
输出如下
44

输入倒是可以正常输入输出不出来程序直接退出了 大佬们帮忙看看吧QAQ（我知道二维数组就可以实现，就是想知道vector能不能这样用解决问题）
*/
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,temp;
    cin>>n;
    vector<vector<int> > f(n+1);
    vector<vector<int> > dp(n+1);
    vector<int> v(n+1);
    for(int i=1;i<=n;i++){
            v.clear();
      for(int j=1;j<=i;j++){
            cin>>temp;
            v.push_back(temp);
      }
      f.push_back(v);
    }
    for(int j=1;j<=n;j++){
      dp=f;
    }
    for(int i=n-1;i>=1;i++){
      for(int j=1;j<=i;j++)
      {

            dp=max(dp,dp)+f;
      }
    }
    cout<<dp<<endl;
    return 0;
}

人造人 发表于 2021-3-31 18:34:21

本帖最后由 人造人 于 2021-4-1 02:08 编辑

你的这个算法参考的哪个教程？我有点看不懂你的这个算法，我需要先去看一看你这个算法的实现思路，因为你的代码没有注释，^_^
我用vector写了4个版本，两个递归的和两个非递归的，同样没有注释，^_^
我参考了这个教程，如果要理解我写的这些代码，可以先去看一下这篇文章
https://blog.csdn.net/theonegis/article/details/45801201

#include <iostream>
#include <memory>
#include <vector>

struct data_tower_t {
    ssize_t data;
    std::shared_ptr<data_tower_t> lchild;
    std::shared_ptr<data_tower_t> rchild;
    std::shared_ptr<data_tower_t> rsibling;
};

const std::vector<std::shared_ptr<data_tower_t>> get_data(std::istream &is, size_t size) {
    std::vector<std::shared_ptr<data_tower_t>> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
      if(is >> data) {
            std::shared_ptr<data_tower_t> n = std::make_shared<data_tower_t>();
            n->data = data;
            result.push_back(n);
      } else if(i == 0) return result;
      else throw "输入数据错误";
    }
    return result;
}

const std::shared_ptr<data_tower_t> create_data_tower(std::istream &is) {
    std::shared_ptr<data_tower_t> result;
    std::shared_ptr<data_tower_t> p, q;
    for(size_t i = 1; ; ++i) {
      std::vector<std::shared_ptr<data_tower_t>> v = get_data(is, i);
      if(v.empty()) return result;
      for(auto iter = v.begin(); iter != v.end() - 1; ++iter) (*iter)->rsibling = *(iter + 1);
      if(i == 1) p = result = v;
      else {
            q = p;
            for(auto iter = v.begin(); iter != v.end(); ++iter) {
                if(!q->lchild) q->lchild = *iter;
                else {
                  q->rchild = *iter;
                  q = q->rsibling;
                  if(q) q->lchild = *iter;
                }
            }
            p = p->lchild;
      }
    }
    return result;
}

ssize_t get_sum(const std::vector<ssize_t> &v) {
    ssize_t sum = 0;
    for(const auto &i: v) sum += i;
    return sum;
}

const std::vector<ssize_t> get_path(const std::shared_ptr<data_tower_t> &d) {
    if(d->lchild == nullptr && d->rchild == nullptr) return std::vector<ssize_t>({d->data});
    std::vector<ssize_t> lv = get_path(d->lchild);
    std::vector<ssize_t> rv = get_path(d->rchild);
    std::vector<ssize_t> *mv = get_sum(lv) > get_sum(rv) ? &lv : &rv;
    mv->insert(mv->begin(), d->data);
    return *mv;
}

std::ostream &operator<<(std::ostream &os, const std::vector<ssize_t> &rhs) {
    for(const auto &i: rhs) os << i << " ";
    return os;
}

int main() {
    std::shared_ptr<data_tower_t> data_tower = create_data_tower(std::cin);
    std::cout << get_path(data_tower) << std::endl;
    return 0;
}


#include <iostream>
#include <memory>
#include <vector>

struct data_tower_t {
    ssize_t data;
    std::shared_ptr<data_tower_t> lchild;
    std::shared_ptr<data_tower_t> rchild;
    std::shared_ptr<data_tower_t> rsibling;
};

const std::vector<std::shared_ptr<data_tower_t>> get_data(std::istream &is, size_t size) {
    std::vector<std::shared_ptr<data_tower_t>> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
      if(is >> data) {
            std::shared_ptr<data_tower_t> n = std::make_shared<data_tower_t>();
            n->data = data;
            result.push_back(n);
      } else if(i == 0) return result;
      else throw "输入数据错误";
    }
    return result;
}

const std::shared_ptr<data_tower_t> create_data_tower(std::istream &is) {
    std::shared_ptr<data_tower_t> result;
    std::shared_ptr<data_tower_t> p, q;
    for(size_t i = 1; ; ++i) {
      std::vector<std::shared_ptr<data_tower_t>> v = get_data(is, i);
      if(v.empty()) return result;
      for(auto iter = v.begin(); iter != v.end() - 1; ++iter) (*iter)->rsibling = *(iter + 1);
      if(i == 1) p = result = v;
      else {
            q = p;
            for(auto iter = v.begin(); iter != v.end(); ++iter) {
                if(!q->lchild) q->lchild = *iter;
                else {
                  q->rchild = *iter;
                  q = q->rsibling;
                  if(q) q->lchild = *iter;
                }
            }
            p = p->lchild;
      }
    }
    return result;
}

ssize_t get_max(const std::shared_ptr<data_tower_t> &d) {
    if(d->lchild == nullptr && d->rchild == nullptr) return d->data;
    ssize_t ls = get_max(d->lchild);
    ssize_t rs = get_max(d->rchild);
    ssize_t ms = ls > rs ? ls : rs;
    return ms + d->data;
}

int main() {
    std::shared_ptr<data_tower_t> data_tower = create_data_tower(std::cin);
    std::cout << get_max(data_tower) << std::endl;
    return 0;
}


#include <iostream>
#include <vector>

const std::vector<ssize_t> get_line_data(std::istream &is, size_t size) {
    std::vector<ssize_t> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
      if(is >> data) {
            result.push_back(data);
      } else if(i == 0) return result;
      else throw "输入数据错误";
    }
    return result;
}

const std::vector<std::vector<ssize_t>> create_data_tower(std::istream &is) {
    std::vector<std::vector<ssize_t>> result;
    for(size_t i = 1; ; ++i) {
      std::vector<ssize_t> v = get_line_data(is, i);
      if(v.empty()) return result;
      result.push_back(v);
    }
    return result;
}

ssize_t get_sum(const std::vector<ssize_t> &v) {
    ssize_t sum = 0;
    for(const auto &i: v) sum += i;
    return sum;
}

const std::vector<ssize_t> get_path(const std::vector<std::vector<ssize_t>> &d) {
    std::vector<std::vector<ssize_t>> p((d.end() - 1)->size());
    for(size_t i = d.size() - 1; i > 0; --i) {
      std::vector<std::vector<ssize_t>> c(d.size());
      for(size_t j = 0; j < c.size(); ++j) {
            if(j == 0) p.insert(p.begin(), d);
            p.insert(p.begin(), d);
            ssize_t ls = get_sum(p);
            ssize_t rs = get_sum(p);
            c = ls > rs ? p : p;
      }
      p = c;
    }
    p.insert(p.begin(), d);
    return p;
}

std::ostream &operator<<(std::ostream &os, const std::vector<ssize_t> &rhs) {
    for(const auto &i: rhs) os << i << " ";
    return os;
}

int main() {
    std::vector<std::vector<ssize_t>> data_tower = create_data_tower(std::cin);
    std::cout << get_path(data_tower) << std::endl;
    return 0;
}


#include <iostream>
#include <vector>

const std::vector<ssize_t> get_line_data(std::istream &is, size_t size) {
    std::vector<ssize_t> result;
    ssize_t data;
    for(size_t i = 0; i < size; ++i) {
      if(is >> data) {
            result.push_back(data);
      } else if(i == 0) return result;
      else throw "输入数据错误";
    }
    return result;
}

const std::vector<std::vector<ssize_t>> create_data_tower(std::istream &is) {
    std::vector<std::vector<ssize_t>> result;
    for(size_t i = 1; ; ++i) {
      std::vector<ssize_t> v = get_line_data(is, i);
      if(v.empty()) return result;
      result.push_back(v);
    }
    return result;
}

ssize_t get_max(const std::vector<std::vector<ssize_t>> &d) {
    std::vector<ssize_t> p((d.end() - 1)->size());
    for(size_t i = d.size() - 1; i > 0; --i) {
      std::vector<ssize_t> c(d.size());
      for(size_t j = 0; j < c.size(); ++j) {
            ssize_t ls = p + d;
            ssize_t rs = p + d;
            c = ls > rs ? ls : rs;
      }
      p = c;
    }
    return p + d;
}

int main() {
    std::vector<std::vector<ssize_t>> data_tower = create_data_tower(std::cin);
    std::cout << get_max(data_tower) << std::endl;
    return 0;
}

人造人 发表于 2021-4-1 12:17:13

我看懂了，思路用的就是我上面那篇文章中提到的方法
代码改动的地方有点多，你一行一行的对代码吧

/*因为最近在学STL库，所以想用vector代替二维数组实现数塔问题
输入如下
5
5
8 3
12 7 16
4 10 11 6
9 5 3 9 4
输出如下
44

输入倒是可以正常输入输出不出来程序直接退出了 大佬们帮忙看看吧QAQ（我知道二维数组就可以实现，就是想知道vector能不能这样用解决问题）
*/
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,temp;
    cin>>n;
    vector<vector<int> > f;
    vector<vector<int> > dp(n);
    vector<int> v;
    for(int i=1;i<=n;i++){
      v.clear();
      for(int j=1;j<=i;j++){
            cin>>temp;
            v.push_back(temp);
      }
      f.push_back(v);
    }
    dp = f;
    for(int i = 0; i < n - 1; ++i) {
      for(int j = 0; j <= i; ++j) {
            dp.resize(j + 1);
      }
    }
    for(int i = n - 2; i >= 0; i--){
      for(int j = 0; j <= i; j++)
      {
            dp = max(dp, dp) + f;
      }
    }
    cout<<dp<<endl;
    return 0;
}

狂野的小黄花 发表于 2021-4-1 12:20:00

人造人 发表于 2021-3-31 18:34
你的这个算法参考的哪个教程？我有点看不懂你的这个算法，我需要先去看一看你这个算法的实现思路，因为你的 ...

太感谢大佬了！看完你的代码对vector有一定了解了

人造人 发表于 2021-4-1 12:21:33

数据结构中确实说 数数从1开始，但是在编程中绝大多数情况都是从0开始
如果你在数据结构编程的时候从1开始，你就要非常非常的小心，因为一不小心就弄错边界了
所以还是建议数数从0开始，即使是数据结构编程的时候，这样就绝对不会弄错边界了

查看完整版本: 求教怎么用vector实现数塔问题