gpt4 book ai didi

Python 递归函数奇怪的行为

转载 作者:搜寻专家 更新时间:2023-10-31 00:56:17 25 4
gpt4 key购买 nike

<分区>

我使用带内存的递归在 Python 中编写了最长公共(public)子序列:

def print2d(table):
print '\n'.join([''.join(['{:4}'.format(item) for item in row]) for row in table])

a="123"
b="213"
m = [[-1]*len(b)]*len(a)
def lcs(i,j):
print i, j
print2d(m)

if i== -1 or j == -1:
return 0;
if m[i][j] != -1:
return m[i][j]

res = 0
res = max(res, lcs(i, j-1))
res = max(res, lcs(i-1, j))
if a[i] == b[j]:
res = max(res, 1 + lcs(i-1,j-1))
m[i][j]=res
return res

print lcs(len(a)-1,len(b)-1)
print2d(m)

所有那些 print 语句都在那里,因为我没有得到正确的结果并决定看看算法是如何工作的。我的发现让我吃惊。如果您自己运行它,您可以看到打印的表格并且它们看起来不错,直到:

0 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 0
-1 -1 -1
-1 -1 -1
-1 -1 -1
0 -1
0 -1 -1
0 -1 -1
0 -1 -1
1 1
1 -1 -1
1 -1 -1
1 -1 -1
1 0
1 -1 -1
1 -1 -1
1 -1 -1
0 1
1 -1 -1
1 -1 -1
1 -1 -1

为什么突然在 0 -1 这一步整个第一列变成了 0 ?因此,我快速创建了 C++ 程序,以相同的方式执行完全相同的操作:

#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
using namespace std;
string a = "123",
b = "213";
int mem[1000][1000];

int lcs(int i, int j) {
cout << i << " " << j << "\n";
for(auto i = 0; i < a.length(); i++){
for(auto j = 0; j < b.length(); j++){
cout << setw(4) << right << mem[i][j];
}
cout << "\n";
}
if (i == -1 || j == -1) {
return 0;
}
if (mem[i][j] != -1) {
return mem[i][j];
}
int res = 0;
res = max(res, lcs(i, j - 1));
res = max(res, lcs(i - 1, j));
if (a[i] == b[j]) {
res = max(res, 1 + lcs(i - 1, j - 1));
}
mem[i][j] = res;
return res;
}
int main(){
memset(mem, -1, sizeof mem );
int r = lcs(a.length()-1, b.length()-1);
cout << r << "\n";
return 0;
}

它按预期工作。对应的表如下所示:

0 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
-1 0
-1 -1 -1
-1 -1 -1
-1 -1 -1
0 -1
0 -1 -1
-1 -1 -1
-1 -1 -1
1 1
0 -1 -1
1 -1 -1
1 -1 -1
1 0
0 -1 -1
1 -1 -1
1 -1 -1
0 1
0 -1 -1
1 -1 -1
1 -1 -1

我很困惑,为什么 Python 和 C++ 代码并没有那么不同,却产生如此截然不同的结果。

我是否遗漏了一些有关 Python 中递归函数如何工作的信息?或者是因为在 Python 中我使用列表列表而不是 C++ 中的二维数组?

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com