跳至正文
View Categories

< 1 min read

数字拆分 #

  1. 数字拆分问题的介绍
  2. 数字拆分问题的算法分析
  3. 数字拆分问题代码实现

数字拆分问题的介绍 #

任何一个大于1的自然数n，总是可以拆分成若干个不大于n的自然数之和:例如输入n=4，可以拆分为：(1):4=1+1+1+1 (2):4=1+1+2 (3):4=1+3 (4):4=2+2 (5):4=4

数字拆分问题的算法分析1 #

和之前的回溯例子不同之处在于，数字拆分时并不确定每一条路径所需的步骤数，我们可以使用被拆分的整数S，来判断拆分是否完成：
1.第一步:从1~S的整数中任意选取一个数i，保存这一结果，并使s=s-i
2.第二步:判断s是否为零，如果不为零继续从1~S的整数中任意选取一个数i，直到s为零

数字拆分问题的代码实现1 #

和普通回溯问题一样，套用回溯代码框架:

res=[0]#res[1],保存第一步的结果依次类推
def dfs(s,step=1):#定义回溯函数dfs(s,step),s为需要分解的数，step代表每一步
    if s==0:
        print(res[1:])
        return
    for i in range(1,s+1):#从1~s中依次选择当前
        res.append(i)#保存结果
        s=s-i
        dfs(s,step+1)
        res.pop()#取消结果
        s=s+i
dfs(4)

事实上上述代码运行后，也能求出上述数字4，所得拆分结果如下:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 3]
[2, 1, 1]
[2, 2]
[3, 1]
[4]
上述结果明显比我们想要的要多，因为我们在执行策略上，只是要求拆分结果的和为4，对每一次选择并没有做要求，因此造成了相同拆分的排列问题

数字拆分问题的算法分析2 #

针对上述上述存在的问题我们对算法的第二步做出如下改进:
第二步:判断s是否为零，如果不为零继续从1~S的整数中，任意选取一个不小于第一步选择的数，直到s为零

数字拆分问题的代码实现2 #

res=[0]#res[1],保存第一步的解过依次类推
def dfs(s,step=1):#定义回溯函数dfs(s,step),s为需要分解的数，step代表每一步，默认值为1
    if s==0: #s拆分为零时输出结果
        print(res[1:])
        return
    for i in range(1,s+1):
     if(i>=res[step-1]):#当前步骤的选择不小于上一步骤的选择，第一步时大于res[0]
        res.append(i)#保存结果
        s=s-i
        dfs(s,step+1)
        res.pop()#取消结果
        s=s+i
dfs(4)

该问题与素数环类似，当上下步之间选择的结果存在联系时，通常需要第一步做出选择，或者使问题回溯到第一步时有被判断的依据。例如本例中第一步的选择不小于我们提前设定的res[0]

小结 #

  • 根据数字拆分问题，理解回溯算法的思想
  • 掌握使用上下步骤之间的关系，对回溯算法进行优化的思想

习题 #

  1. 如果将问题改为:任何一个大于1的自然数n，总是可以拆分成若干个小于n的自然数之和,该如何求解该数的拆分，编程求解？
  2. 如果将问题改为:任何一个大于1的自然数n，总是可以拆分成若干个小于n//2的自然数之和,该如何求解该数的拆分，编程求解？
What are your Feelings