puzzleup 2018

solomon_007 · 发表于 2018-10-19 00:06

SQL> set serveroutput on;
SQL>
SQL>
SQL> declare
  2 l_v int :=0;
  3 l_res number :=0;
  4  begin
  5
  6 delete from res;
  7
  8 for i in 1..10000 loop
  9    with t as (select level n from dual connect by level <= 12),
10    r as (select n,
11                   decode(n - 1, 0, 12, n - 1) left_n,
12                   case
13                   when n + 1 > 12 then
14                      mod(n + 1, 12)
15                   else
16                      n + 1
17                   end right_n
18             from t ),
19    s(lvl,list_n,curr_n) as (select 1,cast(1 as varchar2(4000)),1 from dual
20                               union all
21                               select lvl + 1,
22                                     s.list_n ||','||case when a.x =1 then r.left_n else r.right_n end,
23                                     case when a.x =1 then r.left_n else r.right_n end
24                               from s,r,(select ceil(dbms_random.value(0,2)) x from dual) a
25                               where (
26                                        instr(s.list_n,',2')=0
27                                     or instr(s.list_n,3)=0
28                                     or instr(s.list_n,4)=0
29                                     or instr(s.list_n,5)=0
30                                     or instr(s.list_n,6)=0
31                                     or instr(s.list_n,7)=0
32                                     or instr(s.list_n,8)=0
33                                     or instr(s.list_n,9)=0
34                                     or instr(s.list_n,10)=0
35                                     or instr(s.list_n,11)=0
36                                     or instr(s.list_n,12)=0
37                                     )
38                                  and s.curr_n = r.n
39                               )
40  select substr(list_n,instr(list_n,',',-1)+1) end_n
41 into l_v
42 from s
43 where lvl = (select max(lvl) from s);
44
45 insert into res values(i,l_v);
46
47 end loop;
48 commit;
49
50 select sum(case when v=6 then 1 end)/count(*) into l_res from RES;
51
52 dbms_output.put_line( 'result = '||l_res );
53  end;
54  /
result = .0945
PL/SQL procedure successfully completed

SQL> /
result = .0946
PL/SQL procedure successfully completed

SQL> /
result = .0878
PL/SQL procedure successfully completed

SQL> /
result = .0901
PL/SQL procedure successfully completed

SQL> /
result = .0935
PL/SQL procedure successfully completed

newkid · 发表于 2018-10-19 03:10

理论上讲是有可能永远绕不出来的，VARCHAR2(4000)也会溢出。不如用二进制位表示哪些人已经知道了。
要模拟的话用PLSQL比SQL好，因为我们只关心最后结果，里面绕来绕去的那些中间结果没必要保留。

solomon_007 · 发表于 2018-10-19 10:49

newkid 发表于 2018-10-19 03:10
理论上讲是有可能永远绕不出来的，VARCHAR2(4000)也会溢出。不如用二进制位表示哪些人已经知道了。
要模拟 ...

PLSQL 模拟：

SQL> set serveroutput on;
SQL>
SQL>
SQL> declare
  2 l_cnt int := 0;
  3 function end_n
  4 return pls_integer
  5 is
  6    type t_val is table of pls_integer index by pls_integer;
  7    l_val t_val;
  8    l_random int := 0;
  9    l_sum int := 0;
10    i int := 0;
11 c constant int default power(2,12)-1;
12 begin
13    l_val(1) := 1;
14    l_sum := l_val(1);
15    i := 2;
16
17    while l_sum < c loop
18       l_random := ceil(dbms_random.value(0,2));
19
20       if l_random = 1 then
21          l_val(i) := case when l_val(i-1) - 1 = 0  then 12 else l_val(i-1) - 1 end;
22       else
23          l_val(i) := case when l_val(i-1) + 1 > 12 then mod(l_val(i-1) + 1, 12) else l_val(i-1) + 1 end;
24       end if;
25
26       l_sum := (l_sum + power(2,l_val(i)-1)) - bitand(l_sum,power(2,l_val(i)-1));
27       i := i + 1;
28    end loop;
29
30    return l_val(l_val.last);
31 end;
32  begin
33 for i in 1..10000 loop
34    if end_n = 6 then
35    l_cnt := l_cnt + 1;
36 end if;
37 end loop;
38
39 dbms_output.put_line('result = '||l_cnt/10000);
40  end;
41  /
result = .089
PL/SQL procedure successfully completed

SQL> /
result = .0886
PL/SQL procedure successfully completed

SQL> /
result = .0929
PL/SQL procedure successfully completed

SQL> /
result = .0924
PL/SQL procedure successfully completed

SQL> /
result = .0933
PL/SQL procedure successfully completed

SQL> /
result = .0923
PL/SQL procedure successfully completed

newkid · 发表于 2018-10-19 22:52

你这个l_val的设计纯粹是浪费内存。只须一个变量表明当前是第几号。然后根据随机数决定下一个是几号。就这样传来传去，直到 l_sum = c 就把这个变量返回。
我建议用PLSQL就是为了避免存储这些中间结果，结果你还是用了l_val来保存每次结果。

solomon_007 · 发表于 2018-10-20 20:03

newkid 发表于 2018-10-19 22:52
你这个l_val的设计纯粹是浪费内存。只须一个变量表明当前是第几号。然后根据随机数决定下一个是几号。就这 ...

我的 return 前面有一段是测试用的

--for j in l_val.first .. l_val.last loop
-- dbms_output.put_line(l_val(j));
--end loop;

的确，用一个变量就够了：
SQL> set serveroutput on;
SQL>
SQL>
SQL> declare
  2 l_cnt int := 0;
  3 function end_n return pls_integer
  4 is
  5    l_val pls_integer := 0;
  6    l_random pls_integer := 0;
  7    l_sum pls_integer := 0;
  8    i       pls_integer := 0;
  9    c       constant pls_integer default power(2,12)-1;
10 begin
11    l_val := 1;
12    l_sum := l_val;
13    i := 2;
14
15    while l_sum < c loop
16       l_random := ceil(dbms_random.value(0,2));
17
18       if l_random = 1 then
19          l_val := case when l_val - 1 = 0  then 12 else l_val - 1 end;
20       else
21          l_val := case when l_val + 1 > 12 then mod(l_val + 1, 12) else l_val + 1 end;
22       end if;
23
24       l_sum := (l_sum + power(2,l_val-1)) - bitand(l_sum,power(2,l_val-1));
25       i := i + 1;
26    end loop;
27
28    return l_val;
29 end;
30  begin
31 for i in 1..10000 loop
32    if end_n = 6 then
33    l_cnt := l_cnt + 1;
34 end if;
35 end loop;
36
37 dbms_output.put_line('result = '||l_cnt/10000);
38  end;
39  /
result = .0894
PL/SQL procedure successfully completed

SQL> /
result = .0939
PL/SQL procedure successfully completed

SQL> /
result = .0916
PL/SQL procedure successfully completed

SQL> /
result = .0908
PL/SQL procedure successfully completed

SQL> /
result = .0904
PL/SQL procedure successfully completed

SQL> /
result = .0934
PL/SQL procedure successfully completed

solomon_007 · 发表于 2018-10-20 20:07

这个题要是用公式计算，那应该怎么做啊？。。。

lugionline · 发表于 2018-10-21 20:34

solomon_007 · 发表于 2018-10-21 22:41

lugionline 发表于 2018-10-21 20:34

Niubility！
前面听你科普过，好像又是什么马尔科夫链的东东。。。

newkid · 发表于 2018-10-22 21:33

lugionline 发表于 2018-10-21 20:34

这个公式是如何得到的? 其他编号的概率要怎么算?

solomon_007 · 发表于 2018-10-23 09:43

lugionline 发表于 2018-10-21 20:34

对啊，大神，给我们讲讲，公式一步一步怎么来的啊？

[每日一题] puzzleup 2018

浏览过的版块