鱼C论坛

 找回密码
 立即注册
查看: 1538|回复: 18

[已解决]关于 Python 递归时修改全局变量失败的问题

[复制链接]
发表于 2018-9-23 18:47:19 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
  1. def dfs_maze(path, target):
  2.         global paths
  3.         maze = [[" ","#","#"," "," "],[" "," "," ","#"," "],["#"," "," ","#"," "],[" "," "," ","#","#"],[" "," "," "," "," "]]

  4.         if path[-1] == target:
  5.                 paths.append(path)
  6.                 print(path)
  7.                 return
  8.         for each in [[0,1], [0,-1], [1, 0], [-1, 0]]:
  9.                 node = [path[-1][0] + each[0], path[-1][1] + each[1]]
  10.                 if -1 not in node and 5 not in node and node not in path and maze[node[0]][node[1]] != '#':
  11.                         path.append(node)
  12.                         dfs_maze(path, target)
  13.                         path.pop(-1)

  14. def main():
  15.         dfs_maze([[0,0]], [4, 4])

  16.         for each in paths:
  17.                 print(each)
  18. paths = []
  19. main()
复制代码

就是一个深搜解决迷宫最短路径的函数,path 是一个二维数组,储存已经走过的每一个点,target 是终点。在边界条件满足时,打印出来的路径是没问题的。但在深搜结束后,打印出来的 paths 是一堆[[0,0]]的二维数组,这是为何?
最佳答案
2018-9-23 20:10:33
path分配的地址一样,每次做个切片
  1. def dfs_maze(path, target):
  2.         global paths
  3.         maze = [[" ","#","#"," "," "],[" "," "," ","#"," "],["#"," "," ","#"," "],[" "," "," ","#","#"],[" "," "," "," "," "]]

  4.         if path[-1] == target:
  5.                 paths.append(path[:])
  6.                 print(path)
  7.                 return
  8.         for each in [[0,1], [0,-1], [1, 0], [-1, 0]]:
  9.                 node = [path[-1][0] + each[0], path[-1][1] + each[1]]
  10.                 if -1 not in node and 5 not in node and node not in path and maze[node[0]][node[1]] != '#':
  11.                         path.append(node)
  12.                         dfs_maze(path, target)
  13.                         path.pop(-1)

  14. def main():
  15.         dfs_maze([[0,0]], [4, 4])

  16.         for each in paths:
  17.                 print(each)
  18. paths = []
  19. main()
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-9-23 19:07:14 | 显示全部楼层
  1. paths.extend(path)
复制代码
append 多了 [], 比较无效
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-9-23 19:16:27 | 显示全部楼层
claws0n 发表于 2018-9-23 19:07
append 多了 [], 比较无效

不好意思,不是太懂,打印出来的path是二维数组,描述了走过的路径,用append(path)会出问题吗?我希望最终得到的paths是三维的,即包含所有可行的路径。换成extend的话,paths就成二维了,每条路径的点都罗列到一起了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 19:51:16 | 显示全部楼层
本帖最后由 claws0n 于 2018-9-23 19:52 编辑
ElmLiu 发表于 2018-9-23 19:16
不好意思,不是太懂,打印出来的path是二维数组,描述了走过的路径,用append(path)会出问题吗?我希望最 ...


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 20:10:33 | 显示全部楼层    本楼为最佳答案   
path分配的地址一样,每次做个切片
  1. def dfs_maze(path, target):
  2.         global paths
  3.         maze = [[" ","#","#"," "," "],[" "," "," ","#"," "],["#"," "," ","#"," "],[" "," "," ","#","#"],[" "," "," "," "," "]]

  4.         if path[-1] == target:
  5.                 paths.append(path[:])
  6.                 print(path)
  7.                 return
  8.         for each in [[0,1], [0,-1], [1, 0], [-1, 0]]:
  9.                 node = [path[-1][0] + each[0], path[-1][1] + each[1]]
  10.                 if -1 not in node and 5 not in node and node not in path and maze[node[0]][node[1]] != '#':
  11.                         path.append(node)
  12.                         dfs_maze(path, target)
  13.                         path.pop(-1)

  14. def main():
  15.         dfs_maze([[0,0]], [4, 4])

  16.         for each in paths:
  17.                 print(each)
  18. paths = []
  19. main()
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-9-23 20:15:15 | 显示全部楼层
塔利班 发表于 2018-9-23 20:10
path分配的地址一样,每次做个切片

您好,能说的详细一点不,每次给函数传path这个值难道不是新分配空间吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 20:16:48 | 显示全部楼层
不会啊,你从头到位一共就用了一共path,只不过过程中一直在变化
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 20:17:59 | 显示全部楼层
print(id(path))
函数里加上这个,你可以确认下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 20:48:33 | 显示全部楼层
塔利班 发表于 2018-9-23 20:17
print(id(path))
函数里加上这个,你可以确认下

呃,代码我看懂了,不过你们讨论的是个什么东西,我怎么跟不上你们的思路。。。。。、
什么叫三维的数组,哪三维啊。。。。。。
还有你知不知道如果路径不允许重复的话,怎么写这个代码啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-9-23 20:50:04 | 显示全部楼层
塔利班 发表于 2018-9-23 20:17
print(id(path))
函数里加上这个,你可以确认下

确实,传入列表是可以修改原值的,类似于引用, 那请问做切片的意义是什么呢?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 20:52:33 | 显示全部楼层
ElmLiu 发表于 2018-9-23 20:50
确实,传入列表是可以修改原值的,类似于引用, 那请问做切片的意义是什么呢?

放一个深拷贝,path后续的变化不会影响添加进的元素
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 20:54:39 | 显示全部楼层
RIXO 发表于 2018-9-23 20:48
呃,代码我看懂了,不过你们讨论的是个什么东西,我怎么跟不上你们的思路。。。。。、
什么叫三维的数组 ...

这个已经是不重复版本了吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 21:03:23 | 显示全部楼层
塔利班 发表于 2018-9-23 20:54
这个已经是不重复版本了吧

按照 C 的思路是没有问题的,我只是好奇,每一次 append, 是有添加数组,但是对之前的数据覆盖了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-9-23 21:04:39 | 显示全部楼层
RIXO 发表于 2018-9-23 20:48
呃,代码我看懂了,不过你们讨论的是个什么东西,我怎么跟不上你们的思路。。。。。、
什么叫三维的数组 ...

就是paths储存所有可行的路径,每条路径又是一个二维数组,包含路径的每个点。
这个不重复,给路径添加新节点的时候判断过了新节点是否包含在走过的节点中
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 21:05:35 | 显示全部楼层
claws0n 发表于 2018-9-23 21:03
按照 C 的思路是没有问题的,我只是好奇,每一次 append, 是有添加数组,但是对之前的数据覆盖了

添加了多少个,都是path,虽然放进去时Path内容不一样
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-9-23 21:05:50 | 显示全部楼层
塔利班 发表于 2018-9-23 20:52
放一个深拷贝,path后续的变化不会影响添加进的元素

嗯... 我还是在以后的实践中慢慢去体会这道理  谢谢了!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 21:06:14 | 显示全部楼层
RIXO 发表于 2018-9-23 20:48
呃,代码我看懂了,不过你们讨论的是个什么东西,我怎么跟不上你们的思路。。。。。、
什么叫三维的数组 ...

递归、回溯法
都是一维扩展,还没有到 3 维,2 维而已
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 21:09:06 | 显示全部楼层
塔利班 发表于 2018-9-23 21:05
添加了多少个,都是path,虽然放进去时Path内容不一样

啊,我知道哥哥说什么了,高维数组……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-23 21:09:34 | 显示全部楼层
ElmLiu 发表于 2018-9-23 21:05
嗯... 我还是在以后的实践中慢慢去体会这道理  谢谢了!


def dfs_maze(path, target):
        global paths
        maze = [[" ","#","#"," "," "],[" "," "," ","#"," "],["#"," "," ","#"," "],[" "," "," ","#","#"],[" "," "," "," "," "]]
        
        if path[-1] == target:
                print(path)
                paths.append(path[:])  ##这个要深拷贝
                return paths
            
        for each in [[0,1], [0,-1], [1, 0], [-1, 0]]:
                node = [path[-1][0] + each[0], path[-1][1] + each[1]]
                if (-1 not in node) and (5 not in node) and (node not in path) and (maze[node[0]][node[1]] != '#'):
                    path.append(node)
                    dfs_maze(path, target)
                    path.pop(-1)

def main():
        dfs_maze([[0,0]], [4, 4])

        print("printing all paths")
        for each in paths:
                print(each)
               
paths = []
main()
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 09:14

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表