遞歸算法來尋找數組中的最小元素

Question

我有一些遞歸算法的僞代碼，可以找到數組中的最小數。

這是算法。

Min(A[0..n - 1]) 
If n = 1 return A[0] 
else 
{ 
    temp <-- Min(A[0..n - 2]) 
    if temp <= A[n - 1] 
    return temp 
    else return A[n - 1] 
} 

一部分我不理解該僞代碼是行 「臨時< - 最小（A [0..N - 2]）」。具體來說，爲什麼在遞歸調用中「n - 2」而不是「n - 1」？

我的另一個問題是我將如何在代碼中實現該行。我正在使用Java。

在此先感謝您的幫助。

Answer 1

因爲你的數組索引從0到n-1（含）。你需要遞減一個小數組的子數組，因此n-2。

Answer 2

我的另一個問題是我將如何在代碼中實現該行。

如果您使用的是數組。

// create an array with one less element. 
A a2 = new A[a.length-1]; 
// copy the elements 
System.arrayCopy(a,0,a2,0,a2.length); 

如果您使用的是列表

List<A> a2 = a.subList(0, a.length-1); 

Answer 3

你的第一個問題：

，因爲你使用的是遞歸算法，爲了解決這個問題，首先要解決的與較小尺寸相同的問題。在這個僞代碼中，爲了找到長度爲n的數組的最小值，首先找到大小爲n-1的相同數組的最小值，然後將最小值與第n個元素進行比較。你的數組的索引從0到n-1（這會使它的長度= n），所以爲了遞歸調用，你必須調用從索引0到n-2（n-1個元素）的數組。

你的第二個問題： 這是我將如何實現在Java代碼：每次改乘需要是一個更接近遞歸的結束時間

public class Minimum { 
    public Minimum(int[] A) { 
    findMin(A, 0, A.length-1); 
} 

public int findMin(int [] A, int start, int end){ 
    if (start== end-1) 
     return A[0]; 
    else{ 
     int temp=findMin(A, start, end-1); 
     if (temp<=A[end]) 
      return temp; 
     else 
      return A[end]; 
    } 
} 

}