一个经典的问题,将正整数n表示成一系列正整数之和:n=n1+n2+…+nk, 其中n1≥n2≥…≥nk≥1,k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。 例如正整数6有如下11种不同的划分。 要求: 1、输入一个数字,例如6; 2、输出,格式如下: 6; 5+1; 4+2,4+1+1; 3+3,3+2+1,3+1+1+1; 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1。 实现代码如下: import java.util.HashMap; import java.util.Map; public class Test { private static void getString(String t, int h, int o, Map<String, String> map) { if (h > o) { getString(t, o, o, map); } else { if (h < o) { getString(h + "+" + t, h, o - h, map); for (int i = h - 1; i >= 2; i--) { getString(h + "+" + t, i, o - h, map); } } else { String out = h + "+" + t; out = out.substring(0, out.length() - 1); map.put(out, out); for (int i = h - 1; i >= 2; i--) { getString(t, i, o, map); } } String out = t + ""; for (int x = 0; x < o; x++) out = 1 + "+" + out; out = out.substring(0, out.length() - 1); map.put(out, out); } } public static void outAll(int n) { Map<String, String> map = new HashMap<String, String>(); getString("", n, n, map); for (String key : map.keySet()) { System.out.println(key); } } public static void main(String[] args) { outAll(6); } } |
|