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

nlrte13

原帖由 lastwinner 于 2010-10-21 11:14 发表


253# 已经证明了，但是我没证明出这就是最大的……

用数学归纳法可以证明你那方法得到的是最大的^^

lastwinner

原帖由 nlrte13 于 10-10-21 11:51 发表


用数学归纳法可以证明你那方法得到的是最大的^^

愿闻其详

newkid

原帖由 nlrte13 于 2010-10-21 10:57 发表
这个题，要用程序暴力，有很简单的思路，不用考虑数字大小，
想象是20个球，两个一组
{ A-A, B-B,  C-C, D-D …… }
要把它们按排成队，一个一个按顺序放，放了一组中的一个就要优先考虑另一个，
同时要满足条件不能有相同间隔数。
这样排好队以后，再把最前的替换成9，次前的替换成8，就是答案了。

要是按ABC顺序放置，那么把 A-9，B-8，C-7，就是答案。

我的方法和你类似，即不用考虑数字的排列，肯定是大数先出现。剩下的就是间隙的排列，数量还是十分巨大。我从左到右一个一个放，如果能有一种方法能预见到凑不足20位，就可以提早放弃。

lastwinner

原帖由 newkid 于 10-10-21 21:30 发表

我的方法和你类似，即不用考虑数字的排列，肯定是大数先出现。剩下的就是间隙的排列，数量还是十分巨大。我从左到右一个一个放，如果能有一种方法能预见到凑不足20位，就可以提早放弃。

大家的思路看来都差不多，最后就在怎么排列了
我之前的两个推论也是为此服务的

newkid

用SQL证明奥数哥的答案已是最大的：

WITH t(str,occur,intv,c,lvl) AS (
SELECT '9' str
      ,'0000000001' as occur         ---- 每个数字出现次数
      ,'0000000000000000000' intv    ---- 哪些间隔已被用过
      ,9 c
      ,1 FROM DUAL
UNION ALL
SELECT str||rn
      ,SUBSTR(occur,1,rn)||(CASE WHEN rn=c-1 THEN '1' ELSE '2' END)||SUBSTR(occur,rn+2)
      ,CASE WHEN rn=c-1 THEN intv
            ELSE SUBSTR(intv,1,LENGTH(str)-INSTR(str,rn))||'1'||SUBSTR(intv,LENGTH(str)-INSTR(str,rn)+2)
       END
      ,LEAST(c,rn)
      ,lvl+1
  FROM t
      ,(SELECT ROWNUM-1 rn FROM DUAL CONNECT BY ROWNUM<=10)
WHERE str >= SUBSTR('99878675432106520134',1,LENGTH(str)) AND   ---- 人肉加速器. 如果代入野花的99878675432103526401，结果相同
       (rn=c-1
        OR (rn>=c
            AND SUBSTR(occur,rn+1,1)='1'
            AND SUBSTR(intv,LENGTH(str)-INSTR(str,rn)+1,1)='0'
            )
       )
)
SELECT MAX(str)
  FROM t
WHERE INSTR(occur,'1')=0;

MAX(STR)
-----------------------------------------
99878675432106520134

Elapsed: 00:00:00.03

nlrte13

原帖由 lastwinner 于 2010-10-21 12:34 发表



愿闻其详

数学归纳法的证明方法如下：

分两步，
首先，
（1）K 个节点，其中有最少边的节点，其边数不能超过 [K/2]（"[]"表示取整，下同）。
证明：
因为若超过 [K/2]，则某节点 K<1> 至少与 K<2>，K<3>，K<4>，……，K<[K/2]+1>，K<[K/2]+2> 有连接（"<>"表示下标，下同），
且 K<2> 至少与 K<1>，K<[K/2]+3>，K<[K/2]+4>，K<[K/2]+5>，……，K<[K/2]*2+1>，K<[K/2]*2+2> 有连接。
显然下标 [K/2]*2+2 已经大于总节点数 K，说明 K<2> 与 K<1> 有相同连接的节点，即出现了“三角形”，不满足题目要求。
因此，（1）得证。

（2）若 K 个节点最多 N 条边，则 K+1 个节点最多 N+[(K+1)/2] 条边。
反证法：
由（1）可知，K+1 个节点时，其中有最少边的节点，其边数不能超过 [(K+1)/2]，
若 K+1 个节点连接了多于 N+[(K+1)/2] 条边，去掉最少边的节点，剩下 K 个节点的边数就一定多于 N，与题设矛盾。
故（2）得证。

nlrte13

这样就可以推啦~~

K=4 时，N=4 =>
K=5 时，N=4+2=6 =>
K=6 时，N=6+3=9 =>
。。。。。。。。

嘿嘿

nlrte13

K>2 时通项：
(K-2)^2 + (K-2)/2 - (-1)^K * (K-2)/2

newkid

"（2）若 K 个节点最多 N 条边，则 K+1 个节点最多 N+[(K+1)/2] 条边。"

你的证明是不超过N+[(K+1)/2]，怎么证明这个N+[(K+1)/2]是可以达到的？

nlrte13

原帖由 newkid 于 2010-10-25 21:52 发表
"（2）若 K 个节点最多 N 条边，则 K+1 个节点最多 N+[(K+1)/2] 条边。"

你的证明是不超过N+[(K+1)/2]，怎么证明这个N+[(K+1)/2]是可以达到的？

汗。。。这不是鹦鹉哥要求证的么^^


========================================================
鹦鹉哥说：

原帖由 lastwinner 于 2010-10-21 12:34 发表
QUOTE:原帖由 nlrte13 于 10-10-21 11:51 发表


用数学归纳法可以证明你那方法得到的是最大的^^



愿闻其详

========================================================

[ 本帖最后由 nlrte13 于 2010-10-26 10:01 编辑 ]