puzzleup 2011

solomon_007

原帖由 newkid 于 2011-8-11 22:37 发表
奥数哥很久不来了，要不然请他指导一下。去年他说要研究哥德巴赫猜想，不知道搞出来没有，报纸上也没见报道。

这个陈景润做的1+2已经在传统的证明方法上达到了极致，如果没有全新的理论方法，不可能证明1+1。。。

历史上一元5次方程不存在公式解，按照传统的高等代数的理论是证明不出来的，因为有了伽罗华群论这一全新的理论，才被证明。。。

newkid

Q3:

Code Length

Each of the 26 letters of the English Alphabet are written on a card. All 26 cards are put in a bag. Cards are drawed from the bag randomly and put together to form codes. Each code must contain three vowels. When third vowel is drawn, we get a legitimate code and stop drawing cards.

The opearation is repeated for a long time. What is the expected mean codelength?

(The letters A, E, I, O and U are considered as vowels for this question)

编码长度

26个英文字母分别写作一张卡片上。所有26张卡放入一个袋子中。卡片被随机抽出组成编码。每个编码必须包含三个元音字母。当抽到第三个元音字母时，我们认为这是一个合法编码并停止抽取。

这个操作被长期重复。预期的平均编码长度是多少？

(本题提及的元音字母是A,E,I,O,U)

Ryan_Faith

看看~~

newkid

可以理解为：把26个字母全排列，第三个元音出现位置的平均值。

假设第三个元音出现位置为N(取值范围3-24)，其排列方法总共有：

C(5,3)*(N-1)!*3*C(26-5,N-1-2)*(26-N)!

求N的平均值。

newkid

如果上述公式没错，SQL写起来就是：

WITH f(lvl,prd) AS (
SELECT 0,1 FROM DUAL
UNION ALL
SELECT lvl+1,prd*(lvl+1)
FROM f
WHERE lvl<23
)
SELECT SUM(n*occ)/SUM(occ)
  FROM (SELECT n
              ,30*f1.prd*f2.prd/f3.prd/f4.prd*f5.prd occ
          FROM (SELECT LEVEL n FROM DUAL WHERE LEVEL>=3 CONNECT BY LEVEL<=24) n
              ,f f1
              ,f f2
              ,f f3
              ,f f4
              ,f f5
        WHERE f1.lvl=N-1
              AND f2.lvl=26-5
              AND f3.lvl=26-5-(N-1-2)
              AND f4.lvl = N-1-2
              AND f5.lvl = 26-N
       )
      ;

SUM(N*OCC)/SUM(OCC)
-------------------
               13.5

xqmei

= (min(length) + max(length) )/2 = (3+24)/2 = 13.5

newkid

原帖由 xqmei 于 2011-8-18 01:33 发表
= (min(length) + max(length) )/2 = (3+24)/2 = 13.5

你倒是省事。咱们简化一点，1234四个数，取到偶数即停，平均编码长度是多少？(1+3)/2=1.5 ?

newkid

1234的题：

SELECT AVG(LEAST(INSTR(S,'2'),INSTR(S,'4')))
  FROM (SELECT REPLACE(SYS_CONNECT_BY_PATH(N,','),',') S
          FROM (SELECT LEVEL N FROM DUAL CONNECT BY LEVEL<=4)
         WHERE LEVEL=4 CONNECT BY NOCYCLE LEVEL<=4 AND N<>PRIOR N
        );


AVG(LEAST(INSTR(S,'2'),INSTR(S,'4')))
-------------------------------------
                           1.66666667

guostong

问题1

假设 x 个人
各个entry的最小数目应该是 ceil(x/3)
一共是4个entry
排列是 ceil(x/3)^4

然后判断任意4个没有相同的entry?

xqmei

Am I right? list all the possible, and cal the avg_len?

SQL> SELECT s, length(s) lens, AVG(length(s)) over() avg_len
  2    FROM (SELECT DISTINCT substr(a.s, 1, (least(instr(s, '2'), instr(s, '4')))) s
  3            FROM (SELECT DISTINCT *
  4                    FROM (SELECT n, REPLACE(sys_connect_by_path(n, ','), ',') s
  5                            FROM (SELECT LEVEL n FROM dual CONNECT BY LEVEL <= 4)
  6                           WHERE LEVEL = 4
  7                          CONNECT BY nocycle LEVEL <= 4
  8                                 AND n <> PRIOR n)) a);

S                                                                                      LENS    AVG_LEN
-------------------------------------------------------------------------------- ---------- ----------
12                                                                                        2        2.2
312                                                                                       3        2.2
32                                                                                        2        2.2
14                                                                                        2        2.2
314                                                                                       3        2.2
134                                                                                       3        2.2
132                                                                                       3        2.2
2                                                                                         1        2.2
34                                                                                        2        2.2
4                                                                                         1        2.2

10 rows selected

SQL>