prologでＮの階乗の逆関数を考える。

質問

prologで、Ｎ！の逆関数をだすプログラムを
作りたいんですが、どうしたらいいですか？
逆関数でなければ作れるんですけど、逆関数となると
良い方法が思いつきません。
分かる方がいらっしゃいましたら、教えてくださいm(_ _)m

回答No.1

mide · ベストアンサー

Prologですか、なつかしいっす。

＜方針１＞
Prologらしくバックトラック機構を生かして作るとすると…、

まず、0から順に数字を発生させる述語を作ります。逆階乗のプログラムでは、この述語を呼び、戻り値をすでに作ってある階乗の述語にかけ、その結果が与えられた数と等しければ発生させた数を答えとして返し、等しくなければバックトラックによって次の数を試します。

ただ、毎回階乗計算をし直すので、効率は悪いですね。

＜方針２＞
バックトラックせずに再帰で、積が与えられた数になるまで繰り返す、効率の良いバージョン。与えられた数が１なら、答え０でおしまい。そうでない場合、現在のNとN!を渡せるように引数を２つ増やした述語を、最初はN=1,N!=1で呼ぶことにします。この述語では、再帰のたびにNを１ずつ増やし、現在の積はN!として、それが与えられた数になるまで再帰を繰り返し、一致したらその時のNを答えとして返します。

どちらもN!が与えられた数を越えたらfailするようにしないと、対応するNがない時に止まらなくなります。また１に対しては０と１の両方が（バックトラックで）帰るようにした方がいいでしょうね。

お礼

ありがとうございましたm(_ _)m
２の方の方針で頑張ってみようと思います。