Puzzleup 2013挑战赛即将开始

newkid

#20 Twelve Cards


There are twelve cards which are numbered from 1 to 12. You shuffle the cards, and open them one by one. For each card, if the card has a number larger than all previous cards, you score 1 point. After all the cards are opened, the sum of the scores is your total score. If you repeat this operation many times, what would be the average of your total score.

Note: For the first card you score 1 point directly.

(If your answer is not an integer, enter it with two digits after the decimal point without rounding.)

有12张牌标号从1到12。你把牌洗乱，然后逐一翻开。对于每张牌，如果它的数字比前面所有牌的数字都大，你就得一分。所有牌都翻开后，分数的和就是你的总分。如果你重复此操作许多次，你的总分的平均值会是多少？
注意，第一张牌直接给你一分。
如果你的答案不是整数，保留小数后两位不需要舍入。

---------------
这其实是个简单的排列组合问题。

jixch

newkid 发表于 2013-7-31 23:25
哪里用那么麻烦，就是笛卡尔积嘛，一下子就算出来了：
SELECT LEVEL N FROM DUAL WHERE LEVEL>1 CONNECT B ...

剩余的用1u拼
where 条件用得好巧妙....

jixch

newkid 发表于 2013-8-21 22:18
题库中抽出的题构成了20份试卷。
每份试卷的题目数都相同。
每个问题最多用于10份试卷。

这题卡了好久了....
还是没做出来....

先看后面的题去

peter1166

20# , 我尝试了一下。 如果列出所有再求平均可能太多了。
我觉得这个尝试次数越多平均值会越接近一个值，按照这个想法先把一次的弄出来，再反复看看。  
单次的分数如下， 可以反复执行，呵呵。

SELECT COUNT(DISTINCT MAX_VAL) TTL_SCR
FROM (
      SELECT ROWNUM RN, N
             ,MAX(N)OVER(ORDER BY ROWNUM) MAX_VAL
      FROM (SELECT LEVEL N FROM DUAL CONNECT BY LEVEL <= 12 ORDER BY DBMS_RANDOM.value )
     );  


之后是要反复执行了。
我记得 newkid 说过标量子查询如果传过来的值变，就不使用缓存结果。验证了一下，果然好用。
下面就简单了， 次数越多果然趋近于一个值， 3.11  ，但也会越来越慢。


SELECT MAX(CNT) TTL_CNT
       ,ROUND(AVG(SCR),2) AVG_SCR
FROM (
SELECT T2.CNT
       ,( SELECT COUNT(DISTINCT MAX_VAL) TTL_SCR
          FROM (
                SELECT ROWNUM RN, N
                       ,MAX(N)OVER(ORDER BY ROWNUM) MAX_VAL
                FROM (SELECT LEVEL N FROM DUAL CONNECT BY LEVEL <= 12 ORDER BY DBMS_RANDOM.value )
               ) A
          WHERE T2.CNT = T2.CNT      
        ) SCR
FROM (SELECT LEVEL CNT FROM DUAL CONNECT BY LEVEL <= 10000) T2
);

最后问下 newkid  ， 这个给章不？  ^^  

newkid

peter1166 发表于 2014-9-17 18:55
20# , 我尝试了一下。 如果列出所有再求平均可能太多了。
我觉得这个尝试次数越多平均值会越接近一个值， ...

奇怪，这道题我明明写出来了，当时不知道为什么没有发。这道题的难度只能给一个章。你现在的写法不行，我要求精确值。

peter1166

newkid 发表于 2014-9-17 21:21
奇怪，这道题我明明写出来了，当时不知道为什么没有发。这道题的难度只能给一个章。你现在的写法不行，我 ...

好的，再想想其他方法。

asamiya310

是不是把所有的组合列出来求个平均就好了呢？
WITH T AS
(SELECT ROWNUM R
    FROM DUAL
  CONNECT BY ROWNUM <= 12),
R(R,
RT,
LVL) AS
(SELECT R
        ,R RT
        ,1 LVL
    FROM T
  UNION ALL
  SELECT T.R
        ,R.RT
        ,LVL + 1
    FROM T
        ,R
   WHERE T.R > R.R)
SELECT AVG (LVL)
  FROM R
WHERE R = 12;
不知道这样对不对，可能考虑的不是很全面
做出是6.5

newkid

asamiya310 发表于 2014-9-18 09:30
是不是把所有的组合列出来求个平均就好了呢？
WITH T AS
(SELECT ROWNUM R

差远了，你这全是升序的。比如213就没有考虑到，这里3也是得分的。

asamiya310

newkid 发表于 2014-9-19 02:25
差远了，你这全是升序的。比如213就没有考虑到，这里3也是得分的。

我觉得只要排升序的就可以了吧
213就是23，因为2已经不得分了，也可能是43215，其实就是45,321都不得分了，然后取出所有排到12的值的层数就是分数。这样想有什么地方漏掉了么？

newkid

asamiya310 发表于 2014-9-19 09:34
我觉得只要排升序的就可以了吧
213就是23，因为2已经不得分了，也可能是43215，其实就是45,321都不得分了 ...

漏掉了个数的考虑，你不知道45中间的的123可以有多少种排列。
题目是12张牌，你改用1,2,3三张，套用你自己的公式再验证一下六种排列的得分情况。