-2

以下に示すコードは正常に動作します。if 句内で見つかった要素の位置を出力して終了します。要素が見つからない場合、関数は最大まで実行され、要素が見つからなかったことを示すために呼び出し元の関数に 0 を返します。

ただし、見つかった要素の位置を出力するのではなく、呼び出し元の関数に返すことを考えていました。位置を返すと、呼び出し元の関数ではなく、関数の以前のインスタンスに戻るだけなので、私は打たれました。これを達成する方法は？

#include <stdio.h>
#include <stdlib.h>

int RLinearSearch(int A[],int n,int key)
{
    if(n<1)
        return 0;
    else
    {
        RLinearSearch(A,n-1,key);
        if(A[n-1]==key)
        {
            printf("found %d at %d",key,n);
            exit(0);
        }
    }
    return 0;
}

int main(void) 
{
    int A[5]={23,41,22,15,32};   // Array Of 5 Elements 
    int pos,n=5;

    pos=RLinearSearch(A,n,23);

    if(pos==0)
        printf("Not found");

    return 0;
}
4

4 に答える 4

2

位置を返すと、呼び出し元の関数ではなく、関数の以前のインスタンスに戻るだけなので、私は打たれました。

この問題は、再帰呼び出し自体から再帰呼び出しの結果を返すことで解決できます。

int RLinearSearch(int A[], int n, int key) {
    if(n<0) { // Base case - not found
        return -1;
    }
    if(A[n]==key) { // Base case - found
        return n;
    }
    // Recursive case
    return RLinearSearch(A, n-1, key);
}

この実装はn現在の要素のインデックスとして扱われるため、呼び出し元はこの例では 5 ではなく 4 を渡す必要があります。

デモ 1。

注:基本ケースを結合することで、コードをさらに単純化できます。

int RLinearSearch(int A[], int n, int key) {
    return (n<0 || A[n]==key) ? n : RLinearSearch(A, n-1, key);
}

デモ 2。

于 2016-07-11T16:01:34.997 に答える
1

あなたの問題から始めてください：キーが見つかった場所のインデックスを返す線形検索関数には、配列、検索nの開始インデックス、検索キーkの3つのパラメータがあります。

だからあなたは持っています：

int RLinearSearch(int[] A, int n, int k) 
{    
    if (n=>A.length()) return (-1);//base case(k not found in A)
    else if (A[n]==k) return n; //found case
    else return RLinearSearch(A, n+1, key); //continue case(keep looking through array)
}
int main(void){
    int A[5]={23,41,22,15,32};   // Array Of 5 Elements 
    int pos,n=0;

    pos=RLinearSearch(A,n,23);
    if (pos == -1) printf("Not Found");
    return 0;
}

n-1 を返すだけで正しいインデックスが得られるように変更することもできます。

于 2016-07-11T16:17:02.120 に答える
0 
public static int recursiveLinearSearch(int[] data, int index, int key){
    
    if(index==data.length)
        return -1;
    if(data[index]==key)
        return index;
    
    return recursiveLinearSearch(data, index+1, key);
    
}
于 2020-12-22T00:38:29.193 に答える