请教大家一个Java递归求解组合数的基本算法问题

Question

本帖最后由 vicki007 于 2011-05-30 21:05:14 编辑

Answer 1

for example
class Test {
    public static void main(String[] args) {
        cal(9, 7, new StringBuilder());
    }    public static void cal(int n, int c, StringBuilder sb) {
        if (n < c) {
            return;
        }
        if (n == c) {
            for (int i=1; i<=n; i++) {
                sb.append("1");
            }
            System.out.println(sb);
            return;
        }
        if (c == 1) {
            sb.append(n);
            System.out.println(sb);
            return;
        }
        
        for (int i=1; i<=n; i++) {
            StringBuilder s = new StringBuilder(sb);
            s.append(i);
            cal (n-i, c-1, s);
        }    }
}

Answer 2

可以，不过就不用字符串作为参数了，用数组方便计算，这里给出了递归和非递归的方法，均方差的求法不知道对不对，LZ可以自己再作修改，另外，均方差打印时是以保留5位小数打印的，LZ也可以自行修改import java.util.*;
class Test {
    public static void main(String[] args) {
        //cal(9, 7, new StringBuilder()); //最开始的只有打印没有计算的递归
        //cal2(9, 7); //非递归
        cal3(9, 7, new int[7], 0); //递归
    }    public static void cal(int n, int c, StringBuilder sb) {
        if (n < c) {
            return;
        }
        if (n == c) {
            for (int i=1; i<=n; i++) {
                sb.append("1");
            }
            System.out.println(sb);
            return;
        }
        if (c == 1) {
            sb.append(n);
            System.out.println(sb);
            return;
        }
        
        for (int i=1; i<=n; i++) {
            StringBuilder s = new StringBuilder(sb);
            s.append(i);
            cal (n-i, c-1, s);
        }    }    public static void cal2(int n, int c) { //非递归方法
        int max = n-c+1;
        int[] idx = new int[c];
        Arrays.fill(idx, 1);
        int sum = 0;
        while (true) {
            sum = 0;
            for (int i=0; i<idx.length; i++) {
                sum += idx[i];
            }
            if (sum == n) {
                System.out.printf("%s : %.5f\n", Arrays.toString(idx), ev(idx));
            }
            idx[idx.length-1]++;
            for (int i=idx.length-1; i>0; i--) {
                if (idx[i]-1 == max) {
                    idx[i] = 1;
                    idx[i-1]++;
                }
            }
            if (idx[0] == max) {
                System.out.printf("%s : %.5f\n", Arrays.toString(idx), ev(idx));
                break;
            }
        }
    }    public static void cal3(int n, int c, int[] a, int k) { //递归方法
        if (n < c) {
            return;
        }
        if (n == c) {
            for (int i=1; i<=n; i++) {
                a[k+i-1] = 1;
            }
            System.out.printf("%s : %.5f\n", Arrays.toString(a), ev(a));
            return;
        }
        if (c == 1) {
            a[a.length-1] = n;
            System.out.printf("%s : %.5f\n", Arrays.toString(a), ev(a));       
            return;
        }
        
        for (int i=1; i<=n-c+1; i++) {
            a[k] = i;
            cal3(n-i, c-1, a, k+1);
        }
    }    public static double ev(int[] a) { //求均方差
        double e = 0.0;
        for (int i=0; i<a.length; i++) {
            e += a[i]; //和
        }
        e /= a.length; //平均数
        double ex = 0.0;
        for (int i=0; i<a.length; i++) {
            ex += Math.pow((e-a[i]), 2); //差平方和
        }
        ex /= a.length; //方差
        
        return Math.sqrt(ex); //方差平方根--均方差    }
}