第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全,請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問(wèn)題,去搜搜看,總會(huì)有你想問(wèn)的

Go:打印結(jié)果數(shù)組的最長(zhǎng)公共子序列

Go:打印結(jié)果數(shù)組的最長(zhǎng)公共子序列

Go
函數(shù)式編程 2021-07-09 03:35:46
我已經(jīng)實(shí)現(xiàn)了最長(zhǎng)公共子序列算法并獲得了最長(zhǎng)的正確答案,但無(wú)法弄清楚打印出最長(zhǎng)公共子序列的組成部分的方法。也就是說(shuō),我成功獲得了最長(zhǎng)公共子序列數(shù)組的長(zhǎng)度,但我想打印出最長(zhǎng)的子序列。此代碼的游樂(lè)場(chǎng)在這里http://play.golang.org/p/0sKb_OARnf/*X = BDCABAY = ABCBDAB => Longest Comman Subsequence is B C BDynamic Programming method : O ( n )*/package mainimport "fmt"func Max(more ...int) int {  max_num := more[0]  for _, elem := range more {    if max_num < elem {      max_num = elem    }  }  return max_num}func Longest(str1, str2 string) int {  len1 := len(str1)  len2 := len(str2)  //in C++,  //int tab[m + 1][n + 1];  //tab := make([][100]int, len1+1)  tab := make([][]int, len1+1)  for i := range tab {    tab[i] = make([]int, len2+1)  }  i, j := 0, 0  for i = 0; i <= len1; i++ {    for j = 0; j <= len2; j++ {      if i == 0 || j == 0 {        tab[i][j] = 0      } else if str1[i-1] == str2[j-1] {        tab[i][j] = tab[i-1][j-1] + 1        if i < len1 {          fmt.Printf("%c", str1[i])        }      } else {        tab[i][j] = Max(tab[i-1][j], tab[i][j-1])      }    }  }  fmt.Println()  return tab[len1][len2]}func main() {  str1 := "AGGTABTABTABTAB"  str2 := "GXTXAYBTABTABTAB"  fmt.Println(Longest(str1, str2))  //Actual Longest Common Subsequence: GTABTABTABTAB  //GGGGGTAAAABBBBTTTTAAAABBBBTTTTAAAABBBBTTTTAAAABBBB  //13  str3 := "AGGTABGHSRCBYJSVDWFVDVSBCBVDWFDWVV"  str4 := "GXTXAYBRGDVCBDVCCXVXCWQRVCBDJXCVQSQQ"  fmt.Println(Longest(str3, str4))  //Actual Longest Common Subsequence: ?  //GGGTTABGGGHHRCCBBBBBBYYYJSVDDDDDWWWFDDDDDVVVSSSSSBCCCBBBBBBVVVDDDDDWWWFWWWVVVVVV  //14}當(dāng)我嘗試在選項(xiàng)卡更新時(shí)打印出子序列時(shí),結(jié)果是重復(fù)的。我想為 str1 和 str2 打印出類似“GTABTABTABTAB”的內(nèi)容
查看完整描述

1 回答

?
有只小跳蛙

TA貢獻(xiàn)1824條經(jīng)驗(yàn) 獲得超8個(gè)贊

似乎我在回答這個(gè)問(wèn)題時(shí)跳了起來(lái)。在最長(zhǎng)公共子序列的維基百科頁(yè)面上,他們給出了計(jì)算出 LCS 后打印出 LCS 的偽代碼。只要我有時(shí)間,我就會(huì)在 go up here 中放置一個(gè)實(shí)現(xiàn)。


舊的無(wú)效答案

一旦將角色注冊(cè)為子序列的一部分,您就會(huì)忘記從角色移動(dòng)。


下面的代碼應(yīng)該可以工作。查看該行之后的兩fmt.Printf("%c", srt1[i])行。


游樂(lè)場(chǎng)鏈接


/*

X = BDCABA

Y = ABCBDAB => Longest Comman Subsequence is B C B


Dynamic Programming method : O ( n )

*/


package main


import "fmt"


func Max(more ...int) int {

    max_num := more[0]

     for _, elem := range more {

        if max_num < elem {

            max_num = elem

        }

    }

    return max_num

}


func Longest(str1, str2 string) int {

    len1 := len(str1)

    len2 := len(str2)


    //in C++,

    //int tab[m + 1][n + 1];

    //tab := make([][100]int, len1+1)


    tab := make([][]int, len1+1)

    for i := range tab {

        tab[i] = make([]int, len2+1)

    }


    i, j := 0, 0

    for i = 0; i <= len1; i++ {

        for j = 0; j <= len2; j++ {

            if i == 0 || j == 0 {

                tab[i][j] = 0

            } else if str1[i-1] == str2[j-1] {

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

                if i < len1 {

                    fmt.Printf("%c", str1[i])

                                            //Move on the the next character in both sequences

                    i++

                    j++

                }

            } else {

                tab[i][j] = Max(tab[i-1][j], tab[i][j-1])

            }

        }

    }

    fmt.Println()

    return tab[len1][len2]

}


func main() {

    str1 := "AGGTABTABTABTAB"

    str2 := "GXTXAYBTABTABTAB"

    fmt.Println(Longest(str1, str2))

    //Actual Longest Common Subsequence: GTABTABTABTAB

    //GGGGGTAAAABBBBTTTTAAAABBBBTTTTAAAABBBBTTTTAAAABBBB

    //13


    str3 := "AGGTABGHSRCBYJSVDWFVDVSBCBVDWFDWVV"

    str4 := "GXTXAYBRGDVCBDVCCXVXCWQRVCBDJXCVQSQQ"

    fmt.Println(Longest(str3, str4))

    //Actual Longest Common Subsequence: ?

     //GGGTTABGGGHHRCCBBBBBBYYYJSVDDDDDWWWFDDDDDVVVSSSSSBCCCBBBBBBVVVDDDDDWWWFWWWVVVVVV

    //14

}


查看完整回答
反對(duì) 回復(fù) 2021-07-12
  • 1 回答
  • 0 關(guān)注
  • 280 瀏覽
慕課專欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)