1

次の2つのステートメントで少し混乱しています。

以下のプログラムはfinds the index of an element out of a sorted array[no duplicates] using binary search.

int bin(int *arr,int l,int h,int k)
{
    int mid;
    if(l>h)
            return -1;
    if(l==h)
    {
            return arr[l]==k?l:-1;
    }
    else
    {
            mid=(l+h)>>1;
            if(arr[mid]==k)
                    return mid;
            else if(k>arr[mid])
                    bin(arr,mid+1,h,k);
            else
                    bin(arr,l,mid-1,k);
    }
}

プログラムに問題はありません[完璧に動作しています]：

私は次の2つのステートメントで混乱しています：

bin（arr、l、mid-1、k）; http://ideone.com/p1o5U
return bin（arr、l、mid-1、k）; http://ideone.com/lMhgB

上記のステートメントのいずれかを使用すると、正しい結果が得られます。
時間の点でより効率的なステートメントはどれですか？
How the program is working fine even without return statement?

4

3 に答える 3

0

returnステートメントがなくてもプログラムはどのように正常に機能していますか？

この場合、再帰は、指定したパラメーターに関係のないreturnステートメントで終了するため（最後の2回の呼び出しで指定しなくても）、実際には違いはないと思います。ただし、これはコンパイラ固有の詳細であり、信頼すべきではありません。

時間の点でより効率的なステートメントはどれですか？

returnステートメントを含むものは、「else」チェックを読み取る必要がないため、もう少し効率的であると考えるかもしれませんが、違いは非常に小さいです。

ただし、returnステートメントがないと、「機能」していても「正しくない」と見なされ、-Wallから警告が表示されることに注意してください。

この同様の質問も参照してください。その答えからコピー：

表示されるのは、一部のアーキテクチャで機能する実装の詳細が、既知のレジスタをその値（i386ではeax）に設定することによって（整数値）を返すことが原因である可能性があります。したがって、一番下の再帰呼び出しが戻ってこのレジスタを設定し、その間の呼び出しがそのレジスタを踏みつけない場合は、それが一種の機能を果たしていることがわかります。ただし、それに依存してはなりません。

編集：意図的な最適化としての動作を意味しないように文言を変更しました。それがそうであるかどうかわからない。とにかく、一部のコンパイラは実行し、一部は実行しないものです。

于 2012-06-23T10:41:34.217 に答える
0

このプログラムは、さまざまなコンパイラでコンパイルすると、さまざまな結果を生成します。

#include <stdio.h>

int bin(int *arr,int l,int h,int k)
{
    int mid;
    if(l>h)
            return -1;
    if(l==h)
    {
            return arr[l]==k?l:-1;
    }
    else
    {
            mid=(l+h)>>1;
            if(arr[mid]==k)
                    return mid;
            else if(k>arr[mid])
                    bin(arr,mid+1,h,k);
            else
                    bin(arr,l,mid-1,k);
    }
}

int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int main(void)
{
  int i;
  for (i = 0; i <= 11; i++)
    printf("bin(%d): %d\n", i, bin(arr, 0, 9, i));
  return 0;
}

出力（コンパイラ：Open Watcom C / C ++ 1.9）：

>nrv.exe
bin(0): 0
bin(1): 1
bin(2): 2
bin(3): 3
bin(4): 4
bin(5): 4
bin(6): 6
bin(7): 7
bin(8): 8
bin(9): 9
bin(10): 10
bin(11): 11

出力（コンパイラ：MinGW gcc 4.6.2）：

$ nrv.exe
bin(0): -1
bin(1): 0
bin(2): 1
bin(3): 2
bin(4): 3
bin(5): 4
bin(6): 5
bin(7): 6
bin(8): 7
bin(9): 8
bin(10): 9
bin(11): -1

プログラムに問題はないと言っても過言ではありません[完璧に動作しています]。関数は未定義のbin()動作を呼び出します。

于 2012-06-23T11:15:23.003 に答える
0

トピック外：とにかく再帰を使用する場合は、下限を削除してプログラムを大幅に簡素化し、代わりにポインターをバンプすることができます。

#include <stdio.h>

int bin(int *arr, int n, int k);
int bin(int *arr, int n, int k)
{
    int mid;
    if (n <= 0) return -1;

    mid = n / 2;
    if (arr[mid] == k) return mid;
    if (k < arr[mid]) return bin(arr, mid, k);

    n = bin(arr+mid+1, n-(mid+1), k);
    return (n<0) ? n : mid+1+n;
}

int main(void)
{
    int array[] = {0,1,2,3,4,5,6,7,8,9,10,11};
    int result, val;

    for (val= -2; val < 15; val++) {
        result = bin(array, 10, val);
        printf("Val=%d -> %d\n", val, result);
        }
return 0;
}
于 2012-06-23T13:05:23.437 に答える