讨论/算法和数据结构/求设计算法/
求设计算法

比如3可以拆成(1,1,1)(2,1) 4可以拆成(1,1,1,1)(2,2)(3,1) F(n)?

展开讨论
奔跑中的小新发起于 2020-01-06

思路

  1. 首先对于输入 n ,先展开得到第一个全 1 答案。
  2. 根据题意,答案为组合。
  3. 由一个答案演变为下一个答案有以下规律。
    31. 因为和固定,所以最后一位数字无法直接增加。
    32. 倒数第二位数字要增加。
    33. 先将最后两位数字的和记录下来,删掉最后一位,给原倒数第二位也就是现在最后一位尝试上升 1 ,得到新值。
    34. 剩余的部分将切割成 0 ~ n 份大小为新值,依次重新排在后面。
    35. 直到最后,也不能小于新值,把小于部分加在最后一位上。
    35. 得到新的答案。
  4. 依次演变新的答案,直到不符合条件,得到所有答案。

答题

bool getNext(vector<int>& a)
{
	if (a.size() <= 1) return false;

	int sum = a[a.size() - 1] - 1;
	a.pop_back();
	a.back()++;

	size_t i = a.size() - 1;
	while (sum >= a[i])
	{
		sum -= a[i];
		a.push_back(a[i]);
	}
	a.back() += sum;

	return (a.size() > 1);
}

vector<vector<int>> combine(int n) 
{
	vector<vector<int>> ans;
	vector<int> a(n, 1);

	do
	{
		ans.push_back(a);
	} while (getNext(a));

	return ans;
}

测试用例

输入:2
输出:[[1,1]]

输入:3
输出:[[1,1,1],[1,2]]

输入:4
输出:[[1,1,1,1],[1,1,2],[1,3],[2,2]]

输入:5
输出:[[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3]]

输入:6
[[1,1,1,1,1,1],[1,1,1,1,2],[1,1,1,3],[1,1,2,2],[1,1,4],[1,2,3],[1,5],[2,2,2],[2,4],[3,3]]

输入:7
输出:[[1,1,1,1,1,1,1],[1,1,1,1,1,2],[1,1,1,1,3],[1,1,1,2,2],[1,1,1,4],[1,1,2,3],[1,1,5],[1,2,2,2],[1,2,4],[1,3,3],[1,6],[2,2,3],[2,5],[3,4]]

输入:8
输出:[[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,2],[1,1,1,1,1,3],[1,1,1,1,2,2],[1,1,1,1,4],[1,1,1,2,3],[1,1,1,5],[1,1,2,2,2],[1,1,2,4],[1,1,3,3],[1,1,6],[1,2,2,3],[1,2,5],[1,3,4],[1,7],[2,2,2,2],[2,2,4],[2,3,3],[2,6],[3,5],[4,4]]

输入:9
输出:[[1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,2],[1,1,1,1,1,1,3],[1,1,1,1,1,2,2],[1,1,1,1,1,4],[1,1,1,1,2,3],[1,1,1,1,5],[1,1,1,2,2,2],[1,1,1,2,4],[1,1,1,3,3],[1,1,1,6],[1,1,2,2,3],[1,1,2,5],[1,1,3,4],[1,1,7],[1,2,2,2,2],[1,2,2,4],[1,2,3,3],[1,2,6],[1,3,5],[1,4,4],[1,8],[2,2,2,3],[2,2,5],[2,3,4],[2,7],[3,3,3],[3,6],[4,5]]

输入:10
输出:[[1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,2],[1,1,1,1,1,1,1,3],[1,1,1,1,1,1,2,2],[1,1,1,1,1,1,4],[1,1,1,1,1,2,3],[1,1,1,1,1,5],[1,1,1,1,2,2,2],[1,1,1,1,2,4],[1,1,1,1,3,3],[1,1,1,1,6],[1,1,1,2,2,3],[1,1,1,2,5],[1,1,1,3,4],[1,1,1,7],[1,1,2,2,2,2],[1,1,2,2,4],[1,1,2,3,3],[1,1,2,6],[1,1,3,5],[1,1,4,4],[1,1,8],[1,2,2,2,3],[1,2,2,5],[1,2,3,4],[1,2,7],[1,3,3,3],[1,3,6],[1,4,5],[1,9],[2,2,2,2,2],[2,2,2,4],[2,2,3,3],[2,2,6],[2,3,5],[2,4,4],[2,8],[3,3,4],[3,7],[4,6],[5,5]]
1
展开全部 2 讨论