将递归改成循环

P(i,j)=P(i-1,j-1)*p0+P(i,j-1)*(1-p0)
其中p0已知。递归可以做，问各位大神如何改成循环来做呢？ 
补充一下，当i=0时候，返回1；当i>j时候返回0
我写的递归是
 
double p(i,j){
    double p0;//这是一个可以求出的数，这里就用常数来表示吧
    if(i==0){
    return 1;
}else if(i>j){
    return o;
}
else{
    return p(i-1,j-1)*p0 + p(i,j-1)*(1-p0);
}
 
}
 现在想换成循环来做，求各位大神帮忙！

9 个解决方案

#1

这东西要是用循环得控制N各循环变量，甭费那劲了，啥业务需要这么处理啊。

#2

引用 1 楼 chokio 的回复:

这东西要是用循环得控制N各循环变量，甭费那劲了，啥业务需要这么处理啊。

概率频繁模式挖掘算法中 求概率部分，因为针对小型数据库可以，如果大型事务数据库就会出现栈溢出

#3

给楼主指一条路吧，参考杨辉三角的做法，这样就可以不用递归，只用两个一维数组就能实现，难度挺小的。

#4

package com.tur.demo;

import java.util.Arrays;

public class Hello {
    /**
     * 递归实现
     * @param i
     * @param j
     * @return
     */
    static double p(int i, int j){
        double p0 = 0.6;//这是一个可以求出的数，这里就用常数来表示吧

        if(i == 0) { return 1; }
        if(i > j)  { return 0; }

        return p(i - 1, j - 1) * p0 + p(i, j - 1) * (1 - p0);
    }

    /**
     * 非递归实现
     * @param i
     * @param j
     * @return
     */
    static double pExt(int i, int j) {
        double p0 = 0.6;
        double[][] result = new double[100][100]; // 这个空间得根据你的数据空间来决定.

        Arrays.fill(result[0], 1);

        // 把二维数组换成两个一维数组，这样会节省很多空间.
        for (int row = 1; row <= i; ++row) {
            for (int col = 1; col <= j; ++col) {
                result[row][col] = result[row - 1][col - 1] * p0 + result[row][col - 1] * (1 - p0);
            }
        }

        for (int row = 0; row <= i; ++row) {
            for (int col = 0; col <= j; ++col) {
                System.out.printf("%-5f, ", result[row][col]);
            }
            System.out.println();
        }

        return result[i][j];
    }

    public static void main(String[] args) {
        System.out.println(p(5, 8));
        System.out.println(pExt(5, 8));
    }
}

输出：

0.5940863999999999
1.000000, 1.000000, 1.000000, 1.000000, 1.000000, 1.000000, 1.000000, 1.000000, 1.000000, 
0.000000, 0.600000, 0.840000, 0.936000, 0.974400, 0.989760, 0.995904, 0.998362, 0.999345, 
0.000000, 0.000000, 0.360000, 0.648000, 0.820800, 0.912960, 0.959040, 0.981158, 0.991480, 
0.000000, 0.000000, 0.000000, 0.216000, 0.475200, 0.682560, 0.820800, 0.903744, 0.950193, 
0.000000, 0.000000, 0.000000, 0.000000, 0.129600, 0.336960, 0.544320, 0.710208, 0.826330, 
0.000000, 0.000000, 0.000000, 0.000000, 0.000000, 0.077760, 0.233280, 0.419904, 0.594086, 
0.5940863999999999

做到这一步，下面的楼主应该会很容易实现了吧。

#5

再进一步，一个一维数组也能实现

#6

引用 4 楼 Inhibitory 的回复:

Java code?123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354package com.tur.demo; import java.util.Arrays; public class Hello {    /**    ……

万分感激，很清晰

#7

package com.tur.demo;

import java.util.Arrays;

public class Hello {
    /**
     * 递归实现
     * @param i
     * @param j
     * @return
     */
    static double p(int i, int j){
        double p0 = 0.6;//这是一个可以求出的数，这里就用常数来表示吧

        if(i == 0) { return 1; }
        if(i > j)  { return 0; }

        return p(i - 1, j - 1) * p0 + p(i, j - 1) * (1 - p0);
    }

    /**
     * 非递归实现
     * @param i
     * @param j
     * @return
     */
    static double pExt(int i, int j) {
        if(i == 0) { return 1; }
        if(i > j)  { return 0; }

        double p0 = 0.6;
        double[][] result = new double[100][100]; // 这个空间得根据你的数据空间来决定.

        Arrays.fill(result[0], 1);

        // 把二维数组换成两个一维数组，这样会节省很多空间.
        for (int row = 1; row <= i; ++row) {
            for (int col = 1; col <= j; ++col) {
                result[row][col] = result[row - 1][col - 1] * p0 + result[row][col - 1] * (1 - p0);
            }
        }

        for (int row = 0; row <= i; ++row) {
            for (int col = 0; col <= j; ++col) {
                System.out.printf("%5f, ", result[row][col]);
            }
            System.out.println();
        }

        return result[i][j];
    }

    static double pExt2(int i, int j) {
        if(i == 0) { return 1; }
        if(i > j)  { return 0; }

        double p0 = 0.6;
        double[] previous = new double[100];
        double[] current = new double[100];

        Arrays.fill(previous, 1);
        Arrays.fill(current, 1);

        for (int row = 1; row <= i; ++row) {
            for (int col = 0; col <= j; ++col) {
                current[col] =  (row > col) ? 0 : (previous[col - 1] * p0 + current[col - 1] * (1 - p0));
            }

            for (int col = 0; col <= j; ++col) {
                System.out.printf("%5f, ", current[col]);
            }

            System.out.println();

            double[] temp = previous;
            previous = current;
            current = temp;
        }

        return previous[j]; // 最因为最后current指向了i的下一行.
    }

    public static void main(String[] args) {
        System.out.println(p(8, 8));
        System.out.println(pExt(8, 8));
        System.out.println(pExt2(8, 8));
    }
}

#8

引用 7 楼 Inhibitory 的回复:

Java code?12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788package co……

谢谢啊！

#9

该回复于2013-04-15 09:54:23被管理员删除