拆解数字

数学都不错啊 

C++版的：

/*
输入一个整数，如:整数7它的和为 N1+N2+...+Nk=7,且 N1>=N2>=..>=Nk(k>=1),
将其拆分，并打印出各种拆分.对于7有: 6+1=7..5+2=7....1+1+1+1+1+1+1=7共有14种拆分方法。
分解过程:
输入3:
				      (对5分解)  5=4+1             5=3+2   
				(用递归对4分解)    4=3+1     4=2+2
                			(用递归对3分解)      3=2+1
				(用递归对2分解)	 2=1+1
*/

#include<iostream>
#include<list>

using namespace std;

int count=0;//记录总的分解方法
int temp=0;

list<int> ilist;  //保存分解过程中产生的每种分解方法

void divide(int num, int flag);
void print(list<int> ilist, int num)	//打印每种分解方法
{
	list<int>::iterator ibegin, iend;
	ibegin=ilist.begin();
	iend=ilist.end();
	if(ibegin==iend)
	{
		cout<<"The list is empty!"<<endl;
		exit(EXIT_FAILURE);
	}
	cout<<num<<" = "<<*ibegin;
	ibegin++;
	while(ibegin!=iend)
	{
		cout<<"+"<<*ibegin;
		ibegin++;
	}
	cout<<endl;
}

int main()
{
	cout<<"Please inpu the num:"<<endl;
	int num;
	while(cin>>num , num<=0)
	{
		cout<<"请输入大于0的正整数!"<<endl;
	}
	temp=num;
	divide(num,1);//第二个参数可以改变(>0)
	cout<<"共有: "<<count<<" 种分法!"<<endl;
	return 0;
}

void divide(int num, int flag)
{

	if(num==flag)	//当num==flag时到了最底层的分解
	{
		if(!ilist.empty())
		{
			ilist.pop_front();
		}
		ilist.push_front(flag);
		
		print(ilist,temp);
		ilist.pop_front();  //当递归回退一层时删除list中的第一个元素
		return;
	}
	if(!ilist.empty())
	{
		print(ilist,temp);//每次进入divide一次就产生了一种分法,将其打印输出
	}
	for(int i=flag; i<=num/2; i++)
	{
		count++;

		if(!ilist.empty())		
		{
			ilist.pop_front();	//对于ilist.front()产生了一种分解方法，
		}
		ilist.push_front(i);	//将ilist.front()取出并将两分解元素push到ilist头部
		ilist.push_front(num-i);

		divide(num-i,i);//递归
	}
	if(!ilist.empty())
	{
		ilist.pop_front();//当递归回退一层时删除list中的第一个元素
	}	
}

  

 

来个清爽的，随手写的，不保证一定正确，简单测了一下，应该没有问题。

public class Test {

	public static LinkedList<Integer> stack = new LinkedList<Integer>();

	public static int num = 5;

	public static void main(String[] args) {
		stack.add(1);
		decompose(num);
	}

	// 为了避免重复，所以拆解以后后面的数据>=前面的数字：4=1+3或2+2,5=1+4或2+3...
	public static void decompose(int i) {
		for (int j = stack.getLast(); j <= i / 2; j++) {
			stack.add(j);
			// 首先拆解的第二个数是满足条件的，所以先打印出来，再递归拆解第二个数
			stack.add(i - j);
			print();
			stack.removeLast();
			decompose(i - j);
			stack.removeLast();
		}
	}

	public static void print() {
		System.out.print(num + "=");
		for (int i = 1; i < stack.size(); i++) {
			System.out.print(i < stack.size() - 1 ? stack.get(i) + "+" : stack.get(i));
		}
		System.out.println();
	}

}

5=1+4
5=1+1+3
5=1+1+1+2
5=1+1+1+1+1
5=1+2+2
5=2+3

public class SplitNum {
	public static void main(String[] args) {
		System.out.println("一共有" + splitNumber(20) + "种分法");
	}

	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;
	}
}

10 = 10
10 = 9 + 1
10 = 8 + 2
10 = 8 + 1 + 1
10 = 7 + 3
10 = 7 + 2 + 1
10 = 7 + 1 + 1 + 1
10 = 6 + 4
10 = 6 + 3 + 1
10 = 6 + 2 + 2
10 = 6 + 2 + 1 + 1
10 = 6 + 1 + 1 + 1 + 1
10 = 5 + 5
10 = 5 + 4 + 1
10 = 5 + 3 + 2
10 = 5 + 3 + 1 + 1
10 = 5 + 2 + 2 + 1
10 = 5 + 2 + 1 + 1 + 1
10 = 5 + 1 + 1 + 1 + 1 + 1
10 = 4 + 4 + 2
10 = 4 + 4 + 1 + 1
10 = 4 + 3 + 3
10 = 4 + 3 + 2 + 1
10 = 4 + 3 + 1 + 1 + 1
10 = 4 + 2 + 2 + 2
10 = 4 + 2 + 2 + 1 + 1
10 = 4 + 2 + 1 + 1 + 1 + 1
10 = 4 + 1 + 1 + 1 + 1 + 1 + 1
10 = 3 + 3 + 3 + 1
10 = 3 + 3 + 2 + 2
10 = 3 + 3 + 2 + 1 + 1
10 = 3 + 3 + 1 + 1 + 1 + 1
10 = 3 + 2 + 2 + 2 + 1
10 = 3 + 2 + 2 + 1 + 1 + 1
10 = 3 + 2 + 1 + 1 + 1 + 1 + 1
10 = 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1
10 = 2 + 2 + 2 + 2 + 2
10 = 2 + 2 + 2 + 2 + 1 + 1
10 = 2 + 2 + 2 + 1 + 1 + 1 + 1
10 = 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
10 = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
一共有42种分法

5的情况，实际上只有7种：
1 1 1 1 1
1 1 1 2
1 2 3
1 4
2 2 1
2 3
5

其实这个问题可以拆解为将 N元钱化成1，2...N-1,N 元硬币（其中有些硬币是假想出来的）的组合问题，比如将5元钱化成1，2，3，4，5的硬币组合
代码如下：

int[] a = new int[] { 1,2,3,4,5};
		int[] b = new int[6];
		int[] c = new int[6];

		System.out.println(System.currentTimeMillis());
		Arrays.fill(b, 1);
		for (int i = 1; i < a.length; i++) {
			for (int j = 1; j * a[i] <= 5; j++) {
				for (int k = 0; k + j * a[i] <= 5; k++)
					c[k + j * a[i]] += b[k];

			}
			for (int k = 1; k <= 5; k++) {
				b[k] += c[k];
				c[k] = 0;
			}
		}
		System.out.println("totally " + b[5] + " solutions.");
		System.out.println(System.currentTimeMillis());

呵呵，这个算法估计一般人是看不懂了，
给一个用递归实现的：

private static final int[] COINS = new int[] { 1, 2, 3, 4, 5};
         
         private static int SUM = 5;

	private static int count = 0;

	public static void main(String[] args) throws Exception {
		System.out.println(System.currentTimeMillis());
		calc(SUM, COINS.length-1, "");
		System.out.println("totally " + count + " solutions. ");
		System.out.println(System.currentTimeMillis());
	}

	private static void calc(int sum, int coinIdex, String pre) {
		if (sum <= 0) {
			if (sum == 0) {
				count++;
			}
		}
		for (int i = coinIdex; i >= 0; i--) {
			if (sum >= 0) {
				calc(sum - COINS[i], i, pre + " " + COINS[i]);
			}
		}
	}

对这类问题可以参考我的博客最近总结的“硬币分钱”问题http://hxz-qlh.iteye.com/

过程中 最后一个循环改成这样  不知有么有更好 。

for (int k = 0; k <=(i-j>j?j:i-j); k++) {
	dp[i][j] += dp[i - j][k];
}