拆解数字
论坛上看到的一个题目：
http://www.iteye.com/topic/963980
将任一个数字进行拆解，例如：
3 = 2+1 = 1+1+1 所以3有三種拆法
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五種
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1 共七种
随便给一个数字，对其进行拆解，并打印可拆解情况和拆解结果数。
public class SplitNum {public static void main(String[] args) {System.out.println("一共有" + splitNumber(10) + "种分法");}public static int splitNumber(int a) {return splitNumberWithMax(a, a, 0, a+" = ");}private static int splitNumberWithMax(int max, int tag, int c, String s) {if (tag == 1 || tag == 0) {System.out.println(tag == 1 ? (s + tag ) : s.substring(0,s.length()-2));c++;} else {for (int i = (max >= tag ? tag : max); i > 0; i--) {c = splitNumberWithMax(i, tag - i, c, s + i + " + ");}}return c;}}import java.util.Stack;public class SplitNum2 {public static void main(String[] args) {System.out.println(splitNum(200));}public static int splitNum(int tag){int a,b;int c = 0;Stack<Integer> s = new Stack<Integer>();s.push(tag);while(true){c++;System.out.print(c+":");print(s);while (!s.isEmpty() && s.peek() == 1) {s.pop();}if (s.isEmpty())break;a = s.pop();s.push(--a);do {b = tag - sum(s);if (b==0)break;s.push(a<b?a:b);} while (true);}return c;}private static int sum(Stack<Integer> s){int sum = 0;for (int i:s) {sum += i;} return sum;}private static void print(Stack<Integer> s){for (int i:s) {System.out.print(i+"+");} System.out.println();}}