尋找最大公共子

Question

我有下面的代碼，它不因爲某些原因，我想弄清楚正常工作：

public static int score(String gene1, String gene2){ 
    char[] a=new char[gene1.length()]; 
    char[] b=new char[gene2.length()]; 
    a=gene1.toCharArray(); 
    b=gene2.toCharArray(); 
    return score(a, b, 0,0); 
} 

private static int score(char[] a, char[] b, int i, int j){ 
    if(a[i]=='\0' || b[j]=='\0') 
     return 0; 
    else if (a[i]==b[j]) 
     return 1+score(a, b, i+1, j+1); 
    else 
     return max(score(a, b,i+1, j),score(a, b, i, j+1)); 
} 

private static int max (int a, int b){ 
    if (a<b) return b; 
    else return a; 
} 

這裏是它失敗：

assertEquals(2, GeneAnalysis.score("ACGT","AC")); 

我得到一個IndexOutofBoundsError

任何想法？另外，在提供幫助時，請不要更改方法參數。他們應該是他們的樣子。這

Answer 1

部分似乎是C和Java之間的混亂....

if(a[i]=='\0' || b[j]=='\0') 
     return 0; 

C有字符串空終止，Java則沒有。相反，檢查Java數組，你將需要使用。長度屬性的結束......是這樣的：

if(i >= a.length || j >= b.length) 

編輯基於評論。

真的，你應該就這個問題提出一個單獨的問題......但這裏是一個刺探它是如何工作的。首先你使用遞歸，這是一個棘手的概念。維基百科可能可以幫助您掌握遞歸的基礎知識。

下面是代碼更接近我會怎麼寫呢，有意見顯示您的訂單發生的事情：

public class Main 
{ 
    public static void main(String[] args) 
    { 
     final int value; 

     value = score("ACGT", "AC"); 
     System.out.println(value); 
    } 

    public static int score(final String gene1, 
          final String gene2) 
    { 
     final char[] a; 
     final char[] b; 
     final int s; 

     a = gene1.toCharArray(); 
     b = gene2.toCharArray(); 
     s = score(a, b, 0, 0); 

     return (s); 
    } 

    private static int score(final char[] a, 
          final char[] b, 
          final int idxA, 
          final int idxB) 
    { 
     final int value; 

     // for all calls: a.length == 4 and b.length == 2 
     // first call: idxA == 0 and idxB == 0 - false || false == false 
     // second call: idxA == 1 and idxB == 1 - false || false == false 
     // third call: idxA == 2 and idxB == 2 - false || true == true  
     if(idxA >= a.length || idxB >= b.length) 
     { 
      // third call: will return 0    
      value = 0; 
     } 
     // first call: a[idxA] == A and b[idxB] == A - true 
     // second call: a[idxB] == C and b[idxB] == C - true 
     else if(a[idxA] == b[idxB]) 
     { 
      // this is recursion 
      // first call: 1 + score(a, b, 1, 1) 
      // second call: 1 + score(a, b, 2, 2) 

      // after the third call the call stack starts unwinding 
      // second call: 1 + 0 == 1 
      // first call: 1 + 1 == 2 
      value = 1 + score(a, b, idxA + 1, idxB + 1); 
     } 
     else 
     { 
      final int x; 
      final int y; 

      x = score(a, b, idxA + 1, idxB); 
      y = score(a, b, idxB,  idxB + 1); 
      value = max(x, y); 
     } 

     // third call: 0 
     // second call: 1 
     // first call: 2 
     return (value); 
    } 

    // Can you use Math.max(int, int) instad? 
    private static int max(final int x, final int y) 
    { 
     final int value; 

     if(x < y) 
     { 
      value = y; 
     } 
     else 
     { 
      value = x; 
     } 

     return (value); 
    } 
} 

Answer 2

public static int score(String gene1, String gene2){ 
    char[] a=gene1.toCharArray();//assign it directly 
    char[] b=gene2.toCharArray(); 
    return score(a, b, 0, 0); 
} 

private static int score(char[] a, char[] b, int i, int j) { 
    //check for end using length, java doesn't use that nullbyte-stuff for it 
    //this caused the failure 
    if(i==a.length || j==b.length) { 
     return 0; 
    } else if (a[i]==b[j]) { 
     return 1+score(a, b, i+1, j+1); 
    } else { 
     return max(score(a, b, i+1, j), score(a, b, i, j+1)); 
    } 
} 

private static int max (int a, int b){ 
    if (a<b) return b; 
    return a; 
} 

Answer 3

char[] a=new char[gene1.length()]; 
a=gene1.toCharArray(); 

嗯。在第一行中分配的數組會發生什麼？