整数的分划问题。
如，对于正整数n=6，可以分划为：
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+1
现在的问题是，对于给定的正整数n,编写算法打印所有划分。
用户从键盘输入 n （范围1~10）
程序输出该整数的所有划分。
------解决方案--------------------
- Java code
package com.mine;public class DivInt { public static void dividedInt(int n, int maxDivid) { int i, sub = 0, res = 0, tmp = 0; int[] num = new int[n]; for(i=0; i<n; ++i)//初始化 { num[i] = 1; } num[sub++] = maxDivid; for(i=0; i<n; ++i)//输出 { tmp += num[i]; System.out.print(num[i] + " "); if(tmp == n) break; } System.out.println(); if(num[0] == 1 || num[0] == n || 1 == n-num[0]) return; while(true) { res = 0; if(num[sub] < num[0]) ++num[sub]; else if(num[sub] == num[0]) ++num[++sub]; for(i=0; i<=sub; ++i) res += num[i]; if(res <= n) { tmp = 0; for(i=0; i<n; ++i)//输出 { tmp += num[i]; System.out.print(num[i] + " "); if(tmp == n) break; } System.out.println(); } else if(res > n) break; } } public static void main(String[] args) { int i, num = 6; for(i=num; i>=1; --i) dividedInt(num, i); }}
------解决方案--------------------
- Java code
public static void main(String[] args) { int n = 10; //将这个整数拆分为若干个数字的和 int[] a = new int[n]; integer_divide(n, n, a, 0); } //使用递归来拆分 private static void integer_divide(int n, int max, int[] a, int level) { for(int i=max; i>0; i--) { a[level] = i; int sum = sumArray(a, level+1); if(sum==n) { printExpression(n, a, level+1); }else if(sum<n) { integer_divide(n, i, a, level+1); } } } //用于在拆分途中，检测当前这些因子的和是多少 private static int sumArray(int[] a, int length) { int sum = 0; for(int i=0; i<length; i++) { sum += a[i]; } return sum; } //打印出拆分表达式 private static void printExpression(int n, int[] a, int length) { System.out.print(n+" = " +a[0]); for(int i=1; i<length; i++) { System.out.print(" + "+ a[i]); } System.out.println(); }
------解决方案--------------------
自己去看,详细的很!记得给分!
http://www.cnblogs.com/hoodlum1980/archive/2008/10/11/1308493.html