中级编程通关练习题 #2 – 平方分解

给定一个正整数N(N>4),把N的平方分解成若干个小于N而且不重复的正整数的平方之和。譬如,

  • 52 = 42 + 32
  • 102 = 82 + 62
  • 202 = 192 + 52 + 32 + 22 + 12
  • 502 = 492 + 82 + 52 + 32 + 12

如果N可以分解为多个不重复的正整数的平方,选择两组数列里有最大数的那一个。譬如,11的平方可以分解为:1² + 2² + 4² + 10²,也可以分解为:22 + 62+ 92,这种情况下需要选择第一个数列而不是第二个数列,因为第一个数列里的最大值10大于第二个数列里的最大值9。

另外,分解的数列之中不能有重复数值,譬如上面50的平方分解为数列 [1, 3, 5, 8, 49] 而不是数列 [1, 1, 4, 9, 49],因为后一组数列里有重复的数值 1。

输入样例:

N = 1024

输出样例:

[ 1, 2, 5, 9, 44, 1023]

算法思路:

  • 方法一:采用深度优先(Depth First Search)的递归算法,从N-1开始搜索,然后逐步缩小范围,每次选择一个数值后把该数值的平方数从总数中减去,同时把该数值添加到结果数列中,如果最后总数刚好可以减到零,那么就找到了需要的结果数列。如果最后总数小于零,说明需要在前面数列中的某个位置重新搜索。
  • 方法二:同样采用深度优先(Depth First Search)的递归算法,不过和第一个方法不同之处在于,我们不是从大到小添加数值到目标数列,而是一直循环搜索到可以让总数减到零的最小数,然后从小到大来添加数值到目标数列。这样的好处是避免了方法一需要不断调整数列里的数值的麻烦。
  • 方法三: 采用while循环加for循环来搜索目标数列。和方法一相同,也是从大到小来进行搜索,这样也需要不断调整数列里的数值,一直到总数消减为零。