0

我编写了以下代码，它应该符合我的逻辑，但事实并非如此。

我应该检查给定的术语是否是二的幂。例如s(s(s(nul)))应该返回false，s(s(s(s(nul)))应该返回true。

substractWhileY(X,0,rezult).
substractWhileY(s(X),Y,rezult):-
   Y > 0, number is 1,  substractWhileY(X,Y - number, rezult).

degreeOftwo(X):-
   substractWhileY(X,2,rezult),
   pagalba(X, 2, rezult).
calculateAnswer(X, currentCounter, currentValue):-
   currentCounter is currentCounter * 2,
   substractWhileY(currentValue, currentCounter , rezult),
   rezult\= null,
   calculateAnswer(X, currentCounter , rezult).

我的想法是检查给定的 therm 是否是任何两个度数，如果不是，则不是二度数。

有了数字，它应该像这样工作。例如，我给出数字 8。

First time it checks if 8 - 2 = 0.
second time if 8 - 4 = 0.
third time if 8 - 8 = 0.

所以 8 id 两个的幂。

也许其他解决方案会更好，所以感谢您的帮助。

4

3 回答 3

2

假设您正在寻找数字 1、2、4、8...，或者换句话说，2^0、2^1、2^2、2^3、...，那么确定性的解决方案可以是：

two_power_n(s(X)) :-
    two_power_n_minus_one(X). 

two_power_n_minus_one(0).
two_power_n_minus_one(s(X)) :-
    half(s(s(X)), s(Y)),
    two_power_n_minus_one(Y).

half(0, 0).
half(s(s(X)), s(Y)) :-
    half(X, Y).

我不认为这个解决方案是最优的。

于 2013-10-30T09:52:02.100 回答
2

利用计算机中用于有符号整数的二进制补码表示的属性，确定定点二进制补码整数是否是 2 的幂很容易：

pow2( X ) :-     % X is a power of 2, if...
  X > 0 ,        % - X is > 0 , and ...
  X is X /\ (-X) % - A bitwise AND of X and its 2s complement yields X
  .              % Easy!

不需要递归，只是有点玩弄。

鉴于此，解决方案很简单。只需遍历嵌套结构s/1并计算其深度/长度。然后确定这是否是 2 的幂。

IsPowerOf2( S ) :- nested_depth(S,0,D) , pow2(D) .

nested_depth( nul  , D , D ).
nested_depth( s(X) , T , D ) :-
  T1 is T+1 ,
  nested_depth(X)
  .
于 2013-10-30T18:14:21.883 回答
0

鲍里斯的回答肯定更完整/正确（+1），我早于他的 half/2 谓词。但是您的问题的解决方案以这种方式显得更简单：

pow_of_two(s(nul)).
pow_of_two(X) :-
    half(X, H),
    pow_of_two(H).
于 2013-10-30T15:29:43.960 回答