Puzzleup 2010 比赛快开始了，大家用SQL解答啊

newkid

猜一个：
20+(20-4)/2*(20/2)=100

nlrte13

原帖由 newkid 于 2010-10-13 23:03 发表
猜一个：
20+(20-4)/2*(20/2)=100

感觉100有点大了。。。

nlrte13

哇，发现我不知什么时候多了一颗徽章~ ^^

nlrte13

我算出一个结果 = 96，不过不知正确否 ：D

nlrte13

发现通项公式
若机场数为M（M>3）
且 3*2^n < M <= 3*2^(n+1)，
则直班数 P = 2^(2n+1) + 2^(n+1)*( M - 3*2^n )

对于 M = 20，有 3*2^2 < 20 <= 3*2^3
P = 2^5 + 2^3 * ( 20 - 3*2^2 ) = 32 + 8*8 = 96

nlrte13

貌似 P 还可以化简下，
P = 2^(n+1)*[ M - 2^(n+1) ]

lastwinner

原帖由 newkid 于 10-10-13 21:25 发表
又是图论相关，奥数哥大显身手的时候到了：

Airports

In a country there is a total of 20 airports. Each one of these airports are linked to all the others, either through direct or indirect (ie. connecting) flights. There are at most two direct flights among any randomly chosen three airports.

What is the maximum possible number of direct flights among these 20 airports?

Note: If there is a flight between A and B, it can be used in both directions and it will be counted as one flight.

20个机场，它们之间之间或间接可达，任意三个机场之间至多有两个直飞航班。所有机场之间最多可以有多少个直飞航班？注意如果A到B有直飞航班，则为双向，而且只算作一个航班。

20个顶点的连通无向图，任意三个顶点之间只能有两条边，最多可以有多少条边？因为三角形不允许存在，必须画出尽可能多的四边形。

翻译不够准确，已纠正如上，顺带换页

lastwinner

两两互连，总共有C(20,2)=190条航线，从中找到三个机场互连的情况，然后删除其中一条航线，算一种办法
但在没有明确删除哪条航线时，这种方法无法保证得到一个最大值，但可以保证最大值一定不小于这个值（废话……）

若就 3个点，最多2条
4个点，最多4条（a和bc互连，d和cd互连）
5个点，最多6条（a和bc互连，d和cd互连，然后e和ad或者bc互连）
任意四点最多组成一个四边形
6个点，最多9条（a和bc互连，d和cd互连，然后e和ad，f和bc互连，ef互连）
每新增加一个点，都只能从已经联好的点里面选N个互不相连的，然后用该点与这N个点分别连接，所增加的连接数为N
由此推下去
7个点，最多12条（a和bc互连，d和cd互连，然后e和ad，f和bc互连，ef互连）
8个点，这时最多有4个点是两两互不相连的，因而最多16条

lastwinner

h 如上图，可以连接a、d、f、g
————————————————————————————————————
好了，至此我们就能看出规律了
增加第N个点时，至多有trunc(N/2)个互不相连的点可连接，此时总共有T条连接
于是乎，就有
T(9)=t(8)+trunc(9/2)=16+4=20

不excel了，开着sql就sql来吧
SCOTT@lw.lw> select n, y1, sum(y1)over(order by n,y1) Y from
  2  (select rownum n, trunc(rownum/2) y1 from dual connect by rownum<21)
  3  /

         N         Y1          Y
---------- ---------- ----------
         1          0          0
         2          1          1
         3          1          2
         4          2          4
         5          2          6
         6          3          9
         7          3         12
         8          4         16
         9          4         20
        10          5         25
        11          5         30
        12          6         36
        13          6         42
        14          7         49
        15          7         56
        16          8         64
        17          8         72
        18          9         81
        19          9         90
        20         10        100

已选择20行。

已用时间:  00: 00: 00.03


故而答案是100个


天哪，newkid你是咋猜的……╮(╯_╰)╭

nlrte13

原帖由 lastwinner 于 2010-10-14 14:29 发表
h 如上图，可以连接a、d、f、g
————————————————————————————————————
好了，至此我们就能看出规律了
增加第N个点时，至多有trunc(N/2)个互不相连的点可连接，此时总共有T条连接
于是乎，就有
T(9)=t(8)+trunc(9/2)=16+4=20

不excel了，开着sql就sql来吧
SCOTT@lw.lw> select n, y1, sum(y1)over(order by n,y1) Y from
  2  (select rownum n, trunc(rownum/2) y1 from dual connect by rownum

鹦鹉哥的方法是对的，赞~！我的消三角思路错了 - -#