paizaラーニング リアルイベント問題セット: ハノイの塔(Python 解答例 )

スポンサーリンク

はじめに

最初に断っておくが筆者はプログラミング初心者なので「洗練されたコード」を書く能力は無い。一応解説も付けておくが、用語の使い方が間違っている可能性もある。その点ご了承頂きたい。この問題が解けた喜びで調子に乗ってコードを公開しているだけなので、あくまでご参考まで。解説を無視して完成コードだけ見たい人はページの最下部まで進んで頂きたい。

paizaの問題へのリンク(リアルイベント問題セット:ハノイの塔 (paizaランク A 相当)

「ハノイの塔」は再帰関数 (recursive function)を使う代表的な問題のようで、’ハノイ python’とか’hanoi python’で検索すれば色々コードが出てくる。しかし、実際にこの問題を解こうとすると、任意のターンで状態を出力する方法を理解しなければならないので苦労した。

paizaの動画講座には解説があるのだが、Javaなので筆者には分からない(この問題のためにJavaをイチから覚えるのはつらい)。参考にしたのはpaizaの技術者Y氏が公開しているスライド資料で、この言語が何なのかわかる人はそのまま答えとして使えると思う。筆者は何の言語なのか分からないレベルなので、雰囲気を察して自分で作ってみた。

(プログラミング初心者による)解説

基本部分

受け取った2つの数字から関数以外の部分を書いていく。Aランク問題に挑戦する人なら特に問題ない範囲と思われる。

n, m = map(int, input().split())
counter = 0  # ターン数を計測する変数
a = [int(_) for _ in range(n, 0, -1)]  # 塔aをリストにして、大きな数字から順に入れていく
b, c = [], [] # bとcは空のリスト

hanoi(n, a, b, c) # 別途定義するhanoiという関数を呼び出す

関数 hanoi

再帰関数のコアになる部分で、関数の中で同じ関数を呼び出すことになる。この部分は他に解説が沢山あるので調べて頂きたい(自分が正確に解説出来る自信が無い)。再帰が全く分からない人は、ハノイの前に単純な計算問題を使って基本概念を理解した方が良いかもしれない。

def hanoi(disc, frm, to, stay): # from と書くと命名上不都合なのでfrmとしている
    if disc == 0:
        return
    hanoi(disc - 1, frm, stay, to)
    move_one(disc, frm, to)
    hanoi(disc - 1, stay, to, frm)

関数 move_one

ここではターン数を更新するのだが、global counter という一文を抜かすと上手く動かない。counterをグローバル変数として宣言する必要がある。paizaの動画講座では「あまり推奨されません」と書いてあるので、きちんとした人は別の書き方をするのかも知れない。とりあえず自分は100点が取れるものを作りたかったのでこの方法にした。

コメントアウトしてある部分が2行あるが、このコメントアウトを外せば各ステップの作業がprintされる。discはコメントアウト部分でしか使っていないので本来は必要ないが、解説のために残した。

def move_one(disc, frm, to):
    global counter # グローバル変数
    counter += 1
    # print('this move is t = ' + str(counter))
    # print('move_disc ' + str(disc) + ' from ' + str(frm) + 'to' + str(to))
    disc_to_move = frm.pop(-1)
    to.append(disc_to_move)
    if counter == m:
        show()
        return

関数 show

最後に規定のターン数に到達した場合に出力するものを書く。forループのinにa,b,cの各リストを入れる。リストの長さが0の時はその塔に円盤が無いということなので’-‘を出力する。数字の入ったリストをそのままjoinで繋ごうとするとエラーが出るのでmapで各要素を文字列に変換する。

最後にコード全体を貼っておく。pep8のガイドラインに従って関数を先に書いている。

def show():
    for i in (a, c, b):
        if len(i) == 0:
            print('-')
        else:
            output = map(str, i)
            print(' '.join(output))
    return


def move_one(disc, frm, to):
    global counter
    counter += 1
    # print('this move is t = ' + str(counter))
    # print('move_disc ' + str(disc) + ' from ' + str(frm) + 'to' + str(to))
    disc_to_move = frm.pop(-1)
    to.append(disc_to_move)
    if counter == m:
        show()
        return


def hanoi(disc, frm, to, stay):
    if disc == 0:
        return
    hanoi(disc - 1, frm, stay, to)
    move_one(disc, frm, to)
    hanoi(disc - 1, stay, to, frm)


n, m = map(int, input().split())
counter = 0
a = [int(_) for _ in range(n, 0, -1)]
b, c = [], []

hanoi(n, a, b, c)

「pandasでpaiza問題」記事一覧へのリンク

コメント

当ブログのコンテンツが気に入ったら広告ブロックの解除(ホワイトリスト化)をご検討下さい。

Please disable your adblocker or whitelist this site!

タイトルとURLをコピーしました