蓝点杯 打印整数划分问题

本文主要是介绍蓝点杯 打印整数划分问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正整数n可能存在不同的划分，例如正整数6的全部划分为

6=6

6=5+1

6=4+2     6=4+1+1

6=3+3       6=3+2+1       6=3+1+1+1

6=2+2+2   6=2+2+1+1   6=2+1+1+1+1

6=1+1+1+1+1+1

在王晓东的书上有关本题的递归公式，但公式不好推，而且求的只是方案个数不满足本题题意。

仔细会发现其实本题就是一颗树。dfs+剪枝+数组保存轻松解决。

public class Spit
{static int sum=0,num=0;static int t[]=new int[121];static void dfs(int n,int m){if(sum==m){System.out.print(m+"=");for(int k=1;k<n-1;k++)System.out.print(t[k]+"+");System.out.println(t[n-1]);num++;}else{for(int i=m-n+1;i>=1;i--){sum+=i;if(sum<=m){if(i<=t[n-1]){t[n]=i;dfs(n+1,m);}}	sum-=i;}}}public static void main(String args[]){Scanner cin=new Scanner(System.in);while(cin.hasNext()){int n=cin.nextInt();t[0]=120;dfs(1,n);System.out.println("一共有"+num+"方案.");num=0;}}
}

这篇关于蓝点杯 打印整数划分问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---