9

解決するように求められた質問の 1 つで、for ループを使用して配列の最大値を見つけたので、再帰を使用してそれを見つけようとしましたが、これが私が思いついたものです。

public static int findMax(int[] a, int head, int last) {

    int max = 0;
    if (head == last) {
        return a[head];
    } else if (a[head] < a[last]) {
        return findMax(a, head + 1, last);
    } else {
        return a[head];
    }
}

したがって、問題なく動作し、最大値を取得しますが、私の質問は次のとおりです。基本ケースのリターン a[head] と、ヘッドの値が > 最後の値の場合は大丈夫ですか?

4

14 に答える 14

17

今回は比較したい値のインデックスだけで、カウンターを 1 つだけでも同じように簡単に実行できます。

public static int findMax(int[] a, int index) {
    if (index > 0) {
        return Math.max(a[index], findMax(a, index-1))
    } else {
        return a[0];
    }
}

これは何が起こっているかをよりよく示しており、デフォルトの「再帰」レイアウトを使用しています。たとえば、共通の基本ステップがあります。最初の呼び出しは、 を実行することによって行われfindMax(a, a.length-1)ます。

于 2013-10-25T12:50:48.203 に答える
8

実際にはそれよりもはるかに簡単です。基本的なケースは、配列の最後 (以下の 3 項制御ブロックの「else」部分) に達した場合です。それ以外の場合は、現在の呼び出しと再帰呼び出しの最大値を返します。

public static int findMax(int[] a) {
    return findMax(a, 0);
}
private static int findMax(int[] a, int i) {
    return i < a.length
           ? Math.max(a[i], findMax(a, i + 1))
           : Integer.MIN_VALUE;
}

各要素で、現在の要素のうち大きい方と、より大きなインデックスを持つすべての要素を返します。Integer.MIN_VALUE空の配列でのみ返されます。これは線形時間で実行されます。

于 2013-10-25T12:57:15.990 に答える
2

このスレッドに出会い、とても助かりました。再帰と分割統治の両方のケースでの私の完全なコードが添付されています。分割統治の実行時間は、再帰よりわずかに優れています。

//use divide and conquer.
public int findMaxDivideConquer(int[] arr){
    return findMaxDivideConquerHelper(arr, 0, arr.length-1);
}
private int findMaxDivideConquerHelper(int[] arr, int start, int end){
    //base case
    if(end - start  <=  1) return Math.max(arr[start], arr[end]);
    //divide
    int mid = start + ( end - start )/2;
    int leftMax =findMaxDivideConquerHelper(arr, start, mid);
    int rightMax =findMaxDivideConquerHelper(arr, mid+1, end);
    //conquer
    return Math.max( leftMax, rightMax );
}

// use recursion. return the max of the current and recursive call
public int findMaxRec(int[] arr){
    return findMaxRec(arr, 0);
}
private int findMaxRec(int[] arr, int i){
    if (i == arr.length) {
        return Integer.MIN_VALUE;
    }
    return Math.max(arr[i], findMaxRec(arr, i+1));
}
于 2017-01-13T20:46:02.840 に答える
1

これはどうですか ？

public static int maxElement(int[] a, int index, int max) {
    int largest = max;
    while (index < a.length-1) {
        //If current is the first element then override largest
        if (index == 0) {
            largest = a[0];
        }
        if (largest < a[index+1]) {
            largest = a[index+1];
            System.out.println("New Largest : " + largest); //Just to track the change in largest value
        }
        maxElement(a,index+1,largest);
    }
    return largest;
}
于 2016-05-17T05:55:44.440 に答える
0

以下のように再帰的に行うことができます。

反復関係はこのようなものです。

   f(a,n)   = a[n]   if n == size
            = f(a,n+1) if n != size

実装は以下の通り。

   private static int getMaxRecursive(int[] arr,int pos) {
         if(pos == (arr.length-1)) {
                return arr[pos];
         } else {           
                return Math.max(arr[pos], getMaxRecursive(arr, pos+1));
         }
   }

呼び出しは次のようになります

      int maxElement = getMaxRecursive(arr,0);
于 2014-09-13T19:56:53.477 に答える