各位老大,请教一个平方数的算法,不知道哪位赏脸给教导一下

Question

平方数:
众所周知，一个正整数可以分成若干个正整数的和（废话），现在我们把问题改一下。把一个正整数分成若干个平方数的和，显然这也是一定可以达到的。例如8＝4＋4＝2^2＋2^2 41＝4^2＋5^2 3＝1＋1＋1。但是现在试卷空格有限，不可能让你写n个1上去，所以我们需要最少的分拆。
Input
本题包含多组测试数据，每行是一个正整数n(1<=n<=100000)。 Output
  对于每个数据，需要输出两行，第一行为最少的平方数的数量，第二行是这些平方数的算术根，按升序输出。不需要多余的空格。如果有多种最优分拆，输出使前面的数尽量小的方案。 Sample Input
  23
  29Sample Output
 4
 1 2 3 3
 2
 2 5

Answer 1

Sorry,I don't kown,but,help you Up!  UP!

Answer 2

public static string GetSqrtList(int n)
{
string s = null;
while (n > 0)
{
int sqrt = (int)Math.Floor(Math.Sqrt(n));
s = sqrt.ToString() + " " + s;
n = n - sqrt;
}
return s.Trim()
}

Answer 3

jimh(Jimmy) ,不对啊..得到的是一个列表..但是他们的平方相加不等于我输入的数啊..

Answer 4

改了一下楼上朋友的程序： public static string GetSqrtList(int n)
{
string s = null;
int num=0;
while (n > 0)
{
int sqrt = (int)Math.Floor(Math.Sqrt(n));
s = sqrt.ToString() + " " + s;
num++;
n = n - (int)Math.Pow((double)sqrt,2);
}
return num+"\r\n"+s;
}

Answer 5

to min_jie(止戈):需不需要回溯，你用你的程序试试看就知道了。你的程序运行23得到的是1,1,1,2,4

Answer 6

//入口
public static string GetSqltList2(int n)
{
if(n == 1)
{
return "1\n1";
}
ArrayList temp = new ArrayList();
int sqrt = (int)Math.Floor(Math.Sqrt(n)); for(int i = sqrt; i > 0; i--)
{
GetN(i,ref temp, n);
}

string tttt = temp.Count.ToString() + "\n";
for(int i = 0; i < temp.Count; i++)
{
tttt +=  temp[i].ToString()+"    ";
}
return tttt;
}
//搭配。
public static void GetN(int i,ref ArrayList minal, int sum)
{
int tsum = 0;
ArrayList t = new ArrayList();
int j = i;
while(j >= 1)
{
tsum += j * j;
t.Add(j);
if(tsum == sum)
{
if(t.Count < minal.Count || minal.Count == 0)
{
minal = t;
}
break;
}
else if(tsum > sum)
{
tsum -= j * j;
t.RemoveAt(t.Count -1);
if(j > 1)
{
j--;
}
}
}
}