python递归二元函数 python定义二元函数

【python】求两个字符串的公共字串？

题目：找出两个字符串的最长公共字串，例如字符串“abccade”与字符串“dgcadde”的最长公共子串为“cad”。

分析：动态规划法。通过把中间的比较结果记录下来，从而可以避免字符的重复比较。：

首先定义二元函数（i，j）：表示分别以s1[i],s2[j]结尾的公共子串的长度，显然，f（0， j） = 0 (j = 0),f(i, 0) = 0(i = 0),那么对于f(i +1, j + 1)而言，则有如下两种取值：

（1) f(i + 1, j +1) = 0,当str1[i + 1] != str2[j + 1]时

（2）f(i + 1, j +1) = f(i, j) + 1,当str1[i + 1] == str2[j + 1]时

根据这个公式可以计算出f(i, j)（0= i=len(s1), 0 = j = len(s2)，所有的值，从而可以找出最长的子串。

def getMaxSubStr(str1, str2):

    len1 = len(str1)

    len2 = len(str2)

    sb = ''

    maxs = 0  # 用来记录最长公共子串的长度

    maxI = 0  # 用来记录最长公共字串最后一个字符的位置

    # 申请新的空间来记录公共字串长度信息

    M = [([None] * (len1 + 1)) for i in range(len2 + 1)]

    i = 0

    while i len1 + 1:

        M[i][0] = 0

        i += 1

    j = 0

    while j len2 + 1:

        M[0][j] = 0

        j += 1

    # 通过利用递归公式填写新建得二维数组（公共字串得长度信息）

    i = 1

    while i len1 + 1:

        j = 1

        while j len2 + 1:

            if list(str1)[i - 1] == list(str2)[j - 1]:

                M[i][j] = M[i - 1][j - 1] + 1

                if M[i][j] maxs:

                    maxs = M[i][j]

                    maxI = i

            else:

                M[i][j] = 0

            j += 1

        i += 1

    i = maxI - maxs

    while i maxI:

        sb = sb + list(str1)[i]

        i += 1

    return sb

if __name__ == "__main__":

    str1 = 'abccade'

    str2 = 'dgcadde'

    print(getMaxSubStr(str1, str2))

程序运行结果：

cad

相关问答

Q1: python如何用递归函数求1+2+3+4+5的值

python用递归函数求1+2+3+4+5的值的方法：

1、写出临界条件

2、找这一次和上一次的关系

3、假设当前函数已经能用，调用自身计算上一次的结果，再求出本次的结果

代码实现如下：

Q2: Python进阶：递归算法

  递归算法常用来解决结构相似python递归二元函数的问题。

  所谓结构相似python递归二元函数，是指构成原问题的子问题与原问题在结构上相似python递归二元函数，可以用类似的方法解决。具体地python递归二元函数，整个问题的解决，可以分为两部分python递归二元函数：第一部分是一些特殊情况，有直接的解法；第二部分与原问题相似，但比原问题的规模小，并且依赖第一部分的结果。

  本质上，递归是把一个不能或不好解决的大问题转化成一个或几个小问题，再把这些小问题进一步分解成更小的问题，直至每个小问题都可以直接解决。

  实际上，递归会将前面所有调用的函数暂时挂起，直到递归终止条件给出明确的结果后，才会将所有挂起的内容进行反向计算。其实，递归也可以看作是一种反向计算的过程，前面调用递归的过程只是将表达式罗列出来，待终止条件出现后，才依次从后向前倒序计算前面挂起的内容，最后将所有的结果一起返回。

Q3: 如何理解python中的递归函数

递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。

绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。

计算机科学家尼克劳斯·维尔特如此描述递归：

递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此，在计算机科学中，递归可以被用来描述无限步的运算，尽管描述运算的程序是有限的。

python 2 递归函数和其它语言，基本没有差别，只是不支持尾递归。无限递归最大值为固定的，但可以修改。

作者：黄哥

python递归二元函数的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于python定义二元函数、python递归二元函数的信息别忘了在本站进行查找喔。