假设圆已经被分成了n个扇区,并且已经在这n个扇区中填好了数字,先来看看填好数字后最多有多少种选择连续的数字并求和的方法,以N=4为例:
单独选一个,有n种即1、2、3、4;
选择相邻两个也有n种即12、23、34、41
选择相邻三个也有n种即123、234、341、412;
选择相邻四个只有一种即1234。
总共有n*(n-1)+1种,当n=4时有13种。
如果每一种选择所求的和都不同,那么能够构成的最多有n*(n-1)+1个不同的数。我们当然希望能够达到的最大的连续数就是从1到n*(n-1)+1了,如N=4时就是1到13。
现在的问题是如何保证这n*(n-1)+1个数就是从1到n*(n-1)+1。在填数时首先填1,接下来的n-1个数都保证不同且最小为2,再看其他的取相邻的多个数的情况了。在n<=6的情况下都能满足这个要求,对于n>6时就不一定了。
从这种最优策略出发,再结合回溯法找出所有可能的情况。