Java プログラミングスキル - データ構造とアルゴリズム「再帰」

[[392763]]

コンセプト

簡単に言うと、再帰とは、毎回異なる変数を渡しながら、自身を呼び出すメソッドです。再帰は、プログラマーが複雑な問題を解決するのに役立ち、コードを整理することができます。

再帰はどのような問題を解決できますか?

8 人のクイーンの問題、ハノイの塔、階乗の問題、迷路の問題、ボールとバスケットの問題など、さまざまな数学の問題 (Google プログラミングコンテスト)。
再帰は、クイックソート、マージソート、バイナリ検索、分割統治アルゴリズムなどのさまざまなアルゴリズムでも使用されます。
スタック->再帰コードで解決される問題は比較的簡潔です。

再帰に従うべきルール

メソッドが実行されると、新しい保護された独立したスペース (スタックスペース) が作成されます。
メソッドのローカル変数は独立しており、相互に影響を与えません。
メソッド内で使用される変数が参照型変数（配列など）の場合、参照型のデータが共有されます。
再帰は再帰を終了するための条件に近づく必要があり、そうでない場合は無限再帰になります。
メソッドが実行されるか、または return に遭遇すると、呼び出した人に結果が返されるという規則に従ってメソッドが返されます。同時に、メソッドが実行されるか返されると、メソッドも実行されます。

迷路問題を解くための再帰バックトラッキング

2 次元配列では、1 は壁を表します。指定された点から終点までのボールの経路を見つけます。

パッケージ com.structures.recursion; 
 
パブリッククラス MiGong {
公共 静的void main(String[] args) {
        //まず迷路と地図をシミュレートするための2次元配列を作成します
int [][] マップ = 新しいint [8][7];
        //壁を表すために 1 を使用し、迷路の上、下、左、右を 1 に設定します
( int i = 0; i < 7; i++) {
            マップ[0][i] = 1;
            マップ[7][i] = 1;
        }
 ( int i = 0; i < 8; i++)の場合{
            マップ[i][0] = 1;
            マップ[i][6] = 1;
        }
        //バッフルを設定する
        マップ[3][1] = 1;
        マップ[3][2] = 1;
        // 出力マップ
        System.out.println ( "元のマップ" ) ;
 ( int i = 0; i < 8; i++)の場合{
 ( int j = 0; j < 7; j++)の場合{
                システム.out.print (map[i][j] + " " );
            }
            System.out.println( ) ;
        } 
 
        // 再帰バックトラッキングを使用してパスを見つける
        マップにWayを設定します。
        System.out.println ( "戦略に従って取られたパス" ) ;
 ( int i = 0; i < 8; i++)の場合{
 ( int j = 0; j < 7; j++)の場合{
                システム.out.print (map[i][j] + " " );
            }
            System.out.println( ) ;
        } 
 
        /*
        オリジナルマップ
        1 1 1 1 1 1 1
        1 0 0 0 0 0 1
        1 0 0 0 0 0 1
        1 1 1 0 0 0 1
        1 0 0 0 0 0 1
        1 0 0 0 0 0 1
        1 0 0 0 0 0 1
        1 1 1 1 1 1 1
        戦略が辿った道
        1 1 1 1 1 1 1
        1 2 0 0 0 0 1
        1 2 2 2 0 0 1
        1 1 1 2 0 0 1
        1 0 0 2 0 0 1
        1 0 0 2 0 0 1
        1 0 0 2 2 2 1
        1 1 1 1 1 1 1
         */
    } 
 
    /**
     * 再帰バックトラッキングを使用してパスを見つけます。[6][5]をマップできる場合は、パスが見つかったことを意味します。
     * 規則: map[i][j] が 0 の場合、そのポイントは訪問されていないことを意味し、1 の場合、壁を意味し、2 の場合、通路を訪問できることを意味し、3 の場合、そのポイントは訪問済みだが訪問できないことを意味します。
     * 迷路を歩くときは、下→右→上→左と戦略（方法）を決め、通り抜けられない場合は戻る必要があります
     *
     * @param mapはマップを表します
     * @param i 行座標の開始位置
     * @param j 列座標の開始位置
     * @returnパスが見つかった場合はtrueを返し、そうでない場合はfalseを返します。  
     */
公共 静的ブールsetWay( int [][] map, int i, int j) {
        (map[6][5] == 2)の場合{
戻る 真実;
        }それ以外{
            if (map[i][j] == 0){//現在のポイントを通過していない場合
                //戦略に従って、下->右->上->左に進みます
                map[i][j] = 2; //この地点を通過できると仮定する
                if (setWay(map, i + 1, j)) 下へ進む
戻る 真実;
                } else if (setWay(map, i, j + 1)){//右に進む
戻る 真実;
                } else if (setWay(map, i - 1, j)){//上へ進む
戻る 真実;
                } else if (setWay(map, i, j - 1)){//左に進む
戻る 真実;
                }それ以外{
                    map[i][j] = 3; // この地点は行き止まりであり通過できないことを示します
戻る 間違い;
                }
            }それ以外{
                //map[i][j] != 0 の場合、1、2、3 のいずれかである可能性がある
戻る 間違い;
            }
        }
    }
 }

8つのクイーンの問題

8×8 のチェス盤に 8 つのクイーンを配置して、クイーン同士が攻撃し合わないようにする方法、つまり、同じ行、列、または対角線上に 2 つのクイーンがないようにする方法は、何通りありますか。

理論的には、チェス盤を表すには 2 次元配列を作成する必要がありますが、実際には、アルゴリズムを通じて 1 次元配列で問題を解決できます。arr[8]={0,4,7,5,2,6,1,3}、対応する arr の添え字は行、つまりクイーンを示します。arr[i]=val、val は i+1 番目のクイーンを示し、i+i 番目の行の val+1 列に配置されます。

パッケージ com.structures.recursion; 
 
パブリッククラス Queen8 {
    //女王が何匹いるかを示す
    プライベートint  最大= 8;
    //クイーン配置の結果を保存する配列を定義します。例: arr[8]={0,4,7,5,2,6,1,3}
    プライベートint [] 配列 = 新しいint [ max ]; 
 
静的 整数 カウント= 0; 
 
公共 静的void main(String[] args) {
        Queen8 を新しい Queen8() に変換します。
        クイーン8.チェック(0);
        System.out.printf ( "合計%d通り\n" , count ); // 92通り
    } 
 
    //n番目のクイーンを配置する
パブリックvoidチェック( int n) {
        if (n == max ) //n=8は前に配置されていることを意味する
            印刷();
カウント++;
戻る;
        }
        //クイーンを順番に並べて競合があるかどうかを判断します
( int i = 0; i < max ; i++) {
            //まず現在のクイーンnを新しい行の最初の列に置きます
            配列[n] = i;
            //n 番目のクイーンを i 番目の列に配置するときに競合が発生するかどうかを判断します。
            もし（判断（n））{
                //次にn+1のクイーンを置いて再帰を開始します
チェック(n + 1);
            }
        }
    } 
 
    // n 番目のクイーンを配置するときに、そのクイーンがすでに配置されているクイーンと競合するかどうかを確認します。
    プライベートブールジャッジ( int n) {
 ( int i = 0; i < n; i++)の場合{
            //array[i] == array[n]は、n番目のクイーンが前のクイーンと同じ列にあるかどうかを示します。
            //Math.abs (n - i) == Math.abs ( array[n] - array[i]) は、n番目のクイーンが前のクイーンと同じ対角線上にあるかどうかを示します。
            if (配列[i] == 配列[n] || Math.abs (n - i) == Math.abs (配列[n] - 配列[i])) {
戻る 間違い;
            }
        }
戻る 真実;
    } 
 
    //クイーンの位置を出力する
パブリックボイドプリント（）{
 ( int i = 0; i < 配列の長さ; i++) {
            システム.out.print (配列[i] + " " );
        }
        System.out.println( ) ;
    }
 }