当前位置: 代码迷 >> 综合 >> 搜索与回溯 自然数的拆分
  详细解决方案

搜索与回溯 自然数的拆分

热度:27   发布时间:2024-01-15 08:39:34.0

【例5.3】自然数的拆分


时间限制: 1000 ms        内存限制: 65536 KB
提交数: 687     通过数:427 

【题目描述】

任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和。

当n=7共14种拆分方法:

7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14

【输入】

输入n。

【输出】

按字典序输出具体的方案。

【输入样例】

7

【输出样例】

7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4

【来源】


No

算法分析:

分出来的组合特点:

1.    sum=n

2.    每一组数个数不一定

3.    每一组后面的数必定大于等于前一个数,一是能避免等式重复,二是可以减少不必要的搜索

设计算法需要注意两点:

1.    设一数组a记录每一步所取数

2.    递归实现,每一条路口的值不变

具体细节在代码中。

代码实现:

#include<bits/stdc++.h>
using namespace std;
int n,total=0;
int a[10001]={1};
int print(int);
int search(int s,int t);//回溯算法
int main()
{cin>>n;search(n,1);        //将要拆分的数n传递给scout<<total<<endl;       //这是总方案数return 0;
}
int search(int s,int t)
{int i;for(i=a[t-1];i<=s;i++)if(i<n)                //当前数i要大于等于前1位数,且不过n{a[t]=i;            //保存当前拆分的数is-=i;              //s减去i,s的值继续拆分if(s==0) print(t);  //s==0  拆分结束输出结果else search(s,t+1); //s>0,继续递归s+=i;               //回溯:加上拆分的数,以便产分所有可能的拆分}return 0;
}
int print(int t)
{total++;cout<<n<<"=";for(int i=1;i<=t;i++){if(i==t){cout<<a[i];cout<<endl;}else  cout<<a[i]<<"+";}
}


  相关解决方案