P1911 自然数的拆分 题解

涉及算法：深搜

作者注：此题涉及知识点有轻微难度，没有深搜或递归基础的建议移步其他题目

1、普通思路

• 如果使用单纯的暴力，那就会很难实现本题，毕竟我们是没法确定$n$要拆分成几个数字，所以普通思路是很难实现本题的
• 普通思路还有个缺点，我们如果用$for$循环来实现拆分，不仅没法确定要打几个，码量还十分巨大，所以作者不推荐使用普通思路（注：作者不是大佬，也只是不推荐，不代表不能用哦~）

2、正确思路

• 通过观察样例，我们可以将题目抽象成：有$x$ $(1 \leq x \leq n)$个数，要求这$x$个数的全排列，使这些数按字典序排列，并且和为$n$
• 根据以上思路，就可以采用深搜来解决，代码详解：

1、定义变量$n$，作用如题面所述

2、定义数组$a$，用数组$a$来求$x$个数的全排列，并定义深搜函数$dfs$，并在其中定义参数$u$和$cnt$，$u$表示$a_u$存放的数字$i$（注：也就是数组$a$第$u$个元素是数字$i$），$cnt$表示数组$a$目前的总和

3、深搜内部的写法：众所周知，深搜首先判断的就是什么时候终止，第一个$if$语句理所当然的应写为$cnt == n ~\&\&~ u ~!= 2$，为什么呢？因为只有当数组$a$的总和等于$n$时，我们才需要输出数组$a$中所存放的元素，而$u$之所以要不等于2是才输出，是因为$u$当时是下一步的值（注：也就是当时真正需要输出的是第$u-1$个元素），而判断是在深搜一开始，$u$是在判断结束后才更新的值，所以当$u$等于2时，说明就只拆分了一个数字，$u$只是指向了需要拆数的位置，输出就不用讲了吧（该步骤详见标程1）

4、如果$cnt$比$n$大时，那直接退出本次调用（注：$cnt$比$n$大时肯定说明这种方法不可行，详见标程2）

5、当前位置是否选该数，只需写一个$check$函数（详见标程3），来判断是否选该数，如果这个数比前面的数大，那肯定是不可选的，因为题面中说要按字典序排序

6、$dfs$开始肯定得写成$dfs(1, 0)$，因为你总得从第1位开始拆，总和为0吧

3、各种标程

标程1：

if (cnt == n && u != 2)
{
    cout << n << "=";
    for (int i = 1; i < u - 1; i++)
        cout << a[i] << "+";
    cout << a[u - 1] << endl;
    return ;
}

标程2：

if (cnt > n)
    return ;

标程3：

for (int i = 1; i <= n; i++)
{
    if (check(i, u))
    {
        a[u] = i;
        dfs(u + 1, cnt + a[u]);
        a[u] = 0;
    }
}

4、完整代码思路

#include <bits/stdc++.h>
using namespace std;
int n, a[25];  // n如题所述，a是用来拆数的数组
bool check(int x, int u)
{
    // x表示该位是否能放x，u表示前面有u个数
    for (int i = 1; i < u; i++)
        if (a[i] > x)  // 如果前面的数比当前的数大，那就不满足字典序了，所以放回0
            return 0;
    return 1;  // 如果上面的条件都不满足，那说明该位置是可以放x，放回1
}
void dfs(int u, int cnt)
{
    if (cnt == n && u != 2)  // cnt == n && u != 2我上面讲过了，所以没必要讲吧
    {
        cout << n << "=";
        for (int i = 1; i < u - 1; i++)
            cout << a[i] << "+";
        cout << a[u - 1] << endl;
        return ;
        // 输出，没什么好讲的吧，写return只不过懒得写else而已
    }
    if (cnt > n)
        return ;
    // 说明该方案行不通
    for (int i = 1; i <= n; i++)
    {
        // 枚举每一种可能，并判断是否能选
        if (check(i, u))  // 特判
        {
            a[u] = i;  // 若可行，将该位设为i
            dfs(u + 1, cnt + a[u]);  // 继续向下搜索
            a[u] = 0;  // 回溯
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);  // 读入加速
    cin.tie(0);
    cout.tie(0);
    cin >> n;  // 输入
    dfs(1, 0);  // 开始搜索
    return 0;
}

5、完整$AC ~ Code$（无注释版）

#include <bits/stdc++.h>
using namespace std;
int n, a[25];
bool check(int x, int u)
{
    for (int i = 1; i < u; i++)
        if (a[i] > x)
            return 0;
    return 1;
}
void dfs(int u, int cnt)
{
    if (cnt == n && u != 2)
    {
        cout << n << "=";
        for (int i = 1; i < u - 1; i++)
            cout << a[i] << "+";
        cout << a[u - 1] << endl;
        return ;
    }
    if (cnt > n)
        return ;
    for (int i = 1; i <= n; i++)
    {
        if (check(i, u))
        {
            a[u] = i;
            dfs(u + 1, cnt + a[u]);
            a[u] = 0;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    dfs(1, 0);
    return 0;
}

• 刷信奥赛CSP-J 难度1：题目2
• 自然数的拆分
• 这是必刷题之一啊，要重视，首先！思路如下↓

1. 根据搜索回滴溯法，观察输出；
2. 发现最后一项1 变二且项数减少，即最后一次遍历时，使遍历停止的条件增加了1；
3. 要想按格式输出，还需要在输出时知道项数，因此，函数中应该有项数的变化和使遍历停止的条件的变化。
4. 此方法由蒟蒻编写，如果范围太多那就……（TIE、TIE、TIE）

#include <bits/stdc++.h>
using namespace std;
int n, a[100000] = {1};
void print(int t)
{
    if (t == 1) return;
    cout << n << "=";
    for (int i = 1; i < t; i++)
        cout << a[i] << "+";
    cout << a[t] << endl;
}
int search(int t,int s)
{
    for (int i = 1; i <= s; i++)
    {
        if (a[t - 1] <= i)
        {
            a[t] = i;
            t++;
            s = s - i;
            if (s == 0) print(t - 1);
            else search(t, s);
            s = s + i;
            t--;
        }
    }
}
int main()
{
    cin >> n;
    search(1, n);
    return 0;
}

#include <iostream>
using namespace std;
int p[25] , n ;//p[i]为第i个加数
void dfs(int step, int num){//深度优先寻找，step表示有多少加数，num表示现在的和
	if(num == n ){//和等于n就可以输出了
		cout << n << '=' << p[1] ;//输出第一个加数和"n="
		for(int i = 2 ; i <= step ; i ++)
			cout << '+' << p[i];//输出接下来的加数
		cout << endl ;
		return ;//输出完成
	}
	if(num > n)//和大于n就不用继续了
		return ;
	for(int i = p[step] ; i <= n ; i ++){
        //字典序，所以加数从小到大,直接从上一个加数枚举到n
		p[step+1] = i ;//i就是下一个加数
		dfs(step+1,num + p[step+1]) ;//加数数量加1，和加上加数
	}
}
int main(){
	cin >> n ;
	for(int i = 1 ; i <= n / 2 ; i ++){
		p[1] = i ;//第一个加数不大于n/2
		dfs(1,i);
	}
	return 0 ;
} 

#include <bits/stdc++.h>
using namespace std;
int n, a[35], cnt;
void output(int p) {
cout << n << "=" << a[1];
for (int i = 2; i < p; i++) {
cout << "+" << a[i];
}
cout << '\n';
}
void dfs(int x, int p) {
if (x == 0) {
output(p);
cnt++;
return;
}
for (int i = a[p - 1]; i <= x && i < n; i++) {
a[p] = i;
dfs(x- i, p + 1);
}
}
int main() {
cin >> n;
a[0] = 1;
dfs(n, 1);
return 0;
}