将正整数n拆分为若干数之和,但是和式中相邻两数的奇偶性必须不相同.例如对于6,6=1+2+3、6=3+2+1、6=1+2+1+2等,但是6=2+4不合法。那么对于n的拆分,共有多少中不同的和式?
输入:3
输出:3
说明:3=1+2、3=2+1、3=3
将正整数n拆分为若干数之和,但是和式中相邻两数的奇偶性必须不相同.例如对于6,6=1+2+3、6=3+2+1、6=1+2+1+2等,但是6=2+4不合法。那么对于n的拆分,共有多少中不同的和式?
输入:3
输出:3
说明:3=1+2、3=2+1、3=3
望采纳!
#include<bits/stdc++.h>
using namespace std;
int t=0,a[40],n,f[31],summ=0,top=0;
void dfs(int index)
{
if(summ==n)
{
t++;
cout<<n<<"=";
for(int i=0;i<top;i++)
{
if(i!=0)
cout<<"+";
cout<<a[i];
}
if(t!=4&&a[0]!=n) cout<<";";
else
{
cout<<endl;
t=0;
}
return ;
}
if(summ>n)
return ;
for(int i=index;i<=n;i++)
{
a[top++]=i;
summ+=i;
dfs(i);
summ-=i;
top--;
}
}
int main()
{
cin>>n;
dfs(1);
return 0;
}