この問題が解けなかったので、再帰関数を勉強した。⇩
- 参考サイト
- 多重for文
- 再帰関数の使い所
- 全探索・順列全探索・組合せ全探索を再帰関数で書いてみた
- 処理の流れイメージ
- 再帰処理のスレッドとは？
- ABC302-C Almost Equalの解答
- 組合せ全探索の例題
参考サイト
多重for文
全通り。順列。組合せ。
この3つを再帰関数で作りたい。
//重複あり全探索。3*3*3＝27通り for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { System.out.println(i + " " + j + " " + k); } } } System.out.println(); //重複なし全探索。順列。3P3 = 3! = 6通り boolean[] used = new boolean[3]; for (int i = 0; i < 3; i++) { if(used[i]) { continue; } used[i] = true; for (int j = 0; j < 3; j++) { if(used[j]) { continue; } used[j] = true; for (int k = 0; k < 3; k++) { if(used[k]) { continue; } used[k] = true; System.out.println(i + " " + j + " " + k); used[k] = false; } used[j] = false; } used[i] = false; } System.out.println(); //重複なし全探索。組合せ。3C3 = 3*2*1 / 3*2*1 = 1通り for (int i = 0; i < 3; i++) { for (int j = i + 1; j < 3; j++) { for (int k = j + 1; k < 3; k++) { System.out.println(i + " " + j + " " + k); } } } System.out.println(); //重複なし全探索。組合せ2。5C3 = 5*4*3 / 3*2*1 = 10通り for (int i = 0; i < 5; i++) { for (int j = i + 1; j < 5; j++) { for (int k = j + 1; k < 5; k++) { System.out.println(i + " " + j + " " + k); } } }
Nの値が定まっているときは、こんな感じでN個のfor文を入れ子にすればOK.
問題はNが定まらないとき。
再帰関数の使い所
全探索・順列全探索・組合せ全探索で、Nの値が定まらないとき。
全探索・順列全探索・組合せ全探索を再帰関数で書いてみた
import java.util.ArrayList; import java.util.List; //多重for文を再帰で作る練習 public class RecursiveFunctionPractice { private static List<Integer> list = new ArrayList<>(); private static boolean[] seen = new boolean[5]; // 重複あり全探索。0～2の数字を含む、N桁の数列を全通り作る private static void recursion1(int N) { //ベース条件（終了条件） // Nが２なら２重for。Nが３なら３重for文になる。 if (list.size() == N) { for (int num : list) { System.out.print(num + " "); } System.out.println(); return; } for (int i = 0; i < 3; i++) { list.add(i); recursion1(N); list.remove(list.size() - 1);// 末尾を削除。ここがポイント } } // 重複なし全探索。順列全探索。0～2の数字を含む、N桁の数列を作る private static void recursion2(int N) { //ベース条件（終了条件） // Nが２なら２重for。Nが３なら３重for文になる。 if (list.size() == N) { for (int num : list) { System.out.print(num + " "); } System.out.println(); return; } for (int i = 0; i < 3; i++) { if (seen[i]) { continue; } list.add(i); seen[i] = true; recursion2(N); list.remove(list.size() - 1);// 末尾を削除。ここがポイント seen[i] = false; } } // 重複なし全探索。組合せ全探索。0～4の数字を含む、N桁の数列を作る private static void recursion3(int N, int index) { //ベース条件（終了条件） // Nが２なら２重for。Nが３なら３重for文になる。 if (list.size() == N) { for (int num : list) { System.out.print(num + " "); } System.out.println(); return; } //順列全探索との違い // Listが空でないなら前回index＋１をnumに代入 int num = 0; if (list.size() > 0) { num = index + 1; } for (int i = num; i < 5; i++) { list.add(i); recursion3(N, i); list.remove(list.size() - 1);// 末尾を削除。ここがポイント } } public static void main(String[] args) { recursion1(3); System.out.println(); recursion2(3); System.out.println(); recursion3(3, 0); } }
PythonやC++だともっと簡単に書けるらしい。乗り換えようかなあ。
処理の流れイメージ
・recursionメソッド
listに0を加える。リストの中身→(0)
⇩再帰呼出し
listに0を加える (0, 0)
⇩再帰呼出し
listのサイズが2なのでreturn
⇩
list.remove(list.size()-1)でリストの末尾を削除 (0)
⇩for文が1個進む
listに1を加える。(0,1)
listのサイズが2なのでreturn
⇩
list.remove(list.size()-1)でリストの末尾を削除 (0)
⇩
for文終了して、1つ前のスレッドへ戻る。
⇩
list.remove(list.size()-1)でリストの末尾を削除 ()
⇩for文が1個進む
listに1を加える(1)
⇩再帰呼出し
listに0を加える（1,0)
⇩処理が終わるまで続く
再帰処理のスレッドとは？
こっちの「再帰関数の面白い所」に書きました⇩
ABC302-C Almost Equalの解答
冒頭の問題の解答コード。
順列全探索問題だった。
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class AlmostEqual { private static int n; private static int m; private static boolean answer = false; private static boolean[] seen; private static List<char[]> charList = new ArrayList<>(); private static List<char[]> surveyTarget = new ArrayList<>(); private static void recursion() { if(answer) { return; } // ベース条件（再帰を終了する条件） // 配列数がNと同じなら比較処理に飛ぶ if(surveyTarget.size() == n) { // 比較処理にとんでTRUEなら終了。FALSEなら処理継続 if(compareCharList()) { answer = true; return; } } // 未探索なら配列に加える for(int i = 0; i < n; i++) { if(seen[i] == false) { surveyTarget.add(charList.get(i)); seen[i] = true; recursion();//再帰 surveyTarget.remove(surveyTarget.size()-1); seen[i] = false; } } } // 文字列同士の比較。 // 隣り合う文字列同士が全て一文字違いならTRUE private static boolean compareCharList() { boolean result = true; for(int i = 0; i < n-1; i++) { char[] c1 = surveyTarget.get(i); char[] c2 = surveyTarget.get(i+1); int count = 0; for (int j = 0; j < m; j++) { if(c1[j] != c2[j]) { count++; } } if(count != 1) { result = false; return result; } } return result; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); seen = new boolean[n]; for(int i = 0; i < n; i++) { char[] c = sc.next().toCharArray(); charList.add(c); } //再帰処理開始 recursion(); if(answer) { System.out.println("Yes"); }else { System.out.println("No"); } // 旧回答。バケット法ではダメだった。いけそうな気もするんだけど。 // List<int[]> list = new ArrayList<>(); // List<char[]> charList = new ArrayList<>(); // // for (int i = 0; i < n; i++) { // char[] arr2 = sc.next().toCharArray(); // charList.add(arr2); // // int[] arr = new int[26]; // // for (char c : arr2) { // arr[(int) (c - 'a')]++; // } // // list.add(arr); // } // // // 2つだけ違えばOK。２重で全探索 // int count = 0; // for (int i = 0; i < list.size(); i++) { // int[] arr3 = list.get(i); // for (int j = i + 1; j < list.size(); j++) { // int[] arr4 = list.get(j); // // int sai = 0; // for (int k = 0; k < 26; k++) { // sai = sai + Math.abs(arr3[k] - arr4[k]); // } // if (sai == 2) { // count++; // } // } // } // if (count >= n-1) { // System.out.println("Yes"); // } else { // System.out.println("No"); // } } }
これも深さ優先探索と言えるのかな？
