Блог

Главная - Вопросы по программированию - Оценка многочлена в прологе

Оценка многочлена в прологе

#prolog

Вопрос:

В настоящее время я пытаюсь улучшить использование рекурсии в прологе. Я не уверен, почему мне немного сложнее понять его, чем другие языки программирования. Для начала я хотел бы показать свой код с результатами.

 eval_term([H|T], X, Y):- Y is X^T * H.   eval_poly([],X,Y). eval_poly([H|T],X,Y):- eval_term(H, X, Y2), eval_poly(T, X, Y2). eval_poly([H|T],X,Y):- Y is Y2   Y, eval_poly(T,X,Y).  ?- eval_poly([[1|2],[2|1],[3|0]],2, Y). true .

Выше у меня есть то, что у меня есть до сих пор из нескольких неудачных итераций. Я даю базовый случай с пустым списком, за которым следует числовое значение, которое заменит переменную(X) и предполагаемый результат(Y). Многочлен структурирован таким образом, что начало каждой пары является коэффициентом, а конец-показателем степени. Y должен выдавать 11 для предоставленных входных данных, но я, похоже, получаю только истину. Используя трассировку, я вижу, что он может правильно использовать eval_term (), но с этого момента я застрял. Любая помощь или подсказки будут высоко оценены!

Комментарии:

1. eval_poly([H|T],X,Y):- Y is Y2 Y, eval_poly(T,X,Y). использует Y2 , но никогда не привязывает его к значению.

2. Я думал, что это связано с переменной Y?

3. is Привязывается только левая сторона (если это еще не так). Кроме того, если бы это предложение действительно связывало Y2 , оно всегда связывало бы его с 0, предполагая Y is Y2 Y , что на самом деле это ничего не дает.

4. О, так, может быть, я заменю букву Y на Y2?

5. Y2 is Y2 Y ? Или Y is Y2 Y2 ? Я не вижу, чтобы кто-то из них чего-то добился.

Ответ №1:

Чтобы правильно работать, ваш код нуждается в некоторых изменениях:

  • Когда список, представляющий многочлен, пуст, независимо от значения второго аргумента, результат, полученный предикатом eval_poly/3 , должен быть равен 0. Поэтому вам нужно изменить базовый вариант на: 
     eval_poly([], _, 0).
  • Поскольку значения созданных переменных не могут быть изменены, вам необходимо использовать новую переменную для каждого нового вычисленного значения. Поэтому вам нужно изменить рекурсивный регистр на: 
     eval_poly([H|T], X, Y):-  eval_term(H, X, Y1),  eval_poly(T, X, Y2),  Y is Y1   Y2.

Помимо предложения , определяющего предикат eval_term/3 , для правильной работы предиката необходимы только эти два измененных eval_poly/3 предложения. Однако в вашем коде есть несколько моментов, которые можно улучшить:

  • В прологе более идиоматично представлять пару как термин формы First-Second . Поэтому вы должны кодировать предикат eval_term/3 как: 
     eval_term(Coefficient-Exponent, X, Y):-   Y is Coefficient * X^Exponent.
  • Кроме того, для большей эффективности вы можете избавиться от предиката eval_term/3 и переопределить предикат eval_poly/3 , используя хвостовую рекурсию и накопитель: 
     eval_poly(Terms, X, Y) :-  eval_poly_loop(Terms, X, 0, Y).  eval_poly_loop([], _, Acc, Acc). eval_poly_loop([Coefficient-Exponent|Terms], X, Acc, Y):-  NewAcc is Acc   Coefficient * X^Exponent,  eval_poly_loop(Terms, X, NewAcc, Y).
  • Запуск примеров: 
     ?- eval_poly([1-2, 2-1, 3-0], 2, Y). % 1*x^2   2*x^1   3 Y = 11.  ?- eval_poly([2-3, (-5)-1, 3-0], 3, Y). % 2*x^3 - 5*x   3 Y = 42.
Метки: