|
- 帖子
- 541
- 精华
- 11
- 积分
- 9986
- 鲜花
- 413 朵
- 主题
- 73 帖
- 来自
- M Set
     
|
对于n≤32的情况，最优的移动方案可以归纳为如下图所示的移动模式。
但n=0、n=1、n=3和n=6例外，需要特殊处理。
令f(0)=0，f(1)=3，f(3)=19，f(6)=88，
然后利用f(0)到f(n)的结果，枚举a,b,c,d,e的值，就可以求得f(n+1)。
这样求f(n)的时间复杂度为O(n^6)。
f(2)到f(100)的结果如下：
n f(n) d e c a b
--------------------------------
2: 10 0 0 0 0 1
3: 19 0 0 0 0 1
4: 34 0 0 1 1 2
5: 57 1 1 2 2 3
6: 88 1 1 2 2 3
7: 123 1 2 3 3 4
8: 176 2 3 4 4 5
9: 253 3 3 5 5 6
10: 342 3 4 5 6 7
11: 449 3 4 6 6 7
12: 572 4 5 7 7 8
13: 749 5 7 7 8 10
14: 980 5 7 8 9 11
15: 1261 6 8 9 10 12
16: 1560 6 8 9 10 12
17: 1903 7 9 10 11 13
18: 2328 8 10 11 12 14
19: 2889 9 11 12 13 15
20: 3562 10 12 12 14 17
21: 4377 10 13 13 15 18
22: 5276 10 13 13 15 18
23: 6251 11 14 14 16 19
24: 7392 12 14 16 17 19
25: 8779 13 16 16 18 21
26: 10488 14 17 17 19 22
27: 12469 14 17 18 20 23
28: 14832 15 18 19 21 24
29: 17497 15 18 19 21 24
30: 20228 16 19 20 22 25
31: 23377 17 20 21 23 26
32: 27082 18 21 22 24 27
33: 31465 19 22 23 25 28
34: 36636 20 23 24 26 29
35: 42581 20 24 24 27 31
36: 49348 21 25 25 28 32
37: 57157 22 25 26 28 32
38: 65222 22 26 26 29 33
39: 73865 23 27 27 30 34
40: 84022 24 28 28 31 35
41: 95757 25 28 30 32 35
42: 109094 26 30 30 33 37
43: 124525 27 31 31 34 38
44: 142220 27 31 32 35 39
45: 161801 28 32 33 36 40
46: 184494 29 33 34 37 41
47: 208359 30 34 34 37 42
48: 233220 30 34 35 38 42
49: 260873 31 35 36 39 43
50: 293016 32 36 37 40 44
51: 329391 33 37 38 41 45
52: 369778 34 38 39 42 46
53: 415899 35 39 40 43 47
54: 468000 35 40 40 44 49
55: 524585 36 41 41 45 50
56: 589570 37 42 42 46 51
57: 660389 38 42 43 46 51
58: 732678 38 43 43 47 52
59: 810215 39 44 44 48 53
60: 897344 40 45 45 49 54
61: 998343 41 46 46 50 55
62: 1109122 42 47 47 51 56
63: 1230093 43 48 48 52 57
64: 1366910 44 49 49 53 58
65: 1522459 45 50 50 54 59
66: 1687510 45 50 51 55 60
67: 1874643 46 51 52 56 61
68: 2079700 47 52 53 57 62
69: 2294287 48 53 53 57 63
70: 2516366 48 53 54 58 63
71: 2757895 49 54 55 59 64
72: 3030880 50 55 56 60 65
73: 3340433 51 56 57 61 66
74: 3675094 52 57 58 62 67
75: 4038133 53 58 59 63 68
76: 4443818 54 59 60 64 69
77: 4898969 55 60 60 65 71
78: 5384602 55 61 61 66 72
79: 5923263 56 62 62 67 73
80: 6511900 57 63 63 68 74
81: 7144699 58 64 64 69 75
82: 7793996 58 64 64 69 75
83: 8482247 59 65 65 70 76
84: 9228136 60 66 66 71 77
85: 10077385 61 67 67 72 78
86: 11018610 62 68 68 73 79
87: 12024387 63 69 69 74 80
88: 13105218 64 70 70 75 81
89: 14305059 65 71 71 76 82
90: 15636282 66 72 72 77 83
91: 17081249 66 72 73 78 84
92: 18638390 67 73 74 79 85
93: 20334841 68 74 75 80 86
94: 22165538 69 75 76 81 87
95: 24079237 70 76 76 81 88
96: 26068688 70 76 77 82 88
97: 28180781 71 77 78 83 89
98: 30496934 72 78 79 84 90
99: 33092587 73 79 80 85 91
100: 35924570 74 80 81 86 92
其中，n≤32的结果与之前做出来的结果完全吻合。
从表中可以看出五个参数均有良好的单调性和平滑性。
利用a,b,c,d,e的单调性和平滑性，可将时间复杂度优化为O(n)。
优化后可以计算很大的n，用来观察数据的增长趋势。
计算到n=100000，结果如下：
n log(f(n)) d e c a b
--------------------------------------------------
10: 2.534026 3 4 5 6 7
100: 7.555392 74 80 81 86 92
1000: 22.358183 914 935 936 956 977
10000: 68.093119 9724 9793 9793 9861 9930
100000: 211.641457 99125 99344 99344 99562 99781
上述结果很可能不是最终结果，但可以作为最终结果的一个很好的上界。
因为当n>32时，很可能会有新的移动模式出现。
而当前的移动模式仅仅只是新的移动模式的一个特例。
新的移动模式会在当前的基础上新增若干个参数，把当前的移动模式更为一般化。
所以接下来的工作是尝试寻找新的移动模式，看看上述结果能不能继续优化。
如果找不到新的移动模式，则说明上述结果就是最终结果，对其加以证明就完美解决问题了。
|
|
发表于 2009-11-18 20:48
| 
踩窝窝
送礼物
问候Ta
( 苏ICP备07505100号)|联系我们
|论坛统计|Archiver|
发表于 2010-4-15 20:03
| 
