PUZZLEUP 2014

〇〇

newkid 发表于 2014-12-11 04:43
#20 Balls

There are six red balls and four black balls in a box. The balls are randomly drawn one ...

一个个就是要求排列,但颜色相同又要去除重复

〇〇

newkid 发表于 2014-12-11 04:43
#20 Balls

There are six red balls and four black balls in a box. The balls are randomly drawn one ...

不知道能否用归纳法,比如先用2红1黑
r1r2b --ok
r2r1b --ok
r1br2
r2br1
br1r2
br2r1
=1/3

newkid

第19题的第一个递归是不必要的：

VAR N NUMBER;
EXEC :N:=4;

WITH p AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') p,POWER(2,ROWNUM-1) id
  FROM (SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=:N)
WHERE LEVEL=:N
CONNECT BY NOCYCLE n<>PRIOR n
)
,l AS (
SELECT p1.p||SUBSTR(p1.p,1,:N-1) s,SUM(p2.id) all_id
  FROM p p1,p p2
WHERE INSTR(p1.p||SUBSTR(p1.p,1,:N-1),p2.p)>0
GROUP BY p1.p
)
,q(s,all_id) AS (
SELECT s,all_id
  FROM l        
UNION ALL
SELECT CASE WHEN SUBSTR(q.s,-2)=SUBSTR(l.s,1,2) THEN q.s||SUBSTR(l.s,3)
            ELSE  q.s||SUBSTR(l.s,2)
       END
      ,q.all_id+l.all_id
  FROM l,q
WHERE (SUBSTR(q.s,-2)=SUBSTR(l.s,1,2) OR SUBSTR(q.s,-1)=SUBSTR(l.s,1,1))
      AND BITAND(q.all_id,l.all_id)=0
)
SELECT MIN(s) KEEP(DENSE_RANK FIRST ORDER BY LENGTH(s)) s FROM q WHERE all_id=(SELECT SUM(id) FROM p);


123412314231243121342132413214321

newkid

第20题用手工算瞬间得到结果：

CREATE OR REPLACE FUNCTION P(N IN NUMBER,M IN NUMBER DEFAULT NULL) RETURN NUMBER
AS
  lv_ret NUMBER;
BEGIN
  lv_ret := 1;
  FOR i IN 1..NVL(M,N) LOOP
      lv_ret := lv_ret*(N-i+1);
  END LOOP;
  RETURN lv_ret;
END;
/

SELECT P(10)-P(4,1)*P(9)-P(6,1)*P(4,1)*P(8)-P(6,2)*P(4,2)*P(6)-2*P(6,3)*P(4,3)*P(4)-5*P(6,4)*P(4,4)*P(2) FROM DUAL;

725760

lastwinner

20# 可以想象成有5个抽屉，里面总共要装6个红球，每个抽屉里可以不装红球，也可以最多装6个红球，看看有多少种不同的安排方法，然后计算其中满足条件（or 不满足条件）的安排方法，最后就可以得到所需概率了

lastwinner

lastwinner 发表于 2014-12-12 10:58
20# 可以想象成有5个抽屉，里面总共要装6个红球，每个抽屉里可以不装红球，也可以最多装6个红球，看看有多少 ...

红球不是一直都比黑球大的排列方式数量为
  1  with t as (select rownum-1 n from dual connect by rownum<=7)
  2  select count(*) from (
  3      select a.n, b.n, c.n, d.n, e.n from t a, t b, t c, t d ,t e
  4           where a.n+b.n+c.n+d.n+e.n=6
  5             and (a.n=0
  6                  or a.n+b.n<=1
  7                  or a.n+b.n+c.n<=2
  8                  or a.n+b.n+c.n+d.n<=3)
  9* )
lastwinner@lw> /

  COUNT(*)
----------
       120


总的排列方式为：
lastwinner@lw>with t as (select rownum-1 n from dual connect by rownum<=7)
  2  select count(*) from (
  3      select a.n, b.n, c.n, d.n, e.n from t a, t b, t c, t d ,t e
  4           where a.n+b.n+c.n+d.n+e.n=6)
  5  /

  COUNT(*)
----------
       210


所以红球数量始终都比黑球大的概率为
(210-120)/210=3/7

lastwinner

newkid 发表于 2014-12-11 22:45
第20题用手工算瞬间得到结果：

CREATE OR REPLACE FUNCTION P(N IN NUMBER,M IN NUMBER DEFAULT NULL) R ...

红球都是一样的，黑球也都是一样的，不能看作是不同的

newkid

lastwinner 发表于 2014-12-12 11:07
红球都是一样的，黑球也都是一样的，不能看作是不同的

把同色的球区别对待也是没错的；如果分子分母都含有相同的排列数作为公约数，你说的也没错。
比如：第一个球黑色的概率，4/10
如果把每个球都编号，那么算法变成 P(4,1)*9!/10!
两种结果相同。我把所有球都编号是为了防止漏算。

这道题说的是只要黑球大于等于红球数就算赢，那么我们哪怕只考察前两个:
黑=4/10
红黑=(6/10)*(4/9)
至此黑球胜出的概率为：2/3
后面还有。

你算出的黑球胜率为 4/7, 这甚至比前两轮的胜率还低，显然不对。你把公式说明一下。

newkid

把所有黑胜的结果及其概率列出：

黑: =4/10 = 2/5
红黑: =(6/10)*(4/9) = 4/15
红红黑黑: =(6/10)*(5/9)*(4/8)*(3/7) = 1/14

红红红黑黑黑: =(6/10)*(5/9)*(4/8)*(4/7)*(3/6)*(2/5) = 2/105
红红黑红黑黑: =(6/10)*(5/9)*(4/8)*(4/7)*(3/6)*(2/5) = 2/105

红红红红黑黑黑黑:= (6/10)*(5/9)*(4/8)*(3/7)*(4/6)*(3/5)*(2/4)*(1/3) = 1/210
红红红黑红黑黑黑:= (6/10)*(5/9)*(4/8)*(4/7)*(3/6)*(3/5)*(2/4)*(1/3) = 1/210
红红红黑黑红黑黑:= (6/10)*(5/9)*(4/8)*(4/7)*(3/6)*(3/5)*(2/4)*(1/3) = 1/210

红红黑红红黑黑黑:= (6/10)*(5/9)*(4/8)*(4/7)*(3/6)*(3/5)*(2/4)*(1/3) = 1/210
红红黑红黑红黑黑:= (6/10)*(5/9)*(4/8)*(4/7)*(3/6)*(3/5)*(2/4)*(1/3) = 1/210


总和=2/5+4/15+1/14+2/105+2/105+1/210+1/210+1/210+1/210+1/210=4/5

所以红胜的概率=1-4/5=1/5

我上面的公式结果=725760/10!=1/5

newkid

看出问题来了，你的黑胜条件有误，以第一个黑球出现为例，前面有0,1个红球都算黑胜，所以条件必须为a.n<=1而不是a.n=0。后面的类推：

with t as (select rownum-1 n from dual connect by rownum<=7)
select count(*) from (
     select a.n, b.n, c.n, d.n, e.n from t a, t b, t c, t d ,t e
          where a.n+b.n+c.n+d.n+e.n=6
            and (a.n<=1
                 or a.n+b.n<=2
                 or a.n+b.n+c.n<=3
                 or a.n+b.n+c.n+d.n<=4)
);

  COUNT(*)
----------
       168

这就和我算出来的一样了。