puzzleup 2018

〇〇

打电话  THE TELEPHONE GAME THE TELEPHONE GAME  2 people sit on a round table to play a variation of the telephone game. They are numbered from 1 to 12 in clockwise order, i.e. the people with adjacent numbers (including 1 and 12) sit next to each other. Person #1 chooses a secret word and starts the game by randomly selecting one of the two neighbors and whispering the word to that person. Upon hearing the word, each person continues the game by randomly selecting one of the neighbors and whispering the word. The game ends when everyone knows the secret word.  What is the probability that the last person whispering the word is numbered 6?  Enter your answer as a reduced fraction. Example: 123/4567

newkid

就是说，所有的UTF-8字符全是敏感词？

solomon_007

12 #

概率大约 0.094

solomon_007

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

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

solomon_007

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

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

solomon_007

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

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

lugionline