这题如果要求输出算式个数,有没有通项公式什么的?
以下是本人亲测数据:
2 1
3 2
4 4
5 6
6 10
7 14
8 21
9 29
10 41
11 55
12 76
13 100
14 134
15 175
16 230
17 296
18 384
19 489
20 626
21 791
22 1001
23 1254
24 1574
25 1957
26 2435
27 3009
28 3717
29 4564
30 5603
40 37337
50 204225
60 966466
70 4087967
80 15796475
(换个问法,时间复杂度的准确表达式是什么?)
以下为本人AC代码:
#include<bits/stdc++.h>
using namespace std;
int n;
int nums[105];
void dfs(int sumn,int numn,int maxn){
if (sumn==n)
{
for (int i=1;i<=numn-2;i++)
cout<<nums[i]<<"+";
cout<<nums[numn-1]<<endl;
return ;
}
if (sumn>n) return ;
for (int j=maxn;j<=n-1;j++)
{
nums[numn]=j;
dfs(sumn+j,numn+1,j);
nums[numn]=0;
}
}
int main()
{
cin>>n;
dfs(0,1,1);
return 0;
}