2 u010918104 u010918104 于 2015.07.15 17:24 提问

求一个随机抽奖的算法

有没有这样一个算法,要求:
用n次随机结果代替排列组合的概率。
具体比如
枚举step1到20
a=(int)(10000/(20-step+1))
b=(int)(10000×random)
如果b小于a则认为该step被选中。同时该step到20为止都不再计算概率。这样就完成从20个数里即时选出一个数,同时我运行了1000w组,统计得到每个step被选中的频率都是0.05;每二十个数会选中一个。
那么有没有这样的算法可以实现: 我要从二十个数中选三个,每个数都有0.15的中选可能,同时每20个数中必中三个。

3个回答

Tiger_Zhao
Tiger_Zhao   Rxr 2015.07.16 11:36
已采纳

“20个数中必中三个”参考:从未知大小的n个数中取m个数,使各数被取出的概率相等
现在m=3,就算已知n=20也用不到。反正以20个为一组按这个算法选3。

u010918104
u010918104 嗯 这个办法 大大能不能回答下我后面这个问题,为什么在模拟次数多了以后会出现例外?是因为int的精度问题还是别的什么
2 年多之前 回复
u010918104
u010918104 嗯 这个办法 大大能不能回答下我后面这个问题,为什么在模拟次数多了以后会出现例外?是因为int的精度问题还是别的什么
2 年多之前 回复
u010918104
u010918104 嗯 这个办法 大大能不能回答下我后面这个问题,为什么在模拟次数多了以后会出现例外?是因为int的精度问题还是别的什么
2 年多之前 回复
u010918104
u010918104   2015.07.16 12:10

这个算法我明白了,把经典概率转化为条件概率就可以了,然后我写了这个
[code=java]
package choujiang;

public class hit {
public static int a[] = new int[21];
public static int b[] = new int[21];
public static int c[] = new int[21];
static boolean mark = false;// 记录是否发出一等奖
static int mark2 = 0;

boolean go_hit(int round) {// 伪随机方法
    int fate = 0;
    int rate = 0;
    boolean temp = false;
    if (mark == false) {
        rate = (int) (10000 / (20 - round + 1));
        fate = (int) (10000 * Math.random());
        if (fate < rate) {
            mark = true;
            temp = true;
        }
    } else {
        temp = false;
    }
    return temp;
}

boolean go_hit2(int round) {// 伪随机方法
    boolean temp = false;
    int fate = 0;
    int rate = 0;
    if (mark2 <= 3) {
        rate = (int) ((3 - mark2) * 1000 / (20 - round + 1));
        rate = (int) (rate / 0.95);
        fate = (int) (1000 * Math.random());
        if (fate <= rate) {
            mark2 = mark2 + 1;
            temp = true;
        }
    }
    return temp;
}

public static void main(String[] args) {
    int round = 0;
    for (int i = 0; i < 10000000; i++) {// 模拟1000000次
        hit see = new hit();
        round = 1;
        mark = false;
        mark2 = 0;
        while (round <= 20) {
            if (see.go_hit(round)) {
                a[round] = a[round] + 1;// 累计结果观察概率
                // System.out.println("一等奖" + round);// 模拟抽奖中奖过程
            } else {
                if (see.go_hit2(round)) {
                    b[round] = b[round] + 1;
                    // System.out.println("二等奖" + round);
                } else {
                    c[round] = c[round] + 1;
                    // System.out.println("三等奖" + round);
                }

            }
            round++;
        }
    }
    for (int i = 1; i < a.length; i++) {
        System.out.print("a" + i + "is" + "   " + a[i] + " ");// 查看概率
        System.out.print("b" + i + "is" + "   " + b[i] + " ");// 查看概率
        System.out.print("c" + i + "is" + "   " + c[i] + " ");// 查看概率
        System.out.println("*");
    }
}

}
[/code]
运行结果
a1is 500753 b1is 1501149 c1is 7998098 *
a2is 499482 b2is 1497660 c2is 8002858 *
a3is 500282 b3is 1496837 c3is 8002881 *
a4is 500130 b4is 1502287 c4is 7997583 *
a5is 499141 b5is 1500685 c5is 8000174 *
a6is 499022 b6is 1504222 c6is 7996756 *
a7is 499067 b7is 1501090 c7is 7999843 *
a8is 499833 b8is 1501011 c8is 7999156 *
a9is 500068 b9is 1504420 c9is 7995512 *
a10is 500269 b10is 1499587 c10is 8000144 *
a11is 499821 b11is 1507425 c11is 7992754 *
a12is 497801 b12is 1504257 c12is 7997942 *
a13is 500746 b13is 1508028 c13is 7991226 *
a14is 498638 b14is 1502178 c14is 7999184 *
a15is 500871 b15is 1502920 c15is 7996209 *
a16is 500978 b16is 1508363 c16is 7990659 *
a17is 500327 b17is 1508092 c17is 7991581 *
a18is 500772 b18is 1503604 c18is 7995624 *
a19is 500923 b19is 1495613 c19is 8003464 *
a20is 501076 b20is 1422746 c20is 8076178 *

有一个问题就是为什么我这里在20上的取值会少那么多,我加标记数组尝试了下,发现出现了不少二等奖只取两个数的特例,但是根据概率
P=(3-已取个数)/(20-位置+1)来看 就算前面一个不取,那最后三个的概率都是100%,为什么能出现只选择2个的情况???
@Tiger_Zhao

u010918104
u010918104 恩恩 搞清楚了我把两个概率分开看了才导致最后会出现要选两个数但总共只有一个数的情况。我直接把四个数看成等价的然后从四个数中再求一次独立事件的概率就好了,谢谢大大!
2 年多之前 回复
Tiger_Zhao
Tiger_Zhao 完全不对。那个算法是先把前m个放入备选数组,然后对剩下的n-m个按照各自个概率去替换备选数组中的(随机)某个成员。最后剩下的备选数组成员才是结果。
2 年多之前 回复
u010918104
u010918104   2015.07.16 14:00

贴下整理后的代码:

public class fullhit{
public static int geted = 0;
public static boolean task = false;
public static int[] a = new int[21];
public static int[] b = new int[21];
public static int[] c = new int[21];

boolean first_hit(int round) {
    boolean tempmark;
    tempmark = false;
    int rate = 0;
    int fate = 0;
    rate = (int) ((4 - geted) * 10000 / (20 - round + 1));
    fate = (int) (10000 * Math.random() + 1);
    if (fate <= rate) {
        tempmark = true;
        geted++;
    }
    return tempmark;
}

int socend_hit() {
    int r;
    int f;
    int tempint = 0;
    r = (int) 10000 / (4 - geted + 1);
    f = (int) (10000 * Math.random());
    if ((task == false) & (f <= r)) {
        tempint = 1;
        task = true;
    } else {
        tempint = 0;
    }
    return tempint;
}

public static void main(String[] args) {
    int round = 0;
    int s = 0;// 模拟楼层计数器
    int ta = 0;// 一等奖检测
    int tb = 0;// 二等奖检测
    boolean mark;// 检测:不符合每20个出现1个一等奖和3个二等奖就终止程序
    fullhit fh = new fullhit();
    for (int i = 1; i <= 10000000; i++) {//模拟10mX20个楼层
        round = 0;
        geted = 0;
        task = false;
        ta = 0;
        tb = 0;
        mark = true;
        while (round < 20) {
            round++;
            if (fh.first_hit(round)) {
                if (fh.socend_hit() == 1) {
                    // 模拟一等奖;
                    a[round]++;
                    ta++;
                } else {
                    // 模拟二等奖;
                    b[round]++;
                    tb++;
                }
            } else {
                // 模拟三等奖;
                c[round]++;
            }
        }
        if (ta != 1) {
            mark = false;
        }
        if (tb != 3) {
            mark = false;
        }
        if (mark == false) {
            System.out.println("error");
            break;
        }

    }
    for (int i = 1; i <= 20; i++) {
        // 查看选中概率
        System.out.print("a" + i + "的个数=" + a[i] + "("+a[i]/10000+"%。)|");
        System.out.print("b" + i + "的个数=" + b[i] + "("+b[i]/10000+"%。)|");
        System.out.print("c" + i + "的个数=" + c[i]+"("+c[i]/10000+"%。)");
        System.out.println("|");
        s = a[i] + b[i] + c[i];
    }
    System.out.println(s);
}
}
运行结果:

a1的个数=499824(49%。)|b1的个数=1497290(149%。)|c1的个数=8002886(800%。)|
a2的个数=500605(50%。)|b2的个数=1498930(149%。)|c2的个数=8000465(800%。)|
a3的个数=500648(50%。)|b3的个数=1498506(149%。)|c3的个数=8000846(800%。)|
a4的个数=498906(49%。)|b4的个数=1499513(149%。)|c4的个数=8001581(800%。)|
a5的个数=499420(49%。)|b5的个数=1501569(150%。)|c5的个数=7999011(799%。)|
a6的个数=499057(49%。)|b6的个数=1499303(149%。)|c6的个数=8001640(800%。)|
a7的个数=499637(49%。)|b7的个数=1500461(150%。)|c7的个数=7999902(799%。)|
a8的个数=499751(49%。)|b8的个数=1497757(149%。)|c8的个数=8002492(800%。)|
a9的个数=499362(49%。)|b9的个数=1500223(150%。)|c9的个数=8000415(800%。)|
a10的个数=500398(50%。)|b10的个数=1501744(150%。)|c10的个数=7997858(799%。)|
a11的个数=500780(50%。)|b11的个数=1499652(149%。)|c11的个数=7999568(799%。)|
a12的个数=501419(50%。)|b12的个数=1500825(150%。)|c12的个数=7997756(799%。)|
a13的个数=499531(49%。)|b13的个数=1498670(149%。)|c13的个数=8001799(800%。)|
a14的个数=500125(50%。)|b14的个数=1499623(149%。)|c14的个数=8000252(800%。)|
a15的个数=499369(49%。)|b15的个数=1500529(150%。)|c15的个数=8000102(800%。)|
a16的个数=500528(50%。)|b16的个数=1499332(149%。)|c16的个数=8000140(800%。)|
a17的个数=500256(50%。)|b17的个数=1501182(150%。)|c17的个数=7998562(799%。)|
a18的个数=500026(50%。)|b18的个数=1500794(150%。)|c18的个数=7999180(799%。)|
a19的个数=500726(50%。)|b19的个数=1501076(150%。)|c19的个数=7998198(799%。)|
a20的个数=499632(49%。)|b20的个数=1503021(150%。)|c20的个数=7997347(799%。)|
s=10000000
Csdn user default icon
上传中...
上传图片
插入图片