Форум программистов, компьютерный форум, киберфорум
Lisp
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
1 / 1 / 0
Регистрация: 06.11.2013
Сообщений: 87
1

Умножение многочленов

14.05.2015, 20:02. Показов 1356. Ответов 24
Метки нет (Все метки)

Здравствуйте, помогите пожалуйста реализовать на Lisp'е данный код

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
domains
int=integer
intl=int*
 
predicates
len(intl,int)
elt(intl,int,int)
pcoeff(intl,intl,int,int,int)
coeff(intl,intl,int,int,int)
poly_mult(intl,intl,int,intl)
polymult(intl,intl,intl)
 
clauses
len([],0).
len([_|T],N) :- len(T,N1), N=N1+1.
 
elt([],_,0)    :- !.  
elt([X|_],0,X) :- !.
elt([_|T],N,X) :- N1=N-1, elt(T,N1,X).
 
pcoeff(PX,PY,I,J,Q) :- elt(PX,I,XX), elt(PY,J,YY), Q=XX*YY.
 
coeff(_,_,N,I,0)  :- I>N, !.
coeff(PX,PY,N,I,S)  :- J=N-I, pcoeff(PX,PY,I,J,Q), I1=I+1, coeff(PX,PY,N,I1,S1), S=S1+Q.
 
poly_mult(PX,PY,I,[])    :- len(PX,N1), len(PY,N2), N=N1+N2-2, I>N, !.
poly_mult(PX,PY,I,[Q|T]) :- coeff(PX,PY,I,0,Q), I1=I+1, poly_mult(PX,PY,I1,T). 
 
polymult(PX,PY,R) :- poly_mult(PX,PY,0,R).
Заранее спасибо
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.05.2015, 20:02
Ответы с готовыми решениями:

Работа со списками и умножение многочленов
Здравствуйте, помогите пожалуйста переписать две программы на Lisp. Они у меня на прологе, но не...

Разложение многочленов на множители
Реализуйте процедуру factorize, выполняющую разложение многочленов вида a2−b2, a3−b3 и...

Перемножение двух многочленов
Помогите пожалуйста написать программу перемножения двух многочленов от n переменных. Например:...

Процедура деления многочленов
Здравствуйте) помогите пожалуйста с заданием. Задание: Составьте процедуру деления с остатком...

24
Модератор
Эксперт Python
28606 / 15467 / 3059
Регистрация: 12.02.2012
Сообщений: 25,348
Записей в блоге: 4
14.05.2015, 21:28 2
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Не думаю, что код на Прологе сильно поможет... Вот:


Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
(defun poly-add (p1 p2)
   (let* ((n1 (- (length p1) 1))
          (n2 (- (length p2) 1))
          (n (max n1 n2))
          (res nil))
    (iter (for i from 0 to n)
      (cond ((and (<= i n1) (<= i n2)) (collecting (+ (nth i p1) (nth i p2)) into res))
            ((<= i n1) (collecting (nth i p1) into res))
            (t (collecting (nth i p2) into res))))
    res))
 
==> poly-add
 
(defun poly-by-mon (p c m) ;; с-коэфф, m-степень
   (append (replicate 0 m) (mapcar #'(lambda (q) (* c q)) p)))
 
==> poly-by-mon
 
(defun poly-mult (p1 p2 &optional (c 0) (r (list 0)))
  (cond ((null p1) r)
        (t (let ((pp2 (poly-by-mon p2 (car p1) c)))
                 (poly-mult (cdr p1) p2 (+ c 1) (poly-add r pp2))))))
 
==> poly-mult
 
(poly-mult '(1 1) '(1 -1))
 
==> (1 0 -1)
 
(poly-mult '(1 1) '(1 1))
 
==> (1 2 1)
1
1 / 1 / 0
Регистрация: 06.11.2013
Сообщений: 87
14.05.2015, 21:41  [ТС] 3
Я видимо снова делаю что-то не так

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
? (defun poly-add (p1 p2)
   (let* ((n1 (- (length p1) 1))
          (n2 (- (length p2) 1))
          (n (max n1 n2))
          (res nil))
    (iter (for i from 0 to n)
      (cond ((and (<= i n1) (<= i n2)) (collecting (+ (nth i p1) (nth i p2)) into res))
            ((<= i n1) (collecting (nth i p1) into res))
            (t (collecting (nth i p2) into res))))
    res))
 
;;==> poly-add
 
(defun poly-by-mon (p c m) ;; с-коэфф, m-степень
   (append (replicate 0 m) (mapcar #'(lambda (q) (* c q)) p)))
 
;;==> poly-by-mon
 
(defun poly-mult (p1 p2 &optional (c 0) (r (list 0)))
  (cond ((null p1) r)
        (t (let ((pp2 (poly-by-mon p2 (car p1) c)))
                 (poly-mult (cdr p1) p2 (+ c 1) (poly-add r pp2))))))
 
;;==> poly-mult
 
(poly-mult '(1 1) '(1 -1))
 
;;==> (1 0 -1)
 
(poly-mult '(1 1) '(1 1))
 
;;==> (1 2 1)
;Compiler warnings :
;   In POLY-ADD: Undefined function ITER
;   In POLY-ADD: Undefined function FOR
;   In POLY-ADD: Undeclared free variable FROM
;   In POLY-ADD: Undeclared free variable TO
;   In POLY-ADD: Undefined function COLLECTING
;   In POLY-ADD: Undefined function COLLECTING
;   In POLY-ADD: Undefined function COLLECTING
;   In POLY-ADD: Undeclared free variable I (8 references)
;   In POLY-ADD: Undeclared free variable INTO (3 references)
POLY-ADD
? 
;Compiler warnings :
;   In POLY-BY-MON: Undefined function REPLICATE
POLY-BY-MON
? 
POLY-MULT
? 
> Error: Undefined function REPLICATE called with arguments (0 0) .
> While executing: POLY-BY-MON, in process Listener(5).
0
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,354
14.05.2015, 22:52 4
Цитата Сообщение от Catstail Посмотреть сообщение
collecting (nth i p2) into res
Предлагаю res объявлять в теле iter. В том смысле что подправить iter.
1
Модератор
Эксперт Python
28606 / 15467 / 3059
Регистрация: 12.02.2012
Сообщений: 25,348
Записей в блоге: 4
15.05.2015, 07:14 5
Цитата Сообщение от castorsky Посмотреть сообщение
Предлагаю res объявлять в теле iter. В том смысле что подправить iter.
- дело в том, что iter может собирать данные в разные переменные по разным алгоритмам. Собирать данные в переменную без объявления можно:

Lisp
1
   (iter (for i from 1 to 10) (collecting i))
и результат будет верный. Но воспользоваться результатом у меня получается только в случае, когда collecting выполняется последним (iter в HomeLisp - это функция, а не макро). Поэтому, вот это:

Lisp
1
   (iter (for i from 1 to 10)  (if (***) (collecting i) ***))
может и не дать ожидаемого результата. Но подумать надо. Спасибо!

Добавлено через 1 минуту
Цитата Сообщение от Ligeros Посмотреть сообщение
Я видимо снова делаю что-то не так
- в CL iter - это внешний пакет. Его нужно подключать. Могу переделать код, чтобы обойтись без iter.
1
1 / 1 / 0
Регистрация: 06.11.2013
Сообщений: 87
15.05.2015, 11:43  [ТС] 6
Цитата Сообщение от Catstail Посмотреть сообщение
- в CL iter - это внешний пакет. Его нужно подключать. Могу переделать код, чтобы обойтись без iter.
Давайте попробуем переделать код без iter
0
Модератор
Эксперт Python
28606 / 15467 / 3059
Регистрация: 12.02.2012
Сообщений: 25,348
Записей в блоге: 4
15.05.2015, 12:14 7
Без iter:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
(defun poly-add (p1 p2)
   (let* ((n1 (- (length p1) 1))
          (n2 (- (length p2) 1))
          (n (max n1 n2))
          (res nil))
    (dotimes (i (+ 1 n) (reverse res))      
      (cond ((and (<= i n1) (<= i n2)) (push (+ (nth i p1) (nth i p2)) res))
            ((<= i n1) (push (nth i p1) res))
            (t (push (nth i p2) res))))))
 
==> poly-add
 
(poly-add '(1 2 1) '(-1 1))
 
==> (0 3 1)
 
(defun poly-by-mon (p c m) ;; с-коэфф, m-степень
   (append (replicate 0 m) (mapcar #'(lambda (q) (* c q)) p)))
 
==> poly-by-mon
 
(defun poly-mult (p1 p2 &optional (c 0) (r (list 0)))
  (cond ((null p1) r)
        (t (let ((pp2 (poly-by-mon p2 (car p1) c)))
                 (poly-mult (cdr p1) p2 (+ c 1) (poly-add r pp2))))))
 
==> poly-mult
 
(poly-mult (poly-mult '(1 1) '(1 1)) '(1 1))
 
==> (1 3 3 1)
Список (1 1) соответствует полиному https://www.cyberforum.ru/cgi-bin/latex.cgi?(1+x). Таким образом, пример выше означает, что:

https://www.cyberforum.ru/cgi-bin/latex.cgi?{(1+x)}^{3}=1+3x+3{x}^{2}+{x}^{3}
3
1 / 1 / 0
Регистрация: 06.11.2013
Сообщений: 87
15.05.2015, 15:03  [ТС] 8
Lisp
1
2
;Compiler warnings :
;   In POLY-BY-MON: Undefined function REPLICATE
Я так понимаю нужно еще и функцию Replicate подключить?
0
Модератор
Эксперт Python
28606 / 15467 / 3059
Регистрация: 12.02.2012
Сообщений: 25,348
Записей в блоге: 4
15.05.2015, 15:40 9
Ligeros, а попробуй реализовать ее сам! Хоть что-то нужно делать и самому...
1
1 / 1 / 0
Регистрация: 06.11.2013
Сообщений: 87
15.05.2015, 19:20  [ТС] 10
Catstail, Ок, попробую. Я так понимаю, что Replicate должен объявить до poly-by-mon?
0
Модератор
Эксперт Python
28606 / 15467 / 3059
Регистрация: 12.02.2012
Сообщений: 25,348
Записей в блоге: 4
15.05.2015, 19:45 11
Цитата Сообщение от Ligeros Посмотреть сообщение
Я так понимаю, что Replicate должен объявить до poly-by-mon?
- не обязательно. Важно, чтобы при вызове ploy-mult эта функция была определена.
1
1 / 1 / 0
Регистрация: 06.11.2013
Сообщений: 87
15.05.2015, 20:07  [ТС] 12
Catstail, спасибо попробую реализовать.
0
4455 / 2074 / 263
Регистрация: 01.03.2013
Сообщений: 5,516
Записей в блоге: 22
17.05.2015, 07:07 13
Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(defn poly-mul (a b) (
  (defn winfold (l1 l2 acc)
    (cond (null? l1) acc
          (null? l2) acc
          (winfold (cdr l1) (cdr l2) (+ (* (car l1) (car l2)) acc))))
  (defn addzeros (n l) (cond (= 0 n) l (addzeros (- n 1) (cons 0 l))))
  (def la (length a))
  (def lb (length b))
  (def a0 (addzeros (- lb 1) a))
  (def b0 (addzeros (+ la lb -2) (reverse b)))
  (defn go (n a b r) (cond (= 0 n) r (go (- n 1) a (cdr b) (cons (winfold a b 0) r))))
  (go (+ la lb -1) a0 b0 nil)))
 
(print (poly-mul (list-from-to 0 3) (cons 5 (list-from-to 1 3))))
(def p (cons 1 1))
(poly-mul (poly-mul p p) p)
Код
(0 5 11 19 10 12 9)
(1 3 3 1)
3
1 / 1 / 0
Регистрация: 06.11.2013
Сообщений: 87
17.05.2015, 11:28  [ТС] 14
_Ivana, Простите,а не поясните как код работает?
0
4455 / 2074 / 263
Регистрация: 01.03.2013
Сообщений: 5,516
Записей в блоге: 22
17.05.2015, 11:39 15
Переворачиваю второй список, и совмещаю конец первого и начало второго, перемножаю почленно со сложением результатов (обычная оконная свертка, гуглите термин) - получаю коэффициент при старшей степени, потом сдвигаю второй список влево, чтобы накладывалось уже 2 элемента списков, делаю свертку - получаю коэффициент при степени на 1 меньше, и т.д. до нулевой степени. Совмещения и сдвиги делаю через забитие обоих списков необходимым количеством ведущих нулей - они исключают лишние элементы при свертке.
0
1 / 1 / 0
Регистрация: 06.11.2013
Сообщений: 87
17.05.2015, 11:43  [ТС] 16
Цитата Сообщение от _Ivana Посмотреть сообщение
Переворачиваю второй список, и совмещаю конец первого и начало второго, перемножаю почленно со сложением результатов (обычная оконная свертка, гуглите термин) - получаю коэффициент при старшей степени, потом сдвигаю второй список влево, чтобы накладывалось уже 2 элемента списков, делаю свертку - получаю коэффициент при степени на 1 меньше, и т.д. до нулевой степени. Совмещения и сдвиги делаю через забитие обоих списков необходимым количеством ведущих нулей - они исключают лишние элементы при свертке.
А на примере, какой многочлен можно перемножить и представить?
0
4455 / 2074 / 263
Регистрация: 01.03.2013
Сообщений: 5,516
Записей в блоге: 22
17.05.2015, 11:48 17
На примере будет понятнее. Начинайте, пишите коэффициенты 2 многочленов, переворачивайте их у второго и совмещайте конец первого и начало второго.
Цитата Сообщение от Catstail Посмотреть сообщение
Хоть что-то нужно делать и самому...
0
1 / 1 / 0
Регистрация: 06.11.2013
Сообщений: 87
17.05.2015, 11:51  [ТС] 18
_Ivana, Спасибо, но я имел в виду как запрос подается после компилирования?
0
4455 / 2074 / 263
Регистрация: 01.03.2013
Сообщений: 5,516
Записей в блоге: 22
17.05.2015, 11:55 19
Конструируете списки коэффициентов каждого многочлена и скармливаете их функции - получаете список результата. Все как обычно.
1
1 / 1 / 0
Регистрация: 06.11.2013
Сообщений: 87
17.05.2015, 12:15  [ТС] 20
Catstail, _Ivana, Прошу прощения за еще один глупый вопрос. Понимаю, что уже дикая наглость, но есть ли возможность этот код реализовать на языке Haskell?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.05.2015, 12:15

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Умножение многочленов
дорогие форумчане!! помогите пожалуйста не могу написать программу умножения двух многочленов и их...

Умножение 3 многочленов
Привет всем. Нужно перемножить многочлены: x^4 + x+ 1, x^4+ x^3 + x^2+ x+ 1, x^2+ x+ 1. ...

Умножение 2-х многочленов.
Правильно ли написанно!!! если нет то исправте Умножение 2-х многочленов. 1 :uses Crt;...

Умножение многочленов
Помогите пожалуйста написать программу. &quot;Перемножить два многочлена, заданных списками...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.