matematykaszkolna.pl
Eliminacja Gaußa , pisanie kodu Mariusz: Filip Jeśli chodzi o eliminację Gaußa to strona o którą ci chodziło to ważniak http://wazniak.mimuw.edu.pl/index.php?title=MN05 Kiedyś znalazłem kod programu do odwracania macierzy i przełożyłem go z Pascala na C http://codepad.org/GZWexB6t Tutaj jako typ dla indeksów dałem unsigned int Przekładałem ten kod w miarę dokładnie i indeksowałem macierz od jedynki Jeśli chcesz zmodyfikować ten kod tak aby indeksować macierz od zera to zrób to ostrożnie aby nie spowodować problemów podczas wstecznej iteracji Zmienne sterujące instrukcjami iteracyjnymi proponowałbym zmienić indeksy podczas odwoływania się do elementów tablicy
8 sty 16:18
Filip: Cześć Mariusz, przez chwile byłem nieobecny, jednak wracam. Właśnie pierwszym krokiem do działającego programu rozwiązującego układy równań będzie napisanie przekształcenia macierzy ze współczynnikami przy niewiadomych do macierzy górnej trójkątnej. W linku który podałeś, chyba nie ma tego algorytmu, aby przejść do macierzy górnej trójkątnej, jest tylko rozkład LU, ale zakładam że jest to co innego Próbowałem tylko testowo narazie napisać przejście do macierzy górnej trojkątnej, tutaj wrzucam kod, jednak nie działa on poprawnie, gdzieś się wykrzacza #include <stdio.h> #include <stdlib.h> struct Matrix { int r, c; double** a; }; void schodkowanie(struct Matrix* m) { for (int k=0;k<m−>c−1;k++) { for (int w=k+1;w<m−>r;w++) { double wsp=m−>a[w][k]/m−>a[k][k]; for (int j=k;k<m−>c;j++) { m−>a[w][j]−=m−>a[k][j]*wsp; } } } } int main() { struct Matrix* m=malloc(sizeof(*m)); m−>r=4; m−>c=4; m−>a=malloc(m−>r*sizeof(*m−>a)); for (int i=0;i<m−>r;i++) { m−>a[i]=malloc(m−>c*sizeof(**m−>a)); } for (int i=0;i<4;i++) { for (int j=0;j<4;j++) fscanf(stdin, "%g", &m−>a[i][j]); } schodkowanie(m); for (int i=0;i<4;i++) { for (int j=0;j<4;j++) { printf("%lf ", m−>a[i][j]); } printf("\n"); } } Tutaj kolejne pytanie, jak zapobiec temu, ze m−>a[k][k] może być równe zero, co zrobić jeśli będzie?
8 sty 20:02
Filip: Blad znaleziony, w funkcji schodkowanie() w 3cim forze(), powinno byc j<m−>c, jednak nadal nie wiem czy dziala poprawnie
8 sty 20:06
Filip: Jeszcze jedno pytanie, mam równanie AX=B, modyfikuje tylko macierz A, czy powinienem modyfikować także macierz B w sprowadzaniu macierzy A do schodkowej?
8 sty 20:11
Mariusz: A dokonałeś częściowego wyboru elementu głównego ? W kolumnie poniżej głównej przekątnej wyszukujesz elementu największego co do wartości bezwzględnej i gdy go znajdziesz to zamieniasz wiersze Jeśli tym elementem głównym będzie zero to masz macierz osobliwą
8 sty 20:27
Mariusz: Kiedyś pisałem program do eliminacji Gaußa Tutaj ograniczyłem się do układów oznaczonych #include<stdio.h> #include<stdlib.h> #include<math.h> #include<conio.h> void gauss(double** Ab,int n,double *d) { int i,j,k,p; double temp,s; (*d) = 1.0; for( k = 0; k < n; k++) { p = k; for( j = k; j < n; j++) if( fabs(Ab[j][k]) > fabs(Ab[p][k]) ) p = j; for( j = 0; j <= n; j++) { temp = Ab[k][j]; Ab[k][j] = Ab[p][j]; Ab[p][j] = temp; } if(p != k) (*d) = −(*d); (*d) *= Ab[k][k]; if(Ab[k][k] == 0.0) return ; for( j = k + 1; j< n; j++) { s = (double)(Ab[j][k]/Ab[k][k]); for( i = k + 1; i <= n; i++ ) Ab[j][i] −= s * Ab[k][i]; } } } void backsub(double** Ab,int n) { int i,j; double sum; for(i = n − 1; i >=0 ;i−−) { sum = 0.0; for(j = i + 1; j < n;j++) sum += Ab[i][j]*Ab[j][n]; Ab[i][n] = (double)((Ab[i][n]−sum)/Ab[i][i]); } } int main() { int i,j,n; double d; double **A; char esc; do { printf("Rozwiazywanie ukladow rownan liniowych metoda eliminacji Gaussa\n"); printf("Podaj liczbe rownan \n"); scanf("%d",&n); A = (double**)malloc((n )*sizeof(double*)); for(i = 0;i < n;i++) A[i] = (double*)malloc((n+1)*sizeof(double)); for(i = 0;i < n; i++) { for(j = 0;j < n;j++) { printf("A[%d][%d]=",i,j); scanf("%lf",&A[i][j]); } printf("B[%d]=",i); scanf("%lf",&A[i][n]); } gauss(A,n,&d); for(i=0;i<n;i++) { for(j = 0;j<=n;j++) { printf("%lf ",A[i][j]); } printf("\n"); } if(d != 0) { backsub(A,n); for(i = 0;i < n;i++) printf("X[%d]=%.12lf\n",i,A[i][n]); } for(i = 0;i < n;i++) free(A[i]); free(A); esc = getch(); } while(esc != 27); }
8 sty 20:31
Mariusz: Ad 8 sty 2021 20:11 Modyfikujesz obydwie macierze
8 sty 20:33
Filip: To jeszcze przed przystąpieniem do pisania tego (faktycznie o tym zapomniałem) mam pytanie. Napisałeś "...W kolumnie poniżej głównej przekątnej..." Czy to zakłada, że elementu na głównej przekątnej nie bierzemy pod uwagę? W kodzie natomiast bierzesz ten element pod uwage
8 sty 20:43
Mariusz: Wydaje mi się że mógłbyś iterować bez tego elementu na głównej przekątnej
8 sty 21:13
Filip: Zmodyfikowałem moją funkcję, dodałem częściowy wybór elementu głównego: void schodkowanie(struct Matrix* m) { int q,s; for (int k=0;k<m−>c−1;k++) { s=0; for (int i=k;i<m−>r−2;i++) { if (abs(m−>a[i+1][k])>abs(m−>a[i+2][k])) { q=i+1; s=1; } } if (s==1) { for (int j=0;j<m−>r;j++) { double temp=m−>a[k][j]; m−>a[k][j]=m−>a[q][j]; m−>a[q][j]=m−>a[k][j]; } } if (m−>a[k][k]==0) return; for (int w=k+1;w<m−>r;w++) { double wsp=m−>a[w][k]/m−>a[k][k]; for (int j=k;j<m−>c;j++) { m−>a[w][j]−=m−>a[k][j]*wsp; } } } } Też właśnie mam się tylko ograniczyć do układów oznaczonych, natomiast jak zmodyfikować macierz wyrazów wolnych? Czy przeprowadzić taką samą operacje z odejmowaniem tak jak dla macierzy głównej? A, no i dodałem zmienną 's', która mi mówi, czy znaleziono w k−tej kolumnie pod diagonalą element główny, aby tylko zamieniać wiersze kiedy to konieczne − czy jest to dobry sposób?
8 sty 21:45
Filip: Diagonala to może złe określenie − przekątna
8 sty 21:47
Mariusz: Mam wątpliwości czy twój częściowy wybór elementu głównego będzie działał poprawnie
8 sty 21:57
Filip: Właśnie potestowałem i wygląda właśnie tak jak napisałeś, że nie działa poprawnie. Już doszedłem czemu. Ja porównuje elementy tylko obok siebie, przykładowo Kolumna pod główną przekątną 10 7 9 Moja część programu wskaże, że największy element (co do wartości bezwzględnej) to 9 (powinno być 10)
8 sty 22:02
Mariusz: Jak masz tablice jednowymiarową to jak wyszukujesz największy element ?
8 sty 22:31
Filip: Pierwszy element tablicy zapisujemy do zmiennej max. Kolejne elementy porównujemy z tą zmienną, jeśli natrafimy na wiekszy element, podmieniamy wartość zmiennej max. Zmieniłem już to w kodzie: maxsofar=abs(m−>a[k+1][k]); for (int i=k+2;i<m−>r−2;i++) { if (abs(m−>a[i][k])>maxsofar) { maxsofar=abs(m−>a[i][k]); s=1; q=i; } } Jednak ty znalazłeś chyba lepszy sposób z podmianą indeksu? Nie znam takiego
8 sty 23:41
Mariusz: No tak ja zapamiętywałem indeks największego elementu
9 sty 06:06
Mariusz: Podrzuć kod tego co już napisałeś tak abym mógł go przetestować
9 sty 08:25
Mariusz: Jeśli chodzi o odwracanie macierzy to zmodyfikowałem poprzedni kod tak aby tablice były indeksowane od zera Oszczędzi to trochę pamięć http://codepad.org/PJ1UfA0y
9 sty 11:48
Filip: https://pastebin.com/wncs4D90 Tutaj jest co do tej pory napisałem, kilka uwag: (1) funkcja schodkowanie() nie modyfikuje także macierzy wyrazów wolnych − musze to dodać (2) Program napisany aby sprawdzić czy działa schodkowanie − wprowadzanie danych nie jest wygodne, finalnie chce czytać dane z pliku tekstowego. (3) brakuje funkcji podstawienia wstecz − najprawdopodobniej dzisiaj ją dorobię Ogólnie program wymaga troche modyfikacji − najprawdopodobniej będe je dorabiał i na bieżąco podsyłał Pytanie: Czy fragment kodu, gdzie zamieniamy wiersze trzeba pisać iteracyjnie, czy można użyć swap()?
9 sty 14:08
Mariusz: A jest ona dostępna w C czy to dopiero wynalazek C++ ? Sprawdzę co tam do tej pory masz
9 sty 14:31
Mariusz: Ja tu chyba się źle wyraziłem Zmiennej w której przechowujesz maksa przed wejściem do pętli przypisujesz wartość elementu na głównej przekątnej a później już pętlę iterujesz od indeksu elementu znajdującego się zaraz poniżej głównej przekątnej i iterujesz już do końca kolumny Myślałem że chcesz zacząć iterować od elementu znajdującego się na głównej przekątnej tak jak ja (pętli nie musisz zaczynać od elementu na głównej przekątnej ale uwzględnić go chyba jednak musisz)
9 sty 14:46
Filip: Ja w pełni opuściłem element na głównej przekątnej, ponieważ moim maxsofar jest element ak+1k, w pętli iteruje od k+2 Przykładowo dla macierzy 1 2 3 4 4 5 6 4 7 8 9 4 1 2 3 4 weźmy kolumnę o indeksie 0 u mnie maxsofar=4 i zaczynam iterować i porównywać 7 i 4, 1 i 7 Masz racje, jeśli jednak element na głównej przekątnej trzeba także brać pod uwagę, w takim razie: maxsofar=akk i iteracje w pętli for() zaczynam od k+1 Ad. 14:31 Jednak tak, jest to wynalazek C++
9 sty 15:22
Mariusz: Ja poprawiłem już błędy w kodzie schodkowanie powinno już działać https://pastebin.com/index.php
9 sty 15:27
Mariusz: Wsteczne podstawianie możesz napisać w oddzielnej funkcji
9 sty 15:30
Mariusz: Dobrze by było aby efektem ubocznym działania funkcji schodkowanie było zwrócenie wyznacznika macierzy albo wskaźnikiem na liście parametrów albo instrukcją return
9 sty 15:34
Filip: Link który podesłałeś nie działa − w sensie dostaje pustą stronę. Co do wytycznych, które dostałem do pisania tej funkcji, to ma ona zwracać 1 gdy mamy macierz osobliwą, natomiast 0 gdy eliminacja została zakończona powodzeniem Jak podeślesz mi poprawiony kod, przeanalizuje go i postaram się to dopisać, ale to nie wszystko. Jeszcze musze zrobić nowy argument Matrix* b, gdzie to będzie macierz wyrazów wolnych i go także zmodyfikować odpowiednio w pętli I wtedy myślę, że ten etap będzie już zakończony i będzie można przejść do kolejnego
9 sty 15:48
Mariusz: Ach zapomniałem wysłać https://pastebin.com/fRpX9rqr Acha to ok jak ma takie wartości zwracać
9 sty 15:54
Mariusz: A to musisz wczytywać te macierze oddzielnie Na obydwu macierzach wykonujesz te same operacje więc można by to "włożyć" do jednej macierzy
9 sty 16:21
Filip: Tak, założyłem że czytam dane z dwóch plików tekstowych − jeden ze współczynnikami przy niewiadomych, drugi z wyrazami wolnymi, taki fragment kodu poglądowy: Matrix* A=readFromFile(argc>1?argv[1]:"A.txt"); //macierz współczynników Matrix* b=readFromFile(argc>2?argv[2]:"b.txt"); //macierzy wyrazów wolnych Matrix* x; //macierz z wynikami Zaraz podeśle dokończoną funkcję schodkowanie(Matrix* a, Matrix* b) dokończoną, zmienię jej nazwę na eliminate() (ze względu na to, że już przyjąłem anglojęzyczną formę nazywania zmiennych)
9 sty 17:10
Filip: int eliminate(struct Matrix* m, struct Matrix* b) { int q,s; double maxsofar; for (int k=0;k<m−>c;k++) { s=0; maxsofar=abs(m−>a[k][k]); for (int i=k+1;i<m−>r;i++) { if (abs(m−>a[i][k])>maxsofar) { maxsofar=abs(m−>a[i][k]); s=1; q=i; } } if (s==1) { for (int j=0;j<m−>r;j++) { double temp=m−>a[k][j]; m−>a[k][j]=m−>a[q][j]; m−>a[q][j]=temp; } } if (m−>a[k][k]==0) return 1; for (int w=k+1;w<m−>r;w++) { double wsp=m−>a[w][k]/m−>a[k][k]; for (int j=k;j<m−>c;j++) { m−>a[w][j]−=m−>a[k][j]*wsp; } b−>a[w][0]−=b−>a[k][0]*wsp; } } return 0; } Tak wygląda finalnie funkcja eliminate()
9 sty 17:31
Filip: Czy dobrze modyfikuje macierz wyrazów wolnych?
9 sty 17:39
Mariusz: Nie zamieniasz wierszy w tej macierzy Jeśli dopiszesz zamianę wierszy to schodkowanie powinno być ok
9 sty 18:29
Filip: int eliminate(struct Matrix* m, struct Matrix* b) { int q,s; double maxsofar; for (int k=0;k<m−>c;k++) { s=0; maxsofar=abs(m−>a[k][k]); for (int i=k+1;i<m−>r;i++) { if (abs(m−>a[i][k])>maxsofar) { maxsofar=abs(m−>a[i][k]); s=1; q=i; } } if (s==1) { for (int j=0;j<m−>r;j++) { double temp=m−>a[k][j]; m−>a[k][j]=m−>a[q][j]; m−>a[q][j]=temp; } double t=b−>a[k][0]; b−>a[k][0]=b−>a[q][0]; b−>a[q][0]=t; } if (m−>a[k][k]==0) return 1; for (int w=k+1;w<m−>r;w++) { double wsp=m−>a[w][k]/m−>a[k][k]; for (int j=k;j<m−>c;j++) { m−>a[w][j]−=m−>a[k][j]*wsp; } b−>a[w][0]−=b−>a[k][0]*wsp; } } return 0; } W takim razie tak to będzie wyglądać?
9 sty 19:07
Mariusz: Dopisz tę zamianę wierszy macierzy b i napisz funkcję do wstecznego podstawiania Na koniec piszesz to co ma być w funkcji main Czytanie z pliku i zapis do pliku zrealizujesz za pomocą oddzielnych funkcji które w funkcji main wywołasz ? Można i tak choć ja odczyt z pliku i zapis do pliku realizowałem już w funkcji main
9 sty 19:18
Mariusz: Teraz eliminacja wygląda ok Zostaje jeszcze wsteczne podstawianie Wsteczne podstawianie jest już łatwiejsze , możesz się wzorować na tym pseudokodzie z ważniaka
9 sty 19:28
Filip: Tak u mnie podstawienie w tył wygląda. jak widzisz funkcja zwraca wartość całkowitą, ponieważ tak mam w wytycznych (1) zwraca 2 − błąd nieprawidłowych rozmiarów macierzy −−−− tutaj nie wiem czy wszystko uwzględniłem w pierwszej linijce kodu w ciele funkcji (2) zwraca 1 − błąd dzielenia przez 0 (3) zwraca 0 − wsteczne podstawienie zakończone sukcesem int backsubst(struct Matrix* m, struct Matrix* x, struct Matrix* b) { if (x−>c!=1||x−>r!=m−>r||m−>r!=m−>c||b−>c!=1||b−>r!=m−>r) return 2; for (int i=m−>r−1;i>=0;i−−) { double sum=0.0; for (int j=i+1;j<m−>r;j++) { sum+=m−>a[i][j]*x−>a[j][0]; } if (m−>a[i][i]==0) return 1; x−>a[i][0]=(b−>a[i][0]−sum)/m−>a[i][i]; } return 0; }
9 sty 20:20
Filip: Natrfaiłem na problem, gdy odwołuję się do macierzy wyrazów wolnych. odwołouje sie do niej za pomocą b−>a[i][0] czy powinienem b−>a[i]? Program gdzieś się wykrzacza
9 sty 20:36
Mariusz: Teraz trzeba by przetestować tą funkcję realizującą podstawianie w tył w przypadku źle podanych danych bo dla poprawnych danych zdaję się działać ok A jeszcze jedno do obliczania wartości bezwzględnej lepiej użyć funkcji fabs
9 sty 20:47
Mariusz: U mnie dla poprawnych danych działa ok Nie testowałem jeszcze dla błędnych danych Myślę że odwołanie do tablicy jest poprawne b−>a[i][0]
9 sty 20:57
Filip: Tak, tez teraz przetestowałem na kilkunastu układach równań i wygląda na to, że pierwiastki dobrze oblicza
9 sty 21:08
Mariusz: Wiesz co jeszcze mógłbyś dodać − globalną stałą (czy makrodefinicję) która udawałaby zero Przydałaby się ze względów numerycznych w sytuacji gdybyś musiał dzielić przez bardzo małą liczbę Lepiej jest wtedy udać że macierz jest osobliwa
9 sty 21:50
Filip: Hmm, tego chyba nie robiłem nigdy, co to znaczy że by udawała 0, byłaby zerem czy nie do końca?
9 sty 22:11
Mariusz: Chodzi o to że ta stała byłaby liczbą bardzo bliską zera Gdybyś po wyszukaniu największego elementu w kolumnie miał bardzo małą liczbę to mógłbyś udać że jest to macierz osobliwa Udać bo z matematycznego punktu widzenia macierz nie byłaby osobliwa jednak ze względów numerycznych warto uznać wtedy że mamy wtedy macierz osobliwą Ba gdybyś miał dostatecznie małą liczbę to podczas dzielenia mógłbyś wyjść poza zakres obranego typu zmiennych
9 sty 22:23
Filip: Mariusz odbiegając trochę od tematu... widziałem, że liczysz całki przez podstawienie Eulera, czy masz jakieś przykłady na jego zastosowanie? Właśnie zobaczyłem, że jednak miałem ten sposób i chciałbym sobie przećwiczyć
10 sty 02:02
Mariusz: Mogę ci dać jakieś ale gdybym chciał ci je tutaj sprawdzić to kerajsy będą się wtrącać i przeszkadzać Tutaj kerajs nie zna się na programowaniu i się nie wtrącał i od razu przyjemniej się pisało Jeśli chodzi o podstawienia Eulera to Z tego co zauważyłem to jak masz całkę
 1 

dx
 xnax2+bx+c 
to najpierw patrzysz czy możesz użyć drugiego podstawienia ax2+bx+c=xt±c przy czym znak + lub − możesz sam wybrać Jeśli nie to sprawdzasz czy możesz użyć pierwszego podstawienia ax2+bx+c=t±ax a na końcu dopiero sprawdzasz trzecie podstawienie Eulera ax2+bx+c=(x−x1)t Jak masz całkę z
 W(x) 

dx
 ax2+bx+c 
to sprawdzasz czy możesz zastosować pierwsze podstawienie Jeśli nie to możesz oczywiście sprawdzać pozostałe podstawienia ale można też się zastanowić nad innymi sposobami liczenia całek takiej postaci
 1 

dx
 xx2+4x−4 
Pierwsze podstawienie będzie najwygodniejsze w użyciu
 1 

dx
 xx2+x+1 
Drugie podstawienie będzie najwygodniejsze w użyciu
 1 

dx
 (x+2)4−x2 
Trzecie podstawienie będzie najwygodniejsze w użyciu A teraz całka którą kiedyś dostałem z równania różniczkowego
 1 

dx
 x2(4x2−3)2x2−1 
Tutaj pierwsze podstawienie będzie wygodniejsze o ile po tym podstawieniu zauważysz coś w mianowniku Policz te co wymieniłem a później zobaczymy
10 sty 05:37
Mariusz: A jeszcze jedno co do kodu to tak z ciekawości zapytam czemu nie zwalniasz pamięci
10 sty 07:02
Filip: zapomniałem o zwalnianiu pamięci
10 sty 12:05
Mariusz: Filip to zadanie miałeś na metodach numerycznych czy np na programowaniu w C Jak na metodach numerycznych to są też iteracyjne metody rozwiązywania układów równań liniowych np iteracja Jacobiego czy Gaußa−Seidela
10 sty 16:59
Filip: na programowaniu w C
10 sty 21:19
Mariusz : Teraz ćwiczysz metodę Ostrogradskiego i skoro uczysz się programować to mógłbyś też oprogramować działania na wielomianach Strukturka do reprezentowania wielomianu mogłaby wyglądać tak struct Polynomial { int deg; double *coeff; }; a co do operacji na wielomianach to przydałyby się np takie dodawanie wielomianów odejmowanie wielomianów mnożenie wielomianów iloraz z dzielenia dwóch wielomianów reszta z dzielenia dwóch wielomianów NWD dwóch wielomianów no i opcjonalnie jakieś numeryczne metody szukania pierwiastków tych wielomianów
11 sty 12:19
Filip: Ok, zakładam, że: deg − stopień wielomianu coeff − vector ze współczynnikami przy kolejnych potęgach przy x Przykładowo (czy dobrze rozumiem), zapiszmy w kodzie taki wielomian: 3x5−12x4+9x2−0.5x+18 W kodzie: struct Polynomial* p = malloc(sizeof(*p)); p−>deg = 5; p−>coeff = malloc(sizeof(*coeff) + 1) // dodajemy miejsce dla x0 czyli wyraz wolny p[0] = 18 p[1] = −0.5 p[2] = 9 p[3] = 0 p[4] = −12 p[5] = 3 czyli p[i] reprezentuje kolejne współczynniki przy xi Jeżeli dobrze zrozumiałem jak to wygląda w kodzie, mogę przejść do pisania kolejnych funkcji
11 sty 12:52
Mariusz : No tak to miałoby wyglądać
11 sty 12:53
Filip: To możemy zacząć po kolei, czyli od dodawania, napisałbym to tak: struct Polynomial* addPolynomials(struct Polynomial* a, struct Polynomial* b) { int newDeg = a−>deg > b−>deg ? a−>deg : b−>deg; struct Polynomial* new = malloc(sizeof(*new)); new−>coeff = malloc(sizeof(*coeff) + 1); for (int i = newDeg − abs(a−>deg − b−>deg); i >= 0; i++) { new−>coeff[i] = a−>coeff[i] + b−>coeff[i]; } if (a−>deg > b−>deg) { for (int i = a−>deg; i >= a−>deg − abs(a−>deg − b−>deg); i−−) { new−>coeff[i] = a−>coeff[i]; } } else { for (int i = b−>deg; i >= b−>deg − abs(a−>deg − b−>deg); i−−) { new−>coeff[i] = b−>coeff[i]; } } //szukanie nowego stopnia wielomianu wyjściowego for (int i = newDeg; i >= 0; i++) { if (new−>coeff[i] != 0) { new−>deg = coeff[i]; return new; } new−>deg = 0; return new; } Takie coś udało mi się skleić na "sucho", nie testowałem czy działa bo pisałem od razu tutaj, idea jest prosta Mamy załóżmy dwa wielomiany W(x) = x4 + 3x2 + x − 1 −−−−> deg = 4 Q(x) = x2 − 2x + 1 −−−−> deg = 2 Orazy wyjściowy P(x) −−−> deg 4 (zakładamy, bo może być sytuacja że współczynnik będzie wynosić 0) Reprezentując je tablicowo: W(x) − {−1, 1, 3, 0, 1} Q(x) − {1, −2, 1} P(x) − { , , , , ,} newDeg = 4 Pierwsza pętla for(), od i = 2 do 0 włącznie P(x) = {0, −1, 4, , } − stan po wykonaniu całej pętli 3 razy Pózniej musimy uzupełnić współczynnik z wielomianu o większym stopniu Po ifie() P(x) = {0, −1, 4, 0, 1} Matematycznie: W(x) + Q(x) = x4 + 3x2 + x − 1 + x2 − 2x + 1 = x4 + 4x2 − x
11 sty 13:12
Filip: W if() else w warunku pętli for() (w obu przypadkach) zamiast znaku >= powinno być >
11 sty 13:14
Mariusz : Gdzieś segmentation fault dostajesz
11 sty 14:16
Filip: Tak, w pierwszej pętli for() zamiast i++ powinno być i−−, teraz dopiero zauważyłem jak powiedziałeś
11 sty 14:22
Filip: Zmodyfikowałem funkcję, działała źle, ponieważ niepoprawnie alokowałem pamięć: struct Polynomial* addPolynomials(struct Polynomial* a, struct Polynomial* b) { int newDeg = a−>deg > b−>deg ? a−>deg : b−>deg; struct Polynomial* n = malloc(sizeof(*n)); n−>coeff = malloc((newDeg + 1) * sizeof(*n−>coeff)); for (int i = newDeg − abs(a−>deg − b−>deg); i >= 0; i−−) { n−>coeff[i] = a−>coeff[i] + b−>coeff[i]; printf("%lf ", n−>coeff[i]); } if (a−>deg > b−>deg) { for (int i = a−>deg; i > a−>deg − abs(a−>deg − b−>deg); i−−) { n−>coeff[i] = a−>coeff[i]; } } else { for (int i = b−>deg; i > b−>deg − abs(a−>deg − b−>deg); i−−) { n−>coeff[i] = b−>coeff[i]; } } for (int i = newDeg; i >= 0; i++) { if (n−>coeff[i] != 0) { n−>deg = i; return n; } } n−>deg = 0; return n; }
11 sty 15:36
Filip: A, no i w ostatniej pętli for zamiast i++, i−−
11 sty 15:38
Filip: Okej, potestowałem i wygląda na to, że działa poprawnie, z odejmowaniem to po prostu zamieniam operator + na −?
11 sty 15:41
Mariusz : No u mnie taki kod działa jeśli chodzi o dodawanie https://pastebin.com/8h0sWZs8 No możesz od tej zamiany operatora zacząć i sprawdzimy czy działa poprawnie
11 sty 15:49
Filip: Dokładnie, kod taki sam, tylko nazwy zmiennej się różnią, ja zmieniłem z new na n, ponieważ w moim edytorze mi new podświetlało − a tego nie chciałem. Co do odejmowania, zmiana operatora to jednak nie wszystko. Po testowaniu, doszedłem do wniosku, że gdy dodajemy współczynniki, które nie brały udziału w odejmowaniu, powinniśmy zmienić ich znak na przeciwny czyli ten fragment kodu zmienić także if (a−>deg > b−>deg) { for (int i = a−>deg; i > a−>deg − abs(a−>deg − b−>deg); i−−) { n−>coeff[i] = a−>coeff[i]; } } else { for (int i = b−>deg; i > b−>deg − abs(a−>deg − b−>deg); i−−) { n−>coeff[i] = b−>coeff[i]; } }
11 sty 15:57
Filip: Hmm, wiesz co, chyba zbyt szybko do tego doszedłem, wydaje się to być bardziej skomplikowane, narazie nie wiem czy ta powyższa zmiana wystarczy
11 sty 16:05
Filip: ehh, sorry że tak cały czas pisze emotka, powyższa zmiana jest prawie dobra, powinno być if (a−>deg > b−>deg) { for (int i = a−>deg; i > a−>deg − abs(a−>deg − b−>deg); i−−) { n−>coeff[i] = a−>coeff[i]; } } else { for (int i = b−>deg; i > b−>deg − abs(a−>deg − b−>deg); i−−) { n−>coeff[i] = b−>coeff[i]; } } Jak dla mnie to wystarczy plus oczywiście zmiana operatora wcześniej
11 sty 16:13
Mariusz : Jeśli chodzi o mnożenie to naiwny algorytm ma złożoność O(n2) Mnożenie można przyśpieszyć korzystając z szybkiej transformaty Fouriera
11 sty 17:14
Mariusz : Jeśli chodzi o dzielenie to w książce Numerical Recipes in C jest funkcja https://www.cec.uchile.cl/cinetica/pcordero/MC_libros/NumericalRecipesinC.pdf
11 sty 18:03
Filip: Dokładnie, napisałem mnożenie tak jak mówiłeś, czy złożoność tego to nie będzie O((a−>deg+1)* (b−>deg+1))? struct Polynomial* multiplyPolynomials(struct Polynomial* a, struct Polynomial* b) { struct Polynomial* n = malloc(sizeof(*n)); n−>deg = a−>deg + b−>deg; n−>coeff = calloc((a−>deg + b−>deg + 1), sizeof(*n−>coeff)); for (int i = 0; i < a−>deg + 1; i++) { for (int j = 0; j < b−>deg + 1; j++) { n−>coeff[i + j] += a−>coeff[i] * b−>coeff[j]; } } return n; }
11 sty 18:58
Mariusz : No tak miałem na myśli przypadek dla wielomianów tego samego stopnia bo wtedy będziemy mieli taką złożoność
11 sty 19:19
Mariusz : Dopisałem funkcję wypisującą wielomian void printPolynomial(struct Polynomial *c) { for(int i = c−>deg;i >=0;i−−) if(c−>coeff[i] < 0.0) printf("−%lf x ** %d",−c−>coeff[i],i); else if(c−>coeff[i] > 0.0) printf("+%lf x ** %d",c−>coeff[i],i); printf("\n"); } Dałem podwójny asterisk jako operator potęgowania bo tamtego znaku nie wyświetla tutaj poprawnie
11 sty 19:26
Filip: Ok, właśnie ją skopiowałem do mojego programu, będzie wygodniej wyświetlać i czytać otrzymany wielomian. Jak rozumiem, nie da się zrobić, by zamiast x**5 wyświetlało w konsoli przykładowo x5
11 sty 19:45
Filip: Właśnie czytam o dzieleniu wielomianów i zdania są podzielone. Z jednej strony schemat Hornera będzie tylko dobry do dzielenie wielomianu przez dwumian (x−a), bo podobno ciężko go napisać aby działał dla większych wielomianów. Sugerują aby wzorować się na metodzie pisemnej. Na ważniaku znalazłem algorytm http://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Wyk%C5%82ad_4#Dzielenie_wielomian.C3.B3w Gdzie w książce, która mi podesłałeś jest dzielenie? Nie mogę znaleźć
11 sty 20:20
Mariusz : Na stronie 175 czyli w polu gdzie masz numery stron wpisz liczbę 199
11 sty 21:17
Mariusz : Schemat Hornera też się może przydać np gdybyśmy chcieli policzyć wartość wielomianu dla jakiejś liczby
11 sty 21:19
Filip: Właśnie, można dodać funkcję, która liczy wartość wielomianu dla dowolnej wartości. Pierwsze co przychodzi na myśl, to po prostu popodnosić nasze x do potęgi i−tej itp, jednak czy takie rozwiązanie nie będzie optymalne? Można wykorzystać funkcję pow(), która chyba jest już dostępna w C
11 sty 21:24
Mariusz : Tak funkcja pow jest dostępna w C ale jeśli chcesz mieć optymalne rozwiązanie to raczej korzystasz ze schematu Hornera Jeśli chodzi o dzielenie to w wyniku dostajesz dwa wielomiany więc jeśli chcesz je napisać w jednej funkcji to np iloraz zwracasz instrukcją return a resztę przekazujesz na liście paqrametrów
11 sty 21:44
Filip: Zaimplementowałem dzielenie do mojego programu, wygląda na to, że działa zarówno jak i dla dzielenie z resztą jak i bez reszty. Kod: struct Polynomial* dividePolynomials(struct Polynomial* a, struct Polynomial* b, struct Polynomial* r) { struct Polynomial* q = malloc(sizeof(*q)); q−>coeff = malloc((a−>deg + 1) * sizeof(*q−>coeff)); q−>deg = a−>deg; for (int i = 0; i < a−>deg + 1; i++) { r−>coeff[i] = a−>coeff[i]; q−>coeff[i] = 0.0; } for (int i = a−>deg − b−>deg; i >= 0; i−−) { q−>coeff[i] = r−>coeff[b−>deg + i] / b−>coeff[b−>deg]; for (int j = b−>deg + i − 1; j >= i; j−−) { r−>coeff[j] −= q−>coeff[i] * b−>coeff[j − i]; } } for (int i = b−>deg; i < a−>deg + 1; i++) { r−>coeff[i] = 0.0; } return q; }
11 sty 22:46
Filip: Daj znać, jakbyś zaalokowałam pamięc dla r−>coeff oraz q−>coeff, ja tutaj zaalakowałem, zakładając te same stopnie co dla wielomianu, którego dzielimy, jednak czy nie dałoby się zrobić, że: (1) q−>coeff to współczynniki nowego wielomiany, więc największa potęga przy x może wynosić a−>deg − b−>deg (2) r−>coeff można zaalokować jako b−>deg − 1
11 sty 22:53
Filip: Właśnie tak jak napisałem to zrobiłem na początku, jednak mi wychodziło poza tablice, ponieważ pierwszy for() działą w zakresie 0 − a−>deg, tego się chyba nie da obejśc, więc r−>coeff oraz q−>coeff muszą być takich samych rozmiarów jak a−>coeff. Ewentualnie można zmienić q−>deg i r−>deg, jednak matematycznie nie pamiętam jak to jest z tymi wykładnikami potęg w wielomianach
11 sty 23:20
Mariusz: Jeśli chodzi o stopnie tych wielomianów to co gdyby stopień dzielnika był większy niż stopień dzielnej ? Co wyszłoby z różnicy tych stopni ? Czy wtedy stopień reszty jest ostro mniejszy od stopnia dzielnika ? Gdybyś przyjął że stopień reszty jest równy stopniu dzielnika to z ostatniej pętli for powinieneś zrezygnować No właśnie gdybyśmy chcieli zoptymalizować kod to tą pierwszą pętlę for też trzeba by było zmodyfikować , być może dodać w niej instrukcję warunkową if albo rozbić na dwie pętle Problemem może być to że ta zagnieżdżona pętla jest skonstruowana w oparciu o założenie że r−>deg = a−>deg i to tutaj może wystąpić to "wyjeżdżanie" indeksem poza tablicę
12 sty 06:23
Mariusz: Na pierwszy rzut oka widać że algorytm którego użyli potrzebuje dodatkowej pamięci do przeprowadzenia obliczeń i właśnie te pomocnicze obliczenia zapamiętuje w zmiennej r dla której zaalokował więcej pamięci niż potrzeba Jeśli chodzi o te stopnie to stopień dla q da się ustalić bez większego problemu Jeśli chodzi Można by pomyśleć nad takimi rozwiązaniami 1. Wielomian r stopnia a−>deg można rozbić na dwa wielomiany z czego jeden będzie zmienną lokalną a drugi będzie wyprowadzany na liście parametrów funkcji jako reszta 2. Spróbować modyfikować wielomian a
12 sty 07:47
jc: Wtrącę się. Mariusz, masz rację, wartość wielomianu liczymy wg wzoru: ax3+bx2+cx+d = ((ax+b)x+c)x+d W przypadku wielomianów przekazujemy wskaźniki (no, chyba że masz wielomiany niskiego, ustalonego stopnia).
12 sty 10:04
Mariusz: jc a ty co byś odpowiedział ba pytanie Filipa zadane we wpisie z 11 sty 2021 22:53
12 sty 12:20
Filip: Aby uniknąć przykładowo dzielenia wielomianu o niższym stopniu niż ten przez którego dzielimy, można na początku w ciele funkcji po prostu dodać if (a−>deg < b−>deg) .... No właśnie nie przyjmuje się tak, że stopień reszty jest mniejszy niż stopień dzielnika (?)
12 sty 12:33
Mariusz: No tak się przyjmuje if (a−>deg < b−>deg) { q = 0; r = a; } Gdybyś chciał napisać NWD wielomianów to przydałaby się jeszcze funkcja sprawdzająca czy wielomiany są równe no i korzystałbyś już z wcześniej napisanych funkcji zwłaszcza tej która realizuje dzielenie wielomianów Pętla while byłaby wygodniejsza w użyci oraz pewnie przyda się jakaś zmienna lokalna reprezentująca pomocniczy wielomian
12 sty 13:07
Filip: Jak takie NWD(P(x), Q(x)) znaleźć Jak rozumiem pierw sprawdzamy czy p−>deg > q−>deg − jeśli tak − idziemy dalej
 P(x) 
(1) Wykonujemy działanie

− jeżeli reszta wynosi 0 to NWD(P(x), Q(x)) = Q(x)
 Q(x) 
(2)w przeciwnym razie przypisujemy P(x) wartość Q(x), a Q(x) wartość otrzymanej reszty i powracamy do kroku (1) (?) Wezmę jakiś przykład, mamy wielomiany P(x) = x3+x2−3x−3 Q(x)=x2+3x+2
 P(x) 
(1)

 Q(x) 
P(x)=(x−2)Q(x)+(x−1) − reszta != 0 (2) P(x)=Q(x) Q(x)=(x+1) Wracamy do kroku 1
P(x) 

=(x+2)(x+1) + 0 −− reszta 0, czyli NWD(P(x), Q(x)) = x+1
(x+1) 
Czy to będzie coś tak wyglądać mniej więcej?
12 sty 13:57
Mariusz: No mniej więcej tak to mogłoby wyglądać
12 sty 14:08
Filip: Może do tego przydałaby się funkcja, która sprawdza, które stopnia jest wielomian − jeśli byłby zerowy, np W(x)−>reg = −1
12 sty 15:10
Mariusz: Myślałem o takiej funkcji int equals(struct Polynomial *a,struct Polynomial *b) { int result = (a−>deg == b−>deg); for(int i=a−>deg;result && i >=0 ; i−−) result = result && (a−>coeff[i] == b−>coeff[i]); return result; } i porównywać z wielomianem zerowym ale może twój pomysł jest lepszy Jeśli chodzi o stopień wielomianu p to czy nie wystarczy odwołać się do pola p−>deg;
12 sty 15:30
Filip: ja myślałem aby napisać to tak: − raczej będzie to szukać stopnia wielomianu, bo przy NWD() dostaniemy wielomian, jednak nie wiemy jakiego stopnia int checkDeg(struct Polynomial* p) { for (int i = p−>deg; i >= 0; i−−) { if (p−>coeff[i] != 0.0) { return −1; } return 1; } Ja myslałem by coś takiego zrobić, gdyż nasza reszta zakładamy że będzie tak samo jak a−>deg Tutaj w tej funkcji sprawdzimy, jakiego stopnia rzeczywiście jest nasza reszta − funkcja zwraca −1 gdy reszta nie jest stopnia zerowego, natomiast 1 jeśli jest Jednak ta funkcja sprawdza tylko czy wielomian jest zerowy trzebaby zmienić jej nazwę jednak nie wiem jak w języku angielskim jest wielomian zerowy Jednak nie wiem czy ta funkcja ma sens, jeśli tak − przdałaby się funkcja która reallocuje pamięć dla wielomianu. Przykładowo, zakładamy, że wielomian będzie maksymalnie stopnia 5 (przykładowo założyliśmy to przy dzieleniu) jednak w tablicy może wyglądać tak: [a, b, 0, 0, 0, 0] Po wrzuceniu do funkcji checkDeg() wyjdzie, że wielomian jest stopnia pierwszego, to w sumie już można reallocować w środku tej funkcji Zrozumiałeś o co mi chodzi?
12 sty 16:56
Mariusz: To może tak int checkDeg(struct Polynomial *p) { for(int i = p−>deg; i >= 0; i−−) { if(p−>coeff[i] != 0.0) return i; } return −1; } A co do realokacji pamięci to powinna być dostępna w standardzie funkcja realloc()
12 sty 17:42
Filip: Coś siadłem do NWD, coś takiego udało mi się zrobić − taki ala szablon można powiedzieć struct Polynomial* NWD(struct Polynomial* a, struct Polynomial* b) { struct Polynomial* temp = malloc(sizeof(*temp)); temp−>deg = b−>deg; temp−>coeff = malloc((temp−>deg + 1) * sizeof(*temp−>coeff)); while (checkDeg(b) != −1) { //tutaj by trzeva zrobić, aby wielomian a przejęło deg i *coeff po b temp = b; dividePolynomials(a, b, b); a = temp; } return temp; } Daj znać czy jest chociaż trochę poprawne
12 sty 19:10
Mariusz: Niedawno w C# zacząłem pisać klasę liczb wymiernych i tam NWD przydaje się do skracania ułamków Dla liczb NWD mogłoby tak wyglądać private static long Gcd(long a,long b) { long c; a = Math.Abs(a); b = Math.Abs(b); //Przy wielomianach dwie powyższe instrukcje pomijasz while(b != 0) { c = a; a = b; b = c % b; } return a; } I tutaj trzeba by napisać coś podobnego Myślę że idziesz w dobrym kierunku Lepiej by było usprawnić tą funkcję realizującą dzielenie ale jak nie mamy na to pomysłu
12 sty 20:09
Mariusz: Może dobrze by było gdyby tak przepisać funkcję realizującą dzielenie tak aby nie modyfikować wielomianów a oraz b np struct Polynomial* dividePolynomials(struct Polynomial* a, struct Polynomial* b, struct Polynomial* r) { struct Polynomial* q = malloc(sizeof(*q)); struct Polynomial* temp = malloc(sizeof(*temp)); temp−>coeff = malloc((a−>deg + 1) * sizeof(*temp−>coeff)); temp−>deg = a−>deg; q−>coeff = malloc((a−>deg + 1) * sizeof(*q−>coeff)); q−>deg = a−>deg; for (int i = 0; i < a−>deg + 1; i++) { temp−>coeff[i] = a−>coeff[i]; q−>coeff[i] = 0.0; } for (int i = a−>deg − b−>deg; i >= 0; i−−) { q−>coeff[i] = temp−>coeff[b−>deg + i] / b−>coeff[b−>deg]; for (int j = b−>deg + i − 1; j >= i; j−−) { temp−>coeff[j] −= q−>coeff[i] * b−>coeff[j − i]; } } for(int i = 0;i < b−>deg;i++) r−>coeff[i] = temp−>coeff[i]; return q; }
12 sty 21:21
Filip: Wydaje mi się, że już początkowo ta funkcje nie modyfikowała wielomianów a i b, tylko r. Co do NWD() to właśnie się wzorowałem na funkcji dla liczb całkowitych, jednak jest to zoptymalizowana wersja. Zapewne znasz wersje z odejmowaniem − czy zadziałałoby to na naszych wielomianach? Jutro postaram się poprawić NWD()
12 sty 22:23
Mariusz: Co do tej wersji z odejmowaniem to nie jestem pewny czy zadziała dla wielomianów Spróbuj pomyśleć nad wersją z dzieleniem a testowałeś tę funkcję realizującą dzielenie np na przykładach takich jak dividePolynomials(a,b,b);
12 sty 22:29
Filip: Nie, ale teraz podejrzewam, że może być to problematyczne z takim kodem, iż na nowo alokujemy zaalokowana pamięć − czy jest to dozwolone, może powinniśmy w funkcji dzielącej sprawdzać co jest zaalokowane dla wielowianu r a co nie
12 sty 22:41
Mariusz: No nie wiem w kodzie z 12 sty 2021 21:21 przydałoby się przed zwróceniem wartości zwolnić pamięć na zmienną temp Ja sprawdziłem funkcję dzielącą z parametrami a,b,b i działała ok (oczywiście ta wersja z dodatkową zmienną )
12 sty 23:31
Filip: No właśnie nie rozumiem jaka idea jest dodawanie kolejnej zmiennej? Mógłbyś przybliżyć, bo aktualnie nie widzę, w czym jest różnica czy będziemy pierw działać na "surowym" r niż na temp i później kopiować elementy z temp do q
12 sty 23:40
Mariusz: Zauważ że w kodzie modyfikujemy r i gdy r będzie tym samym co b to możemy dostać błędne obliczenia Gdy wywołujemy funkcje np z parametrami a,b,r to wersja będzie bez dodatkowej zmiennej ale jeśli wywołamy funkcje z parametrami a, b, b to r będzie tym samym co b i możemy otrzymać błędny wynik
13 sty 00:16
Filip: aa racja, czyli w takim razie trzeba na końcu funkcji dodać zwalnianie pamięci, przykładowo tak: free(temp−>coeff) free(temp) czyli po wywołaniu funkcji z argumentami takimi dividePolynomials(a, b, b) − w wielomianie b
 a 
powinniśmy mieć resztę z dzielenia

 b 
13 sty 09:42
Filip: Tak sobie teraz pomyślałem, że można dodać funkcję rest, która zwróci nam reszta z dzielenia struct Polynomial* Rest(struct Polynomial (*)diviedPolynomials(struct Polynomial*, struct Polynomial*, struct Polynomial*), struct Polynomial* a, struct Polynomial* b, struct Polynomial* r) Taki szablon funkcji − jednak nie wiem czy to już nie będzie zbyt duże kombinowanie
13 sty 09:52
Filip: Ten argument ostatni (r) jest niepotrzebny
13 sty 09:54
Filip: Zmodyfikowałem trochę twój kod z dzieleniem, bo początkowo nie działało mi dla argumentów (a, b, b) − nie wiem czy u ciebie też U mnie problem był taki, że gdy r−>deg < a−>deg to wyjeżdżało poza tablicę, dodałem ifa(), aby temu zapobiec + na początku warunek początkowy także dodałem Teraz wygląda na to, że działa poprawnie, kod: struct Polynomial* dividePolynomials(struct Polynomial* a, struct Polynomial* b, struct Polynomial* r) { if (a−>deg < b−>deg) return NULL; struct Polynomial* q = malloc(sizeof(*q)); struct Polynomial* temp = malloc(sizeof(*temp)); temp−>coeff = malloc((a−>deg + 1) * sizeof(*temp−>coeff)); temp−>deg = a−>deg; q−>coeff = malloc((a−>deg + 1) * sizeof(*q−>coeff)); q−>deg = a−>deg; for (int i = 0; i < a−>deg + 1; i++) { temp−>coeff[i] = a−>coeff[i]; q−>coeff[i] = 0.0; } for (int i = a−>deg − b−>deg; i >= 0; i−−) { q−>coeff[i] = temp−>coeff[b−>deg + i] / b−>coeff[b−>deg]; for (int j = b−>deg + i − 1; j >= i; j−−) { temp−>coeff[j] −= q−>coeff[i] * b−>coeff[j − i]; } } for (int i = 0; i < b−>deg; i++) { r−>coeff[i] = temp−>coeff[i]; } if (r−>deg < a−>deg) { for (int i = b−>deg; i < r−>deg + 1; i++) { r−>coeff[i] = 0.0; } } else { for (int i = b−>deg; i < a−>deg + 1; i++) { r−>coeff[i] = 0.0; } } free(temp−>coeff); free(temp); return q; }
13 sty 10:27
Filip: A, no i zrobiłem test, jakbyś kwestionował ten fragment kodu − u ciebie go nie widzę: if (r−>deg < a−>deg) { for (int i = b−>deg; i < r−>deg + 1; i++) { r−>coeff[i] = 0.0; } } else { for (int i = b−>deg; i < a−>deg + 1; i++) { r−>coeff[i] = 0.0; } } Jak dla mnie jest on potrzebny, zrobiłem mały test: Dzieliłem wielomiany: x4−3x3+3x2−4x+3 przez x−1 Z tym fragmentem kodu w funkcji dzielącej otrzymuję resztę 0 − czyli taka jaka powinna wyjść, natomiast bez tego fragmentu otrzymuję resze 1, więc wydaje mi się, że musi być
13 sty 10:35
Mariusz: W przypadku gdy if (a−>deg < b−>deg) dobrze by było do reszty przekopiować wielomian a natomiast zwrócić wielomian zerowy Tak po napisaniu to zauważyłem i poprawiłem to u siebie
13 sty 10:57
Mariusz: Mógłbyś się jeszcze pobawić tą funkcją dzielącą tak aby wielomian wyprowadzany poza funkcję jako reszta miał dokładnie taki stopień jaki powinien mieć wtedy funkcja checkDeg nie będzie potrzebna
13 sty 11:09
Filip: Dopisałem taką funkcję void findDeg(struct Polynomial* p) { for (int i = p−>deg; i >= 0; i−−) { if (p−>coeff[i] != 0.0) { p−>deg = i; return; } } p−>deg = 0; } i wywołuje ją przed zwrócenie wielomianu w funkcji dzielącej findDeg(r); findDeg(q); przez co dostaje realne stopnie tychże wielomianów
13 sty 11:12
Filip: Podrzucam ci mój cały kod, jak u mnie wygląda cały program i poszczególne funkcje. Funkcja GCD() coś nie działa poprawnie Tutaj kod: https://pastebin.com/q7Ffu2Ny Pytanie: Chodziło tobie o to, aby nie robić dodatkowej funkcji do sprawdzenia stopni, tylko aby już w funkcji dzielącej te stopnie później zmienić?
13 sty 11:16
Filip: A i zapomniałem, tam w funkcjach gdzie alokujemy pamięć na pomocniczy/nowy wielomian, przydałoby się od razu je tam także zwalniać, lub napisać funkcję, która będzie zwalniać pamięć
13 sty 11:17
Mariusz: Tak chodziło mi o to aby tak zmodyfikować funkcję dzielącą aby reszta miała już taki stopień jaki powinna mieć
13 sty 11:38
Mariusz: Dobra teraz będę pisał inny program, za ok 2h wrócę i spróbuję przetestować twój kod
13 sty 11:53
Filip: Przy okazji, odbiegając od tematu, znasz/spotkałeś się kiedyś z wielomianami Czebyszewa? Dokładniej chodzi mi o aproksymacje średniokwadratową z bazą wielomianów Czebyszewa
13 sty 15:43
Mariusz: Filip , Przetestuj sobie ten kod https://pastebin.com/g8HLnFWr
13 sty 15:46
Mariusz: Wielomiany Czebyszowa , tak średnio używałem ich jedynie do rozwijania cos(nx) jako sumę potęg
13 sty 15:48
Mariusz: Jeszcze ta funkcja licząca NWD nadal nie działa poprawnie
13 sty 17:02
Filip: Potestowałem i działa, wprowadziłem jednak pewną modyfikację w funkcji dodawania i odejmowania pozbyłem się tej ostatniej pętli for na rzecz użycia funkcji findDeg(), jednak przy alokacji dodałem, że n−>deg = newDeg; struct Polynomial* addPolynomials() { /* * kod */ n−>deg = newDeg /* * kod */ findDeg(n); return n; } No i tak samo zrobiłem z funkcją odejmującą wielomiany Jeszcz myślę o przejrzystości tego kodu, sporo alokujemy, może by dodać funkcję, która jako parametr będzie przyjmować stopień wielomianu, zwracającą zaalokowany wielomian − według mnie poprawi to czytelność kodu
13 sty 17:40
Mariusz: https://pastebin.com/g8HLnFWr Jeśli chodzi o funkcję NWD z tego kodu to dotychczas zauważyłem że jeśli znajdzie ten dzielnik w pierwszej iteracji pętli while to zwraca poprawną wartość a jeśli nie znajdzie go w pierwszej iteracji to błędnie zwraca wielomian zerowy chyba że ją poprawiłeś Przykładowa para wielomianów dla funkcji NWD x5−x4−2x3+2x2+x−1 5x4−4x3−6x2+4x+1
13 sty 18:21
Mariusz: Wydaje mi się że poprawiłem ten kod Pamiętasz o tej globalnej stałej o której ci pisałem przy rozwiązywaniu układów równań liniowych Tutaj mi była potrzebna (użyłem zamiast stałej makrodefinicji ale jak ja się uczyłem C to tak się pisało) Dodatkowo alokację pamięci na tablicę dla zmiennych lokalnych dałem wewnątrz pętli while https://pastebin.com/cv0HBfJ4
13 sty 19:51
Mariusz: " Jeszcz myślę o przejrzystości tego kodu, sporo alokujemy, może by dodać funkcję, która jako parametr będzie przyjmować stopień wielomianu, zwracającą zaalokowany wielomian − według mnie poprawi to czytelność kodu" Może to być niezły pomysł z tym poprawieniem czytelności kodu
13 sty 21:18
Filip: No właśnie jaka idea stoi za użyciem tej stałej? Jak rozumiem to jest coś w stylu 0.000000000001? I my to uznajemy jako 0.0? W takim razie co by było gdyby w 154 zamiast fabs(b−>coeff[0]) > ZERO dać fabs(b−>coeff[0]) > 0.0 A no i dlaczego robimy wartość bezwzględną? Ze względu na to, że b−>coeff[0] może być równe −0.0? Kod już potestuje jutro, i jeśli będzie działał poprawnie, to zostało do napisania funkcja obliczająca wartość wielomianu dla jakieś liczby zmiennoprzecinkowej, wtedy będzie można się brać za przejrzystość kodu
13 sty 21:51
Filip: Można jeszcze ciekawiej zrobić, można generować losowo wielomiany, przy pomocy rand(), a raczej ich stopień oraz współczynniki
13 sty 21:58
Mariusz: Chodzi o to że tutaj masz skończoną precyzję i zero w języku programowania nie jest tym samym co zero w matematyce Powinieneś już mieć coś o reprezentacji liczb rzeczywistych na maszynie Gdy będziesz miał metody numeryczne to bardziej będą zwracali uwagę na błędy powstałe podczas wykonywania działań arytmetycznych Dla losowych współczynników NWD najczęściej będzie wielomianem zerowego stopnia Jeśli chodzi o ten kod to gdy po wywołaniu funkcji dzielącej próbowałem podzielić współczynniki reszty przez współczynnik wyrazu wiodącego tejże reszty to zwracał błędny wynik
14 sty 07:28
Filip: Wygląda na to, że GCD() działa poprawnie − tutaj moje pytani, gdybyśmy chcieli napisać funkcję NWW(), to czy sprawdzi się taki zapis?
 P(x)*Q(x) 
NWW=

 NWD(P(x), Q(X) 
I fajnie poprawiłeś sposób wprowadzania wielomianów − teraz jest to o wiele wygodniejsze W sensie co chciałeś podzielić? Wyraz wiodący to jest przykładowo dla wielomianu x2−3x+1, x2? A współczynnik to 1? Czyli chciałeś coś takiego zrobić: dividePolynomials(a, b, r); for (int i = 0; i < r−>deg; i++) r−>coeff[i] /= r−>coeff[r−>deg];
14 sty 13:42
Mariusz: No mniej więcej to chciałem zrobić , oczywiście tylko w funkcji liczącej NWD Co do NWW to dla dwóch wielomianów powinien się sprawdzić Jeśli NWD działa dobrze to możesz użyć naszej strukturki do wyznaczenia mianowników we wzorze Ostrogradskiego do całkowania funkcji wymiernych
14 sty 16:26
Filip: Pytanie bardziej o formatowanie kodu, co sądzisz o blank space'ach w ciałach funkcji? Przepadasz za nimi, czy wszystko jednym ciągiem piszesz od góry do dołu. Umownie jest tak, że jak zaczynasz nowy blok logiczny najlepiej zrobić blank space. Jakie jest twoje stanowisko?
14 sty 18:38
Filip: Ja osobiście w ciele funkcji za nimi nie przepadam
14 sty 18:44
Filip: Zmieniłem troche kod do pewnego momentu, tak to wygląda, pozostałe rzeczy narazie pozostają niezmienione: https://pastebin.com/976pniya
14 sty 18:50
Filip: Niestety zepsułem tym funkcję dzielącą wielomiany, zaraz postaram się znaleźć co jest nie tak...
14 sty 21:10
Filip: A nie, u ciebie w kodzie funkcja dzieląca też nie działa poprawnie
14 sty 21:13
Mariusz: 14 sty 2021 18:38 A to już kwestia umowna Jeśli zwiększą czytelność kodu to czemu nie
14 sty 21:13
Mariusz: A co jest nie tak z funkcją dzielącą ?
14 sty 21:14
Filip: Dziele z resztą wielomiany 2x3−5x2+4x−1 i x−1 i reszta wychodzi mi 0, a powinna −x+1
14 sty 21:17
Filip: ...... nie ważne, reszta to 0
14 sty 21:25
Filip: Rozważałeś użycie realloc() w tutaj zamiast tego kodu? free(a−>coeff); a−>deg = b−>deg; a−>coeff = malloc((a−>deg+1)*sizeof(*a−>coeff)); Na: a−>deg = b−>deg; realloc(a−>coeff, ((a−>deg + 1) * sizeof(*a−>coeff))); Wydaje mi się, że będzie to lepsze niż zwalnianie/alokacja
14 sty 21:32
Mariusz: Może i będzie lepiej wyglądać , a czy będzie lepsze zależy od tego jak napisali funkcję realloc Spróbuj i zabacz jak to działa
14 sty 21:47
Filip: https://pastebin.com/Wqs4S2mg Tutaj masz zmienioną funkcję GCD() − na moje działa, potestowałem, ale też możesz potestować jak nie masz pewności Tym akcentem chyba kończymy temat wielomianów, no chyba że masz jeszcze pomysł jakie funkcje można dodać, moje dwie propozycje: findRoots(struct Polynomial* p) − szuka pierwiastków wielomianu countValue(double x) − oblicza wartość wielomianu dla danego x
14 sty 22:03
Filip: Jednak pierwiastki zbytnio nie wiem jak znaleźć, więc zostaje tylko ta druga funkcja
14 sty 22:11
Mariusz: Jeśli chodzi o znajdowanie pierwiastków to myślałem nad jakimiś metodami numerycznymi a jeśli chodzi o tę drugą funkcję to może schemat Hornera Jeśli chodzi o pierwiastki to musiałbyś trochę poczytać o metodach numerycznych Co do schematu Hornera to stosunkowo łatwo go napisać Możemy do tego powrócić jak będziesz miał metody numeryczne lub o tym trochę poczytasz
14 sty 22:20
Filip: No dobra, w takim razie wątek chyba tymczasowo zakończony, jak masz jeszcze jakieś fajne tematy, które można tak omówić to możesz w przyszłości zakładać nowe wątki, ja raczej na forum jestem emotka Ja chyba tym czasem będę zabierał się za listę dwukierunkową
14 sty 22:35
Mariusz: Listę dwukierunkową − kiedyś ją pisałem https://ideone.com/nubXls O tutaj zrealizowałem nawet algorytm Jarvisa na liście https://pastebin.com/VpNqNHuS Co do kodu w C# to tutaj wstawianie w sposób uporządkowany nie jest optymalne bo przepisywałem tę funkcję z listy jednokierunkowej Zastanów się nad wstawianiem przed wybranym elementem Rozpatrz przypadki jakie możesz otrzymać i oprogramuj je
14 sty 22:59
Mariusz: A co z całkami na metodę Ostrogradskiego i podstawienia Eulera ? Będziemy ten temat kontynuować ?
14 sty 23:06
Filip: Można, tylko właśnie utknąłem na tej drugiej całce:
 3x+1 

dx
 (x−1)(x2+1) 
Możesz jakąś podpowiedź dać?
14 sty 23:59
Mariusz: Możesz rozkładać na sumę ułamków prostych a możesz zauważyć że (x2+1)−(x−1)2=2x (x2+1)−(x−1)(x+1)=2 a zatem
3 3 

(x2+1)−

(x−1)(x−1)=3x
2 2 
1 1 

(x2+1)−

(x−1)(x+1)=1
2 2 
 1 
3x+1=2(x2+1)−

(x−1)(3x−3+x+1)
 2 
 1 
3x+1=2(x2+1)−

(x−1)(4x−2)
 2 
3x+1=2(x2+1)−(x−1)(2x−1) Może z tematami dotyczącymi całek przejdźmy do wątku https://matematykaszkolna.pl/forum/406673.html Tematy dotyczące programowania też chcesz kontynuować w innym wątku ? bo wynikałoby to z wpisu z 14 sty 2021 22:35 Obejrzałeś tę listę co podesłałem ?
15 sty 00:15
Filip: Tak, jak widziałeś już tam powróciłem Kod widziałem, widzę że umiesz C++ na przyjemnym poziomie, sam kiedyś sporo siedziałem w C++, jednak już trochę zapomniałem, w sumie mogę "przetłumaczyć" twój kod w C++ na kod w C Wstawianie elementu przed wybranym elementem, zakładam, że jako argument funkcji podajemy naszą listę oraz numer elementu (indeksujemy od 0, czy 1 elementy?) Przykładowo A B C D <− lista wstaw(lista, 1, P) P A B C D czy A P B C D − zależy od indeksowania Jak widzę, będą tutaj trzy przypadki − skoro wstawiamy przed jakiś element, na sam tył listy nie możemy wsadzić Czy zakładamy że w liście jest już co najmniej jeden element? Jeśli tak, to trzeba tylko dwa przypadki rozważyć (1) Gdy wstawiamy przed pierwszy element (2) Gdy wstawiamy w dowolnym miejscu (poza pierwszym elementem) No i gdybyśmy nie wiedzieli jakiej wielkości jest nasza lista, trzeba dodać jeszcze sprawdzenie if (list == NULL) To w sumie skoro nie ma elementów, to nie można wstawić przed element, więc można to na początku funkcji wstaw() umieścić (tego if'a) Tak bym to widział, daj znać czy jest to poprawne rozumowanie
15 sty 01:22
Mariusz: A to ty indeksujesz listę ? Ja myślałem że będziesz wyszukiwał węzeł o podanym kluczu i wstawiał węzeł przed tym znalezionym Gdy rozważysz trzy przypadki to wtedy ciało naszej funkcji będzie można wykorzystać do napisania funkcji wstawiającej do listy w sposób uporządkowany Jak patrzyłeś w kod C# to tam mam też funkcję wstawiającą w sposób uporządkowany ale przepisaną z listy jednokierunkowej dlatego zawiera jeden dodatkowy wskaźnik (do wersji dla listy jednokierunkowej dopisałem ustawianie wskaźników na poprzedników)
15 sty 09:12
Mariusz: A co do naszej strukturki wielomianów to kiedyś pisałem program wyznaczający wielomian interpolacyjny Lagrange https://pastebin.com/4x1GgTUT
15 sty 09:21
Filip: Indeksowanie, nie wiem jak to nazwać, chodziło mi o to, że jak mam listę A B C D to A jest na pierwszym miejsce tej listy (od lewej) B na drugim itd W sensie chodzi o to, że mamy listę A B C D A − klucz 1 B − klucz 2 . . Xi − klucz i−ty Czy chodzi o to, że załóżmy mamy strukturę taką (od ciebie wezmę na kod C) struct Link { int data; struct Link* next; struct Link* prev; } Wywołujemy funkcję wstaw(list, a, 3); gdzie: list − nasza lista a − obiekt klasy Link 3 − klucz To szukamy pierwszego elementu dla ktorego l−>data == 3 czy liczymy elementy i wstawiamy przed trzecim?
15 sty 12:16
Mariusz: Chodzi o to że funkcja wstawiająca mogłaby mieć taki nagłówek template<class T> void DoublyLinkedList::insertBefore(T key,T data); Teraz funkcja template<class T> Link<T> *DoublyLinkedList::find(T key); zwraca wskaźnik na węzeł przed którym należy wstawić nowy węzeł i wg mnie dobrze by było rozpatrzeć trzy przypadki 1) gdy funkcja wyszukująca zwróci NULL 2) gdy funkcja wyszukująca zwróci wskaźnik na głowę 3) gdy funkcja wyszukująca zwróci inny wskaźnik
15 sty 13:52
Mariusz: Ej bawiłeś się wskaźnikiem void * ? W C++ mamy szablony Jeśli tutaj chciałbyś coś podobnego zrealizować to trzeba by było się tymi wskaźnikami (void *) pobawić
15 sty 13:57
Filip: Dokładnie te 3 przypadki bym rozpatrzył, odnośnie tych przypadków: (1) Gdy lista jest pusta to po prostu zwracamy jakąś notkę, że lista jest pusta (2) Jeżeli chcemy insertować na pierwsze miejsce listy. to by to mniej więcej tak wyglądało? Załóżmy że ten element to obiekt listy o nazwie el head−>prev = el−>next; el−>prev = NULL; el−>next = head; (3) Tutaj by trzebabyło wyszukać, w które miejsce wstawić − przykładowo przejść po liście z jakims licznikiem: struct list* l = head; int counter = 0; while (counter != place − 1) { l = l−>next; counter++; } l−>prev = el; el−>next = l l = l−>prev; l−>next = el; el−>prev = l; Ja bym to mniej więcej tak widział, oczywiście możesz potwierdzić czy idzie to w dobrą stronę Bawiłem się jedynie z const void* podczas pisania funkcji porównawczej do sortowania, W C++ szablony to bardzo przydatna rzecz, nawet nie wiedziałem że void* w C może odpowiadać szabloną z C++
15 sty 15:38
Mariusz: Ja to widzę tak jak to napisałem 15 sty 2021 13:52 Wyszukujemy węzeł o podanym kluczu , funkcja wyszukująca zwróci nam wskaźnik na znaleziony węzeł Jeśli zwróci NULL to lepiej chyba wstawić na koniec bo wtedy będziemy mogli wykorzystać tę funkcję do wstawiania w sposób uporządkowany (wstawiamy przed NULLem) Wprowadzanie liczników ogranicza liczbę węzłów − znowu liczby całkowite w programowaniu to nie to samo co liczby całkowite w matematyce Lista bez licznika jest ograniczona tylko ilością dostępnej pamięci Lista z licznikiem jest ograniczona także zakresem typu int
15 sty 16:13
Filip: Zapomniałem o tej funkcji find() w momencie pisania, właśnie patrzę na jej kod w twoim kodzie z C++, w takim razie z tego idzie wywnioskować, że klucz to jest po prostu value, to można z tego licznika zrezygnować
15 sty 16:30
Mariusz: Tak właśnie węzeł przed którym można nowy węzeł wstawić można wyszukać wcześniej napisaną funkcją wyszukującą węzeł o danym kluczu
15 sty 17:57
Filip: No to mi się wydaje, że schemat postępowania będzie taki: (1) Jeżeli find() zwróci wartość NULL (1.1) Jeżeli lista główna nie posiada elementów (1.1.1) zwróć odpowiedni komunitak (1.2) Inaczej dodaj element na koniec listy (1.2.1) wyjdz z funkcji (2) Jeżeli insertujemy na początek listy head−>next−>prev = el el−>next = head−>next el−>prev = NULL no i (3) warunek, zobacze jakby to w kodzie w C wyglądało i podeśle jak coś zlepie
15 sty 18:14
Filip: W kodzie zapisałbym to tak: (1) funkcja zwracająca wskaźnik na konkretny węzeł struct list* find(struct list* l, int key) { struct list* temp = l; while (temp != NULL && temp−>value != key) { temp = temp−>next; } return temp; } (2) funkcja wstawiająca nowy węzeł przed podanym kluczem void insertAt(struct list *l, int key, struct list* el) { struct list* b = find(key); struct list* temp = l; if (key == NULL) { if (temp == NULL) return; while (temp−>next != NULL) temp = temp−>next; temp−>next = el; el−>prev = temp; el−>next = NULL; } else if (temp == b) { temp−>prev = el; el−>next = temp; el−>prev = NULL; } else { while (temp != b) temp = temp−>next; temp−>prev−>next = el; temp−>prev = el; el−>prev = temp−>prev; el−>next = temp; } } Ja bym to tak widział
15 sty 20:09
Mariusz: struct List { struct Node *head; struct Node *tail; }; struct Node { int data; struct Node *prev; struct Node *next; }; struct Node *find(struct List L,int key) { struct Node *temp = L.head; while(temp != NULL && temp−>data != key) temp = temp−>next; return temp; } void insertBefore(struct List *L,int key int d) { struct Node *newNode = (struct Node *)malloc(sizeof(struct Node )); newNode−>data = d; struct Node *temp = find(*L,key); if(temp == NULL) { newNode−>next = NULL; if(L−>head == NULL) L−>head = newNode; else L−>tail−>next = newNode; newNode−>prev = L−>tail; L−>tail = newNode; } else if(temp−>prev == NULL) { newNode−>prev = NULL; if(L−>head == NULL) L−>tail = newNode; else L−>head−>prev = newNode; newNode−>next = L−>head; L−>head = newNode; } else { temp−>prev−>next = newNode; newNode−>next = temp; newNode−>prev = temp−>prev; temp−>prev = newNode; } } No ja tak to widzę
15 sty 21:02
Filip: Mój kod ma trochę błędów, postaram się poprawić, pytani − po co rozbijać to na strukturę List oraz Node? Tak trzeba czy to jakaś prywatna preferencja?
15 sty 21:12
Mariusz: Każda lista dwukierunkowa reprezentowana jest przez dwa wskaźniki − na głowę i na ogon i ja po prostu opakowałem te wskaźniki w strukturę Wskaźnik na ogon przydaje się do wstawiania na koniec i do wstecznej iteracji
15 sty 21:26
Filip: Ok, czyli jakby to w jedną strukturę zapakować to by wyglądała tak? struct List { int data; struct List* next; struct List* prev; struct List* head; struct List* tail; }
15 sty 21:39
Mariusz: Nie jestem przekonany do takiego rozwiązania bo tak to każdy węzeł miałby pole head i tail Przyjrzyj się wersji z C++ albo C# tam też masz oddzielnie klasę dla listy i klasę dla węzła Choć z drugiej strony w C++ można było zagnieździć klasę węzła w klasie listy tylko nie jestem pewny jak to będzie wtedy z szablonami gdy zagnieździmy klasę węzła w klasie listy Sam jestem ciekawy czy ten pomysł będzie dobry
15 sty 21:49
Mariusz: Gdybyśmy chcieli to napisać w jednej strukturce to może w ten sposób ? struct List { struct Node { int data; struct Node *next; struct Node *prev; }; struct Node *head; struct Node *tail; };
15 sty 21:57
Filip: hmm to chyba już rozumiem, list−>head wskazuje na pierwszy Node, a list−>tail na ostatni, czyli przykładowo jak zrobie: struct List* l = head; I moge teraz zrobić l−>data, l−>next oraz l−>prev Właśnie do końca nie wiem jak działa zagnieżdżanie w sobie struktur
15 sty 22:09
Filip: Tak właściwie to nie zagnieżdżanie struktury, tylko taki przykład jak podałeś nazywa się po angielsku: "embedded structure" − nie wiem jak to na język polski przetłumaczyć
15 sty 22:12
Filip: Jednak chyba aby odwołać się do węzła to w taki sposób struct List* l; l−>Node−>value
15 sty 22:17
Filip: Nie, takie odwołanie nie wchodzi w gre − w takim razie jak się odwołać do takiej struktury?
15 sty 22:26
Filip: Jednak się da, trzeba troche przerobić struktury struct List { struct Node { int data; struct Node *next; struct Node *prev; }* Node; struct Node *head; struct Node *tail; }; I teraz: struct List* l = malloc(sizeof(*l)); l−>Node = malloc(sizeof(l−>Node)); I teraz można się odnosić: l−>Node−>data = 5; l−>node−>prev = NULL; l−>node−>next = NULL;
15 sty 22:33
Mariusz: Na razie masz tyle Funkcję main sobie dopisz i przetestuj te funkcje które masz #include<stdio.h> #include<stdlib.h> struct List { struct Node { int data; struct Node *prev; struct Node *next; }; struct Node *head; struct Node *tail; }; void Init(struct List *L) { L−>head = NULL; L−>tail = NULL; } int IsEmpty(struct List L) { return (L.head == NULL); } void DisplayForward(struct List L) { struct Node *temp = L.head; printf("Lista : (pierwszy −−> ostatni) "); while(temp != NULL) { printf("%d ",temp−>data); temp = temp−>next; } printf("\n"); } void DisplayBackward(struct List L) { struct Node *temp = L.tail; printf("Lista : (ostatni −−> pierwszy) "); while(temp != NULL) { printf("%d ",temp−>data); temp = temp−>prev; } printf("\n"); } void Push(struct List *L,int d) { struct Node *newNode = (struct Node *)malloc(sizeof(struct Node )); newNode−>data = d; newNode−>prev = NULL; if(IsEmpty(*L)) L−>tail = newNode; else L−>head−>prev = newNode; newNode−>next = L−>head; L−>head = newNode; } void Append(struct List *L,int d) { struct Node *newNode = (struct Node *)malloc(sizeof(struct Node )); newNode−>data = d; newNode−>next = NULL; if(IsEmpty(*L)) L−>head = newNode; else L−>tail−>next = newNode; newNode−>prev = L−>tail; L−>tail = newNode; } void Pop(struct List *L) { if(IsEmpty(*L)) return; struct Node * temp = L−>head; if(L−>head−>next == NULL) L−>tail == NULL; else L−>head−>next−>prev = NULL; L−>head = L−>head−>next; free(temp); } struct Node *Find(struct List L,int key) { struct Node *temp = L.head; while(temp != NULL && temp−>data != key) temp = temp−>next; return temp; } int main() { struct List L; return 0; }
15 sty 23:02
Mariusz: No to może przepisz sobie te funkcje z mojego kodu w C++ na C po swojemu a jak nie będzie działać to pomyślimy co jest nie tak
15 sty 23:08
Filip: Ok, tylko chce zrozumieć idee head i tail: Mamy listę A B C D E head wskazuje na A tail na element E
15 sty 23:27
Filip: Może zamiast robić zagnieżdżanie, trzymajmy się tego zapisu: struct List { struct Node *head; struct Node *tail; }; struct Node { int data; struct Node *prev; struct Node *next; };
15 sty 23:33
Mariusz: ad 15 sty 2021 23:27 no tak właśnie jest ad 15 sty 2021 23:33 taką reprezentację listy zaproponowałem na samym początku , więc jeśli ją wolisz możemy przy niej zostać
15 sty 23:41
Filip: void insertAt(struct List* l, int key, struct Node* el) { struct Node* temp = find(l, key); if (temp == NULL) { el−>next = NULL; if (l−>head == NULL) { l−>head = el; } else { l−>tail−>next = el; } l−>tail = el; el−>prev = l−>tail; } else if (temp−>prev == NULL) { el−>prev = NULL; if (l−>head == NULL) { l−>tail = el; } else { l−>head−>prev = el; } el−>next = l−>head; l−>head = el; } else { temp−>prev−>next = el; el−>next = temp; el−>prev = temp−>prev; temp−>prev = el; } } Napisałem coś takiego, jak teraz patrzę ten kod prawie się nie różni od twojego powyższego z 15stycznia 21:02
15 sty 23:57
Filip: No i funkcja find() struct Node* find(struct List* l, int key) { struct Node* temp = l−>head; while (temp != NULL && t−>data != key) temp = temp−>next; return temp; } Zapomniałem zmienić nazwy, bo może być myląca "InsertAt", powinno być "insertBefore" tak jak u ciebie
15 sty 23:58
Mariusz: InsertAt to jest dobra nazwa dla listy z licznikiiem
16 sty 00:37
Filip: Jak mamy tak właściwie inserty do listy, no poza instertBack, ale kod do funkcji insertBefore zapewne będzie podobny, to może teraz jakieś usuwanie elementu? Widzę że masz metody deleteKey(), deleteFirst(), deleteSecond()
16 sty 00:51
Mariusz: Takie operacje usuwające tam są deleteKey(), usuwa węzeł o danym kluczu deleteFirst() usuwa pierwszy węzeł deleteLast() usuwa ostatni węzeł
16 sty 00:56
Filip: Racja, pomyliłem się, chodziło oczywiście o deleteLast(). Pytanie: O co chodzi z tymi punktami, które masz w programie?
16 sty 01:04
Mariusz: Masz dany zbiór punktów na tej liście i chcesz narysować wielokąt wypukły o możliwie najmniejszej liczbie boków który zawierałby wszystkie podane punkty
16 sty 01:24
Mariusz: Co do funkcji których nie ma w programie w C++ to jak zrealizowałbyś konkatenację dwóch list ?
16 sty 08:09
Filip: Załóżmy, że listy to a i b To czy wyjściowa to będzie nowa lista c = a + b czy a = a + b?
16 sty 11:57
Mariusz: Niech funkcje enqueue , dequeue oznaczają operacje wstawiania i usuwania z kolejki a concat oznacza operację konkatenacji dwóch list Rozważmy następującą funkcję void function(struct List *L) { struct List A; struct List B; struct List C; struct Node *temp; struct Node *p; if(L−>head != L−>tail) { A.head = NULL; A.tail = NULL; B.head = NULL; B.tail = NULL; C.head = NULL; C.tail = NULL; p = L−>tail; while(L−>head != NULL) { temp = dequeue(L); if(temp−>data < p−>data) enqueue(A,temp); else if(temp−>data == p−>data) enqueue(B,temp); else enqueue(C,temp); } function(&A); function(&C); concat(L,A); concat(L,B); concat(L,C); } } Co ta funkcja powinna robić ? Jeśli chodzi o konkatenację to myślałem aby ją tak napisać aby można było jej użyć w wygodny sposób w powyższej funkcji
16 sty 12:48
Filip: W funkcji concat(a, b) Na pierwszą myśl przychodzi rozpatrzenie warunku, co jeśli a lub b jest jest puste if (b == NULL) return; If (a == NULL) { a−>head = b−>head; a−>tail = b−>tail; } Tak bym to na początku widział, czyli jeśli lista która chcemy "doczepić" jest pusta, nic nie robimy, jeśli lista do której chcemy doczepić jest pusta, ustawiamy jej head i tail na początek i koniec listy b
16 sty 12:59
Filip: A no i można jeszcze w drugim ifie dodać b−>head = NULL; b−>tail = NULL; czy tak?
16 sty 13:02
Mariusz: Jeśli jedna z list jest pusta to konkatenacja zwraca tę drugą No a teraz rozpatrz pozostałe przypadki Wspomniałem o konkatenacji bo można by jej użyć do napisania funkcji którą napisałem 16 sty 2021 12:48
16 sty 15:10
Filip: Czy ta funkcja function() to jest funkcja sortująca listę, z wyborem ostatniego elementu w danej liście, który służy za pivot?
16 sty 15:21
Filip: Przykładowo dla listy wejściowej 12 34 4 5 6 121 3 20 pivotem bedzie 20 Do listy A idą elementy mniejsze niż 20 Do listy B ida elementy równe 20 Do listy C idą elementy większe niż 20 Przed wywołaniem rekurencyjnym będzie to wyglądać tak: Lista A 12 4 5 6 3 Lista B NULL Lista C 34 121 No i po wywołaniu rekurencyjnym dajmy na to dla listy A 4 − pivot Lista A 3 Lista B NULL Lista C 12 4 5 6
16 sty 15:24
Mariusz: Tak to o to chodziło z tym że w twoim przykładzie na liście B będzie jeden element ten z kluczem równym 20 A to po wywołaniu rekurencyjnym dla listy A pivotem nie będzie 3 wtedy Lista A NULL Lista B 3 Lista C 12 4 5 6 A co z konkatenacją i operacjami na kolejce ?
16 sty 16:02
Filip: dequeue() − ściąga nam pierwszy element z naszej kolejki, przykładowo, mamy taką kolejkę Q = A B C D E Q−>head = A Q−>tail = E czyli po wywołaniu funkcji dequeue(Q) dostaniemy nasz element, który zdejmujemy − czyli A, a kolejka wygląda tak: Q = B C D E Q−>head = B Q−>tail = E W kodzie może to wyglądać tak: struct Node* n = Q−>head; Q−>head = n−>next; n−>next−>prev = NULL; return n;
16 sty 16:20
Filip: A no i czy nie powinnismy w funkcji zwalniać pamięci elementu, którego bierzemy?
16 sty 16:22
Mariusz: Jeśli używamy operacji na kolejce w funkcji sortującej listę to nie a jeśli chcesz użyć tych funkcji aby utworzyć kolejkę to powinieneś zwalniać pamięć
16 sty 16:56
Filip: Funkcja enqueue będzie wyglądać podobnie, tyle że będziemy dodawać element na koniec: struct Node* n = Q−>tail n−>next = el el−>prev = n; el−>next = NULL Q−>tail = el Pytanie, co jeśli mi wywołamy funkcję enqueue() / dequeue() i okaże się, że: if (Q−>tail == NULL && Q−>head == NULL) wejdzie nam w takiego ifa Wydaje mi się, że to trzeba sprawidzć, chociaż po kodzie widzę, że za pierwszym razem nam w tego ifa wejdzie − wtedy rozważamy taki przypadek: if (Q−>tail == NULL && Q−>head == NULL) { temp−>prev = NULL; temp−>next = NULL; Q−>tail = temp; Q−>head = temp } Czy dobrze to rozumiem? Czyli pozostaje do napisania funkcja concat()
16 sty 17:40
Mariusz: A to funkcje do obsługi kolejki nie powinny wyglądać jakoś podobnie do tych insertLast() oraz DeleteFirst() w kodzie który napisałem w C++ https://ideone.com/nubXls No co z konkatenacją ? Jak proponujesz ją zrealizować ?
16 sty 18:16
Mariusz: Funkcje equeue() oraz dequeue() napisane tak aby można ich było użyć w funkcji sortującej void enqueue(struct List *L,struct Node *x) { x−>next = NULL; if(L−>head == NULL) L−>head = x; else L−>tail−>next = x; x−>prev = L−>tail; L−>tail = x; } struct Node * dequeue(struct List *L) { if(L−>head == NULL) return NULL; struct Node *temp = L−>head; if(L−>head−>next == NULL) L−>tail = NULL; else L−>head−>next−>prev = NULL; L−>head = L−>head−>next; return temp; }
16 sty 18:44
Filip: void concat(struct* List a, struct* List b) { if (b−>head == NULL) return; if (a−>head == NULL) { a−>head = b−>head; a−>tail = b−>tail; b−>head = NULL; b−>tail = NULL; return; } struct Node* last = a−>tail; struct Node* first = b−>head; last−>next = first; first−>prev = last; a−>tail = b−>tail; b−>head = NULL; b−>tail = NULL; } Tak?
16 sty 18:47
Mariusz: Trochę pobawiłem się twoim kodem i wygląda ok
16 sty 20:18
Mariusz: No może poza błędnym położeniem asteriska na liście parametrów funkcji
16 sty 20:25
Filip: Racja, tam jest błąd
16 sty 21:14
Filip: Mariusz zajrzysz do wątku z całkami? Obliczyłem tam kolejne dwie, jeszcze z 4 przykłady zostały z metody Ostrogradskiego i można przejść do podstawienia Eulera
16 sty 21:31
Filip: Jak masz jeszcze jakieś ciekawe zagadnienia z programowania, które można omówić to podrzucaj emotka (o ile poprzednie uważasz za zakończone)
16 sty 22:19
Mariusz: A pozostałe funkcje do obsługi listy dasz radę napisać ?
16 sty 22:23
Filip: Napisać to napiszę, gorzej u mnie z testowaniem, możemy umówić się tak, że zrobię spis na podstawie tego co mam i na podstawie twojego kodu, których metod mi jeszcze brakuje i postaram się je napisać po kolei, i tutaj wklejać do ewentualnej weryfikacji
16 sty 22:41
Filip: No i oczywiście (na marginesie) całki konttynuujemy
16 sty 22:48
Filip: Zostało mi do napisania te metody, zdaje mi się, że to wszystkie: Link<T> *getFirst(); void setFirst(Link<T> *first); Link<T> *getLast(); void setLast(Link<T> *first); bool isEmpty(); Link<T> *find(T key); void insertFirst(T dd); void insertLast(T dd); void deleteFirst(); void deleteLast(); bool insertAfter(T key,T dd); void deleteKey(T key);
17 sty 16:47
Mariusz: Z getterów i setterów możesz zrezygnować Przeglądanie listy już masz ?
18 sty 02:31
Filip: W sensie wypisywanie elementów od przodu jak i od tyłu?
18 sty 12:19
Mariusz: tak
18 sty 15:45
Filip: Zorientowałem się, że nie mam nawet dodawania elementu na koniec list Wypisywanie elementy od przodu zrealizowałbym tak: void print(struct List* l) { struct Node* n = l−>head; while (n != NULL) { printf("%d ", n−>data); n = n−>next; } } A od tyłu to tak: void print(struct List* l) { struct Node* n = l−>tail; while (n != NULL) { printf("%d ", n−>data); n = n−>prev; } }
18 sty 16:06
Filip: A, no i inna nazwa metody, przykładowo printBackwards
18 sty 16:09
Filip: dodawanie do listy (na koniec) zrealizowałbym tak: void addElement(struct List* l, struct Node* n) { if (l−>head == NULL) { //pusta lista l−>head = n; l−>tail = n; } else { struct Node* temp = l−>tail; temp−>next = n; l−>tail = n; n−>prev = temp; } }
18 sty 16:28
Mariusz: No tak do tego utworzenie węzła
18 sty 19:51
Filip: Hmm racja,, powinienem sprawdzać warunek, gdy n == NULL, albo trochę zmodyfikować funkcję void addElement(struct List* l, int data) { struct Node* n = malloc(sizeof(*n)); n−>data = data; n−>next = NULL; n−>prev = NULL; if (l−>head == NULL) { //pusta lista l−>head = n; l−>tail = n; } else { struct Node* temp = l−>tail; temp−>next = n; l−>tail = n; n−>prev = temp; } }
18 sty 20:16
Filip: Mariusz troche odbiegając od tematy, załóżmy że mam taki wzór rekurencyjny T0=0 T1=1 Tn(x)=2xTn−1(x)−Tn−2(x) Napisałem funkcję, która przyjmuje x − argument jakiejś funkcji, oraz n − wielomian n−tej pozycji że tak to nazwę double U0(double x){ return 1; } double U1(double x){ return x; } double Un(double x, int n){ if(n==0){ return U0(x); } else if(n==1){ return U1(x); } else{ return 2*x*Un(x,n−1)−Un(x,n−2); } } Wygląda ona tak, przykładowo dla x =1 i dla n = 1 zwróci mi ona wartośc 1 Masz jakiś pomysł, aby liczyło mi 1, 2, oraz 3 pochodną z n−tego wzoru? Przykładowo dla x = 1, n = 5, aby liczyło mi: (T5)'(x)= (T5)''(x)= (T5)'''(x)=
19 sty 14:07
Filip: Może da się znaleźć wzór rekurencyjny na pochodne?
19 sty 14:10
Filip: T1=x*
19 sty 14:10
Filip: Znalazłem wzór tutaj: https://www.degruyter.com/view/journals/math/15/1/article-p1156.xml Dla wielomianów pierwszego rodzaju, wiesz może jak to zaimplementować?
19 sty 14:17
Mariusz: T0=0 T1=1 Tn(x)=2xTn−1(x)−Tn−2(x) G(x,t)=∑n=0Tn(x) ∑n=2Tn(x)tn=∑n=2(2xTn−1(x)tn)−∑n=2Tn−2(x)tnn=2Tn(x)tn=2xt(∑n=2(Tn−1(x)tn−1))−t2(∑n=2Tn−2(x)tn−2) ∑n=2Tn(x)tn=2xt(∑n=1(Tn(x)tn))−t2(∑n=0Tn(x)tn) ∑n=0Tn(x)tn−0−t=2xt(∑n=0(Tn(x)tn)−0)−t2(∑n=0Tn(x)tn) G(x,t)−t=2xtG(x,t)−t2G(x,t) G(x,t)(1−2xt+t2)=t
 t 
G(x,t)=

 1−2xt+t2 
t t 

=

1−2xt+t2 (1−xt)2−(x2−1)t2 
t t 

=

1−2xt+t2 (1−(x−x2−1)t)(1−(x+x2−1)t) 
t A B 

=

+

1−2xt+t2 1−(x−x2−1)t 1−(x+x2−1)t 
A−A(x+x2−1)t+B−B(x−x2−1)t=t A+B=0 A(x+x2−1)+B(x−x2−1)=−1 B=−A A(x+x2−1)+B(x−x2−1)=−1 A(x+x2−1)−A(x−x2−1)=−1 A(2x2−1)=−1
 1 
A=−

 2x2−1 
 1 
B=

 2x2−1 
G(x,t)=
 1 1 

(∑n=0(x−x2−1)ntn)+

n=0((x+x2−1)tn)
 2x2−1 2x2−1 
 1 1 
G(x,t)=∑n=0(−

(x−x2−1)n+

(x+x2−1)n)tn
 2x2−1 2x2−1 
 1 1 
Tn(x)=−

(x−x2−1)n+

(x+x2−1)n
 2x2−1 2x2−1 
Może z tej postaci łatwiej będzie policzyć pochodną
19 sty 15:19
Mariusz: Dla wielomianów pierwszego rodzaju masz tę sam wzór rekurencyjny ale inne warunki początkowe Zdaje się że T0=1 T1=x
19 sty 15:24
Filip: Hmm, kurcze ty założyłeś, że T1=1, jednak to pózniej poprawiłem, że T1=x, czy to zmieni ten wzór rekurencyjny i wynik finalny?
19 sty 15:26
Filip: No tak, z tego mogę obliczyć pierwszą pochodną n−tego wielomianu, a da się znaleźć wzór na m−tą pochodną n−tego wielomianu?
19 sty 15:32
Filip: Nie wiem czy patrzyłeś w link co ci podesłałem, jest tam wzór, ale skomplikowany, może da go się jakoś uprościć, aby dało się zaimplementować
19 sty 15:36
Mariusz: Ten wzór co ty podałeś jest dobry dla wielomianów drugiego rodzaju Ja podałem warunki początkowe dla wielomianów pierwszego rodzaju bo wzór rekurencyjny jest ten sam dla obydwu Patrzyłem na wzór z wpisu 19 sty 2021 14:07 Nie uwzględniłem twojej poprawki
19 sty 15:38
Mariusz: Próbowałeś użyć naszej strukturki i napisać funkcję rekurencyjną która zwracałaby n. ty wielomian Czebyszowa
19 sty 15:45
Filip: No właśnie z tym miałem problem, dlatego od razu stwierdziłem że będę liczyć wartość dla n−tego wielomianu
19 sty 16:01
Filip: Hmm no tak, mamy strukturę przecież, czyli w takim razie jakby to wyglądało: tworzy sobie tablicę kolejnych wielomianów: T0=0 T1=1 I po prostu robimy na początku mnożenie t[n]=2x*Tn−1(x) + Tn−2(x) Hmm, mamy tablicę obiektów struct Polynomial t[10000]; struct Polynomial p; p.deg = 1 p.coeff[1]=2; p.coeff[0]=0 t[0]=1; t[1]=x; t[n]= multiplyPolynomials(p, t[n−1]) t[n]=addPolynomials(t[n], t[n−2]); Tak by to mniej więcej wyglądało?
19 sty 16:07
Filip: a te wielomiany trzeba stworzyć Zapomniałem o mallocach() i oczywiscie o stworzeniu wielomianow 1 oraz x, ale mniej wiecej mam nadzieje ze przekazałem ci patent jak to ma wygladac
19 sty 16:09
Filip: W sensie jakbym to w kodzie napisał
19 sty 16:09
Mariusz: Jak chcesz skorzystać z ich wyników to musiałbyś kilka funkcyj pomocniczych napisać takich jak np dolna silnia czy symbol Newtona no i funkcję która działałałaby na naszej strukturce i zwracałaby wielomian Czebyszowa Ty masz t[n]=2x*Tn−1(x) + Tn−2(x) Powinno być t[n]=2x*Tn−1(x) − Tn−2(x); Dopisz do naszej strukturki schemat Hornera
19 sty 16:39
Filip: Dlaczego to co napisałem by nie zadziałało bez tych dodatkowych funkcji? Po co schemat Hornera bo nie widzę?
19 sty 16:41
Mariusz: Napisałem że gdybyś chciał skorzystać z ich wyników to byś musiał dopisać te dodatkowe funkcję Gdybyś chciał pisać po swojemu to nie musisz ich pisać Napisałeś że chciałeś policzyć wartość wielomianu − do tego przyda się schemat Hornera
19 sty 16:56
Mariusz: A i zastanów się czy potrzebujesz całej tablicy tych wielomianów czy może wystarczy ich mniej W każdej iteracji tworzysz wielomian k+1. stopnia i potrzebujesz do tego dwóch poprzednich wielomianów nie musisz pamiętać wszytkich chyba że z założenia chcesz pamiętać wszytkie
19 sty 17:01
Filip: Chce pamiętać wszystkie, bo dla n=10, mam 11 wielomianów i od każdego z nich liczę wartość 1 i 2 i 3 pochodnej dla jakiegoś x
19 sty 17:03
Filip: Zaraz mam kolokwium z fizyki, wrócę tutaj po kolokwium i postaram się coś popisać w kodzie
19 sty 17:03
Filip: Napisałem taki kodzik, generalnie działa i wyświetla mi n kolejnych wielomianów Czebyszewa int n = 20; struct Polynomial* p = malloc(sizeof(*p)); p−>deg=1; p−>coeff=malloc((p−>deg+1)*sizeof(double)); p−>coeff[0]=0; p−>coeff[1]=2; struct Polynomial* c[100]; c[0]=malloc(sizeof(struct Polynomial)); c[0]−>deg=0; c[0]−>coeff = malloc(sizeof(double)); c[0]−>coeff[0]=1; c[1]=malloc(sizeof(struct Polynomial)); c[1]−>deg=1; c[1]−>coeff = malloc(2*sizeof(double)); c[1]−>coeff[0]=0; c[1]−>coeff[1]=1; for (int i = 2; i < n; i++) { c[i]=malloc(sizeof(*c[i])); c[i]=multiplyPolynomials(p, c[i−1]); c[i]=substractPolynomials(c[i], c[i−2]); } for (int i = 0; i < n; i++) { printf("T%d\t", i); printPolynomial(c[i]); printf("\n"); }
19 sty 18:14
Filip: No i teraz została do napisania funkcja która przykładowo taki szablon będzie mieć struct Polynomial* ddx(struct Polynomial* p, int i) gdzie i to i−ta pochodna
19 sty 18:17
Filip: Przykładowy output dla n=10 T0 +1.000000x0 T1 +1.000000x1 T2 +2.000000x2 −1.000000x0 T3 +4.000000x3 −3.000000x1 T4 +8.000000x4 −8.000000x2 +1.000000x0 T5 +16.000000x5 −20.000000x3 +5.000000x1 T6 +32.000000x6 −48.000000x4 +18.000000x2 −1.000000x0 T7 +64.000000x7 −112.000000x5 +56.000000x3 −7.000000x1 T8 +128.000000x8 −256.000000x6 +160.000000x4 −32.000000x2 +1.000000x0 T9 +256.000000x9 −576.000000x7 +432.000000x5 −120.000000x3 +9.000000x1
19 sty 18:19
Mariusz: Dla i = 0 zwracasz wielomian p Następnie starasz się zbudować rekurencję wiedząc że Pierwsza pochodna to dp−>deg = p−>deg − 1; dp−>coeff = malloc((dp−>deg+1)*malloc(*dp−>coeff)); for(int k = 0;k <= dp−>deg; k++) dp−>coeff[k] = (k+1)*p−>coeff[k+1]; oraz z tego że n. tą pochodną da się zapisać rekurencyjnie
19 sty 19:18
Mariusz: Zastanawiałeś się nad podzieleniem tego programiku do obsługi wielomianów na plik nagłówkowy (*.h) oraz na plik (*c)
19 sty 19:21
Filip: Tak, generalnie program w którym użyje tej struktury wielomianów składa się z kilku c i h, więc tego też przerobie na potrzebne mi funkcje
19 sty 19:54
Filip: Musze przenalizowac twój kod do pochodnej, troche inaczej go pisałem, ale ja uwzględniałem tylko pierwszego stopnia pochodną
19 sty 19:57
Mariusz: To też jest tylko pierwsza pochodna Jeśli na podstawie tego co napisałem napiszesz funkcję rekurencyjną to otrzymasz n. pochodną wielomianu
19 sty 20:43
Filip: Hmm, to potestuje to w kodzie i dam znać czy udało mi się napisać
20 sty 00:41
Mariusz: Widziałeś ten wzór jawny na wielomiany Czebyszowa ? Tutaj miałeś dwa warianty pierwszego podstawienia
20 sty 04:28
Filip: Hmm, jak ciekawie tutaj rekurencje zrobić struct Polynomial* ddx(struct Polynomial* p) { if (p−>deg==0) return p; struct Polynomial* dp=malloc(sizeof(*p)); dp−>deg=p−>deg−1; dp−>coeff=malloc(sizeof(dp−>deg+1)*sizeof(*dp−>coeff)); for (int i = 0; i < dp−>deg+1; i++) { dp−>coeff[i]=(i+1)*p−>coeff[i+1]; } ddx(dp); }
20 sty 18:03
Filip: nie wiem czy to będzie poprawne ze względu na malloci() w kolejnych wywołaniach rekurencyjnych
20 sty 18:03
Mariusz: Ja myślałem o czymś takim struct Polynomial* ddx(struct Polynomial* p, int k) { if(k == 0) return p; // Tutaj przypadek gdy k > 0 } Spróbuje się tym pobawić i przetestować Ty też możesz się tym pobawić
20 sty 18:21
Filip: racja, zapomniałem o tym współczynniku, wtedy wywołanie rekurencyjne by wygladało tak: (dp, n−1);
20 sty 18:23
Filip: właśnie idę, może spróbuje bez dodatkowe alokacji
20 sty 18:23
Filip: struct Polynomial* ddx(struct Polynomial* p, int n) { if (n==0) return p; p−>deg−=1; struct Polynomial* temp=malloc(sizeof(*temp)); temp−>deg=p−>deg; temp−>coeff=realloc(p−>coeff,(p−>deg+1)*sizeof(*p−>coeff)); for (int i=0;i<temp−>deg+1;i++) { temp−>coeff[i]=(i+1)*temp−>coeff[i+1]; } ddx(temp,n−1); } Narazie nie wpadłem, aby działał dla pochodnej większego stopnia niż 1, Działa tylko dla n=1 lub n=0
20 sty 19:11
Filip: struct Polynomial* ddx(struct Polynomial* p, int n) { if (n==0) return p; struct Polynomial* temp=malloc(sizeof(*temp)); p−>deg−=1; temp−>deg=p−>deg; temp−>coeff=malloc((p−>deg+1)*sizeof(*p−>coeff)); for (int i=0;i<temp−>deg+1;i++) { temp−>coeff[i]=(i+1)*p−>coeff[i+1]; } ddx(temp,n−1); } Poprawiona funkcja, powinno działać teraz
20 sty 19:25
Filip: Działa tylko dla Tn, gdzie n>=2
20 sty 19:28
Filip: Jednak, dla pochodnej stopnia przykładowo 5 nie działa nawet, więc myślę jak się przed tym zabezpieczyć Może dam ifa, jeśli stopień pochodnej większy od stopnia wielomianu, return 0
20 sty 19:32
Filip: struct Polynomial* ddx(struct Polynomial* p, int n) { if (n==0) return p; struct Polynomial* temp=malloc(sizeof(*temp)); if (n>p−>deg) { temp−>deg=0; temp−>coeff=malloc(sizeof(*temp−>coeff)); temp−>coeff[0]=0; return temp; } p−>deg−=1; temp−>deg=p−>deg; temp−>coeff=malloc((p−>deg+1)*sizeof(*p−>coeff)); for (int i=0;i<temp−>deg+1;i++) { temp−>coeff[i]=(i+1)*p−>coeff[i+1]; } ddx(temp,n−1); } Powinno działać
20 sty 19:35
Mariusz: A może dobrze by było sobie rozpisać jak ta rekurencja miałaby wyglądać, jak będzie wywoływana itp W pseudokodzie to chyba wyglądałoby tak struct Polynomial* ddx(struct Polynomial* p) Dla n == 0 zwracasz p W przeciwnym przypadku Przyjmujesz że funkcja policzyła ci ci już n−1 pochodną i liczysz pierwszą pochodną tego co ci zwróciła a pierwszą pochodną liczysz właśnie tak dp−>deg=p−>deg−1; dp−>coeff=malloc(sizeof(dp−>deg+1)*sizeof(*dp−>coeff)); for (int i = 0; i < dp−>deg+1; i++) { dp−>coeff[i]=(i+1)*p−>coeff[i+1]; } Ty zapisałeś tę rekurencję ogonowo więc gdyby zadziałała to stosunkowo łatwo byłoby ją zamienić na iterację
20 sty 19:36
Mariusz: A to nawet lepiej że przeniosłeś wywołanie rekurencyjna na koniec Łatwiej będzie tą rekurencję wyeliminować choć obecne komipiatory chyba automatycznie to optymalizują
20 sty 20:28
Filip: No dobra to to mam, a teraz jak obliczyć wartość pochodnej dla danego x?
20 sty 22:30
Mariusz: double Horner(struct Polynomial *p,double x) { double v = p−>coeff[0]; for(int i=1;i<= p−>deg;i++) v = v * x +p>coeff[i]; return v; } Może coś takiego Miałeś schemat Hornera na zajęciach ?
20 sty 23:03
Filip: yy miałem w liceum, jednak nie pamiętam go zupełnie (no jedynie że coś się brało współczynniki i to w jakieś tabelce zapisywaliśmy − na tabliczce woskowej), bo z niego ani razu nie skorzystałem
20 sty 23:07
Mariusz: Gdybyś podał jakiś przykład to mógłbym si przypomnieć jak go stosować (Służy do dzielenia wielomianu przez dwumian a reszta z tego dzielenia jest przy okazji wartością wielomianu w punkcie) A temat podstawieniami Eulera będziemy kontynuować ? Jeśli tak to myślę że możemy już do nich przejść chyba że chciałbyś jeszcze przećwiczyć metodę Ostrogradskiego
20 sty 23:48
Filip: właśnie to jc kiedyś pisał tutaj o tym, że przykładowo dla wielomianu ax3+bx2+cx+d nie liczymy w tradycyjny sposób, tylko: x(ax2+bx)+c x(x(ax+b)+c)+d czyli zaczynamy od: ax+b x(ax+b)+c x(x(ax+b)+c)+d Czy w kodzie to wygląda na dobrze zapisane: double result=p−>coeff[0]; for (int i=1;i<p−>deg+1;i++) result=result*x+p−>coeff[i]; return result; No przepisałem twój kod tak właściwie, tylko bez szablonu funkcji
20 sty 23:59
Filip: Tak, Eulera możemy zacząć od piątku
21 sty 00:01
Mariusz: Weźmy jako przykład wielomian Czebyszowa T3 i dwumian x − 1 (4x3−3x):(x−1) Zapisujesz współczynniki wielomianu w tabelce Z boku zapisujesz x0 z dwumianu (x−x0) (Tutaj x0=1) 4 0 −3 0 1 Teraz współczynnik przy x3 przepisujesz 4 0 −3 0 1 4 ^ | Mnożysz 1 przez 4 pokazaną przez tę "strzałkę" i dodajesz współczynnik przy x2 4 0 −3 0 1 4 4 ^ | Mnożysz 1 przez 4 pokazaną przez tę "strzałkę" i dodajesz współczynnik przy x 4 0 −3 0 1 4 4 1 ^ | Mnożysz 1 przez 1 pokazaną przez tę "strzałkę" i dodajesz współczynnik przy wyrazie wolnym 4 0 −3 0 1 4 4 1 1 Teraz odczytujesz wynik trzy pierwsze współczynniki to iloraz 4x2+4x+1 a ostatni to reszta i przy okazji także wartość wielomianu w punkcie x=1 No to teraz sobie to przećwicz Może uda ci się samemu napisać tę funkcję − to tylko jedna pętla
21 sty 00:16
Mariusz: Tutaj chyba będzie lepiej dać wsteczną iterację i zainicjować współczynnikiem wiodącym double Horner(struct Polynomial *p,double x) { double v = p−>coeff[p−>deg]; for(int i=p−>deg−1;i >= 0;i−−) v = v * x +p>coeff[i]; return v; }
21 sty 00:31
Mariusz: Tak ta druga wersja jest dobra
21 sty 00:38
Mariusz: Zasugerowałem się błędnym rozwiązaniem znalezionym w sieci ale jak rozpisałem dla ciebie przykład to już zacząłem podejrzewać że coś jest nie tak Poniższa wersja będzie dobra double Horner(struct Polynomial *p,double x) { double v = p−>coeff[p−>deg]; for(int i=p−>deg−1;i >= 0;i−−) v = v * x +p−>coeff[i]; return v; } Oczwiście moglibyśmy zainicjować zmienną v zerem ale mielibyśmy wtedy jedną interację więcej
21 sty 00:57
Filip: W sumie racja, tak teraz patrze, że jak napisałem przykład to wynika też z tego, że liczymy od największej do najmniejszej potęgi wykładnika
21 sty 14:42
Mariusz: Gdybyś trochę poczytał o schemacie Hornera i odpowiednio go zmodyfikował to okazałoby się że mógłby on zastąpić tę funkcję do liczenia pochodnej
21 sty 18:24
Filip: Aktulanie testuje napisaną aproksymacje funkcji właśnie za pomocą wielomianów Czebyszewa. Masz może pomysł, na jakiś wzór funkcji wyjściowej dla której wylicze punkty z przedziału [a,b] co (a+b)/m, gdzie m − liczba punktów, dla której aproksymacja może się nie powieść, albo będzie bardzo niedokładna?
21 sty 20:01
Mariusz: Ja akurat interpolacją wielomianami Czebyszowa się nie bawiłem Bawiłem się interpolacją Lagrange ale też niezbyt dużo
22 sty 03:45