求自然数n的加法分解要求返回所有等式
如题:4可以分解成1+1+1+1,1+1+2,2+2,1+3;5可以分解成1+1+1+1+1,1+1+1+2,1+2+2,1+1+3,2+3,1+4;编程要求输入自然数n返回或显示所有等式,顺序不要紧,不能重复,要求用C#编其他无所谓出来结果就好.小弟应聘机试两小时败在这个上了,回来后自己苦思n小时无解,不解决这题誓不罢休,特上csdn想各位大侠请教!分不多却是我的所有分了.算法精妙或程序精壮的话更好!

在网上找到相关资料如下:如有用可以参考,注意下面求的是分解的个数,上面题目的分解的个数相当于q(n,n-1);
// 正整数n的一个这种表示称为正整数n的一个划分。
// 正整数n的不同的划分个数称为正整数n的划分数。
// 求划分数
// 将最大数n1不大于m的划分个数记作q(n,m)。
// 递归关系如下:
// 1、q(n,1) = 1 , n >= 1;
// 2、q(n,m) = q(n,n) , m >= n;
// 3、q(n,n) = 1 + q(n,n-1);
// 4、q(n,m) = q(n,m-1) + q(n-m,m) , n > m > 1;

////////////////////////////////////////
#include "iostream.h"

int q( int n , int m )
{
if( n < 1 || m < 1 )
return 0;
if( n == 1 )
return 1;
if( m == 1 )
return 1;
if( n < m )
return q( n , n );
if( n == m )
return q( n , m - 1 ) + 1;
return q( n , m - 1 ) + q( n - m , m );
}
void main()
{
cout<<q(6,6)<<endl;
}

------解决方案--------------------
改成这样吧
class TreeNode
{
public List<TreeNode> Sons = new List<TreeNode>();
public int Value;
public TreeNode(int v)
{
Value = v;
}
public string[] StringList
{
get
{
List<string> ret = new List<string>();
if (Sons.Count == 0) ret.Add("");
else
foreach (var son in Sons)
{
foreach (var stringList in son.StringList)
{
ret.Add(string.Format("{0} {1}", son.Value, stringList));
}
}
return ret.ToArray();

}
}

调用时列出StringList的值。
------解决方案--------------------

C# code

using System;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;ockets