【例题2-5】整数的划分

3 = 1 + 1 +1
3 = 2 + 1
3 = 3
则q(n,m)表示n的划分中最大值不超过m的方案书,q(3,3)=3.

【题解】

q(n,m)=q(n-m,m)+q(n,m-1);//放一个m在开头+不放m在开头然后尝试<=m-1
q(0,m)=1; ①
n<0 || m<=0 ->f(n,m)=0 ②
①在②前。

【代码】

复制代码#include <cstdio> #define ll long long using namespace std; //计算n的划分个数,其中最大数不超过m ll q(int n,int m){ if (n==0) return 1;//0的划分只有一个,那就是它本身 if (n<0 || m<=0) return 0; if (n<m) return q(n,n); return q(n-m,m) + q(n,m-1); //放一个m在开头+不放m了 } int main(){ int n,m; scanf("%d%d",&n,&m); printf("%lldn",q(n,m)); return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#define ll long long
using namespace std;
//计算n的划分个数,其中最大数不超过m
ll q(int n,int m){
if (n==0) return 1;//0的划分只有一个,那就是它本身
if (n<0 || m<=0) return 0;
if (n<m) return q(n,n);
return q(n-m,m) + q(n,m-1); //放一个m在开头+不放m了
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
printf("%lldn",q(n,m));
return 0;
}