算法求解,想了好几天没想明白

sorry,我也迷糊了,也可以的

最笨的方法
int n=0;
for(int i=0; i<10; i++){
    for(int j=0; j<10; j++){
       int k = i+j;
       if(k==10){
         n++
       }
    }
}

比较笨的方法,一定有比这好的方法:
public class MyAdd
{ public static void main(String[] args)
{

    int i,j,m,n;
for(i=1;i<10;i++)
{
for(j=i;j<10;j++)
{
if(10==(i+j))
{
System.out.println("i="+i+"j="+j);
}

}
}

for(i=1;i<10;i++)
{
for(j=i+1;j<10;j++)
{
  for(m=j+1;m<10;m++)
  {
   if(10==(i+j+m))
{
System.out.println("i="+i+"j="+j+"m="+m);
}   }

}
}

for(i=1;i<10;i++)
{
for(j=i+1;j<10;j++)
{
  for(m=j+1;m<10;m++)
  {
    for(n=m+1;n<10;n++)
    {
     if(10==(i+j+m+n))
{
System.out.println("i="+i+"j="+j+"m="+m+"n="+n);
}     }

  }

}
}

}

}

to:liuzhiyuan
i=1j=9
i=2j=8
i=3j=7
i=4j=6
i=5j=5
i=1j=2m=7
i=1j=3m=6
i=1j=4m=5
i=2j=3m=5
i=1j=2m=3n=4
Press any key to continue...这样也不符合要求的,还有四位数相加,五位数相加,一直到九位树相加.
辛苦了!!!

import java.util.ArrayList;
import java.util.Iterator;public class TestAdd { /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] result=new TestAdd().getAddMethods(10);
for (int i=0;i<result.length;i++){
System.out.println("10="+result[i]);
}
} private String[] getAddMethods(int number) {

ArrayList result = new ArrayList();
if (number == 1) {
return new String[] { "1" };
}
for (int i = 1; i <= number-1; i++) {
String[] subMethods = getAddMethods(number - i);
for (int subIndex = 0; subIndex < subMethods.length; subIndex++) {
StringBuffer sb = new StringBuffer();
sb.append("" + i);
sb.append("+");
sb.append(subMethods[subIndex]);
result.add(sb.toString());
}
}
String resultArray[] = new String[result.size()];
int index = 0;
Iterator it = result.iterator();
while (it.hasNext()) {
resultArray[index++] = (String) it.next();
}
return resultArray; }}

再次强烈BS所有把超过20行运行结果全部放上来的人！！！我的想法
10 = 9 + 1，8 + 2，7 + 3 ...
也就是说10的算法，记作A(10)的个数=A(9) + A(8) + A(7) + ... + A(2) + A(1)
而A(9) = A(8) + A(7) + ... + A(2) + A(1)
A(8) = A(7) + ... + A(2) + A(1)
...

总共有42个结果
public class Main {
    public static void main(String[] args) {
      int count1=0;
      for(int j=2;j<=10;j++){
          for(int l=1;l<10/j;l++){
              count1+=a(l,j,10);
          }
      }
       System.out.println(String.valueOf(count1));
    }//这个函数里k代表起始的数字，m代表有几个数字相加，n为加起来的和
    public static int a(int k,int m,int n){

        int count=0;
        if(k>n/m) return 0;
        if(n==m)return 1;
        if(m==1)return 0;

        int i;
        int[] num=new int[m];
        for(i =0;i<num.length;i++)
            num[i]=n/m;
        for(i=k;i<=num[0];i++){
            if(m==2){
                num[1]=n-i;
                count++;
            }
            else
            count=count+a(i,m-1,n-i);
        }
                return count;
    }

}

例如算a(1,3,10)则要计算3个数相加为10的情况。
a函数第一次循环，返回的值为a(1,2,9),为4
第二次循环，返回值为a(2,2,8),为3
第三次循环，返回a(3,2,7)为1
不一一列举了

我也写了一个，还可以再优化,不过好像10有41种，和上面兄弟的结果不一样,hehe
public int foo(int n) {
int mArray[][] = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
  for (int j = 1; j < i; j++) {
   for (int k = 1; k <= Math.min(j, i - j); k++) {
    mArray[i][j] += mArray[i - j][k];
   }
    mArray[i][0] += mArray[i][j];
  }
  mArray[i][i] = 1;
}
return mArray[n][0];
}

应该是41种，
public class Main {
    public static void main(String[] args) {
      int count1=0;
      for(int j=2;j<=10;j++){
          //for(int l=1;l<10/j;l++){    这条语句没用
              count1+=a(1,j,10);   这条语句改为a(1,j,10)
          //}
      }
       System.out.println(String.valueOf(count1));
    }这个主函数里我多写了一个循环，搞错了

动态规划
mArray[i][j]代表和为i且加法表达式中最大数字为j的表达式数量

呵呵，我把我的程序和你的比较了一下，运行速度你的比我的快，尤其是计算数额很大的时候，比如说100
pfpf啊

public class TestDG {
    static int count=0;
    void setCount (int num){
        for(int i=1;i<num;i++){
            for(int j=1;j<num;j++){
                if(i+j==num)
                    count++;
            }
            setCount(i);
        }
    }
    int getCount(){
        return count;
    }    public static void main(String[] args) {
        TestDG testdg = new TestDG();
        testdg.setCount(10);
        System.out.println(testdg.getCount());
    }
}

zhuang_zi(庄子)的算法不错,li_kewei()也好,怎么给大家加分呀?不要笑话我哦

我的，用的是递归，改成迭代？
public class C2D2 {
    private static int nm;
    private static void addfacs( String prefix, int b, int n ) {
        prefix = prefix + b + '+'; // 不需要显示的话可以去掉
        for (int i=b; i<=n/2; i++)
            addfacs( prefix, i, n-i );
        System.out.println( prefix + n ); // 不需要显示的话可以去掉
        nm++;
    }

    public static void main( String[] args ) {
        int n = 10;
        nm = 0;
        for (int i=1; i<=n/2; i++)
            addfacs( "", i, n-i );
        System.out.println( "Total: "+nm );
    }
}

100的不重复方式有190569291种。不重复是指（不同时有1+2+1和1+1+2）。
不显示中间结果的情况下，耗时3453毫秒，递归会影响速度。--
http://www.agui.googlepages.com
mailto: agui.cn(a)gmail.com

调试易

算法求解,想了好几天没想明白

解决方案 »