38

今日私に質問がありましたが、それが可能だとは思いませんが、間違っているか、考えすぎている可能性があります. Cで反復を使用せずに配列を反転するにはどうすればよいですか?

私の考えでは、配列は任意のサイズになる可能性があり、何らかの形式の反復を使用せずにそのようなサポートを念頭に置いて C プログラムを表現することはできないため、それは不可能だと思います。

4

7 に答える 7

86

あなたの質問への答えは、はい、 iteration なしで配列を逆にすることができるということです。質問自体の言い回しはあいまいかもしれませんが、質問の趣旨は明らかです。再帰アルゴリズムを使用できます。この意味での再帰の意味については、まったく曖昧ではありません。

一流企業との面接でこの質問をされた場合、再帰の意味を本当に理解していることを示すには、次の疑似コードで十分です。

function reverse(array)

    if (length(array) < 2) then
        return array

    left_half = reverse(array[0 .. (n/2)-1])
    right_half = reverse(array[(n/2) .. (n-1)])

    return right_half + left_half

end

たとえば、ラテン アルファベットの最初の 16 文字 [A]..[P] を含む 16 要素の配列がある場合、上記の逆アルゴリズムは次のように視覚化できます。

                   Original Input

1.                ABCDEFHGIJKLMNOP                   Recurse
2.        ABCDEFGH                IJKLMNOP           Recurse
3.    ABCD        EFGH        IJKL        MNOP       Recurse
4.  AB    CD    EF    GH    IJ    KL    MN    OP     Recurse

5. A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P    Terminate

6.  BA    DC    FE    HG    JI    LK    NM    PO     Reverse
7.    DCBA        HGFE        LKJI        PONM       Reverse
8.        HGFEDCBA                PONMLKJI           Reverse
9.                PONMLKJIHGFEDCBA                   Reverse

                  Reversed Output

再帰アルゴリズムで解決される問題はすべて、分割統治パラダイムに従います。つまり、次のようになります。

  1. 問題は [2 つ以上の] サブ問題に分割されます。各サブ問題は元の問題よりも小さいですが、元の問題と同様の方法で解決できます (分割)。

  2. 問題は [2 つ以上の] サブ問題に分割され、各サブ問題は独立しており、再帰的に、または十分に小さい場合は単純な方法 (征服) で解決できます。

  3. 問題は [2 つ以上の] サブ問題に分割され、これらのサブ問題の結果が組み合わされて、元の問題の解が得られます (結合)。

配列を反転するための上記の疑似コードは、上記の基準を厳密に満たしています。したがって、これは再帰的アルゴリズムと見なすことができ、反復を使用せずに配列の反転を実行できることは間違いありません。

追加の背景情報
反復、再帰実装、および再帰アルゴリズムの違い

再帰的な実装はアルゴリズムが再帰的であることを意味するというのはよくある誤解です。それらは同等ではありません。上記の解決策の詳細な説明を含む、理由に関する決定的な説明を次に示します。


反復と再帰とは何ですか?

さかのぼること 1990 年に、コンピュータ サイエンスの分野で最も尊敬されている現代のアルゴリズム分析の 3 人の学者、Thomas H. Cormen、Charles E. Leiserson、およびRonald L. Rivestが、高く評価されているIntroduction to Algorithms をリリースしました。この本は、200 を超える尊敬されるテキストをまとめたものであり、20 年以上にわたり、世界中の一流大学のほとんどでアルゴリズムを教えるための最初で唯一のテキストとして使用されてきました。 . Cormen、Leiserson、および Rivest は、何がIteratingを構成し、何が Recursing を構成するかについて明確に説明しました。

2 つの古典的な並べ替えアルゴリズムであるInsertion SortとMerge Sortの分析と比較において、彼らは反復アルゴリズムと再帰アルゴリズムの基本的な特性を説明しています (反復の古典的な数学的概念が同じコンテキストで使用されている場合、あいまいさを解消するためにインクリメンタルアルゴリズムと呼ばれることもあります)。

まず、挿入ソートは反復アルゴリズムとして分類され、その動作は次のように要約されます。

部分配列 A[1.. j -1] をソートしたら、単一項目 A[ j ] を適切な場所に挿入し、ソートされた配列 A[1.. j ] を生成します。

出典:アルゴリズム入門- Cormen、Leisersen、Rivest、1990 MIT Press

このステートメントは、反復アルゴリズムを、アルゴリズムの前の実行 (「反復」) の結果または状態に依存するものとして分類し、そのような結果または状態情報を使用して、現在の反復の問題を解決します。

一方、マージソートは再帰アルゴリズムに分類されます。再帰アルゴリズムは、分割統治法と呼ばれる処理パラダイムに準拠しています。これは、再帰アルゴリズムの操作を非再帰アルゴリズムと区別する 3 つの基本的な基準のセットです。特定の問題の処理中に次の場合、アルゴリズムは再帰的と見なすことができます。

  1. 問題は [2 つ以上の] サブ問題に分割されます。各サブ問題は元の問題よりも小さいですが、元の問題と同様の方法で解決できます (分割)。

  2. 問題は [2 つ以上の] サブ問題に分割され、各サブ問題は再帰的に、または十分に小さい場合は単純な方法 (征服) で解決できます。

  3. 問題は [2 つ以上の] サブ問題に分割され、これらのサブ問題の結果が組み合わされて、元の問題の解が得られます (結合)。

参照:アルゴリズムの紹介- Cormen、Leisersen、Rivest、1990 MIT Press

反復アルゴリズムと再帰アルゴリズムはどちらも、終了条件に達するまで作業を続けます。挿入ソートの終了条件は、j番目のアイテムが配列 A[1.. j ] に適切に配置されていることです。分割統治アルゴリズムの終了条件は、パラダイムの基準 2 が「底を打った」ときです。つまり、サブ問題のサイズが、それ以上分割せずに解決できるほど十分に小さいサイズに達したときです。

分割統治パラダイムでは、再帰を可能にするために、サブ問題が元の問題と同様の方法で解決可能でなければならないことに注意することが重要です。元の問題はスタンドアロンの問題であり、外部に依存していないため、サブ問題も、外部に依存していないスタンドアロンの問題であるかのように、特に他のサブ問題で解決できる必要があります。これは、Divide and Conquer アルゴリズムのサブ問題が自然に独立している必要があることを意味します。

逆に、反復アルゴリズムへの入力はアルゴリズムの以前の反復に基づいているため、考慮して順番に処理する必要があることに注意することも同様に重要です。これにより、アルゴリズムが問題を再帰的に解決できるサブ問題に分割するのを防ぐ反復間の依存関係が作成されます。たとえば、挿入ソートでは、アイテム A[1.. j ] を 2 つのサブセットに分割して、A[ j ] の配列内のソート位置がすべてのアイテム A[1.. j -1の前に決定されるようにすることはできません。 A[1.. j -1]のいずれかが配置されている間に、A[ j ]の実際の適切な位置が移動する可能性があるためです。

再帰アルゴリズムと再帰実装

再帰という用語の一般的な誤解は、あるタスクの再帰的な実装は、問題が再帰的なアルゴリズムで解決されたことを自動的に意味するという一般的で間違った仮定があるという事実に由来します。再帰アルゴリズムは、再帰実装と同じではありません。

再帰的な実装には、タスク全体が解決されているのとまったく同じ方法でタスク全体のサブ部分を解決するために、最終的に自分自身を呼び出す関数または関数のグループが含まれます。再帰アルゴリズム(つまり、分割統治パラダイムを満たすもの)、再帰的な実装に適しています。ただし、再帰アルゴリズムは、再帰アルゴリズムを含むすべてのアルゴリズムが最終的に結果を得るために何らかのタスクを繰り返し実行するため、for(...)andのような反復構造のみを使用して実装できます。while(...)

この投稿の他の寄稿者は、再帰関数を使用して反復アルゴリズムを実装できることを完全に実証しました。実際、何らかの終了条件が満たされるまで反復することを含むすべてに対して、再帰的な実装が可能です。基礎となるアルゴリズムに分割または結合ステップがない再帰的実装は、標準の終了条件を使用した反復実装と同等です。

挿入ソートを例にとると、挿入ソートが反復アルゴリズムであることはすでにわかっています (そして証明されています)。ただし、これはInsertion Sortの再帰的な実装を妨げるものではありません。実際、再帰的な実装は次のように非常に簡単に作成できます。

function insertionSort(array)

    if (length(array) == 1)
        return array
    end

    itemToSort = array[length(array)]
    array = insertionSort(array[1 .. (length(array)-1)])

    find position of itemToSort in array
    insert itemToSort into array

    return array

end

ご覧のとおり、実装は再帰的です。ただし、挿入ソートは反復アルゴリズムであり、これはわかっています。では、上記の再帰的な実装を使用しても、挿入ソート アルゴリズムが再帰的になっていないことをどのように確認できるのでしょうか? 分割統治パラダイムの 3 つの基準をアルゴリズムに適用して確認してみましょう。

  1. 問題は [2 つ以上の] サブ問題に分割され、各サブ問題は元の問題よりも小さいが、元の問題と同様の方法で解決できます。

    YES : 長さ 1 の配列を除き、項目 A[ j ] を配列内の適切な場所に挿入する方法は、以前のすべての項目 A[1.. j -1] を配列に挿入するために使用した方法と同じです。

  2. 問題は [2 つ以上の] サブ問題に分割され、各サブ問題は独立しており、再帰的に、または十分に小さい場合は単純な方法で解決できます。

    NO : アイテム A[ j ]の適切な配置は、A[1.. j -1] アイテムを含む配列とソートされるアイテムに完全に依存します。したがって、アイテム A[ j ] ( itemToSortと呼ばれる) は、配列の残りの部分が処理される前に配列に入れられません。

  3. 問題は [2 つ以上の] サブ問題に分割され、これらのサブ問題の結果が組み合わされて元の問題の解が得られます。

    いいえ: 反復アルゴリズムであるため、1 つの項目 A[ j ] のみを任意の反復に適切に配置できます。空間 A[1.. j ] は、A[1]、A[2]...A[ j ] がすべて独立して適切に配置され、これらすべての適切に配置された要素が組み合わされて並べ替えられたサブ問題に分割されません。配列。

明らかに、私たちの再帰的な実装は、本質的に挿入ソート アルゴリズムを再帰的にしていません。実際、この場合の実装の再帰はフロー制御として機能しており、終了条件が満たされるまで反復を継続できます。したがって、再帰的な実装を使用しても、アルゴリズムが再帰的なアルゴリズムに変更されることはありません。

反復アルゴリズムを使用しない配列の反転

アルゴリズムが反復的である理由と、アルゴリズムが再帰的である理由を理解したところで、「反復を使用せずに」配列を反転できるのはなぜでしょうか?

配列を逆にする方法は 2 つあります。どちらの方法でも、配列の長さを事前に知っておく必要があります。反復アルゴリズムはその効率のために好まれており、その疑似コードは次のようになります。

function reverse(array)

    for each index i = 0 to (length(array) / 2 - 1)
        swap array[i] with array[length(array) - i]
    next

end

これは純粋な反復アルゴリズムです。アルゴリズムの再帰性を決定する Divide and Conquer パラダイムと比較して、なぜこの結論に達することができるのかを調べてみましょう。

  1. 問題は [2 つ以上の] サブ問題に分割され、各サブ問題は元の問題よりも小さいが、元の問題と同様の方法で解決できます。

    YES : 配列の反転は、その最も細かい粒度、要素に分解され、各要素の処理は他のすべての処理済み要素と同じです。

  2. 問題は [2 つ以上の] サブ問題に分割され、各サブ問題は独立しており、再帰的に、または十分に小さい場合は単純な方法で解決できます。

    YES :配列内の要素iの反転は、要素(i + 1) (たとえば) が反転されているかどうかを必要とせずに可能です。さらに、配列内の要素iの反転は、完了するために他の要素の反転の結果を必要としません。

  3. 問題は [2 つ以上の] サブ問題に分割され、これらのサブ問題の結果が組み合わされて元の問題の解が得られます。

    NO : 反復アルゴリズムであるため、各アルゴリズム ステップで 1 つの計算ステージのみが実行されます。問題をサブ問題に分割せず、結果を得るために 2 つ以上のサブ問題の結果をマージすることもありません。

上記の最初のアルゴリズムの上記の分析は、それが分割統治パラダイムに適合しないことを確認したため、再帰的アルゴリズムとは見なされません。ただし、基準 (1) と基準 (2) の両方が満たされているため、再帰アルゴリズムが可能であることは明らかです。

鍵となるのは、反復ソリューションのサブ問題が可能な限り最小の粒度 (要素) であるという事実にあります。問題を (最初から細かい粒度を求めるのではなく) より小さなサブ問題に分割し、サブ問題の結果をマージすることで、アルゴリズムを再帰的にすることができます。

たとえば、ラテン アルファベット (A..P) の最初の 16 文字を含む 16 要素の配列がある場合、再帰アルゴリズムは視覚的に次のようになります。

                   Original Input

1.                ABCDEFHGIJKLMNOP                   Divide
2.        ABCDEFGH                IJKLMNOP           Divide
3.    ABCD        EFGH        IJKL        MNOP       Divide
4.  AB    CD    EF    GH    IJ    KL    MN    OP     Divide

5. A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P    Terminate

6.  BA    DC    FE    HG    JI    LK    NM    PO     Conquer (Reverse) and Merge
7.    DCBA        HGFE        LKJI        PONM       Conquer (Reverse) and Merge
8.        HGFEDCBA                PONMLKJI           Conquer (Reverse) and Merge
9.                PONMLKJIHGFEDCBA                   Conquer (Reverse) and Merge

                  Reversed Output

最上位レベルから、16 個の要素は、サブ問題の最も細かい粒度に到達するまで、正確に同じサイズ (レベル 1 から 4) の小さなサブ問題サイズに徐々に分割されます。順方向の単位長配列 (ステップ 5、個々の要素)。この時点では、16 個の配列要素がまだ順番に並んでいるように見えます。ただし、単一要素配列はそれ自体が逆配列でもあるため、同時に逆になります。次に、単一要素配列の結果をマージして、長さ 2 の 8 つの反転配列を取得し (ステップ 6)、再度マージして長さ 4 の 4 つの反転配列を取得し (ステップ 7)、というように、元の配列が再構築されるまで繰り返します。逆に（手順 6 ～ 9）。

配列を逆にする再帰アルゴリズムの疑似コードは次のようになります。

function reverse(array)

    /* check terminating condition. all single elements are also reversed
     * arrays of unit length.
     */
    if (length(array) < 2) then
        return array

    /* divide problem in two equal sub-problems. we process the sub-problems
     * in reverse order so that when combined the array has been reversed.
     */
    return reverse(array[(n/2) .. (n-1)]) + reverse(array[0 .. ((n/2)-1)])

end

ご覧のとおり、アルゴリズムは問題をサブ問題に分割し、結果がすぐに得られるサブ問題の最も細かい粒度に到達します。次に、マージ中に結果を逆にして、逆の結果配列を生成します。このアルゴリズムは再帰的だと思いますが、確認のために分割統治アルゴリズムの 3 つの基準を適用してみましょう。

  1. 問題は [2 つ以上の] サブ問題に分割され、各サブ問題は元の問題よりも小さいが、元の問題と同様の方法で解決できます。

    YES : レベル 1 での配列の反転は、レベル 2、3、4、または 5 とまったく同じアルゴリズムを使用して行うことができます。

  2. 問題は [2 つ以上の] サブ問題に分割され、各サブ問題は独立しており、再帰的に、または十分に小さい場合は単純な方法で解決できます。

    YES : 単位長ではないすべてのサブ問題は、問題を 2 つの独立したサブ配列に分割し、それらのサブ配列を再帰的に逆にすることによって解決されます。可能な限り最小の配列である単位長配列は、それ自体が反転されるため、終了条件が提供され、結合結果の最初のセットが保証されます。

  3. 問題は [2 つ以上の] サブ問題に分割され、これらのサブ問題の結果が組み合わされて元の問題の解が得られます。

    YES : レベル 6、7、8、および 9 のすべての問題は、すぐ上のレベルの結果のみで構成されています。すなわち、それらのサブ問題の。各レベルで配列を反転すると、全体的に反転した結果になります。

ご覧のとおり、再帰アルゴリズムは分割統治パラダイムの 3 つの基準を満たしているため、真の再帰アルゴリズムと見なすことができます。したがって、反復アルゴリズムを使用せずに配列を逆にすることができます。

興味深いことに、配列反転のための元の反復アルゴリズムは、再帰関数を使用して実装できます。このような実装の擬似コードは次のとおりです。

function reverse(array)

    if length(array) < 2
        return
    end

    swap array[0] and array[n-1]
    reverse(array[1..(n-1)])

end

これは、他のポスターによって提案されたソリューションに似ています。これは、定義された関数が最終的に自分自身を呼び出して、配列内のすべての要素に対して同じタスクを繰り返し実行するため、再帰的な実装です。ただし、問題をサブ問題に分割せず、サブ問題の結果をマージして最終結果を得る必要がないため、これによってアルゴリズムが再帰的になることはありません。この場合、再帰は単にフロー制御構造として使用されており、アルゴリズム的には、全体的な結果は、最初に提案された反復アルゴリズムとまったく同じ順序で同じ一連のステップを実行していることを証明できます。解決。

これが、反復アルゴリズム、再帰アルゴリズム、および再帰実装の違いです。

于 2012-07-06T10:36:47.800 に答える
23

人々がコメントで言ったように、それは反復の定義に依存します。

ケース 1. 再帰とは異なる、プログラミング スタイルとしての反復

反復の代わりに(単純に) 再帰を採用する場合、Kalai によって提示された再帰的なソリューションが正しい答えです。

ケース 2. 下限線形時間としての反復

反復を「各要素を調べる」と見なす場合、問題は、配列の反転に線形時間が必要か、それとも準線形時間で実行できるかという問題になります。

配列反転のための準線形アルゴリズムがないことを示すために、要素がn 個ある配列を考えます。各要素を読み取る必要のない反転用のアルゴリズムAが存在すると仮定します。次に、アルゴリズムが読み取らないという点で、配列を正しく逆にすることができる要素がa[i]いくつかあります。(編集: 奇数長の配列の中央の要素を除外する必要があります -- この範囲から以下のコメントを参照してください -- 以下のコメントを参照してください -- しかし、これは漸近的なケースでアルゴリズムが線形であるか準線形であるかには影響しません。)i0..n-1

アルゴリズムは決して要素a[i]を読み取らないため、その値を変更できます。これを行うとしましょう。次に、この値をまったく読み取っていないアルゴリズムは、値を変更する前と同じ反転の答えを生成します。しかし、この答えは の新しい値には正しくありませんa[i]。したがって、少なくともすべての入力配列要素を読み取らない (1 つ保存する) 正しい反転アルゴリズムは存在しません。したがって、配列反転には O(n) の下限があるため、反復が必要です (このシナリオの作業定義によると)。

(この証明は配列の反転のみを対象としており、二分探索や要素検索など、真にサブリニアな実装を持つアルゴリズムには適用されないことに注意してください。)

ケース 3. ループ構造としての反復

反復が「条件が満たされるまでループする」と見なされる場合、これは条件付きジャンプを伴うマシンコードに変換され、深刻なコンパイラの最適化 (分岐予測を利用するなど) が必要になることが知られています。 「反復なし」で何かを行う方法は、ループの展開(直線コードへの) を念頭に置いている場合があります。この場合、原則として、直線的な (ループのない) C コードを書くことができます。しかし、この手法は一般的ではありません。配列のサイズが事前にわかっている場合にのみ機能します。（この多かれ少なかれ軽薄なケースを回答に追加して申し訳ありませんが、完全を期すために、このように使用される「反復」という用語を聞いたことがあります。ループ展開はコンパイラの重要な最適化です。）

于 2012-07-04T05:06:34.497 に答える
14

再帰関数を使用します。

void reverse(int a[],int start,int end)
{
     int temp;
     temp = a[start];
     a[start] = a[end];
     a[end] = temp;


    if(start==end ||start==end-1)
       return;
    reverse(a, start+1, end-1);
}

上記のメソッドをreverse(array,0,lengthofarray-1)として呼び出すだけです

于 2012-07-04T04:47:16.860 に答える
1

並べ替えられた配列を逆にする再帰関数を実装します。つまり、配列が [1, 2, 3, 4, 5] の場合、プロシージャは [5, 4, 3, 2, 1] を返す必要があります。

于 2013-07-29T14:47:39.547 に答える
0

1つの解決策は次のとおりです。

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

void swap(int v[], int v_start, int v_middle, int v_end) {
    int *aux = calloc(v_middle - v_start, sizeof(int));
    
    int k = 0;
    for(int i = v_start; i <= v_middle; i++) {
        aux[k] = v[i];
        k = k + 1;
    }

    k = v_start;
    for(int i = v_middle + 1; i <= v_end; i++) {
        v[k] = v[i];
        k = k + 1;
    }

    for(int i = 0; i <= v_middle - v_start; i++) {
        v[k] = aux[i];
        k = k + 1;
    }
}

void divide(int v[], int v_start, int v_end) {
    if(v_start < v_end) {
        int v_middle = (v_start + v_start)/2;
        divide(v, v_start, v_middle);
        divide(v, v_middle + 1, v_end);
        swap(v, v_start, v_middle, v_end);
    }
}

int main() {
    int v[10] = {4, 20, 12, 100, 50, 9}, n = 6;
    
    printf("Array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", v[i]);
    }
    printf("\n\n");

    divide(v, 0, n - 1);

    printf("Reversed: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", v[i]);
    }

    return 0;
}
于 2022-02-13T19:53:02.383 に答える