1

私は次の試験のために勉強を始めましたが、良い兆候ではない些細なプロローグの練習問題で立ち往生しています笑。

それは本当に簡単なはずですが、何らかの理由で今は理解できません。

タスクは、prolog の Int のリストにある奇数の数を単純に数えることです。Haskellで簡単にできましたが、プロローグがひどいです。誰かがこれを行う簡単な方法を示して、あなたが何をしたかを簡単に説明してもらえますか?

これまでのところ、私は持っています:

odd(X):- 1 is X mod 2.

countOdds([],0).
countOdds(X|Xs],Y):-
?????
4

2 に答える 2

5

あなたのodd/1の定義は問題ありません。

空のリストの事実も問題ありません。

IN 再帰句では、奇数と偶数を区別する必要があります。数が奇数の場合、カウンターを増やす必要があります。

countOdds([X|Xs],Y1) :- odd(X), countOdds(Xs,Y), Y1 is Y+1.

数が奇数 (= 偶数) でない場合、カウンターを増やしてはなりません。

countOdds([X|Xs],Y) :- \+ odd(X), countOdds(Xs,Y).

ここで\+、失敗として否定を示します。

または、! を使用することもできます。最初の再帰句で、2 番目の条件を削除します。

countOdds([X|Xs],Y1) :- odd(X), !, countOdds(Xs,Y), Y1 is Y+1.

countOdds([X|Xs],Y) :- countOdds(Xs,Y).
于 2012-04-19T06:45:50.387 に答える
4

Prologでは、リストのように、再帰を使用して再帰データ構造体の要素を検査します。パターンマッチングにより、適用する適切なルールを選択できます。あなたの仕事をする簡単な方法：

リスト=[X| Xs]があり、各要素Xについて、奇数（X）の場合はcountOdds（Xs）+1を返し、そうでない場合はcountOdds（Xs）を返します。

countOdds([], 0).
countOdds([X|Xs], C) :-
  odd(X),
  !, % this cut is required, as rightly evidenced by Alexander Serebrenik
  countOdds(Xs, Cs),
  C is Cs + 1.
countOdds([_|Xs], Cs) :-
  countOdds(Xs, Cs).

if、はパターン付きの別のルールで処理されることに注意してくださいsame。Prologが奇数でない要素を見つけると、最後のルールに戻ります。

ISO Prologには、のためのシンタックスシュガーがIf Then Elseあり、それを使って書くことができます

countOdds([], 0).
countOdds([X|Xs], C) :-
  countOdds(Xs, Cs),
  (  odd(X)
  -> C is Cs + 1
  ;  C is Cs
  ).

最初のバージョンでは、再帰呼び出しがテストの後に続き、odd(X)バックトラックで繰り返される必要のあるリストテールの無駄な訪問を回避します。

編集カットなしでは、複数の実行パスが取得されるため、「すべてのソリューション」述語（findall、setofなど）で誤った結果が生じる可能性があります

この最後のバージョンは、手順がそうではないという証拠を示しましたtail recursive。末尾再帰プロシージャを取得するには、：を追加しaccumulatorます。

countOdds(L, C) :- countOdds(L, 0, C).

countOdds([], A, A).
countOdds([X|Xs], A, Cs) :-
  (  odd(X)
  -> A1 is A + 1
  ;  A1 is A
  ),
  countOdds(Xs, A1, Cs).
于 2012-04-19T07:12:47.087 に答える