再帰関数を用いて経路数を求めるプログラム(python)

Question

前提

pythonで、再帰関数を用いて経路数を求めるプログラムを作っていますが、うまくいきません。

実現したいこと

コードを書き換えて、正しい結果が出るプログラムにする

発生している問題・エラーメッセージ

該当のソースコード

def is_available(i,j):
  return i>=0 and j>=0
def num_of_routes_2(i,j):
  if i==0 and j==0:
    return 1
  num=0
  if is_available(i-1,j):
    num=num+num_of_routes_2(i-1,j)
  elif is_available(i,j-1):
    num=num+num_of_routes_2(i,j-1)
  return num

試したこと

全ての(i,j)で、結果が1になってしまいます。

Comments

[meg_]

> 全ての(i,j)で、結果が1になってしまいます。
質問のコードは実行部分がないようですが、上記はどういう状態のことを指していますか？

Answer 1

設問とコードが合っていないので、わけがわかりませんが、取り下げた質問を読んでいたので回答しましょう。

この問題は、「とあるマスにたどりつくための経路の数は、左と上のマスの経路の合計になる」ということを使って解きます。
また、質問にあるコードは、マスの中に通ることができないマス(黒マス)があったときにそれを考慮できるようにするためのコードですよね。

質問のコードの問題は、判定がif ～ elsif になってしまっていて左と上のどちらか一方しか合計の対象にしていないところです。これを左が白マスなら加算、上が白ますなら加算のように、両方確認して通れれば加算するというように変更する必要があります。

ということで、 elif is_available(i,j-1): の elif は if にしなければなりません。

Comments

[shun098]

上のマスの経路数と左のマスの経路数の和、としなければいけないところを、このプログラムでは片方しかできていなかったんですね、、、
説明不足かつ初歩的な質問にも関わらず、わざわざ答えていただきありがとうございます。

[TakaiY]

初歩的ではありませんし、初歩的だと思っていると解けない類いの問題ですね。
問題を解決するにはどのように考えたらいいのかという、プログラミング以前のところをちゃんと考えるのが必要だと思います。