PUZZLEUP 2014

peter1166

弄出来了， 但是跟两位版主弄得性能差很多。
思路是， 先求了2个马的可能情况， 再求2个车的可能情况， 最后再求所有可能情况。
代码贴出来， 献丑了。



WITH T AS (
          SELECT LEVEL N
                 ,CEIL(LEVEL/:N) X
                 ,MOD(LEVEL-1,:N) + 1 Y
          FROM DUAL CONNECT BY LEVEL <= :N*:N
         )
   ,T1 AS ( -- 只2匹马，所有可能的位子         
            SELECT  PRIOR N M1
                   ,N  M2
                   ,PRIOR X MX1
                   ,PRIOR Y MY1
                   ,X MX2
                   ,Y MY2
            FROM T
            WHERE LEVEL = 2
            CONNECT BY N > PRIOR N AND LEVEL <=2
            AND POWER((X - PRIOR X),2) + POWER((Y - PRIOR Y),2) <> 5
          )
   ,T2 AS ( -- 只2 个车，所有可能的位子
            SELECT  PRIOR N C1
                   ,N C2
                   ,PRIOR X CX1
                   ,PRIOR Y CY1
                   ,X CX2
                   ,Y CY2
            FROM T
            WHERE LEVEL = 2
            CONNECT BY N > PRIOR N AND LEVEL <=2
            AND NOT（(X = PRIOR X ) OR （Y = PRIOR Y )）
          )
SELECT  COUNT(*) CNT
FROM T1 , T2
WHERE T1.MX1 <> T2.CX1  -- 马不能在车的线上
AND  T1.MX2 <> T2.CX1
AND  T1.MX1 <> T2.CX2
AND  T1.MX2 <> T2.CX2
AND  T1.MY1 <> T2.CY1
AND  T1.MY2 <> T2.CY1
AND  T1.MY1 <> T2.CY2
AND  T1.MY2 <> T2.CY2
AND  POWER((T1.MX1 - T2.CX1),2) + POWER((T1.MY1 - T2.CY1),2) <> 5  -- 车不能在马脚下
AND  POWER((T1.MX1 - T2.CX2),2) + POWER((T1.MY1 - T2.CY2),2) <> 5  
AND  POWER((T1.MX2 - T2.CX1),2) + POWER((T1.MY2 - T2.CY1),2) <> 5  
AND  POWER((T1.MX2 - T2.CX2),2) + POWER((T1.MY2 - T2.CY2),2) <> 5
;

-- 577056

newkid

#10 Five-Letter Code

You will produce five-letter codes using the letters A, B, C, D, and E.

-You Are not allowed to produce a code that can be constructed by interchanging any two adjacent letters of an existing code.

What is the maximum number of different codes that can be produced according to this rule?

If the problem was asked for three-letter codes using the letters A, B, and C, then the answer would be 18.

AAA, AAB, AAC, ABB, ABC, ACC, BAA, BBA, BBB, BBC, BCA, BCC, CAA, CAB, CBB, CCA, CCB, CCC.

五字母代码
你将用字母A,B,C,D,E生成包含五个字母的代码。
你不允许产生这样的代码：它由一个已存在的代码的相邻两位交换而来。
根据这个规则，最多可以产生多少个不同的代码？
如果问题问的是利用字母A,B,C产生的三字母代码，那么答案是18。
AAA, AAB, AAC, ABB, ABC, ACC, BAA, BBA, BBB, BBC, BCA, BCC, CAA, CAB, CBB, CCA, CCB, CCC.
---------------
三字母还可以用SQL写出来，五个字母难度大得多。

newkid

从三个字母的来看是很有规律的，就是按顺序添加，不符合条件的丢弃。如果这样的话走一遍就得到结果了。但如何证明这样得到的是最大集合？

DECLARE
   TYPE t_exist IS TABLE OF NUMBER INDEX BY VARCHAR2(10);
   TYPE t_res IS TABLE OF VARCHAR2(10) INDEX BY PLS_INTEGER;
   lv_exist t_exist;
   lv_res t_res;
   N PLS_INTEGER :=5;
BEGIN

   FOR lv_rec IN (
       SELECT REPLACE(SYS_CONNECT_BY_PATH(c,','),',') code
         FROM (SELECT CHR(64+LEVEL) c FROM DUAL CONNECT BY LEVEL<=N)
       WHERE LEVEL=N
       CONNECT BY LEVEL<=N
       ORDER BY 1
       )
   LOOP
       IF NOT lv_exist.EXISTS(lv_rec.code) THEN
          lv_res(lv_res.count+1) := lv_rec.code;
          lv_exist(lv_rec.code):=1;
          FOR i IN 1..N-1 LOOP
              lv_exist(SUBSTR(lv_rec.code,1,i-1)||SUBSTR(lv_rec.code,i+1,1)||SUBSTR(lv_rec.code,i,1)||SUBSTR(lv_rec.code,i+2)):=1;
          END LOOP;
       END IF;
   END LOOP;
   DBMS_OUTPUT.PUT_LINE(lv_res.count);
END;
/

1625

牛蛙PETER快来证明一下！

〇〇

power 5 5=3125

newkid

〇〇 发表于 2014-10-1 23:00
power 5 5=3125

这有什么用？现在是要找出一个最大的子集使得任意两个元素之间都满足那个规则。

〇〇

newkid 发表于 2014-10-2 00:03
这有什么用？现在是要找出一个最大的子集使得任意两个元素之间都满足那个规则。

你这个办法是对5个字母公平的,只要验证不包含在内的每个字符串都不符合那个规则

newkid

〇〇 发表于 2014-10-2 07:17
你这个办法是对5个字母公平的,只要验证不包含在内的每个字符串都不符合那个规则

你这没头没脑的几个数字竟然包含了这么深刻的哲理？

我的算法注定了被抛弃的每个代码都加不回去。但这没用，有可能你加入几个，挤走几个，又能够再加入更多的代码。必须证明再加回去的怎么也不会比挤走的更多。

peter1166

newkid 发表于 2014-10-1 22:25
从三个字母的来看是很有规律的，就是按顺序添加，不符合条件的丢弃。如果这样的话走一遍就得到结果了。但如 ...

我是找规律算的是 1875 .
3个的时候，
( 1+2+3 ) 这是一个块儿里的数量，
(3*3*3)  总数
(3*3*3) / (3*3) 这个是块儿的个数。

-----------------
AAA AAB AAC
       ABB ABC
              ACC
-----------------
BAA
BBA BBB BBC
BCA        BCC
-----------------
CAA CAB
       CBB
CCA CCB CCC
-----------------


( 1+2+3 ) * (3*3*3) / (3*3) = 18
( 1+2+3+4 ) * (4*4*4*4) / (4*4) = 160
( 1+2+3+4+5 ) * (5*5*5*5*5) / (5*5) =  1875

〇〇

peter1166 发表于 2014-10-2 16:58
我是找规律算的是 1875 .
3个的时候，
( 1+2+3 ) 这是一个块儿里的数量，

列出来?

newkid

peter1166 发表于 2014-10-2 16:58
我是找规律算的是 1875 .
3个的时候，
( 1+2+3 ) 这是一个块儿里的数量，

你这“块数”的公式是什么意思？(4*4*4*4) / (4*4) ,  (5*5*5*5*5) / (5*5)