1

のべき乗 powの値を計算しようとするべき関数があります。これまでのところ、私はケースを処理します-1。 指数は0です 2.指数はゼロ以外です BE

pow(B,0,1).
pow(B,E,Result):-   E2 is E - 1,
                    pow(B,E2,Result2),
                    Result is B*Result2.

べき関数が負の指数を処理できる別のケースを追加するにはどうすればよいですか？

4

3 に答える 3

4

まず、 0 0を定義する方法を検討する必要があります。正式には不定です。それはゼロかもしれませんし、1かもしれません。 Wolfram's Mathworld がべき乗に関する記事と zero に関する記事で述べているように:

0 0 (ゼロのゼロ乗) 自体は定義されていません。この量に明確な意味が定義されていないのは、a 0は常に 1 であるため、0 0は 1 に等しくなければならないが、0 aは常に 0 であるため ( a > 0 の場合)、0 aは 0 に等しいという相互に矛盾する事実から生じます。 . 0 0の定義の選択は、通常、不確定であると定義されますが、0 0 = 1 を定義すると、いくつかの式を簡単に表現できます (Knuth 1992; Knuth 1997, p. 57)。

したがって、最初に 0 0の特殊なケースを定義する方法を選択する必要があります: Is it 0? 1ですか？未定義ですか？

私はそれを未定義であると見なすことにしました。

そうは言っても、正の指数は乗算の繰り返しを示すものとして見ることができ (たとえば、10 3は 10*10*10 または 1,000 です)、負の指数は除算の繰り返しを示すものとして見ることができます (たとえば、10 -3は ( ((1/10)/10)/10)、または 0.001)。私の傾向は、一部にはこのアプローチの対称性が好きで、一部にはカットを避けるためです (カットは多くの場合、ソリューションを適切に定義していないというシグナルであるため)、次のようになります。

% -----------------------------
% The external/public predicate
% -----------------------------
pow( 0 , 0 , _ ) :- ! , fail .
pow( X , N , R ) :-
  pow( X , N , 1 , R )
  .

% -----------------------------------
% the tail-recursive worker predicate
% -----------------------------------
pow( _ , 0 , R , R  ).
pow( X , N , T , R  ) :-
  N > 0 ,
  T1 is T * X ,
  N1 is N-1   ,
  pow( X , N1 , T1 , R )
  .
pow( _ , 0 , R , R  ) :-
  N < 0 ,
  T1 is T / X ,
  N1 is N+1   ,
  pow( X , N1 , T1 , R )
  .

他の人が指摘したように、他のアプローチは、正の指数を繰り返し乗算を示すものとして定義し、負の指数を正の指数の逆数を示すものとして定義することです。したがって、10 3は 10*10*10 または 1,000 であり、10 -3は1/(10 3 )、または 1/1,000 または 0.001。この定義を使用するには、ここでもカットを避けて、次のようにします。

% -----------------------------
% the external/public predicate
% -----------------------------
pow( 0 , 0 , _ ) :-  % 0^0 is indeterminate. Is it 1? Is it 0? Could be either.
  ! ,
  fail
  .
pow( X , N , R ) :-
  N > 0 ,
  pow( X , N , 1 , R )
  .
pow( X , N , R ) :-
  N < 0 ,
  N1 = - N ,
  pow( X , N1 , 1 , R1 ) ,
  R is 1 / R1
  .

% -----------------------------------
% The tail-recursive worker predicate
% -----------------------------------
pow( _ , 0 , R , R  ).
pow( X , N , T , R  ) :-
  N > 0 ,
  T1 is T * X ,
  N1 is N-1   ,
  pow( X , N1 , T1 , R )
  .
于 2011-11-23T18:45:44.513 に答える
2

それを忘れないでa^(2b) = (a^b)^2くださいx^2 = x*x。トップレベルの「UI」述語から、末尾以外の方法で、アキュムレータを使用して末尾再帰の作業述語を呼び出すことは問題ありません。そうすれば、負の累乗の作業述語を実装する必要はなく、正の累乗の述語を再利用して、その結果を最上位の述語に変更できます（これはすでに提案されているようです）。

pow(B, E, R):- E<0 -> ... ; E=:=0 -> ... ; E>0 -> ... .
于 2011-11-23T12:29:02.337 に答える
2

まず、2 番目の節は非末尾再帰です (件名についてはこちらで読むことができます)。これは、最終的に実行時にコール スタック メモリが不足することを意味します。良いことは、アキュムレータを使用して末尾再帰にすることです。次のようにそれを達成できます：

% we add an accumulator to poW/3, making it pow/4.
pow(B, E, Result) :- pow(B, E, 1, Result).

% when we hit 0, our accumulator holds B^E so we unify it with result.
pow(_, 0, Accu, Accu) :- !.

% at each step, we multiply our accumulator by B
pow(B, E, Accu, Result) :-
    NewE is E - 1,
    NewAccu is Accu * B,
    pow(B, NewE, NewAccu, Result).

次に、この句を他の句の上に追加することで、負のケースを簡単に処理できます (負のべき乗が正のべき乗の逆であることをプロローグに伝えるだけです)。

pow(B, E, Result) :-
    E < 0,
    PositiveE is - E,
    pow(B, PositiveE, 1, R),
    !,
    Result is 1 / R.

コードで直接実行できることに注意してください。

pow(B, E, Result) :-
    E < 0,
    PositiveE is - E,
    pow(B, PositiveE, R),
    !,
    Result is 1 / R.

さらに、非常に赤いカットを導入しました (必要に応じて、赤いカットの意味についてはこちらを参照してください)。したがって、この変更でグリーン カットに変更することをお勧めします。

pow(B, E, Result) :-
    E < 0,
    PositiveE is - E,
    pow(B, PositiveE, 1, R),
    !,
    Result is 1 / R.

% we add an accumulator to poW/3, making it pow/4.
pow(B, E, Result) :-
    E >= 0, %************* HERE *****************
    pow(B, E, 1, Result).

% when we hit 0, our accumulator holds B^E so we unify it with result.
pow(_, 0, Accu, Accu) :- !.

% at each step, we multiply our accumulator by B
pow(B, E, Accu, Result) :-
    NewE is E - 1,
    NewAccu is Accu * B,
    pow(B, NewE, NewAccu, Result).
于 2011-11-23T11:29:07.363 に答える