趣题, 第8道来了。

tree_new_bee

newkid 发表于 2012-5-9 21:36
WITH t AS (
SELECT LEVEL n FROM DUAL CONNECT BY LEVEL

期待你的人肉。

当初QQ群里的一个年轻奥数老师就是手工找的18位。
并且证明了18位就是最长的。
可惜他给的证明我当时没看太明白

newkid

tree_new_bee 发表于 2012-5-9 22:18
期待你的人肉。

当初QQ群里的一个年轻奥数老师就是手工找的18位。

哈哈，前面不是说了吗，我的肉早就老朽了。
那位奥数男找奥数女生奥数孩，真是应了一句话“你们全家都奥数!”

lugionline

小三是个一笔画的问题，如果把四位数字当作一个节点的话。

可以证明这张图是联通的(当然不是移动的)，然后每个节点的出入度都是可以简单计算出来，

没有自己到自己的路径，另外貌似每个节点的出度都=入度，

比方 1234 可以从 1123，2123，3123，4123过来，可以到 2341,2342,2343,2344去，所以出入度都是4
而  4444可以从 1444，2444，3444过来，到4441，4442，4443去，出入度都是3

简单证明就是 ： 如果 abcd = bcdx， 那么 x = d = c = b = a， 于是 xabc = abcd

出入度同时减少一个，但是出度=入度仍然不变


那就是所有节点都可以走到啊，那直接出答案了吧

newkid

lugionline 发表于 2012-5-9 22:50
小三是个一笔画的问题，如果把四位数字当作一个节点的话。

可以证明这张图是联通的(当然不是移动的)，然 ...

现在都流行把踩点叫做一笔画了？注意画的可是边哦。
你说的1123,4444都不是有效的点，相邻数必须相差1.

lastwinner

tree_new_bee 发表于 2012-5-9 22:14
野花非要整个42做例子，给自己找麻烦。
用23-30的话，都能找到软柿子捏的：  这个范围内，18一直是那个软 ...

算术没学好嘛，当时弄42是因为42*2>9^2=81
只是为了改写那个求相邻数的sql才弄的值

我的思路是求每个数在所有相邻数中出现的次数，求出来再找规律

lugionline

newkid 发表于 2012-5-9 22:57
现在都流行把踩点叫做一笔画了？注意画的可是边哦。
你说的1123,4444都不是有效的点，相邻数必须相差1.

哦，我弄错了,不是一笔画，是点遍历问题

如果加上你说的那个限制，那点数和路径会少很多了，画出来估计眼睛看就能看出来

tree_new_bee

lugionline 发表于 2012-5-10 08:26
哦，我弄错了,不是一笔画，是点遍历问题

如果加上你说的那个限制，那点数和路径会少很多了，画出来估计 ...

花点时间画了一幅图，试试你的眼睛能不能看出来吧。

lugionline

tree_new_bee 发表于 2012-5-10 09:19
花点时间画了一幅图，试试你的眼睛能不能看出来吧。

应当有26条路径吧，为什么只有24挑

tree_new_bee

lugionline 发表于 2012-5-10 09:47
应当有26条路径吧，为什么只有24挑

你看到的应该是23条吧， 有3条线是双向箭头。

lugionline

你的图画的不好啊，我用GraphViz生成的就是看得出来，呵呵
先生成路径

with
A (n) As
(
        Select 1
        Union All
        Select n + 1 From A Where n < 4
),
V0 (S, L, C) As
(
        Select Cast(n As Varchar(Max)) S, n L, 1 C From A
        Union All
        Select S + Cast(n As Varchar(Max)), n, C + 1 From V0, A
        Where Abs(L - n) = 1 And C <= 4
),
V (S) As (Select S From V0 Where C = 4),
R (F, T, GV) As
(
        Select VF.S, VT.S, VF.S + '->' + VT.S From V VF, V VT
        Where SubString(VF.S, 2, Len(VT.S) - 1) = SubString(VT.S, 1, Len(VT.S) - 1)
)
Select * From R Order By F