StartupStockPhotosによるPixabayからの画像
こんにちは。倉内です。
プログラミング問題には、計算問題だけでなく配列や文字列を操作したり、図形から法則を見つけたりといろいろなものがあります。その中でも「関数を定義して処理を書くのは苦手だな…」と感じている方は多いのではないでしょうか。
私もまさにそのひとりで、基本は学んだものの使いこなせていません…。そこで今回は、さまざまな問題を集めた「レベルアップ問題集」の中から再帰関数を使って解く問題に挑戦しようと思います！
今回はスマートな解き方や綺麗なコードを書くというよりは、プログラミング初心者でもこういう方針を立てて、こう考えてみたら解けるかもということを重視して解いていきます。
プログラミング学習を始めたばかりの初心者の方もぜひ参考にしてみてください。
レベルアップ問題集「山折り谷折り」をPythonで解く
paizaではスキルチェックと言って、難易度別のプログラミング問題を解いてプログラミングスキルをランクづけするサービスを提供しています。問題の難易度は高い順にS・A・B・C・Dとなっています。
スキルチェック本番の問題はヒントや解答の公開は禁止させていただいているため、今回は「レベルアップ問題集」にあるAランクに相当する問題で練習してみることにしました。
レベルアップ問題集ではユーザー同士で解答を教え合うことやコードの公開は自由です。
ちなみに今回扱う問題のように再帰関数を使ったり、アルゴリズムや計算量の考慮も必要になってくるS・Aランク相当の問題は「リアルイベント」問題集にまとめてあります。
問題文
最近、ひたすら紙を折り続けるということがマイブームとなっているあなたは、今日もひたすら紙を折り続けています。それも、折り紙のような凝った折り方ではなく、紙の右辺が上から左辺に重なるような二つ折りを、ただひたすら繰り返すだけです。
さて、上記のように N 回折ったあと手順を逆にたどるように紙を広げます。すると、山折りと谷折りの折り目が等間隔に並んだ紙の完成です。あなたはこの折り目を眺めるのが好きですが、実際に紙を折るには紙の大きさや厚さから数回が限界です。
そこで、紙を上記のように折る回数 N が与えられるので、紙を折って広げたあとの山折り谷折りの折り目を計算するプログラムを作成してください。
2回折り (N = 2) の場合は以下のように折り目が付きます。
入力される値
入力は以下のフォーマットで与えられます。
N
N は紙を上記の形式で折る回数を表します。
期待する出力
山折りの折り目を "1"、谷折りの折り目を "0" として、答えとなる折り目を左から順に "0" と "1" からなる文字列として一行に出力してください。
条件
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 20
・N は整数
入力例
入力例1：
1出力例1：
0
入力例2：
2出力例2：
001
問題を理解する
ひとまずN=1から5くらいまで、実際折ってみるとどうなるか見てみましょう。手元で紙を用意してやってみると分かりやすいです！
下図は谷折りを点線、山折りを実線で表しています。
N=1のとき：0
N=2のとき：001
N=3のとき：0010011
N=4のとき：001001100011011
N=5のとき：0010011000110110001001110011011
なんとなく法則がありそうですね。
実際紙を折った方は見ていただければと思いますが、N=1のとき、折りたたんだ紙を上から見ると
表面・谷折り（0）・裏面
の順に重なっています。
これをもう1度折ったN=2のとき、同じく折りたたんだ紙を上から見ると
表面・谷折り（0）・裏面・谷折り（0）・表面・山折（1）・裏面
の順に重なっています。つまり、真ん中の谷折り（0）を挟んで表裏と折り目が反転することが分かります。
それらを踏まえて考えてみましょう。
N=2のとき：0 0 1
N=3のとき：001 0 011
N=4のとき：0010011 0 0011011
N=5のとき：001001100011011 0 001001110011011
真ん中の"0"を挟んで、右側の文字列は左側の文字列の"0"を1に、”1”を"0"にして、さらに反転した文字列になるという法則が見えました。（以降、左側・真ん中の"0"・右側という表現を使いますので覚えておいてください）
N=4で考えてみると、"0"を挟んで左側の
0010011
の"0"を"1"に、”1”を"0"にすると
1101100
それを反転させると
0011011
になり"0"を挟んだ右側の文字列と一致します。
そしてこの左側の"0"と"1"の並びは、1つ前の答えであることが分かります。N=4の左側は"0010011"でした。N=3の答えは"0010011"で一致します。つまり、
N番目の折り目 = （N-1の折り目） + "0" + （N-1の折り目の0と1を逆にして反転させたもの）
と考えていいでしょう。これを実装していくことにします。
以降はPythonの基本を理解している前提で説明していきますので、Pythonを初めて学習するという方は「Python入門編」を先に受講していただくとよいかと思います。
また、ブラウザ上でコードが実行できるpaiza.IOを使って、実際に手を動かしながら考えると理解が深まるのでおすすめです。
0を1に、1を0にする処理を考える
Pythonでは文字列の置換で使える関数がいくつかありますが、すぐ思い浮かぶのは replace() かなと思います。
ただ、ちょっと厄介なのが、たとえば"0010011"をreplaceを使って置換しようとすると…
s = "0010011" # "0"を"1"に置換 result1 = s.replace("0", "1") # "1"を"0"に置換 result2 = result1.replace("1", "0") # 結果は"0000000"になる -> NG print(result2)
「"0"を"1"に置換」の段階で"1111111"になって、「"1"を"0"に置換」で"0000000"になるんですよね。
そのため置換したい文字列を先頭から1文字ずつ見て、"0"の場合は"1"に置換、"1"の場合は"0"に置換と順番にやっていくことにします。
Pythonでは 文字列[インデックス] と書くことでインデックスに指定した位置の文字を抽出できます。そこで、文字列sをi=0番目から置き換えるコードを書いてみました。
s = "0010011" for i in range(len(s)): if(s[i] == "0"): s[i] = "1" else: s[i] = "0" print(s)
しかし、このままではエラーになります。
TypeError: 'str' object does not support item assignment
str型の文字列を1文字ずつ置き換えたいときは、list型に変換する必要があります。
s = "0010011" # 文字列sをリストにする s_list = list(s) # 0と1を入れ替えるために先頭から1文字ずつ置換 for i in range(len(s_list)): if(s_list[i] == "0"): s_list[i] = "1" else: s_list[i] = "0" # リストを文字列に戻す result = "" for i in s_list: result += i # 結果は"1101100"になる -> OK print(result)
ちなみにリストを文字列にするときは上記のようにfor文を使ってもいいのですが、joinを使った書き方もできます。1行で表現できるので覚えておくと便利ですよ。
# リストを文字列に戻す result = "".join(s_list)
文字列を反転して出力する処理を考える
逆順に出力する関数は reverse() や reversed() が思い浮かびますが、文字列には使えないのでスライスを使用します。スライスは
文字列[開始位置: 終了位置: 増分]
のように指定することができ、増分を「-1」にすることでうしろから逆順に取得してくれます。
# さきほどのresultの値を使う result = "1101100" # 結果は"0011011"になる -> OK print(result[::-1])
ここまでできたら、N-1の答えが分かっているという前提でNの答えを求めるコードが書けます。N=4のときを想定して書いてみましょう。
result_N3 = "0010011" # 文字列をリストにする result_N3_list = list(result_N3) # 0と1を入れ替えるために先頭から1文字ずつ置換 for i in range(len(result_N3_list)): if(result_N3_list[i] == "0"): result_N3_list[i] = "1" else: result_N3_list[i] = "0" # リストを文字列に戻す result_N4_right_tmp = "".join(result_N3_list) # 文字列を逆順にする result_N4_right = result_N4_right_tmp[::-1] # N=4の答えを求める result_N4 = result_N3 + "0" + result_N4_right # 結果は"001001100011011"になる -> OK print(result_N4)
求めた折り目を使って処理をする
この問題では、「問題を理解する」で整理したとおり、N番目の折り目を出すためにはNの1つ前の折り目を使って処理をする必要があります。
N番目の折り目 = （N-1の折り目） + "0" + （N-1の折り目の0と1を逆にして反転させたもの）
よってもしN=4が与えられた場合、N=3の答えが必要になり、N=3の答えを導き出したいときはN=2の答えが必要となります。
そこで今回のメインテーマである「再帰関数」を使って実現することにしましょう。
再帰関数とは
定義した関数の中にその関数自身を呼び出す処理が書かれているものを「再帰関数」といいます。
Pythonでは以下のように再帰関数を定義することができます。
def 関数名(引数): if 処理を終了する条件: 戻り値 # 処理 # 自身を呼び出し 関数名(引数)
簡単な例として、1からnまでの自然数の和を求めるプログラムを再帰関数で実装してみます。
def sum(n): if n == 0: return n # sum関数の中でsum関数自身を呼び出している return n + sum(n - 1) # n=10のとき55と出力される -> OK print(sum(10))
ちなみに関数の基本は「Python入門編」の「レッスン7: 関数を理解しよう」で学習できます。
（補足）再帰関数を使う際の注意点
再帰処理は通常のループ処理よりもメモリを多く消費します。そのためあまりにも再帰関数の呼び出し回数が多いと、メモリを大量に消費しいずれエラーになってしまいます。
Pythonではデフォルトで再帰は最大1000回までしか呼び出せないようになってます。この上限は変更することもできますが、最終的にはPythonが使えるメモリ領域の上限が最大回数となります。
今回の課題はNの最大値が20と決まっており、再帰回数は最大20回と分かっているため問題ありません。ただし、別の環境で実行を試す際にNに大きな値を設定してしまうとメモリが足りなくなりますのでご注意ください。
N番目の折り目を再帰関数で求める
さて、いよいよ問題に沿って再帰関数でN番目の折り目を求めるコードを書いていきます。さきほどまでに書いたコードも踏まえて以下のような処理を書きたいと思います。
Nを標準入力で取得
折り目を求める関数を定義
終了条件Nの折り目の右側を求めるために…
N-1の折り目を文字列からリストにする
0と1を入れ替えるために先頭から1文字ずつ置換
置換したリストを文字列に戻す
文字列を逆順にする（Nのときの右側の折り目が完成！）N-1のときの折り目に真ん中の"0"と導出した右側をくっつける
戻り値は折り目を求める関数のN-1のときの折り目
N番目の折り目を出力する
処理の部分はさきほどほとんど書けたので当てはめてみます。
# Nをint型で標準入力から取得 N = int(input()) #折り目を求める関数 result を定義 def result(orime, N): # Nが0になったら終了 if N == 0: return orime # 文字列orimeをリストにする orime_list = list(orime) # 0と1を入れ替えるために先頭から1文字ずつ置換 for i in range(len(orime_list)): if orime_list[i] == "0": orime_list[i] = "1" else: orime_list[i] = "0" # 置換したリストを文字列に戻す orime_tmp = "".join(orime_list) # 文字列を逆順にする（Nのときの折り目の右側が完成） orime_tmp_re = orime_tmp[::-1] # N-1の折り目に真ん中の"0"と導出した右側をくっつける orime += "0" orime += orime_tmp_re return result(orime, N - 1) print(result("", N))
これで提出してみましょう！
提出前動作確認＆提出結果
提出前にテストケースを1つ実行して動作確認できますので、まずそれが通ることを確認します。
大丈夫ですね！それでは提出します。
テストケースをすべてパスし、スコア100点を取れました！やったー！
スマートなコードとはちょっと遠いかもしれませんが、ひとつひとつの処理を理解しながら書くことができました。この解き方はあくまで一例ですので、自分なりに取り組んでみてくださいね。
レベルアップ問題集ではチケットを消費してテストケースの入力値を見ることができます。失敗したケースがあったときは確認するとミスした箇所が見つけやすいかもしれません。
近々解答例のコードも追加する予定ですので、もっと綺麗なコードの書き方を知りたいという方はそのときはぜひ参考にしてみてください。
まとめ
今回は「レベルアップ問題集」にあるAランク相当の問題を再帰関数を使って解いてみました。
この問題はN番目の折り目が"0"を挟んでなんらかの法則に基づいており左右に分けて考えること、そしてN-1番目の答えを利用することを発見するまでが大変で、それさえ分かれば特別なアルゴリズムの知識が必要というわけではありません。
再帰関数は少し難しかったかもしれませんが、何度か使ってみるとより理解できるようになるはずです。
プログラミング初学者の方は難しい問題に挑戦するときにいきなり綺麗に書こうとすると行き詰まってしまうので、今回のように少しずつ進めていくことを意識してみるといいかもしれないですね。
「このくらいなら意外といけそうだな」と感じた方は、ぜひ時間制限のあるスキルチェックの問題にもチャレンジしてみてください！
スキルチェック問題の取り組み方は「スキルチェック入門編」で解説していますので、初めて挑戦する方はぜひ参考にしてください。
paizaラーニングでは、技術面接でもよく出題されるアルゴリズムを使った問題の解き方を解説する講座「アルゴリズム入門編」も公開しています。いろいろな考え方を鍛えたい方はこちらもごらんください。
Pythonを基礎から学びたい方は、全レッスン無料公開中の「Python入門編」の受講がおすすめです。基本文法が身についたら今回解説した問題の他にもさまざまな練習問題を集めた「レベルアップ問題集」にも挑戦してみましょう。
「paizaラーニング」では、未経験者でもブラウザさえあれば、今すぐプログラミングの基礎が動画で学べるレッスンを多数公開しております。
詳しくはこちら
そしてWebサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
詳しくはこちら
