自然数n的分解

输入自然数n（n<100），输出所有和的形式。不能重复。

如：4=1+1+2；4=1+2+1;4=2+1+1 属于一种分解形式。

样例：

输入：

输出：

7=1+6

7=1+1+5

7=1+1+1+4

7=1+1+1+1+3

7=1+1+1+1+1+2

7=1+1+1+1+1+1+1

7=1+1+1+2+2

7=1+1+2+3

7=1+2+4

7=1+2+2+2

7=1+3+3

7=2+5

7=2+2+3

7=3+4

分析：

假设n=a[1]+a[2]+...+a[n],为了避免分解重复，可以约定a[1]≤a[2]≤...≤a[n],

假设当前已经分解出cur项，待分解的数字为m(m=n-a[1]-a[2]...-a[cur]);

则 a[1],a[2],...,a[cur],m即是一种分解方案(cur>0)

如何继续分解呢，a[cur+1]=？

a[cur+1]的取值范围：a[cur]~m/2 (因为 m-a[cur+1]>=a[cur+1],则a[cur+1]/2<=m才能继续分解)

代码：

 #include<iostream>

 #include<cstring>

 using namespace std;

 int a[],b[];

 int s=, n;

 void dfs(int cur,int m){

     if (cur>){

         s++;

         cout<<n<<"=";

         for (int i=;i<=cur;i++) cout<<a[i]<<"+";

         cout<<m<<endl;

     }

      for (int i=a[cur];i<=m/;i++){

          a[cur+]=i;

         dfs(cur+,m-i);

         }

      }

 int main(){

     memset(a,,sizeof(a));

     memset(b,,sizeof(b));

     cin>>n;

     a[]=;

     dfs(,n);

     cout<<s<<endl;

     return ;

 }

巴特西

自然数n的分解

最新文章

热门文章