Matsushita's Blog

シンプルな再帰処理による全列挙

問題

C: Brute-force Attack - AtCoder Beginner Contest 029 | AtCoder

解法

問題のタイトル通り虱潰しに出していく。Nの最大値が小さいのでfor文を何重にも書いても良いが、再帰関数を用いて書いてみる。

再帰処理を書くポイント

再帰処理を書く場合以下のポイントを押さえる

  • 再帰処理を使うパターン
  • 再起する度に変化するもの
  • 再帰を抜ける条件
  • 再帰処理で求めたいもの
  • i回目からi+1回目の再帰を呼ぶ

再帰処理を使うパターン

再帰を使うパターンは以下の通り。

  • 同じ処理を複数回する
  • 繰り返し処理中に使用する値は異なる
  • 1つ前の繰り返し処理で行った結果を元に次の繰り返し処理を行う

今回の問題では、a, b, cの3つの文字の中から毎回どれか1つを選ぶ。それをN回繰り返すというものである。

再起する度に変化するもの

今回の問題では再帰処理を行う度に変化するのは、count(文字数)とpass(パスワード)になる。 これらを再帰関数の引数にする。(hoge(int count, String pass))

再帰を抜ける条件

再帰処理を抜ける条件は、文字数がNに到達した時である。Nに到達した時のpassが求めたいものになる。

再帰処理で求めたいもの

再帰処理で求めたい物を引数に置くパターンと戻り値に置くパターンの2つがある。今回は引数に求めたいもの(pass)が存在するので戻り値はvoidにする。

i回目からi+1回目の再帰を呼ぶ

i番目の処理をhoge(count, pass)とした時に、i+1番目ではhoge(count + 1, pass + word(a,b, cのどれか))となる。

ソースコード