C++算法训练：整数拆分 |21xrx.com

C++算法训练：整数拆分

2023-06-27 17:20:06 深夜i -- --

C++ 算法训练整数拆分数学运算递归函数

整数拆分是指将一个正整数拆分成多个正整数的和，其中每个正整数可以使用多次，也可以不使用。例如，将6拆分成3+2+1或2+2+2都是一种拆分方式。

整数拆分问题可以用递归来解决。我们可以从当前数字开始，逐个尝试将其拆分成若干个小于等于它的数字的和。递归的出口是将剩下的数字拆分成1的和，这时递归结束。

例如，对于整数6，我们可以从6开始尝试拆分。第一次尝试将6拆分成5和1，但是5无法继续拆分，所以我们需要递归拆分1。最终得到的所有拆分方式有：

5+1

4+2，4+1+1，3+3，3+2+1，3+1+1+1，2+2+2，2+2+1+1，2+1+1+1+1，1+1+1+1+1+1

下面是C++代码实现：


#include <iostream>
#include <vector>
using namespace std;
void dfs(int n, int i, vector<int>& nums, vector<vector<int>>& res) {
  if (n == 0) {
    res.push_back(nums);
    return;
  }
  for (int j = i; j <= n; j++) {
    nums.push_back(j);
    dfs(n - j, j, nums, res);
    nums.pop_back();
  }
}
int main() {
  int n;
  cout << "请输入整数n：";
  cin >> n;
  vector<int> nums;
  vector<vector<int>> res;
  dfs(n, 1, nums, res);
  for (auto& v : res) {
    for (auto& num : v) {
      cout << num << "+";
    }
    cout << "\b " << endl; // 去掉末尾的加号
  }
  return 0;
}

在输入整数n后，我们调用dfs函数求解所有的拆分方式。dfs函数中，n表示当前需要拆分的数字，i表示枚举拆分的起始数字，nums保存当前拆分的数字序列，res保存所有的拆分方式。

dfs函数中首先判断n是否为0，如果为0则将当前拆分序列保存到res中。然后循环枚举当前能够拆分成的数字，依次递归拆分剩余的数字，最后还原状态。

最终输出所有的拆分方式即可。

上一篇: idea打包java可执行jar包

下一篇: C++教程 · Web版

评论区

()

相似文章