puzzleup 2021

solomon_007

〇〇 发表于 2021-11-3 21:57
cte可以模拟，但不知道怎么计算平均值

CTE 检测有循环，不好使。。。

solomon_007

# 10
模拟

SQL> with function f_dart
  2  return int
  3  is
  4  
  5    type t_seg is table of int index by pls_integer;
  6    l_seg t_seg;
  7  
  8    l_total int := power(2,20)-1;
  9    l_bit_sum int;
10    l_sign    int;
11    l_tmp     int;
12  begin
13  
14    l_seg(1) := trunc(dbms_random.value(1,21));
15    l_bit_sum := power(2,l_seg(1)-1);
16  
17    while (l_bit_sum < l_total) loop
18  
19      l_sign := trunc(dbms_random.value(1,3));
20      l_tmp := case when l_sign =1 then
21                       case when l_seg(l_seg.count) = 1 then 20
22                            else l_seg(l_seg.count) - 1
23                       end
24                     else
25                       case when l_seg(l_seg.count) = 20 then 1
26                            else l_seg(l_seg.count) + 1
27                       end
28                end;
29  
30      l_seg(l_seg.count+1) := l_tmp;
31  
32      if bitand(l_bit_sum,power(2,l_tmp -1)) =0 then
33        l_bit_sum := l_bit_sum + power(2,l_tmp -1);
34      end if;
35    end loop;
36  
37    return l_seg.count;
38  end;
39  select avg(f_dart) from dual connect by level <= 100000
40  /

AVG(F_DART)
-----------
  190.81293

SQL> /

AVG(F_DART)
-----------
  191.16794

SQL> /

AVG(F_DART)
-----------
   191.2911

SQL> /

AVG(F_DART)
-----------
  190.58309

应该是 191

〇〇

我写cte死循环就放弃了

〇〇

第10题感觉就是（n-1）*n/2

〇〇

照搬猫猫的思路

import random

def game(n):
  total=pow(2,n)-1
  sum=1
  i=0
  last=1
  while sum<total:
    i+=1
    sig=round(random.random()*100000)%2
    if sig==0:
      last-=1
    else:
      last+=1
    if last>n:
      last=1
    elif last<1:
      last=n
    #print(last,end=',')
    sum |=pow(2,last-1)
  #print("i=",i)
  return i


def p(m,n):
  s=0
  for j in range(m):
    s+=game(n)
  return s/m

#p(10000,20)

for i in range(1,21)rint(i,round(p(1000*i,i)))

'''
1 0
2 1
3 3
4 6
5 10
6 15
7 21
8 28
9 36
10 45
11 55
12 66
13 78
14 91
15 104
16 120
17 135
18 153
19 171
20 191
'''

newkid

2和3答案就不对了。

solomon_007

我改参数后，1-20的模拟值

SQL> with function f_dart (p_n in int)
  2   return int
  3   is
  4  
  5     type t_seg is table of int index by pls_integer;
  6     l_seg t_seg;
  7  
  8     l_total int := power(2,p_n)-1;
  9     l_bit_sum int;
10    l_sign    int;
11    l_tmp     int;
12  begin
13  
14    l_seg(1) := trunc(dbms_random.value(1,p_n + 1));
15    l_bit_sum := power(2,l_seg(1)-1);
16  
17    while (l_bit_sum < l_total) loop
18  
19      l_sign := trunc(dbms_random.value(1,3));
20      l_tmp := case when l_sign =1 then
21                       case when l_seg(l_seg.count) = 1 then p_n
22                            else l_seg(l_seg.count) - 1
23                       end
24                     else
25                       case when l_seg(l_seg.count) = p_n then 1
26                            else l_seg(l_seg.count) + 1
27                       end
28                end;
29  
30      l_seg(l_seg.count+1) := l_tmp;
31  
32      if bitand(l_bit_sum,power(2,l_tmp -1)) =0 then
33        l_bit_sum := l_bit_sum + power(2,l_tmp -1);
34      end if;
35    end loop;
36  
37    return l_seg.count;
38  end;
39  t(n) as (select level from dual connect by level <= 20)
40  select n,(select round(avg(f_dart(n))) from dual connect by level <= 100000) avg_cnt
41    from t
42  /

         N    AVG_CNT
---------- ----------
         1          1
         2          2
         3          4
         4          7
         5         11
         6         16
         7         22
         8         29
         9         37
        10         46
        11         56
        12         67
        13         79
        14         92
        15        106
        16        120
        17        137
        18        154
        19        173
        20        191

20 rows selected

solomon_007

〇〇 发表于 2021-11-6 08:35
第10题感觉就是（n-1）*n/2

纠正一下，通项公式应该是： a(n) = 1 + n*(n-1)/2

solomon_007

newkid 发表于 2021-11-6 09:06
2和3答案就不对了。

加个 1 就应该是对的

jihuyao

Let me try first few steps and see what happens.  For group of 4, if 2/2 is even and each side is 1a+1b then 1a+1b<>2a (from any other groups) and all other groups only contains a and almost done.  Otherwise all  are a in group of 4.  If 2/2 are uneven, one side contains 1 or 2 and the other side contains 2a.  Now take 2 from any other group and compare with side 1 and side 2.  Since the new picked 2 can be either 2a or 1a+1b, side 1 or side 2 must be equal to the new picked 2.  The following need paper or better write a small program to track how many steps have been taken.  I read a article in sins.com about quality control using AI.  So basically it is the same topic but the method should be practical and scalable.