puzzleup 2020 11月开始

newkid

solomon_007 发表于 2020-11-29 10:38
如果吃第11颗糖的时候前一状态为 （10，0），那么下一步的状态只能是 （9，0），不可能是 （10，-1）再吃一 ...

只要一个盒子吃光游戏就结束了，不可能从(10,0)继续变成(9,0)，(10,0)不可能是(5,0)路径上的点。
把这颗二叉树画出来，所有叶子的概率加起来等于1。
叶子的概率等于1/2的幂，指数为高度。
你先用每个盒子两三颗糖的简单情形模拟一下，把整棵树画出来。

dhhb

with t1 as
(select level-1 n1 from dual connect by level<=11),
t2
as
(select level-1 n2 from dual connect by level<=11),
t3 as (
select * from t1, t2),
t4 as (
select t3.* from t3 connect by
(prior n1=n1+1 and prior n2=n2 and prior n1<>0 and prior n2<>0) or (prior n1=n1 and prior n2=n2+1 and prior n2<>0 and prior n1<>0)
start with n1=10 and n2=10)
select count(1) ,sum(case when n1=0 and n2=5 then 1 when n2=0 and n1=5 then 1 else 0 end )
from t4 where (n1=0 and n2 >0 )or (n2=0 and n1>0)
4004/184756=0.02

newkid

dhhb 发表于 2020-11-29 22:15
with t1 as(select level-1 n1 from dual connect by level0)4004/184756=0.02

你用COUNT(1)做分母没有道理。这里面有枝有叶，高度也不一样，概率也不一样。
还是从我建议的简单例子入手去理解。

dhhb

newkid 发表于 2020-11-30 01:28
你用COUNT(1)做分母没有道理。这里面有枝有叶，高度也不一样，概率也不一样。还是从我建议的简单例子入手去 ...

大师我是有where条件的，只包含了叶子，全部的概率：
n   percent%
10 0.002
9  0.011
8  0.06
7  0.239
6  0.775
5  2.168
4  5.418
3  12.384
2  26.316
1  52.632

solomon_007

# 4



--全部叶子节点概率之和为1
SQL> with t(lvl,A,B) as (select 0,10,10 from dual
  2                       union all
  3                      select lvl+1,
  4                             case when n=1 then A-1 else A end,
  5                             case when n=2 then B-1 else B end
  6                       from t,(select 1 n from dual union all select 2 from dual) s
  7                      where lvl < 20
  8                        and A > 0
  9                        and B > 0
10                     )
11  select sum(p)
12  from (
13  select A,B,power(2,-1*lvl) p from t where A=0 or B=0
14  )
15  /

    SUM(P)
----------
         1



--所以本题结果的概率应该为：
SQL> col p format a30;
SQL>
SQL>
SQL> with t(lvl,A,B) as (select 0,10,10 from dual
  2                       union all
  3                      select lvl+1,
  4                             case when n=1 then A-1 else A end,
  5                             case when n=2 then B-1 else B end
  6                       from t,(select 1 n from dual union all select 2 from dual) s
  7                      where lvl < 20
  8                        and A > 0
  9                        and B > 0
10                     )
11  select sum(power(2,-1*lvl)) p from t where (A =0 AND B =5 ) or (A =5 AND B =0 )
12  /

                             P
------------------------------
               0.1221923828125                 

solomon_007

手工花简为分数：

SQL>
SQL>  with s as (select 10000000000000 total_cnt,1221923828125 cnt from dual),
  2   f(total_cnt,cnt) as ( select  total_cnt, cnt from s
  3                                  union all
  4                                 select greatest(total_cnt - cnt,cnt),least(total_cnt - cnt,cnt)
  5                                   from f
  6                                 where total_cnt <> cnt)
  7           select s.cnt/f.cnt||'/'||s.total_cnt/f.cnt as res
  8             from s,f
  9            where f.total_cnt = f.cnt
10  /

RES
--------------------------------------------------------------------------------
1001/8192

跟OO最先说的一样，差不多 1/8 .

solomon_007

newkid 发表于 2020-11-29 21:01
只要一个盒子吃光游戏就结束了，不可能从(10,0)继续变成(9,0)，(10,0)不可能是(5,0)路径上的点。把这颗二叉 ...

还是你的思路清晰，按照这个，45楼就应该是对的了！

newkid

dhhb 发表于 2020-11-30 13:13
大师我是有where条件的，只包含了叶子，全部的概率：n   percent%10 0.0029  0.0118  0.067  0.2396  0.775 ...

确实，没注意看你的WHERE条件只包含了叶子。
但是，叶子的概率（权重）不是全部一样，你不能简单地COUNT。
你把整棵树当作一个迷宫，每次分叉都一半概率，每个叶子当作迷宫的一个出口。那么，离入口越近就越容易走到，藏得越深越远就越不容易走到。

newkid

给猫猫转了章。

我的写法：没有必要每条路径都走到底，这样会快一些。

WITH t(box1,box2,lvl) AS (
SELECT 10,10,0 FROM DUAL
UNION ALL
SELECT DECODE(n,1,box1-1,box1)
      ,DECODE(n,2,box2-1,box2)
      ,lvl+1
  FROM t,(SELECT 1 n FROM DUAL UNION ALL SELECT 2  FROM DUAL)
WHERE (box1>=5 and box2>0) or (box2>=5 and box1>0)
)
select lvl,count(*)
from t where box1=5 and box2=0 or box2=5 and box1=0
group by lvl;

       LVL   COUNT(*)
---------- ----------
        15       4004

4004/power(2,15)=1001/power(2,13)=1001/8192

下面是手工算法：
假设(10,10)为初始状态，目标状态为(0,5)或者(5,0)。
每吃掉一颗糖到达的状态，概率为1/2^被吃糖数，所以每一种(0,5)或者(5,0)状态的概率为1/2^15
现在只需求出有多少条路径到达这两种状态。两种状态是对称的。
(0,5)状态下，第一盒吃掉10颗，第二盒吃掉5颗，需要求出吃掉顺序的组合。相当于把5颗放置到10颗中间有多少种方法。10颗连头尾总共有11个位置可以放置，但是由于最后一颗一定是第一盒，就剩下10个位置可以放置第二盒的5颗。
第二盒5颗的分配方法：
1组：C(10,1) = 10
2组：14,23,32,41 四种，C(10,2)*4 = 180
3组：113,131,311,122,212,221 共6种，C(10,3)*6 = 720
4组：1112,1121,1211,2111 四种，C(10,4)*4 = 840
5组：C(10,5) = 252

总和=2002

加上对称的(5,0)= 2002*2 = 4004

solomon_007

newkid 发表于 2020-11-30 22:14
给猫猫转了章。我的写法：没有必要每条路径都走到底，这样会快一些。WITH t(box1,box2,lvl) AS (SELECT 10, ...

  没有必要每条路径都走到底，对的。每个 （5，0）或（0，5）的叶子节点的概率都是
1/2^15