文心一言 VS 讯飞星火 VS chatgpt （206）-- 算法导论15.4 3题

2024-03-03 15:52
文章标签 chatgpt 算法 ai vs 206 文心一言 讯飞星火 导论 15.4

本文主要是介绍文心一言 VS 讯飞星火 VS chatgpt （206）-- 算法导论15.4 3题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

三、设计 LCS-LENGTH的带备忘的版本，运行时间为O(mn)。需要写代码的时候，请用go语言。

文心一言，代码正常运行：

LCS-LENGTH（Longest Common Subsequence Length）问题的带备忘的版本通常指的是使用动态规划（Dynamic Programming, DP）和备忘录（Memoization）来优化算法性能，避免重复计算。通过维护一个表（即“备忘录”）来存储已经计算过的子问题的解，从而在解决新问题时可以直接查找已存储的结果，而不是重新计算。

以下是使用Go语言实现的一个带备忘的LCS-LENGTH算法的示例。在这个示例中，lcsLength 函数计算两个字符串的最长公共子序列长度，并且使用一个二维数组 memo 来存储子问题的解，其中 memo[i][j] 存储的是 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列长度。

package main  import (  "fmt"  
)  func lcsLength(str1, str2 string) int {  m, n := len(str1), len(str2)  memo := make([][]int, m+1)  for i := range memo {  memo[i] = make([]int, n+1)  }  for i := 1; i <= m; i++ {  for j := 1; j <= n; j++ {  if str1[i-1] == str2[j-1] {  memo[i][j] = memo[i-1][j-1] + 1  } else {  memo[i][j] = max(memo[i-1][j], memo[i][j-1])  }  }  }  return memo[m][n]  
}  func max(a, b int) int {  if a > b {  return a  }  return b  
}  func main() {  str1 := "ABCDEFG"  str2 := "XYZABCDEFGHIJKL"  length := lcsLength(str1, str2)  fmt.Printf("The length of the Longest Common Subsequence is: %d\n", length)  
}

在这个实现中，lcsLength 函数首先初始化一个 (m+1) x (n+1) 的二维数组 memo，其中 m 和 n 分别是两个输入字符串 str1 和 str2 的长度。然后，它使用两个嵌套的循环来遍历 str1 和 str2 的所有字符组合。

如果 str1 的第 i 个字符和 str2 的第 j 个字符相同，则最长公共子序列的长度加一，即 memo[i][j] = memo[i-1][j-1] + 1。如果不同，则最长公共子序列的长度是去掉 str1 的第 i 个字符后的最长公共子序列和去掉 str2 的第 j 个字符后的最长公共子序列中的较大值，即 memo[i][j] = max(memo[i-1][j], memo[i][j-1])。

最后，函数返回 memo[m][n]，即两个字符串的最长公共子序列的长度。

请注意，这个实现的时间复杂度是 O(mn)，其中 m 和 n 分别是两个输入字符串的长度。这是因为我们需要填充一个 m x n 的表，而每个表项的计算时间是常数时间。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

讯飞星火，代码正常运行：

在Go语言中，我们可以使用动态规划来解决这个问题。以下是实现LCS-LENGTH的带备忘的版本的代码：

package main
import "fmt"func max(a, b int) int {if a > b {return a}return b
}func lcsLength(X, Y []int) int {m := len(X)n := len(Y)c := make([][]int, m+1)for i := range c {c[i] = make([]int, n+1)}for i := 0; i <= m; i++ {for j := 0; j <= n; j++ {if i == 0 || j == 0 {c[i][j] = 0} else if X[i-1] == Y[j-1] {c[i][j] = c[i-1][j-1] + 1} else {c[i][j] = max(c[i-1][j], c[i][j-1])}}}return c[m][n]
}func main() {X := []int{1, 3, 4, 5, 6, 7, 7, 8}Y := []int{2, 3, 5, 6, 7, 8, 9, 10}fmt.Println("Length of LCS is", lcsLength(X, Y))
}

在这个程序中，我们首先定义了一个二维数组c，用于存储子问题的解。然后，我们遍历两个输入序列，如果当前位置的元素相同，则该位置的LCS长度为左上角元素的LCS长度加一；否则，该位置的LCS长度为左边元素和上边元素中较大的那个LCS长度。最后，右下角的元素就是整个序列的LCS长度。

在这里插入图片描述

在这里插入图片描述

360智脑，代码不能运行：

以下是一个使用Go语言实现的LCS-Length带备忘的版本：

package mainfunc lcsLength(memo map[int][int]int, X string, Y string, m int, n int) int {if m == 0 || n == 0 {return 0}if v, ok := memo[m][n]; ok {return v}if X[m-1] == Y[n-1] {memo[m][n] = lcsLength(memo, X, Y, m-1, n-1) + 1} else {memo[m][n] = max(lcsLength(memo, X, Y, m-1, n), lcsLength(memo, X, Y, m, n-1))}return memo[m][n]
}func max(a, b int) int {if a > b {return a}return b
}func main() {X := "ABCBDAB"Y := "BDCAB"memo := make(map[int][int]int)m := len(X)n := len(Y)fmt.Println(lcsLength(memo, X, Y, m, n))
}

在这个代码中，我们使用了一个备忘录（memo）来存储之前计算过的LCS长度。当我们计算LCS长度时，我们首先检查备忘录中是否已经有这个值。如果有，我们就直接返回它；如果没有，我们就计算它，并将其存储在备忘录中。

这个算法的运行时间为O(mn)，因为我们在计算LCS长度时，最多需要遍历X和Y字符串的每个字符。

在这里插入图片描述

在这里插入图片描述

智谱清言，代码正常运行：

为了设计一个运行时间为O(mn)的LCS-LENGTH算法，我们可以使用动态规划(DP)技术，并辅以带备忘的递归方法来避免重复计算。在下面给出的Go语言代码中，我们将计算两个字符串str1和str2的最长公共子序列的长度。

package main
import ("fmt"
)
// LCSLength 计算两个字符串的最长公共子序列的长度
// 使用带备忘的递归方法
func LCSLength(str1, str2 string) int {// 创建一个二维切片来保存子问题的结果// dp[i][j] 表示str1的前i个字符与str2的前j个字符的LCS长度dp := make([][]int, len(str1)+1)for i := range dp {dp[i] = make([]int, len(str2)+1)}// 初始化dp数组for i := 0; i <= len(str1); i++ {for j := 0; j <= len(str2); j++ {if i == 0 || j == 0 {dp[i][j] = 0}}}// 递归计算LCS长度，同时更新dp数组return recursiveLCSLength(str1, str2, 0, 0, dp)
}
// recursiveLCSLength 递归计算最长公共子序列的长度
// 同时更新dp数组以避免重复计算
func recursiveLCSLength(str1, str2 string, i, j int, dp [][]int) int {// 检查是否已经计算过这个子问题if dp[i][j] != 0 {return dp[i][j]}// 如果i或j为0，那么LCS长度为0if i == 0 || j == 0 {dp[i][j] = 0return 0}// 如果str1[i-1] == str2[j-1]，那么当前字符是LCS的一部分if str1[i-1] == str2[j-1] {dp[i][j] = 1 + recursiveLCSLength(str1, str2, i-1, j-1, dp)} else {// 否则，取左侧或上侧的LCS长度中的较大值dp[i][j] = max(recursiveLCSLength(str1, str2, i-1, j, dp), recursiveLCSLength(str1, str2, i, j-1, dp))}return dp[i][j]
}
// max 返回两个整数中的较大值
func max(a, b int) int {if a > b {return a}return b
}
func main() {str1 := "ABCBDAB"str2 := "BDCAB"fmt.Println("The length of LCS is:", LCSLength(str1, str2))
}

这段代码定义了一个LCSLength函数，它使用一个二维切片dp来存储子问题的解，并且通过递归函数recursiveLCSLength来计算最长公共子序列的长度。递归函数会在每次需要计算相同子问题时，检查是否已经在dp中存储了结果，以避免重复计算。

main函数中给出了一个例子，计算字符串"ABCBDAB"和"BDCAB"的最长公共子序列的长度，并打印结果。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

天工，代码正常运行：

Certainly! Below is an implementation of the LCS problem with memoization in Go that runs in O(mn) time, where m and n are the lengths of the two input strings. This implementation uses a二维数组 to store the results of subproblems, avoiding重复计算.

package mainimport "fmt"// LCSMemo computes the length of the longest common subsequence between X and Y using memoization.
func LCSMemo(X, Y string) int {m, n := len(X), len(Y)dp := make([][]int, m+1)for i := range dp {dp[i] = make([]int, n+1)}for i := 1; i <= m; i++ {for j := 1; j <= n; j++ {if X[i-1] == Y[j-1] {dp[i][j] = dp[i-1][j-1] + 1} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1])}}}return dp[m][n]
}// max returns the larger of two integers.
func max(a, b int) int {if a >= b {return a}return b
}func main() {X := "AGGTAB"Y := "GXTXAYB"length := LCSMemo(X, Y)fmt.Printf("Length of LCS: %d\n", length)
}

To use this code, simply run it with the Go runtime and it will output the length of the longest common subsequence between the two given strings. The max function is used to handle the comparison of integers, as int in Go does not guarantee a specific signedness.

在这里插入图片描述

在这里插入图片描述

灵小智，代码正常运行：

下面是用Go语言编写的带备忘录的最长公共子序列（LCS）问题的代码示例：

package mainimport ("fmt"
)func max(a, b int) int {if a > b {return a}return b
}func lcsLengthMemoized(X, Y string, m, n int, memo [][]int) int {if m == 0 || n == 0 {return 0}if memo[m][n] != -1 {return memo[m][n]}if X[m-1] == Y[n-1] {memo[m][n] = 1 + lcsLengthMemoized(X, Y, m-1, n-1, memo)return memo[m][n]}memo[m][n] = max(lcsLengthMemoized(X, Y, m-1, n, memo), lcsLengthMemoized(X, Y, m, n-1, memo))return memo[m][n]
}func lcsLength(X, Y string) int {m := len(X)n := len(Y)memo := make([][]int, m+1)for i := range memo {memo[i] = make([]int, n+1)for j := range memo[i] {memo[i][j] = -1}}return lcsLengthMemoized(X, Y, m, n, memo)
}func main() {X := "ABCBDAB"Y := "BDCAB"fmt.Printf("Length of LCS: %d\n", lcsLength(X, Y))
}

在这个代码中，我们使用了备忘录（memo）来保存已计算过的子问题的结果，以避免重复计算。通过将已计算过的结果存储在备忘录中，我们可以将算法的运行时间从指数级别降低到线性级别。这样，算法的运行时间为O(mn)，其中m和n分别是字符串X和Y的长度。

以上是用Go语言编写的带备忘录的LCS问题的代码示例，希望对你有帮助！

在这里插入图片描述

在这里插入图片描述

chatgpt，代码正常运行：

当设计LCS-LENGTH函数的带备忘的版本时，可以使用动态规划的思想。下面是用Go语言实现的代码：

package mainimport ("fmt"
)func lcsLengthMemo(X, Y string) int {m := len(X)n := len(Y)// 创建并初始化备忘录memo := make([][]int, m+1)for i := 0; i <= m; i++ {memo[i] = make([]int, n+1)for j := 0; j <= n; j++ {memo[i][j] = -1}}var lcs func(int, int) intlcs = func(i, j int) int {if memo[i][j] != -1 { // 如果已经计算过，直接返回备忘录中的值return memo[i][j]}if i == 0 || j == 0 { // 边界条件，其中一个字符串为空memo[i][j] = 0return 0}if X[i-1] == Y[j-1] { // 当前字符匹配成功，继续向前匹配memo[i][j] = lcs(i-1, j-1) + 1return memo[i][j]} else { // 当前字符不匹配，取两种情况下的最大值left := lcs(i-1, j)top := lcs(i, j-1)if left > top {memo[i][j] = left} else {memo[i][j] = top}return memo[i][j]}}return lcs(m, n)
}func main() {X := "ABCBDAB"Y := "BDCAB"fmt.Println("LCS长度:", lcsLengthMemo(X, Y))
}

该代码使用了备忘录来存储已经计算过的子问题的结果，避免重复计算。通过递归方式进行动态规划，从后往前匹配字符串，并记录最长公共子序列的长度。运行时间复杂度为O(mn)。

在这里插入图片描述

在这里插入图片描述

kimi，代码正常运行：

在 Go 语言中，设计一个带有备忘（Memoization）的 LCS-LENGTH 版本，可以通过创建一个额外的二维切片来存储已经计算过的子问题的解。这样，当我们需要计算一个新的子问题时，我们首先检查这个解是否已经被计算过。如果已经计算过，我们可以直接使用这个解，而不需要重新计算，从而提高算法的效率。

以下是带有备忘的 LCS-LENGTH 函数的 Go 语言实现：

package mainimport ("fmt"
)// LCS-LENGTH 函数计算两个序列的最长公共子序列的长度
func LCSLength(x, y []int) int {m, n := len(x), len(y)memo := make([][]int, m+1)for i := range memo {memo[i] = make([]int, n+1)}return lcsLengthMemo(x, y, m, n, memo)
}// lcsLengthMemo 是 LCS-LENGTH 的递归实现，带有备忘
func lcsLengthMemo(x, y []int, m, n int, memo [][]int) int {if m == 0 || n == 0 {return 0}// 检查解是否已经在备忘数组中if memo[m][n] != 0 {return memo[m][n]}if x[m-1] == y[n-1] {// 如果当前元素相同，递归计算去掉这两个元素后的子问题的解memo[m][n] = 1 + lcsLengthMemo(x, y, m-1, n-1, memo)} else {// 如果当前元素不同，分别计算两种情况的解，并取最大值memo[m][n] = max(lcsLengthMemo(x, y, m-1, n, memo),lcsLengthMemo(x, y, m, n-1, memo),)}return memo[m][n]
}// max 返回两个整数中的最大值
func max(a, b int) int {if a > b {return a}return b
}func main() {x := []int{1, 0, 0, 1, 0, 1, 0, 1}y := []int{0, 1, 0, 1, 1, 0, 1, 1, 0}length := LCSLength(x, y)fmt.Printf("Length of LCS: %d\n", length)
}

在这个实现中，LCSLength 函数是用户调用的接口，它初始化备忘数组并调用 lcsLengthMemo 函数。lcsLengthMemo 函数是递归实现，它使用备忘数组来避免重复计算。这个算法的时间复杂度是 O(m * n)，因为每个子问题只计算一次，并且我们使用 O(m * n) 的空间来存储备忘数组。

在这里插入图片描述

在这里插入图片描述

混元，代码正常运行：

带备忘的 LCS-LENGTH 算法是一种动态规划方法，用于计算两个字符串的最长公共子序列的长度。以下是使用 Go 语言实现的带备忘的 LCS-LENGTH 算法：

package mainimport ("fmt"
)func lcsLengthMemo(x, y string, m, n int, memo [][]int) int {if m == 0 || n == 0 {return 0}if memo[m][n] != -1 {return memo[m][n]}if x[m-1] == y[n-1] {memo[m][n] = 1 + lcsLengthMemo(x, y, m-1, n-1, memo)} else {memo[m][n] = max(lcsLengthMemo(x, y, m-1, n, memo), lcsLengthMemo(x, y, m, n-1, memo))}return memo[m][n]
}func lcsLength(x, y string) int {m, n := len(x), len(y)memo := make([][]int, m+1)for i := range memo {memo[i] = make([]int, n+1)for j := range memo[i] {memo[i][j] = -1}}return lcsLengthMemo(x, y, m, n, memo)
}func max(a, b int) int {if a > b {return a}return b
}func main() {x := "ABCBDAB"y := "BDCAB"fmt.Printf("The length of the LCS is: %d\n", lcsLength(x, y))
}

这个实现首先创建一个二维数组 memo 用于存储已经计算过的子问题的解。lcsLengthMemo 函数是一个递归函数，用于计算两个字符串的最长公共子序列的长度。当递归到基本情况时，它会返回 0。如果当前子问题已经计算过，它会直接返回已经计算的结果。否则，它会计算当前子问题的解，并将其存储在备忘录中，然后返回解。

lcsLength 函数是一个包装函数，用于初始化备忘录并调用 lcsLengthMemo 函数。最后，main 函数调用 lcsLength 函数并打印结果。

在这里插入图片描述

在这里插入图片描述

这篇关于文心一言 VS 讯飞星火 VS chatgpt （206）-- 算法导论15.4 3题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/770115。

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
AI绘图怎么变现？想做点副业的小白必看！

AI绘图怎么变现？想做点副业的小白必看！

在科技飞速发展的今天，AI绘图作为一种新兴技术，不仅改变了艺术创作的方式，也为创作者提供了多种变现途径。本文将详细探讨几种常见的AI绘图变现方式，帮助创作者更好地利用这一技术实现经济收益。 更多实操教程和AI绘画工具，可以扫描下方，免费获取 定制服务：个性化的创意商机 个性化定制 AI绘图技术能够根据用户需求生成个性化的头像、壁纸、插画等作品。例如，姓氏头像在电商平台上非常受欢迎，
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
从去中心化到智能化：Web3如何与AI共同塑造数字生态

从去中心化到智能化：Web3如何与AI共同塑造数字生态

在数字时代的演进中，Web3和人工智能（AI）正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术，正相互交织，共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界，并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展，它基于去中心化的区块链技术，旨在创建一个开放、透明且用户主导的数字生态。不同于传统
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
AI一键生成 PPT

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人，是不是经常需要制作各种PPT来分享我的生活和想法。但是，你们知道，有时候灵感来了，时间却不够用了！😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手！🌟 什么是Kimi？ 一款月之暗面科技有限公司开发的AI办公工具，帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师，Kimi都能够为你的办公文
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
Andrej Karpathy最新采访：认知核心模型10亿参数就够了，AI会打破教育不公的僵局

Andrej Karpathy最新采访：认知核心模型10亿参数就够了，AI会打破教育不公的僵局

夕小瑶科技说 原创  作者 | 海野 AI圈子的红人，AI大神Andrej Karpathy，曾是OpenAI联合创始人之一，特斯拉AI总监。上一次的动态是官宣创办一家名为 Eureka Labs 的人工智能+教育公司 ，宣布将长期致力于AI原生教育。 近日，Andrej Karpathy接受了No Priors（投资博客）的采访，与硅谷知名投资人 Sara Guo 和 Elad G
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2