数的划分(NOIP2001)
【问题描述】
将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。
例如:n=7,k=3,下面三种分法被认为是相同的。 1，1，5； 1，5，1； 5，1，1；
问有多少种不同的分法。
【输入格式】
n,k (6<n≤200，2≤k≤6)
【输出格式】
一个整数，即不同的分法。
【输入样例】
7 3
【输出样例】
4
{4种分法为：1,1,5；1,2,4；1,3,3; 2,2,3 说明部分不必输出}
1. //回溯 递推 全排列 超时 2. #include<iostream> 3. #include<cstdio> 4. #include<iomanip> 5. using namespace std; 6. int n,k,sum=0; 7. int s[8]={0}; 8. int main() 9. { 10. cin>>n>>k; 11. int i=1; 12. while(i){ 13. s[i]++; 14. if(s[i]>n) i--; 15. else if(i==k){ 16. int su=0; 17. for(int j=1;j<=k;j++) su+=s[j]; 18. if(n==su) sum++; 19. } 20. else{ 21. i++; 22. s[i]=s[i-1]-1; 23. } 24. } 25. cout<<sum; 26. return 0; 27. }
1. //递归法 2. #include<iostream> 3. #include<cstdio> 4. #include<iomanip> 5. using namespace std; 6. int n,k; 7. int fin(int a,int b,int c) 8. { 9. int sum=0; 10. if(b==1) sum=1; 11. else { 12. for(int i=c;i<=a/b;i++) 13. sum+=fin(a-i,b-1,i); 14. } 15. return sum; 16. } 17. int main() 18. { 19. cin>>n>>k; 20. cout<<fin(n,k,1); 21. return 0; 22. }
1. //动态穷举 剪枝 2. #include<iostream> 3. #include<cstdio> 4. #include<iomanip> 5. using namespace std; 6. int n,k,sum=0; 7. int min(int x,int y) 8. { 9. if(x<y) return x; 10. else return y; 11. } 12. void work(int a,int b,int c) 13. { 14. int i; 15. if(a==0) sum++; 16. else { 17. for(i=min(b-a+1,c);i>=b/a;i--) 18. work(a-1,b-i,i); 19. } 20. } 21. int main() 22. { 23. cin>>n>>k; 24. work(k,n,n); 25. cout<<sum; 26. return 0; 27. }
1. //递推 找到递推方程 2. #include<iostream> 3. #include<cstdio> 4. #include<iomanip> 5. using namespace std; 6. int n,k; 7. int s[201][7]={0}; 8. int main() 9. { 10. cin>>n>>k; 11. s[0][0]=1; 12. for(int i=1;i<=n;i++) s[i][1]=1; 13. for(int i=1;i<=n;i++) 14. for(int j=2;j<=(min(i,k));j++) 15. for(int t=1;t<=(min(i,j));t++) 16. s[i][j]+=s[i-t][min(i-t,t)]; 17. cout<<s[n-k][k]; 18. return 0; 19. }
