好友 阅读权限 30
听众 最后登录 1970-1-1
一、前因 最近班上的学生（小学5、6年级）要参加python的白名单比赛，从练习的结果来看，学生对于后面几道答题一直心有余悸，算法实在是太难了。 对于递归法，他们可以胸有成竹。对于回溯法，他们只能留下难过的泪水，因此怎么让学生听懂回溯法是重中之重。 而B站上或其他文章中，对于回溯法的讲解总让我感觉朦朦胧胧，因此自己尝试解开回溯法的面纱。 二、先从嵌套循环求排列 对于固定数量的排列组合，如从'abc'中选2个进行排列，可以使用2个for循环来解决 [Python] 纯文本查看 复制代码
target = 'abc'
for x in target:
for y in target:
if x != y:
print(x, y) 得出的结果为 [Python] 纯文本查看 复制代码
a b
a c
b a
b c
c a
c b 如从'abc'中选3个进行排列，可以使用3个for循环来解决 [Java] 纯文本查看 复制代码
target = 'abc'
for x in target:
for y in target:
for z in target:
if x!=y and x!=z and y!=z:
print(x, y, z) 得出的结果为 [Python] 纯文本查看 复制代码
a b c
a c b
b a c
b c a
c a b
c b a 三、思考 通过嵌套循环的确可以进行排列，但是我想从'abcdefg'中分别选3、4、5个进行排列，难道每次都要手动增加for循环次数吗？ 而之前学习的递归法，函数通过自己调用自己好像可以帮助我解决这些问题，先尝试一下。 四、尝试使用递归法 我先创建一个方法，自己调用自己2次，然后遍历abc不就行了吗，并且使n传入的参数为n-1为嵌套循环 [Python] 纯文本查看 复制代码
def abc_arrange(n, data):
# 遍历abc
for x in data:
print(x)
# 调用自己2次
for i in range(n):
abc_arrange(n-1, data) # 传入的参数为n-1为嵌套循环
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
abc_arrange(n, target) [Python] 纯文本查看 复制代码
a
b
c
a
b
c
a
b
c
a
b
c
a
b
c 不行，思考一下嵌套循环里，大循环套着小小循环。 结果应该是：大循环的a对应小循环abc，大循环的b对应小循环abc，大循环的c对应小循环abc，那调用自身函数也是在循环里执行的，并且当n为0的时候，说明是最后一次嵌套循环，此时应该return [Python] 纯文本查看 复制代码
def abc_arrange(n, data):
if n == 0:
return
# 遍历abc
for x in data:
print(x)
abc_arrange(n-1, data)
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
abc_arrange(n, target) 结果为 [Python] 纯文本查看 复制代码
a
a
b
c
b
a
b
c
c
a
b
c 这次好像可以了，请看下图
现在只要想办法将大循环的abc与每个小循环的abc进行合并，就能得到aa,ab,ac,ba,bb,bc,ca,cb,cc 那就创建一个空列表为combination传入函数，用来存储合并结果 [Python] 纯文本查看 复制代码
def abc_arrange(n, target, combination):
if n == 0:
print(combination) # 打印合并结果
return
# 遍历abc
for x in target:
combination.append(x) # 合并结果
abc_arrange(n-1, target, combination)
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
combination = []
abc_arrange(n, target, combination) 结果为 [Python] 纯文本查看 复制代码
['a', 'a']
['a', 'a', 'b']
['a', 'a', 'b', 'c']
['a', 'a', 'b', 'c', 'b', 'a']
['a', 'a', 'b', 'c', 'b', 'a', 'b']
['a', 'a', 'b', 'c', 'b', 'a', 'b', 'c']
['a', 'a', 'b', 'c', 'b', 'a', 'b', 'c', 'c', 'a']
['a', 'a', 'b', 'c', 'b', 'a', 'b', 'c', 'c', 'a', 'b']
['a', 'a', 'b', 'c', 'b', 'a', 'b', 'c', 'c', 'a', 'b', 'c'] 还不可以，一、元素重复了，二、合并结果长度不是2， 再改一改 判断元素是否重复，重复就跳过 [Python] 纯文本查看 复制代码
def abc_arrange(n, target, combination):
if n == 0:
print(combination) # 打印合并结果
return
# 遍历abc
for x in target:
if x in combination: # 如果已经存在元素就跳过
continue
combination.append(x) # 合并结果
abc_arrange(n-1, target, combination)
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
combination = []
abc_arrange(n, target, combination) 结果为 [Python] 纯文本查看 复制代码
['a', 'b']
['a', 'b', 'c'] 问题又出现了，大循环和小循环的abc都合并在一起了，导致conbination的列表结果只能是abc 想一想嵌套循环，大循环为a，小循环abc，已经排除重复出现的元素了，结果应该为ab,ac 说明进入小循环后，应该把combination里的小循环得到的元素删除，才能进入小循环中的下一次循环 同样的进入大循环中进入下一次循环后，也要 把combination里的大循环得到的元素删除， 才能进入大循环中的下一次循环 而在这个方法中，我在for循环和递归实现了嵌套循环，拿在循环后把conbianation删除最后一个元素不就可以了 这就是回溯的本质吧 [Python] 纯文本查看 复制代码
def abc_arrange(n, target, combination):
if n == 0:
print(combination) # 打印合并结果
return
# 遍历abc
for x in target:
if x in combination: # 如果已经存在元素就跳过
continue
combination.append(x) # 合并结果
abc_arrange(n-1, target, combination)
combination.pop() # 在循环中进入下轮循环前删除最后一个元素
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
combination = []
abc_arrange(n, target, combination) 结果为 [Asm] 纯文本查看 复制代码
['a', 'b']
['a', 'c']
['b', 'a']
['b', 'c']
['c', 'a']
['c', 'b'] 排列成功了，用一个result的列表来存储所有的combination，储存需要添加combination的副本，和全局变量有关系 [Python] 纯文本查看 复制代码
def abc_arrange(n, target, combination):
if n == 0:
print('combination', combination) # 打印合并结果
result.append(combination.copy()) # 要添加副本，不能直接添加combination
return
# 遍历abc
for x in target:
if x in combination: # 如果已经存在元素就跳过
continue
combination.append(x) # 合并结果
abc_arrange(n-1, target, combination)
combination.pop() # 在循环中进入下轮循环前删除最后一个元素
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
combination = [] # 储存合并结果
result = [] # 储存所有的合并结果
abc_arrange(n, target, combination)
print('result', result) # 打印所有的合并结果 结果为 [Python] 纯文本查看 复制代码
combination ['a', 'b']
combination ['a', 'c']
combination ['b', 'a']
combination ['b', 'c']
combination ['c', 'a']
combination ['c', 'b']
result [['a', 'b'], ['a', 'c'], ['b', 'a'], ['b', 'c'], ['c', 'a'], ['c', 'b']] 成功了！试一下将排列换成组合，用集合排除重复的元素就可以了 [Python] 纯文本查看 复制代码
def abc_arrange(n, target, combination):
if n == 0:
if not set(combination) in result:
print('combination', combination) # 打印合并结果
result.append(set(combination.copy())) # 要添加副本，不能直接添加combination
return
# 遍历abc
for x in target:
if x in combination: # 如果已经存在元素就跳过
continue
combination.append(x) # 合并结果
abc_arrange(n-1, target, combination)
combination.pop() # 在循环中进入下轮循环前删除最后一个元素
n = 2 # 选2个进行组合
target = 'abc' # 组合为abc
combination = [] # 储存合并结果
result = [] # 储存所有的合并结果
abc_arrange(n, target, combination)
print('result', result) # 打印所有的合并结果 结果为 [Python] 纯文本查看 复制代码
combination ['a', 'b']
combination ['a', 'c']
combination ['b', 'c']
result [{'a', 'b'}, {'a', 'c'}, {'c', 'b'}] 感想 直接教我回溯法，教的我都懵了，果然从嵌套循环入手领悟到了回溯的本质，深度路径搜索算法和广度路径搜索算法都比这个容易理解
查看全部评分
发表于 2024-5-19 18:35
|
发表于 2024-5-19 20:43
