PUZZLEUP 2015

newkid

再钻研一下把通项公式总结出来？

solomon_007

newkid 发表于 2015-10-18 22:21
再钻研一下把通项公式总结出来？

1     2     3      4       5     ...
5     9     13     17      21
208   2840  32200  344296  3574856

好难 ...

newkid

#13 SET OF CODES

You will produce a set of 7-letter codes using the the letters A, B, C, D, E, F and G.

-Two codes are called similar if they differ by just one letter.

-No two codes will be similar in the set.

-Letters can be used more than once in a code.

What can be the maximum number of codes in this set?


If the problem was asked for a set of 3-letter codes using the letters A, and B then the answer would be 4 (Example: AAA, ABB, BAB, BBA).

你用字母A，B，C，D，E，F和G 产生一组7个字母的代码。

如果两个代码只有一个字母不同，则称为相似。

组中的任意两个代码都不相似。

字母可以在代码中使用一次以上。

这组代码的最多可能有多少个代码？


如果相同的问题被问于一组使用字母A,B的3字母代码，那么答案将是4（例：AAA，ABB，BAB，BBA）。

--------------
这个是M的菜，和前面第七题差不多。

lugionline

是啊，看出来没有，2个代码是正方形，3个代码是立方体，4个代码是超立方体...

我试了6个字母6个代码可以出来，不过 7个代码比较恐怖，等不起啊

这么经典的图形应当有现成结论

solomon_007

13#

12C环境下,先给出小例子的情况:

SQL> with
  2      function similar(p_str1 in varchar2,p_str2 in varchar2)
  3      return int
  4      is
  5        l_cnt int :=0;
  6      begin
  7        for i in 1..length(p_str1) loop
  8          if substr(p_str1,i,1) = substr(p_str2,i,1) then
  9            l_cnt := l_cnt + 1;
10          end if;
11        end loop;
12        if l_cnt >= length(p_str1) - 1 then
13          return 1;
14        else
15          return 0;
16        end if;
17      end;
18      function similar_multi(p1_str in varchar2,p2_str in varchar2)
19      return int
20      is
21        l_sum int default 0;
22      begin
23        for rec in (
24                    select regexp_substr(p1_str,'[^,]+',1,level) item
25                      from dual
26                    connect by level<= regexp_count(p1_str,',',1)+1
27                    ) loop
28  
29            if similar(rec.item,p2_str) = 0 then
30              l_sum := l_sum +1;
31            end if;
32        end loop;
33        if l_sum = regexp_count(p1_str,',',1)+1 then
34          return 0;
35        else
36          return 1;
37        end if;
38      end;
39       t as (select chr(64+level) c from dual connect by level<=2),
40       s(lvl,v) as (select 1 lvl,c v
41                        from t
42                       union all
43                      select lvl+1,
44                             s.v||t.c
45                        from s,t
46                       where lvl<3),
47       s2 as (select v from s where lvl=3),
48       x(lvl,str) as (select 1 lvl,v str
49                        from s2
50                       where v='AAA' --路径很多,仅取以'AAA'开头的路径
51                       union all
52                      select x.lvl+1,
53                             x.str||','||s2.v
54                        from x,s2
55                       where x.lvl<power(2,3)
56                         and similar_multi(x.str,s2.v) = 0
57                     )
58     select lvl,str from x where lvl=(select max(lvl) from x)
59  
60  /
       LVL STR
---------- --------------------------------------------------------------------------------
         4 AAA,ABB,BAB,BBA
         4 AAA,ABB,BBA,BAB
         4 AAA,BAB,ABB,BBA
         4 AAA,BAB,BBA,ABB
         4 AAA,BBA,ABB,BAB
         4 AAA,BBA,BAB,ABB
6 rows selected

solomon_007

SQL>  with t as (select chr(64+level) c from dual connect by level<=3),
  2       s(lvl,v) as (select 1 lvl,c v
  3                        from t
  4                       union all
  5                      select lvl+1,
  6                             s.v||t.c
  7                        from s,t
  8                       where lvl<3),
  9       s2 as (select v from s where lvl=3),
10       x(lvl,str) as (select 1 lvl,v str
11                        from s2
12                       where v='AAA' --路径很多,仅取以'AAA'开头的路径
13                       union all
14                      select x.lvl+1,
15                             x.str||','||s2.v
16                        from x,s2
17                       where x.lvl<power(3,3)
18                         and similar_multi(x.str,s2.v) = 0
19                         and rownum =1
20                     )
21     select lvl,str from x where lvl=(select max(lvl) from x);
       LVL STR
---------- --------------------------------------------------------------------------------
         7 AAA,ABB,ACC,BAB,BBA,CAC,CCA
Executed in 0.212 seconds

solomon_007

SQL>
SQL>  with t as (select chr(64+level) c from dual connect by level<=4),
  2       s(lvl,v) as (select 1 lvl,c v
  3                        from t
  4                       union all
  5                      select lvl+1,
  6                             s.v||t.c
  7                        from s,t
  8                       where lvl<4),
  9       s2 as (select v from s where lvl=4),
10       x(lvl,str) as (select 1 lvl,v str
11                        from s2
12                       where v='AAAA' --路径很多,仅取以'AAA'开头的路径
13                       union all
14                      select x.lvl+1,
15                             x.str||','||s2.v
16                        from x,s2
17                       where x.lvl<power(4,4)
18                         and similar_multi(x.str,s2.v) = 0
19                         and rownum =1
20                     )
21     select lvl,str from x where lvl=(select max(lvl) from x);
       LVL STR
---------- --------------------------------------------------------------------------------
        64 AAAA,AABB,AACC,AADD,ABAB,ABBA,ABCD,ABDC,ACAC,ACBD,ACCA,ACDB,ADAD,ADBC,ADCB,ADDA,
Executed in 13.57 seconds

lugionline

3,3的时候有更大的，验证下看看

"AAA", "BAB", "ACB", "ABC", "CAC", "BBA", "CBB", "CCA", "BCC"

newkid

lugionline 发表于 2015-10-22 08:38
是啊，看出来没有，2个代码是正方形，3个代码是立方体，4个代码是超立方体...

我试了6个字母6个代码可以 ...

看不出来。6个答案是多少？

newkid

solomon_007 发表于 2015-10-22 15:05
SQL>  with t as (select chr(64+level) c from dual connect by level

你中间加那个and rownum =1是不对的。