中文XML论坛--一个很难的数学算法大家进来帮帮小妹啊很急

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

相当于：8个不编号的球放入4个不编号的盒子，有几种放法咯。

用动态规划可以解吧。就不知道最好的解法是什么。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

import java.util.*

class Combines
{
    Vector allCombines = new Vector();
    int[] oneCombine;

    public static void main(String[] args)
    {
        int n=4, m=8;
        Combines c = new Combines();

        int [][] result = c.getAllCombines(n, m);

        for (int i=0; i<result.length; ++i)
        {
            for (int j=0; j<n; ++j)
            {
               System.out.print(result[i][j]+" ");
            }
            System.out.println();

        }
    }


    public int[][]  getAllCombines(int n, int m)
    {
        int [][] result;

        oneCombine = new int [n];

        getOneCombine(0, n, m);

        result = new int [allCombines.size()][n];

        for (int i=0; i<allCombines.size(); ++i)
        {
            ArrayList item = (ArrayList)allCombines.get(i);
            for (int j=0; j<n; ++j)
            {
                result[i][j] = ((Integer)item.get(j)).intValue();
            }
        }

        return result;
    }

    boolean isCurCombineCorrect(int m)
    {
        int sum = 0;

        for (int i=0; i<oneCombine.length; ++i)
        {
            sum += oneCombine[i];
        }

        if (sum == m)
        {
            return true;
        }

        return false;
    }

    boolean isArraylogicalEqual(ArrayList aItem, ArrayList bItem)
    {
        int length = aItem.size();
        int i=0, j=0;

        for (i=0; i<length; ++i)
        {
            boolean equal = false;
            int aVal = ((Integer)aItem.get(i)).intValue();

            for (j=0; j<length; ++j)
            {
                if ( aVal == ((Integer)bItem.get(j)).intValue() )
                {
                    equal = true;
                }
            }

            if (equal == false)
            {
                return false;
            }
        }

        for (i=0; i<length; ++i)
        {
            boolean equal = false;
            int aVal = ((Integer)bItem.get(i)).intValue();

            for (j=0; j<length; ++j)
            {
                if ( aVal == ((Integer)aItem.get(j)).intValue() )
                {
                    equal = true;
                }
            }

            if (equal == false)
            {
                return false;
            }
        }

        return true;
    }

    boolean isCurCombineExist()
    {
        ArrayList curItem = new ArrayList();


        for (int k=0; k<oneCombine.length; ++k)
        {
             curItem.add(new Integer(oneCombine[k])) ;
        }


        for (int i=0; i<allCombines.size(); ++i)
        {
            ArrayList aItem = (ArrayList)allCombines.get(i);

            if (isArraylogicalEqual(aItem, curItem))
            {
                return true;
            }
        }

        return false;
    }

    void getOneCombine(int index, int n, int m)
    {
        if (index >= n)
        {
            //got one!
            if (isCurCombineCorrect(m))
            {
                if (isCurCombineExist() == false)
                {
                    ArrayList item = new ArrayList();

                    for (int k=0; k<oneCombine.length; ++k)
                    {
                        item.add(new Integer(oneCombine[k]));
                    }

                    allCombines.addElement(item);
                }
            }

            return;
        }

        //for (int i=0; i<n; ++i)
        {
            for (int j=1; j<=m-n+1; ++j)
            {
                oneCombine[index] = j;
                getOneCombine(index+1, n, m);
            }
        }
    }

}

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

楼上,不用那么复杂吧!
我给一个VB写的程序:
Private Sub Command1_Click()
    Dim a() As String, k As Integer
    Dim m As Integer, n As Integer
    m = Val(Text1)
    n = Val(Text2)
    k = com(m, n, a)
    Text3 = k
    For i = 1 To k
        List1.AddItem a(i)
    Next i
End Sub

Private Function com(m As Integer, n As Integer, a() As String) As Integer
    Dim b() As String, k As Integer, k1 As Integer, s As Integer
    Dim idx As Integer
    ReDim a(0)
    If m = n Then
        ReDim a(1)
        For i = 1 To n - 1
            a(1) = a(1) & "1 "
        Next i
        a(1) = a(1) & "1"
        com = 1
    ElseIf n = 1 Then
        ReDim a(1)
        a(1) = CStr(m)
        com = 1
    Else
        For i = 1 To m - n + 1
            k = com(m - i, n - 1, b)
            u = UBound(b)
            For j = 1 To u
                k1 = InStr(b(j), " ")
                If k1 = 0 Then
                    s = Val(b(j))
                Else
                    s = Val(Mid(b(j), 1, k1 - 1))
                End If
                If i >= s Then
                    idx = idx + 1
                    ReDim Preserve a(idx)
                    a(idx) = CStr(i) & " " & b(j)
                End If
            Next j
        Next i
        com = UBound(a)
    End If
End Function

实在没有找到更好的论坛,还是凑合来这里吧

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

不晓得楼主要的是不这样,最笨的算法更好的还在想之中.
main()
{
  int i,j,k,l,sum,id;
  id=0;
  for(i=1;i<8;i++)
    {  sum=0;
       for(j=0;j<8;j++)
        for(k=0;k<8;k++)
           for(l=0;l<8;l++)
              {
                sum=i+j+k+l;
                if(sum==8)
                  id+=1;
               }
    }
   id=id+1;
   printf("the number is:%d",id);
}

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

/*by enorm*/
#include "stdio.h"
int cont [21];
void cal(int m,int n,int num)
{

if(m>20||n>20||n<=0||m<=0)
{

     return;
   }
   if(m<n)
   {
    return;
   }
   for(int i=1;i<=m-n+1;i++)
   {
    cont[n-1]=i;
    cal(m-i,n-1,num);
   }
   if(n==1)
   {
      for(int u=0;u<num;u++)
     printf("%d ",cont[u]);
   printf("\n");
}

}
void cal(int m,int n)
{
cal(m,n,n);
}
void main()
{
cal(15,5);

}

c语言精炼，呵呵

[此贴子已经被作者于2005-12-1 22:13:42编辑过]

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

能把规则在详细的说明一下吗？比如产生的只能是1-9数字吗？算法实现好象不是很难啊？可能效率很重要了吧？

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

package ieee;

public class Composite {

public void getComposite(int a, int b) {

int n = 0;
int y = 0;

  for (double i = Math.pow(10, b - 1); i < Math.pow(10, b) - 1; i++) {
   // 每个数
   String itos = String.valueOf((int) i);

   for (int j = 0; j < itos.length(); j++) {
    // 每个数字
    String temp = itos.substring(j, j+1);
    y = y + Integer.parseInt(temp);
   }
   if (y == a)
    n++;
   y = 0;
  }
  System.out.println(n);
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
new Composite().getComposite(8, 4);
}

}

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我大概写些思想和伪代码:
设m=8 ,n=4.按要求说我们可以理解为一个n层的树,只要树遍历到了,那么解也就出来了.那么树是怎么构造呢?
首先来看究竟m,n和树的层中元素有什么关系?m=8,n=4,也就是说位于第一层的元素必然满足这么一个关系:m-n+1,也就是说第一层最多可为5个元素,分别是5,4,3,2,1,第二层的构造是按照第一层中每个元素分别来构造,对于元素1来说,它的第二层元素为1,2,3,4,5;元素2为1,2,3,4.满足下面的关系式:
单个元素的下一层对应的元素个数 = m-当前层数-n+当前总值当前总值=遍历经过的元素值之和

有了上面的公式,用栈来实现遍历.

while((m-n+1)>0)
{
  Node.value = m-n+1;
  Node.floor = 1;
  Stack.push(Node);
  (m-n+1)--;
}
while(棧不为空){//构造下一层的元素，并放入棧中
tmpNode = stack.pop();
curfloor = tmpNode.floor+1;
curValue = curValue +tmpNode.value;
tmpTrace[curfloor -1 ] =curValue;
while(m-curValue-n+curfloor > 0 && curfloor <n)
{
  int i = m-curValue-n+curfloor ;
  Node.value = i;
  Node.floor = curfloor;
  stack.push(Node);
  (m-curValue-n+curfloor) --;
}
curfloor = tmpNode.floor;
if (curfloor = n-1)
{
  tmpTrace[curfloor+1]= m-curValue;
  if (compare(tmpTrace,Trace))//如果路径没有被遍历过，则放入到Trace中
  {
   把tmpTrace放入Trace中；//Trace用来保存遍历到的路径
  }
}
curValue = curValue - tmpNode.value;//把curValue恢复到没有修改以前，以便下个元素遍历
}
*/

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

真深奥啊我看不懂啊

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

#include <math.h>
#include <conio.h>

int main(])
{
unsigned long it, minit, maxit;
int n, m;
int s;
int r;
int count = 0;

scanf("%d, %d", &n, &m);

maxit = (unsigned long)pow(10.0, n);
minit = (unsigned long)pow(10.0, n-1);

for ( it = minit; it < maxit; it++ )
{
  r = it;
  s = 0;
  while(r>0)
  {
   s = s + (r % 10);
   r = r / 10;
  }

  if ( s == m )
  {
   printf("%8ld", it);
   count++;
  }
}

printf("\nCount = %d", count);

getch();

return 0;
}


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	156.250ms