puzzleup 2020 11月开始

〇〇

newkid 发表于 2020-11-25 23:40
#4 CANDIES There are two boxes each having 10 candies. You will randomly (with equal probability) se ...

1/8 ?

1. 
   
2. #include<stdio.h>
   
3. #include<stdlib.h>
   
4. #include<time.h>
   
5. int f()
   
6. {
   
7. int a[2]={10,10};
   
8. for(int j=0;j<15;j++)
   
9. {
   
10. a[rand()%2]--;
    
11. if(a[0]==0 || a[1]==0) break;
    
12. }
    
13. return (a[1]==5 || a[0]==5);
    
14. 
    
15. }
    
16. int main()
    
17. {
    
18. int N=10000;
    
19. int n=0;
    
20. srand(time(NULL));
    
21. for (int i=0;i<N;i++)
    
22. n+=f();
    
23. printf("%d/%d\n",n,N);
    
24. }
    

复制代码

newkid

干嘛要用随机数模拟？总共也没多少种，SQL暴力解决。手算也不难。

solomon_007

# 4

                       
--method 1:
SQL>
SQL> with t as (select level n from dual connect by level<=20),
  2       s as (select substr(sys_connect_by_path(n,','),2) path
  3               from t
  4               where level = 5
  5               connect by nocycle prior n < n ),
  6       r as (select path,regexp_substr(path,'[^,]+',1,level) v
  7                from s
  8               connect by prior path = path
  9                          and level <= regexp_count(path,',')+1
10                          and prior dbms_random.value is not null),
11       p as (
12            select count(distinct a.path) cnt
13              from (
14            select path,v,
15                   count(case when v <=10 then 1 end) over(partition by path) lt,
16                   count(case when v >=11 then 1 end) over(partition by path) gt
17             from r
18             ) a
19            where (lt = 5 and gt = 0) or (lt=0 and gt=5)
20           ),
21       q as (
22             select cnt,(select count(*) from s) as total_cnt from p),
23      f(total_cnt,cnt) as ( select total_cnt,cnt from q
24                             union all
25                            select greatest(total_cnt - cnt,cnt),least(total_cnt - cnt,cnt)
26                              from f
27                            where total_cnt <> cnt)
28      select q.cnt/f.cnt||'/'||q.total_cnt/f.cnt as res
29        from q,f
30       where f.total_cnt = f.cnt
31  /

RES
--------------------------------------------------------------------------------
21/646

solomon_007

method 2:

SQL> with t as (select level n from dual connect by level<=20),
  2       s(lvl,nlist,lt,gt,last_n) as (select 1,cast(n as varchar2(100)),
  3                                      case when n<=10 then 1 else 0 end,
  4                                      case when n>=10 then 1 else 0 end,
  5                                      n
  6                                 from t
  7                               union all
  8                              select lvl+1,
  9                                     s.nlist||','||t.n,
10                                     s.lt + case when t.n<=10 then 1 else 0 end,
11                                     s.gt + case when t.n>11 then 1 else 0 end,
12                                     t.n
13                                from s,t
14                               where s.lvl < 5
15                                 and s.last_n < t.n
16                             ),
17                q as (
18                select cnt,total_cnt
19                  from (
20                        select count(nlist) cnt
21                          from s
22                         where lvl = 5
23                         and (lt=5 and gt=0 or lt=0 and gt=5)
24                      ) a, (select count(*) total_cnt from s where lvl=5) b
25                ),
26    f(total_cnt,cnt) as ( select total_cnt,cnt from q
27                               union all
28                              select greatest(total_cnt - cnt,cnt),least(total_cnt - cnt,cnt)
29                                from f
30                              where total_cnt <> cnt)
31        select q.cnt/f.cnt||'/'||q.total_cnt/f.cnt as res
32          from q,f
33         where f.total_cnt = f.cnt
34             ;

RES
--------------------------------------------------------------------------------
21/646          

newkid

我感觉你的方法有问题。每吃一颗糖就是一次随机的二选一，概率乘以1/2。
假设初始状态(10,10),
第一颗之后变成(10,9) 以及 (9,10),
各占1/2,

第二颗之后状态是(10,8)(9,9)(9,9)(8,10)各占1/4。(9,9)的概率是1/4+1/4=1/2
你不妨套用一下自己的算法看能否得到上述结果。
题目要求的最终状态是(0,5)和(5,0)，每个状态概率1/2^15, 所以只要求出总共有多少条路径会到达这个状态。

solomon_007

newkid 发表于 2020-11-29 02:50
我感觉你的方法有问题。每吃一颗糖就是一次随机的二选一，概率乘以1/2。假设初始状态(10,10),第一颗之后变 ...

是啊，感觉做错了，我计算的是吃完15个糖，余下的5个都剩到一个盒子中的概率。理解错了！

solomon_007

newkid 发表于 2020-11-29 02:50
我感觉你的方法有问题。每吃一颗糖就是一次随机的二选一，概率乘以1/2。假设初始状态(10,10),第一颗之后变 ...

如果吃第11颗糖的时候前一状态为 （10，0），那么下一步的状态只能是 （9，0），不可能是 （10，-1）
再吃一颗，就只能是 （8，0）。。。所以这样 最终状态是(0,5)和(5,0)，每个状态概率1/2^15，这好像也不是吧

solomon_007

# 4

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 < 15
  8                     ),
  9        s as (
10              select count(case when (A=5 and B=0) or (A=0 and B=5) then 1 end) cnt,
11                     count(*) total_cnt
12                from t
13                where lvl = 15 and A >=0 AND B>=0
14              ),
15  f(total_cnt,cnt) as ( select total_cnt,cnt from s
16                                 union all
17                                select greatest(total_cnt - cnt,cnt),least(total_cnt - cnt,cnt)
18                                  from f
19                                where total_cnt <> cnt)
20          select s.cnt/f.cnt||'/'||s.total_cnt/f.cnt as res
21            from s,f
22           where f.total_cnt = f.cnt
23  /

RES
--------------------------------------------------------------------------------
21/**

不知道这个是不是对的。。。

solomon_007

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 < 15
  8                     ),
  9        s as (
10              select count(case when (A=5 and B=0) or (A=0 and B=5) then 1 end) cnt,
11                     count(*) total_cnt
12                from t
13                where lvl = 15 and A >=0 AND B>=0
14              ),
15  f(total_cnt,cnt) as ( select total_cnt,cnt from s
16                                 union all
17                                select greatest(total_cnt - cnt,cnt),least(total_cnt - cnt,cnt)
18                                  from f
19                                where total_cnt <> cnt)
20          select s.cnt/f.cnt||'/'||s.total_cnt/f.cnt as res
21            from s,f
22           where f.total_cnt = f.cnt
23  /

RES
--------------------------------------------------------------------------------
21 /1 0 1

solomon_007

38楼好像也不对，一盒吃完，另一盒可能剩10颗，9，8，。。。，0 都要考虑；  而且剩余5颗糖的时候，可能两个盒子都有。   都只考虑了后一半，前一半都没有考虑。所以不对。