趣题, 第8道来了。

lastwinner

tree_new_bee 发表于 2012-5-8 22:47
前一步容易， 我教孩子的手工做法是：
先列出每个数可能相邻的数：
1  3,8,15

映射到数独里，atgc的方法称为直观法，你的方法称为候选数法
前者更适合人肉解答，后者更适合编程解答

这个问题有意思，不过性质和数独没太大区别

lastwinner

newkid 发表于 2012-5-9 00:38
如果真是一笔画问题，不是已经被欧拉解决了？这里没有要求要走遍所有的边，而是走遍所有顶点而且只能走一 ...

你理解的有偏差，tnb的意思是你后面说的意思，你看他图中3和6之间就没画箭头

newkid

lastwinner 发表于 2012-5-9 01:22
你理解的有偏差，tnb的意思是你后面说的意思，你看他图中3和6之间就没画箭头

他没理解错，我也没理解错，我的意思是不能称之为“一笔画”，因为一笔画是要覆盖所有的边，顶点可以走多次。

tree_new_bee

newkid 发表于 2012-5-9 02:08
他没理解错，我也没理解错，我的意思是不能称之为“一笔画”，因为一笔画是要覆盖所有的边，顶点可以走多 ...

恩， 这确实跟通常意义上说的“一笔画”不同， 所以不能用常用的"奇点数"的方法来判断。

原本我扩展这个题，是以为n超过16以后，会很难找到满足条件的, 没想到似乎越往上越多。 看来也许这个是没上限的？

用newkid的语句，测试n=30已经相当慢了。 要测试更大的数，得找高效的做法。

lastwinner

tree_new_bee 发表于 2012-5-9 08:45
恩， 这确实跟通常意义上说的“一笔画”不同， 所以不能用常用的"奇点数"的方法来判断。

原本我扩展这 ...

我提一个思路，就是之前说过的候选数法
首先改写一下找可用相邻数的sql，原先为

1. with t as (SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=:num)
   
2. select t1.n, wm_concat(t2.n) from t t1, t t2
   
3. where t1.n<>t2.n and t1.n+t2.n in (4,9,16,25,36,49,64,81) group by t1.n;

复制代码

改为

1. with nm as (select :num nm from dual),
   
2. t as (SELECT LEVEL n FROM nm CONNECT BY LEVEL<=nm),
   
3. t1 as (select power(level,2) pf from nm connect by level<=floor(sqrt(2*nm-1)))
   
4. select n, wm_concat(pf-n) from t, t1 ,nm
   
5. where t.n<t1.pf and greatest(t.n, pf-n)<=nm.nm and t.n*2<>t1.pf group by t.n;

复制代码

运行时输入num的值即可（此即为N值）
例如对于n＝42，上述sql的结果为


N        WM_CONCAT(PF-N)
1        3,35,24,15,8
2        7,34,23,14
3        1,33,22,13,6
4        5,32,21,12
5        4,31,20,11
6        3,30,19,10
7        2,42,29,18,9
8        1,41,28,17
9        7,40,27,16
10        6,39,26,15
11        5,38,25,14
12        4,37,24,13
13        3,36,23,12
14        2,35,22,11
15        1,34,21,10
16        9,33,20
17        8,32,19
18        7,31
19        6,30,17
20        5,29,16
21        4,28,15
22        3,42,27,14
23        2,41,26,13
24        1,40,25,12
25        11,39,24
26        10,38,23
27        9,37,22
28        8,36,21
29        7,35,20
30        6,34,19
31        5,33,18
32        4,17
33        3,31,16
34        2,30,15
35        1,29,14
36        13,28
37        12,27
38        11,26
39        10,42,25
40        9,41,24
41        8,40,23
42        7,39,22

lastwinner

然后我们从可用候选数最少的数开始探索
18        7,31
32        4,17
36        13,28
37        12,27
38        11,26
上述数字对没有重复的的出现，因此最坏的情况下需要将所有10种情况都尝试，方能确定是否有一条可用的路径，为简化描述，从32开始，因为配对的17具有第二少的可用候选数。
第一个数32选定后，将4和17中的候选数中的32删除掉
第二个数选定17，将8和19中的17删除，同时，还将32中的17也删除掉。这是为什么呢？因为我们只是从32开始尝试，但不代表32就必须是第一个数，它有可能是最终路径中的中间的某一个节点
第三个数就可能是8或19，任意选择一个均可，假定从19开始，则依上述规则，需从6和30的候选数中剔除19
…………
以此类推，如果走到某一个节点后，发现其候选数为空，则说明此路径有问题，需要回溯
穷尽所有路线，直至发现一条可用路径为止，或者直至发现不了一条可用路径为止

tree_new_bee

涉及到图的遍历问题， 是最头疼的。 先放一放， 来下一道题：

趣题3：

用1、2、3、4组成的数
（1）相邻两位差1;
（2）每连续的4位称作一个“节”（例如12343，有两个“节”：1234,2343），任意两节不同。
这样的数最多能有多少位？


这个SQL做相对容易些， 手工做找到最长数有难度， 证明找到的是最长的更有难度。

jixch

错了....

lastwinner

tree_new_bee 发表于 2012-5-9 15:50
涉及到图的遍历问题， 是最头疼的。 先放一放， 来下一道题：

趣题3：

1234321，这样的算几节？

jixch

lastwinner 发表于 2012-5-9 16:57
1234321，这样的算几节？

（2）每连续的4位称作一个“节”（例如12343，有两个“节”：1234,2343），任意两节不同。

应该算4节吧