LISP - DODAWANIE MNOŻENIE UPRASZANIE WIELOMIANÓW

[gunia]

Hej,
Próbuję stworzyć dodawanie, mnożenie i upraszczanie wielomianów w postaci
2+3x+7xy+xy^2
W internecie znalazłam algorytm http://norvig.com/paip/cmacsyma.lisp, przyznam że nie wiem jak go ugryźć. Proszę o poradę jak podejść do tego zagadnienia, od czego zacząć. Byłabym wdzięczna za każdą poradę i wskazówkę.

[TPJ]

Po pierwsze: link nie działa.
Po drugie: Lisp to nazwa całej rodziny języków programowania. Czy chodzi o program w którymkolwiek dialekcie (np. w Common Lispie, czy w Scheme), czy w konkretnym?

A po trzecie, to czy mogłabyś wyjaśnić bliżej, na czym polega problem? Tak dla tych, którzy algebrę już dawno za sobą mają. (Przykłady, przykłady...)

_________________
Masz dość WP, Interii, Onetów? Zajrzyj na netbird.pl.

[gunia]

Chodzi o konkretnie o COMMON LISP
mamy 2 wielomiany dwóch zmiennych, które chcemy dodać
2xy + y^2 i 2xy+x^2+y^2
Co zapisujemy za pomocą listy odpowiednio
((2 1 1)(1 0 2)) i ((2 1 1)(1 2 0)(1 0 2))
czyli
(2 to współczynnik, a 1-ynki to kolejno stopnie x i y)
wynikiem dodawania jest 4xy+x^2+2y^2 co zapisujemy ((4 1 1)(1 2 0)(2 0 2)),
analogicznie dla mnożenia
Natomiast o upraszczanie to chodzi o to, że jak wprowadzę przykładowo wielomian
x^2-2x+x ((1 2)(-2 1)(1 1)) to otrzymam wynik x^2-x czyli ((1 2)(-1 1)).
Chciałabym móc wprowadzać dowolne wielomiany dwóch zmiennych, aby wykonywało się dodawanie, mnożenie i upraszaczanie

[TPJ]

CLa nie znam (jak zaczynałem się interesować Lispem, to dostępne implementacje CLa odrzuciły mnie na sporą odległość; później całkiem przyjemnie mi się pracowało w Scheme), ale za to znam trochę Scheme.


Tak na szybko (ok. godziny myślenia po obiedzie, jako odskocznia od pracy naukowej w ECLiPSe oraz portowania gier w Javie) wymyśliłem pewne rozwiązanie w Scheme.

Po pierwsze, o danym składniku wielomiany świadczą wszystkie elementy listy, która go opisuje, z wyjątkiem pierwszego. Bo np. (a 1 1) oraz (b 1 1) (gdzie a i b to jakieś liczby) to po prostu axy oraz bxy, które można bardzo łatwo do siebie dodawać i odejmować, wykonując odpowiednie operacje na współczynnikach. Stosunkowo łatwo więc będzie znaleźć te człony wielomianu, które można do siebie dodać. W Scheme służy do tego procedura "equal?".

Zacznijmy może od napisania dwóch procedur. Pierwsza z nich zwróci wszystkie te człony podanego (w formie listy) wielomianu, które są podobne do danego (również w formie listy) elementu. Np. dla wielomianu 3x^2 + 3xy - 2x oraz elementu 5x powinno zostać zwrócone -2x. Oto nasza procedura:

[gunia]

Hej,
Z pomnożeniem już sobie poradziłam. Mam pytanko do dodawania,
Mamy dwa wielomiany w1 (1 1 0)(2 1 1) i w2 (2 1 0) (1 0 0).
Chce je do siebie dodać, mój algorytm wygląda tak:
1) Porównuje ogon pierwszej podlisty pierwszego wielomianu z ogonem pierwszej podlisty drugiego wielomianu itd z każdy z każdym
2) jeśli taki sam ogon to dodać pierwszy element podlisty z pierwszym elementem drugiej podlisty i połączyć to w jedną podlistę
3) jeśli nie skopiować cala podlistę
4)na koniec połączyć 2 i 3 w jedna listę
No i tak, najchętniej przepuściłabym to przez jakąś pętlę – tylko jaką w lispie?
Z połączeniem wyniku punktu drugiego w podlistę mam problem
Do punktu 3 może znajdę gdzieś jakąś funkcję
I w punkcie czwartym znów problem z łączeniem podlist, w listę z podlistami
Proszę o podpowiedź odnośnie funkcji oraz o opinię dotyczącą algorytmu.
Aga

[TPJ]

Algorytm wydaje mi się być niepotrzebnie skomplikowany - za dużo tam tego porównywania i kopiowania podlist. Bardziej podoba mi się to, co zaproponowałem Ci w mojej poprzedniej odpowiedzi.

Zauważ, że problem dodawania dwóch wielomianów w1(x,y) = x + 2xy oraz w2(x,y) = 2x + 1 można przedstawić w postaci uproszczenia wielomianu w(x,y) = w1(x,y) + w2(x,y) = x + 2xy + 2x + 1. A więc zamiast dwóch (czy iluś tam) list przedstawiających wielomiany (i konsekwentnie: zamiast porównywania parami poszczególnych ich elementów) mamy problem wynajdywania "podobnych" elementów w tej samej liście, przy czym "podobne" to takie, które mają taki sam ogon.

Przyda się tutaj procedura "filter" - obecna w Scheme, w Clojure, to pewnie i w CLu podobna się znajdzie. Procedura ta zwraca te elementy danej listy, dla których spełniony jest podany predykat. Predykat to funkcja, która dla argumentu (będącego dowolnym elementem listy) zwraca wartość "prawdziwy" bądź "fałszywy".

Jeśli więc chcemy uzyskać listę wszystkich elementów wielomianu "podobnych" do danego, to potrzebujemy:

[frankie855]

Witam, nie ukrywam, iż jestem początkującym programistą w common lispie;) Zwracam się z pytaniem jak przerobić
(setq lista1 '((1 0 0) (1 1 1) (1 2 2)))
(setq lista2 '((1 0 0) (1 1 1) (1 2 2)))
(setq wynik (concatenate 'list lista1 lista2))
czyli scalanie dwóch wielomianów w jeden na funkcje, która będzie robiła to samo i pobierala 2 listy jako argumenty. Pozdrawiam wszystkich!!

[TPJ]

frankie855, nie jestem ekspertem od CLa, ale poszperałem w Google (przez 5 minut) i... Przecież funkcja "concatenate" robi dokładnie to, czego potrzebujesz!