如何確定需要使用哪種方法來編寫算法？

光店主擁有不同類型，其由以不同順序不同顏色的燈泡的燈泡幾個鏈。除此之外，他還收集各種顏色的燈泡。燈泡鏈由其燈泡的顏色順序標識。他希望通過或者通過將一種類型的燈串轉換成另一種類型的燈串的：如何確定需要使用哪種方法來編寫算法？

•在某個位置添加一個燈泡。 •從位置移除燈泡。 •用另一種不同顏色的燈泡替換燈泡。兩個不同的燈泡鏈

給定兩個顏色序列，找出最小沒有。進行這種轉變所需的操作。（假定每個顏色可以由一個字符來表示，因此，燈泡鏈的顏色序列可被表示爲字符或字符串的序列。）輸入/輸出規格輸入： •第一顏色序列（串A） •第二色序（字符串B）

輸出：最小到第一燈串轉換成第二（整數）所需的操作

實例輸入1數：「asdfgh」輸入2：「sdfgh」

輸出：1

輸入1：「X」輸入2：「ASDF」

輸出：4

在上面給定的情景

，如何找到解決辦法，什麼必須的第一步？我是算法編寫的熱心人和初學者。

來源

2015-01-16 Alok Mishra

問題描述兩個字符串之間的編輯距離（或Levenshtein距離）。查看[Levenshtein distance]（http://en.wikipedia.org/wiki/Levenshtein_distance）瞭解更多信息。 –

有趣的問題，我曾經有過一個類似的問題（上dumbbels更換的權重，但額外增加他們只能從一個側面來代替）;沒有得到答案......你也可以嘗試數學論壇，因爲它可能是一個已知的數學問題。 –

維基百科：

int LevenshteinDistance(string s, string t) 
{ 
    // degenerate cases 
    if (s == t) return 0; 
    if (s.Length == 0) return t.Length; 
    if (t.Length == 0) return s.Length; 

    // create two work vectors of integer distances 
    int[] v0 = new int[t.Length + 1]; 
    int[] v1 = new int[t.Length + 1]; 

    // initialize v0 (the previous row of distances) 
    // this row is A[0][i]: edit distance for an empty s 
    // the distance is just the number of characters to delete from t 
    for (int i = 0; i < v0.Length; i++) 
     v0[i] = i; 

    for (int i = 0; i < s.Length; i++) 
    { 
     // calculate v1 (current row distances) from the previous row v0 

     // first element of v1 is A[i+1][0] 
     // edit distance is delete (i+1) chars from s to match empty t 
     v1[0] = i + 1; 

     // use formula to fill in the rest of the row 
     for (int j = 0; j < t.Length; j++) 
     { 
      var cost = (s[i] == t[j]) ? 0 : 1; 
      v1[j + 1] = Minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost); 
     } 

     // copy v1 (current row) to v0 (previous row) for next iteration 
     for (int j = 0; j < v0.Length; j++) 
      v0[j] = v1[j]; 
    } 

    return v1[t.Length]; 
}

來源

2015-01-16 14:13:21 Joe

謝謝，它幫助了我。儘管我很想知道如何爲這些問題選擇方法。 –

如何確定需要使用哪種方法來編寫算法？

回答

相關問題