假设有 n 根柱子,现要按下述规则在这n 根柱子中依次放入编号为1,2,3,4,⋯的球。
每次只能在某根柱子的最上面放球。在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。试设计一个算法,计算出在 n 根柱子上最多能放多少个球。
这道题有贪心做法,由于答案的数量是O(n^2)所以,复杂度为O(n^3),至于贪心做法的正确性,可以通过证明方案的唯一性来证明,这里不再研究贪心算法。这道题其实是有O(1)出答案,O(答案数量)出方案的做法的。
附上前10个点经过整理后的方案
[1] 1 [2] 3 1 2
[3] 5 4 6 3 1 7 2 [4]11 5 4 10 6 3 1 9 7 2 8 [5]13 12 14 11 5 4 15 10 6 3 1 16 9 7 2 17 8 [6]23 13 12 22 14 11 5 4 21 15 10 6 3 1 20 16 9 7 2 19 17 8 18 [7]25 24 26 23 13 12 27 22 14 11 5 4 28 21 15 10 6 3 1 29 20 16 9 7 2 30 19 17 8 31 18 [8]39 25 24 38 26 23 13 12 37 27 22 14 11 5 4 36 28 21 15 10 6 3 1 35 29 20 16 9 7 2 34 30 19 17 8 33 31 18 32 [9]41 40 42 39 25 24 43 38 26 23 13 12 44 37 27 22 14 11 5 4 45 36 28 21 15 10 6 3 1 46 35 29 20 16 9 7 2 47 34 30 19 17 8 48 33 31 18 49 32 [10]59 41 40 58 42 39 25 24 57 43 38 26 23 13 12 56 44 37 27 22 14 11 5 4 55 45 36 28 21 15 10 6 3 1 54 46 35 29 20 16 9 7 2 53 47 34 30 19 17 8 52 48 33 31 18 51 49 32 50