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

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?

Filip: Blad znaleziony, w funkcji schodkowanie() w 3cim forze(), powinno byc j<m−>c, jednak nadal nie wiem czy dziala poprawnie

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?

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ą

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); }

Mariusz: Ad 8 sty 2021 20:11 Modyfikujesz obydwie macierze

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

Mariusz: Wydaje mi się że mógłbyś iterować bez tego elementu na głównej przekątnej

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?

Filip: Diagonala to może złe określenie − przekątna

Mariusz: Mam wątpliwości czy twój częściowy wybór elementu głównego będzie działał poprawnie

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)

Mariusz: Jak masz tablice jednowymiarową to jak wyszukujesz największy element ?

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: max_so_far=abs(m−>a[k+1][k]); for (int i=k+2;i<m−>r−2;i++) { if (abs(m−>a[i][k])>max_so_far) { max_so_far=abs(m−>a[i][k]); s=1; q=i; } } Jednak ty znalazłeś chyba lepszy sposób z podmianą indeksu? Nie znam takiego

Mariusz: No tak ja zapamiętywałem indeks największego elementu

Mariusz: Podrzuć kod tego co już napisałeś tak abym mógł go przetestować

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

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()?

Mariusz: A jest ona dostępna w C czy to dopiero wynalazek C++ ? Sprawdzę co tam do tej pory masz

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)

Filip: Ja w pełni opuściłem element na głównej przekątnej, ponieważ moim max_so_far jest element a_k+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 max_so_far=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: max_so_far=a_kk i iteracje w pętli for() zaczynam od k+1 Ad. 14:31 Jednak tak, jest to wynalazek C++

Mariusz: Ja poprawiłem już błędy w kodzie schodkowanie powinno już działać https://pastebin.com/index.php

Mariusz: Wsteczne podstawianie możesz napisać w oddzielnej funkcji

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

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

Mariusz: Ach zapomniałem wysłać https://pastebin.com/fRpX9rqr Acha to ok jak ma takie wartości zwracać

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

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)

Filip: int eliminate(struct Matrix* m, struct Matrix* b) { int q,s; double max_so_far; for (int k=0;k<m−>c;k++) { s=0; max_so_far=abs(m−>a[k][k]); for (int i=k+1;i<m−>r;i++) { if (abs(m−>a[i][k])>max_so_far) { max_so_far=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()

Filip: Czy dobrze modyfikuje macierz wyrazów wolnych?

Mariusz: Nie zamieniasz wierszy w tej macierzy Jeśli dopiszesz zamianę wierszy to schodkowanie powinno być ok

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ć?

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

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

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; }

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

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

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]

Filip: Tak, tez teraz przetestowałem na kilkunastu układach równań i wygląda na to, że pierwiastki dobrze oblicza

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

Filip: Hmm, tego chyba nie robiłem nigdy, co to znaczy że by udawała 0, byłaby zerem czy nie do końca?

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

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ć

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
	xn√ax2+bx+c

to najpierw patrzysz czy możesz użyć drugiego podstawienia √ax²+bx+c=xt±√c przy czym znak + lub − możesz sam wybrać Jeśli nie to sprawdzasz czy możesz użyć pierwszego podstawienia √ax²+bx+c=t±√ax a na końcu dopiero sprawdzasz trzecie podstawienie Eulera √ax²+bx+c=(x−x₁)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
	x√x2+4x−4

Pierwsze podstawienie będzie najwygodniejsze w użyciu

	1
∫		dx
	x√x2+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)2√x2−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

Mariusz: A jeszcze jedno co do kodu to tak z ciekawości zapytam czemu nie zwalniasz pamięci

Filip: zapomniałem o zwalnianiu pamięci

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

Filip: na programowaniu w C

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

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: 3x⁵−12x⁴+9x²−0.5x+18 W kodzie: struct Polynomial* p = malloc(sizeof(*p)); p−>deg = 5; p−>coeff = malloc(sizeof(*coeff) + 1) // dodajemy miejsce dla x⁰ 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 xⁱ Jeżeli dobrze zrozumiałem jak to wygląda w kodzie, mogę przejść do pisania kolejnych funkcji

Mariusz : No tak to miałoby wyglądać

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) = x⁴ + 3x² + x − 1 −−−−> deg = 4 Q(x) = x² − 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) = x⁴ + 3x² + x − 1 + x² − 2x + 1 = x⁴ + 4x² − x

Filip: W if() else w warunku pętli for() (w obu przypadkach) zamiast znaku >= powinno być >

Mariusz : Gdzieś segmentation fault dostajesz

Filip: Tak, w pierwszej pętli for() zamiast i++ powinno być i−−, teraz dopiero zauważyłem jak powiedziałeś

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; }

Filip: A, no i w ostatniej pętli for zamiast i++, i−−

Filip: Okej, potestowałem i wygląda na to, że działa poprawnie, z odejmowaniem to po prostu zamieniam operator + na −?

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

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]; } }

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

Filip: ehh, sorry że tak cały czas pisze , 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

Mariusz : Jeśli chodzi o mnożenie to naiwny algorytm ma złożoność O(n²) Mnożenie można przyśpieszyć korzystając z szybkiej transformaty Fouriera

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

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; }

Mariusz : No tak miałem na myśli przypadek dla wielomianów tego samego stopnia bo wtedy będziemy mieli taką złożoność

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

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 x⁵

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źć

Mariusz : Na stronie 175 czyli w polu gdzie masz numery stron wpisz liczbę 199

Mariusz : Schemat Hornera też się może przydać np gdybyśmy chcieli policzyć wartość wielomianu dla jakiejś liczby

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

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

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; }

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

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

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ę

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

jc: Wtrącę się. Mariusz, masz rację, wartość wielomianu liczymy wg wzoru: ax³+bx²+cx+d = ((ax+b)x+c)x+d W przypadku wielomianów przekazujemy wskaźniki (no, chyba że masz wielomiany niskiego, ustalonego stopnia).

Mariusz: jc a ty co byś odpowiedział ba pytanie Filipa zadane we wpisie z 11 sty 2021 22:53

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 (?)

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

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) = x³+x²−3x−3 Q(x)=x²+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?

Mariusz: No mniej więcej tak to mogłoby wyglądać

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

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;

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?

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()

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

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

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; }

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()

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);

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

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ą )

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

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

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

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

Filip: Ten argument ostatni (r) jest niepotrzebny

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; }

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: x⁴−3x³+3x²−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ć

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

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

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

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ć?

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ęć

Mariusz: Tak chodziło mi o to aby tak zmodyfikować funkcję dzielącą aby reszta miała już taki stopień jaki powinna mieć

Mariusz: Dobra teraz będę pisał inny program, za ok 2h wrócę i spróbuję przetestować twój kod

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

Mariusz: Filip , Przetestuj sobie ten kod https://pastebin.com/g8HLnFWr

Mariusz: Wielomiany Czebyszowa , tak średnio używałem ich jedynie do rozwijania cos(nx) jako sumę potęg

Mariusz: Jeszcze ta funkcja licząca NWD nadal nie działa poprawnie

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

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 x⁵−x⁴−2x³+2x²+x−1 5x⁴−4x³−6x²+4x+1

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

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

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

Filip: Można jeszcze ciekawiej zrobić, można generować losowo wielomiany, przy pomocy rand(), a raczej ich stopień oraz współczynniki

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

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 x²−3x+1, x²? 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];

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

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?

Filip: Ja osobiście w ciele funkcji za nimi nie przepadam

Filip: Zmieniłem troche kod do pewnego momentu, tak to wygląda, pozostałe rzeczy narazie pozostają niezmienione: https://pastebin.com/976pniya

Filip: Niestety zepsułem tym funkcję dzielącą wielomiany, zaraz postaram się znaleźć co jest nie tak...

Filip: A nie, u ciebie w kodzie funkcja dzieląca też nie działa poprawnie

Mariusz: 14 sty 2021 18:38 A to już kwestia umowna Jeśli zwiększą czytelność kodu to czemu nie

Mariusz: A co jest nie tak z funkcją dzielącą ?

Filip: Dziele z resztą wielomiany 2x³−5x²+4x−1 i x−1 i reszta wychodzi mi 0, a powinna −x+1

Filip: ...... nie ważne, reszta to 0

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

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

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

Filip: Jednak pierwiastki zbytnio nie wiem jak znaleźć, więc zostaje tylko ta druga funkcja

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

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 Ja chyba tym czasem będę zabierał się za listę dwukierunkową

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

Mariusz: A co z całkami na metodę Ostrogradskiego i podstawienia Eulera ? Będziemy ten temat kontynuować ?

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ć?

Mariusz: Możesz rozkładać na sumę ułamków prostych a możesz zauważyć że (x²+1)−(x−1)²=2x (x²+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(x²+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 ?

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

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)

Mariusz: A co do naszej strukturki wielomianów to kiedyś pisałem program wyznaczający wielomian interpolacyjny Lagrange https://pastebin.com/4x1GgTUT

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 . . X_i − 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?

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

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ć

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++

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

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ć

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

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

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ł

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ę

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?

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

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; }

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

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; };

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

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ć

Filip: Jednak chyba aby odwołać się do węzła to w taki sposób struct List* l; l−>Node−>value

Filip: Nie, takie odwołanie nie wchodzi w gre − w takim razie jak się odwołać do takiej struktury?

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;

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; }

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

Filip: Ok, tylko chce zrozumieć idee head i tail: Mamy listę A B C D E head wskazuje na A tail na element E

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; };

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ć

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

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

Mariusz: InsertAt to jest dobra nazwa dla listy z licznikiiem

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()

Mariusz: Takie operacje usuwające tam są deleteKey(), usuwa węzeł o danym kluczu deleteFirst() usuwa pierwszy węzeł deleteLast() usuwa ostatni węzeł

Filip: Racja, pomyliłem się, chodziło oczywiście o deleteLast(). Pytanie: O co chodzi z tymi punktami, które masz w programie?

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

Mariusz: Co do funkcji których nie ma w programie w C++ to jak zrealizowałbyś konkatenację dwóch list ?

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?

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

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

Filip: A no i można jeszcze w drugim ifie dodać b−>head = NULL; b−>tail = NULL; czy tak?

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

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?

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

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 ?

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;

Filip: A no i czy nie powinnismy w funkcji zwalniać pamięci elementu, którego bierzemy?

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ęć

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()

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ć ?

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; }

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?

Mariusz: Trochę pobawiłem się twoim kodem i wygląda ok

Mariusz: No może poza błędnym położeniem asteriska na liście parametrów funkcji

Filip: Racja, tam jest błąd

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

Filip: Jak masz jeszcze jakieś ciekawe zagadnienia z programowania, które można omówić to podrzucaj (o ile poprzednie uważasz za zakończone)

Mariusz: A pozostałe funkcje do obsługi listy dasz radę napisać ?

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

Filip: No i oczywiście (na marginesie) całki konttynuujemy

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);

Mariusz: Z getterów i setterów możesz zrezygnować Przeglądanie listy już masz ?

Filip: W sensie wypisywanie elementów od przodu jak i od tyłu?

Mariusz: tak

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; } }

Filip: A, no i inna nazwa metody, przykładowo printBackwards

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; } }

Mariusz: No tak do tego utworzenie węzła

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; } }

Filip: Mariusz troche odbiegając od tematy, załóżmy że mam taki wzór rekurencyjny T₀=0 T₁=1 T_n(x)=2xT_n−1(x)−T_n−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: (T₅)'(x)= (T₅)''(x)= (T₅)'''(x)=

Filip: Może da się znaleźć wzór rekurencyjny na pochodne?

Filip: T₁=x*

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ć?

Mariusz: T₀=0 T₁=1 T_n(x)=2xT_n−1(x)−T_n−2(x) G(x,t)=∑_n=0^∞T_n(x) ∑_n=2^∞T_n(x)tⁿ=∑_n=2^∞(2xT_n−1(x)tⁿ)−∑_n=2^∞T_n−2(x)tⁿ ∑_n=2^∞T_n(x)tⁿ=2xt(∑_n=2^∞(T_n−1(x)tⁿ⁻¹))−t²(∑_n=2^∞T_n−2(x)tⁿ⁻²) ∑_n=2^∞T_n(x)tⁿ=2xt(∑_n=1^∞(T_n(x)tⁿ))−t²(∑_n=0^∞T_n(x)tⁿ) ∑_n=0^∞T_n(x)tⁿ−0−t=2xt(∑_n=0^∞(T_n(x)tⁿ)−0)−t²(∑_n=0^∞T_n(x)tⁿ) G(x,t)−t=2xtG(x,t)−t²G(x,t) G(x,t)(1−2xt+t²)=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+√x²−1)t+B−B(x−√x²−1)t=t A+B=0 A(x+√x²−1)+B(x−√x²−1)=−1 B=−A A(x+√x²−1)+B(x−√x²−1)=−1 A(x+√x²−1)−A(x−√x²−1)=−1 A(2√x²−1)=−1

	1
A=−
	2√x2−1

	1
B=
	2√x2−1

G(x,t)=

	1		1
−		(∑n=0∞(x−√x2−1)ntn)+		∑n=0∞((x+√x2−1)tn)
	2√x2−1		2√x2−1

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

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

Może z tej postaci łatwiej będzie policzyć pochodną

Mariusz: Dla wielomianów pierwszego rodzaju masz tę sam wzór rekurencyjny ale inne warunki początkowe Zdaje się że T₀=1 T₁=x

Filip: Hmm, kurcze ty założyłeś, że T₁=1, jednak to pózniej poprawiłem, że T₁=x, czy to zmieni ten wzór rekurencyjny i wynik finalny?

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?

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ć

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

Mariusz: Próbowałeś użyć naszej strukturki i napisać funkcję rekurencyjną która zwracałaby n. ty wielomian Czebyszowa

Filip: No właśnie z tym miałem problem, dlatego od razu stwierdziłem że będę liczyć wartość dla n−tego wielomianu

Filip: Hmm no tak, mamy strukturę przecież, czyli w takim razie jakby to wyglądało: tworzy sobie tablicę kolejnych wielomianów: T₀=0 T₁=1 I po prostu robimy na początku mnożenie t[n]=2x*T_n−1(x) + T_n−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?

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

Filip: W sensie jakbym to w kodzie napisał

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*T_n−1(x) + T_n−2(x) Powinno być t[n]=2x*T_n−1(x) − T_n−2(x); Dopisz do naszej strukturki schemat Hornera

Filip: Dlaczego to co napisałem by nie zadziałało bez tych dodatkowych funkcji? Po co schemat Hornera bo nie widzę?

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

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

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

Filip: Zaraz mam kolokwium z fizyki, wrócę tutaj po kolokwium i postaram się coś popisać w kodzie

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"); }

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

Filip: Przykładowy output dla n=10 T₀ +1.000000x⁰ T₁ +1.000000x¹ T₂ +2.000000x² −1.000000x⁰ T₃ +4.000000x³ −3.000000x¹ T₄ +8.000000x⁴ −8.000000x² +1.000000x⁰ T₅ +16.000000x⁵ −20.000000x³ +5.000000x¹ T₆ +32.000000x⁶ −48.000000x⁴ +18.000000x² −1.000000x⁰ T₇ +64.000000x⁷ −112.000000x⁵ +56.000000x³ −7.000000x¹ T₈ +128.000000x⁸ −256.000000x⁶ +160.000000x⁴ −32.000000x² +1.000000x⁰ T₉ +256.000000x⁹ −576.000000x⁷ +432.000000x⁵ −120.000000x³ +9.000000x¹

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

Mariusz: Zastanawiałeś się nad podzieleniem tego programiku do obsługi wielomianów na plik nagłówkowy (*.h) oraz na plik (*c)

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

Filip: Musze przenalizowac twój kod do pochodnej, troche inaczej go pisałem, ale ja uwzględniałem tylko pierwszego stopnia pochodną

Mariusz: To też jest tylko pierwsza pochodna Jeśli na podstawie tego co napisałem napiszesz funkcję rekurencyjną to otrzymasz n. pochodną wielomianu

Filip: Hmm, to potestuje to w kodzie i dam znać czy udało mi się napisać

Mariusz: Widziałeś ten wzór jawny na wielomiany Czebyszowa ? Tutaj miałeś dwa warianty pierwszego podstawienia

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); }

Filip: nie wiem czy to będzie poprawne ze względu na malloci() w kolejnych wywołaniach rekurencyjnych

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ć

Filip: racja, zapomniałem o tym współczynniku, wtedy wywołanie rekurencyjne by wygladało tak: (dp, n−1);

Filip: właśnie idę, może spróbuje bez dodatkowe alokacji

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

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

Filip: Działa tylko dla T_n, gdzie n>=2

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

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ć

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ę

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ą

Filip: No dobra to to mam, a teraz jak obliczyć wartość pochodnej dla danego x?

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 ?

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

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

Filip: właśnie to jc kiedyś pisał tutaj o tym, że przykładowo dla wielomianu ax³+bx²+cx+d nie liczymy w tradycyjny sposób, tylko: x(ax²+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

Filip: Tak, Eulera możemy zacząć od piątku

Mariusz: Weźmy jako przykład wielomian Czebyszowa T3 i dwumian x − 1 (4x³−3x):(x−1) Zapisujesz współczynniki wielomianu w tabelce Z boku zapisujesz x₀ z dwumianu (x−x₀) (Tutaj x₀=1) 4 0 −3 0 1 Teraz współczynnik przy x³ przepisujesz 4 0 −3 0 1 4 ^ | Mnożysz 1 przez 4 pokazaną przez tę "strzałkę" i dodajesz współczynnik przy x² 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 4x²+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

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; }

Mariusz: Tak ta druga wersja jest dobra

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

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

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

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?

Mariusz: Ja akurat interpolacją wielomianami Czebyszowa się nie bawiłem Bawiłem się interpolacją Lagrange ale też niezbyt dużo

Mariusz : Umiałbyś napisać wersję offline tego programu co podała Qulka https://matematykaszkolna.pl/forum/407266.html Na Windows preferowany język to C# Na Linux to C++ Na Androida mają już gotowca

Filip: Aktualnie nie siedze w C++ i troche go już nie pamiętam

Mariusz: Gdybyś miał dopisać do tej listy co napisaliśmy sortowanie przez łączenie naturalne to jak napisałbyś je

Filip: Mam być szczerym, pierwszy raz słyszę o tym sortowaniu. Teraz mam wolne dwa tygodnie, także jutro mogę coś o nim poczytać i ew pytania na jakie nie znajdę odpowiedzi, mogę je zadać tutaj. Jak rozumiem nadal zostajemy przy języku C PS. Polecasz jakieś dobre źródło do nauki javy?

Mariusz: Przeglądałem Thinking in Java a także Algorytmy w Javie Roberta Lafore Do C# nie mogę znaleźć dobrych książek choć już jakieś podstawowe programiki w nim pisałem − trochę przez podobieństwo do Javy Co do sortowania przez łączenie naturalne to oryginalnie było stosowane do sortowania plików ale można je zaadoptować do sortowania list

Filip: Narazie napotkałem pierwszy problem, ze względu na to, iż nasza struktura wygląda tak struct Node { int val; struct Node* next; }; struct List { struct List* head; struct List* tail; } Przykładowo pokażę na przykładzie z wikipedi: Mamy taki zbiór danych: 1 5 2 3 8 10 4 2 7 5 8 9 1 I dzielimy go na posortowane serie (oddzielone znakiem '|') 1 5 | 2 3 8 10 | 4 | 2 7 | 5 8 9 | 1 Generalnie chyba nie wiemy, ile będziemy mieć takich serii, więc nie możemy robić oddzielnych list, może coś dodać do struktury List? struct List { struct List* head; struct List* tail; struct List* next; } I teraz nasze serie 1 5 | 2 3 8 10 | 4 | 2 7 | 5 8 9 | 1 Niech a = {1, 5} b = {2, 3, 8, 10} Zapisać tak: a−>head = 1 a−>tail = 5 a−>next = b; b−>head = 2 b−>tail = 10 b−>next = c{4} W sensie narazie nie testowałem czy będzie to miało sens, ale jest lepszy niż operowanie na x oddzielnych listach, bez możliwości efektywnego "przeskakiwania" między nimi

Filip: A no i pierwszy krok, to muszę pomyśleć jak napisać funkcję, aby właśnie mi dzieliło np: 1 5 2 3 8 10 4 2 7 5 8 9 1 na takie serie 1 5 | 2 3 8 10 | 4 | 2 7 | 5 8 9 | 1

Filip: aa, no i może tego nowego pola nie nazywać next, bo może wystąpić koalizja oznaczeń − już mamy w struct Node pole o nazwie next

Mariusz: Nie zmieniasz struktury listy Korzystasz z dwóch dodatkowych list przy czym nie allokujesz pamięci na nowe węzły bo sortowanie listy polega na podmianie wskaźników Serie z sortowanej listy rozdzielasz na przemian do dwóch pomocniczych list

Filip: Hmm, mógłbyś przybliżyć? 1 5 | 2 3 8 10 | 4 | 2 7 | 5 8 9 | 1 Lista A − 1 5 4 5 8 9 Lista B − 2 3 8 10 2 7 1 I co dalej z tym robie, bo tego nie widzę

Mariusz: Teraz przy scalaniu bierzesz sobie dwie flagi które będą przechowywać informację czy skończyła się seria Pierwsza flaga jest ustawiana gdy skończy ci się aktualna seria na liście A wtedy kopiujesz pozostałe węzły z aktualnej serii na liście B , ustawiasz drugą flagę i rozpoczynasz łączenie następnych serii Łączenie kończysz gdy wyczerpiesz serie z obydwu list Procedury dzielenia i łączenia powtarzasz aż po etapie dzielenia lista B będzie pusta Przydatne będą trzy funkcje −rozdzielająca listę na dwie listy −łącząca listy −sortująca

Mariusz: W tym przykładzie masz Przed fazą rozdzielania Lista L − 1 5 | 2 3 8 10 | 4 | 2 7 | 5 8 9 | 1 Lista A − NULL Lista B − NULL Po fazie rozdzielania Lista L − NULL Lista A − 1 5 | 4 5 8 9 Lista B − 2 3 8 10 | 2 7 | 1 Po fazie łączenia Lista A − NULL Lista B − NULL Lista L − 1 2 3 5 8 10 | 2 4 5 7 8 9 | 1

Filip: Funkcje rozdzielającą napisałem tak: void splitList(struct List* L, struct List* A, struct List* B) { int where = 0; struct Node* temp = L−>head; while (temp != NULL) { double comp = temp−>val; if (where % 2 == 0) { while (comp <= temp−>val && temp != NULL) { addElement(A, temp); temp = temp−>next; comp = temp−>prev−>val; } } else { while (comp <= temp−>val && temp != NULL) { addElement(B, temp); temp = temp−>next; comp = temp−>prev−>val; } } where++; } } Chyba funkcje scalająca listy już pisaliśmy

Filip: Nie, jednak nie pisaliśmy, daj znać co sądzisz o mojej implementacji − czy przede wszystkim jest poprawna (nawet w brzegowych warunkach)

Filip: No właśnie, odnośnie fazy łączenia, zostajemy nadal przy tych samych danych z 16:55 Jak rozpoznam, do kiedy moge łączyć elementy moge łączyć elementy − w sensie Pierwsze łączenie a − {1, 5} −− skąd wiem, że jest tutaj koniec pierwszej serii? b − {2, 3, 8, 10} Zakładam, że będzie to mniej więcej szło tak: Wybieram serie, o mniejszej długości − w tym wypadku a int i = 0; int j = 0; dopóki pierwsza seria a się nie skończy && i < długość serii a jeżeli a[i] < b[j] addElement(L, a[i]) i++; else addElement(L, b[j]) j++; for (int k = j; j < długośc serii b; k++) addElement(L, b[k]); Tak w wielkim skrócie bym widział scalanie, jednak użyłem operatora [], aby dowiedzieć się czy dobrze zrozumiałem odnośnie zwykłych tablic (wiadomona liście będzie to wyglądać trochę inaczej, ale poglądowo chciałem zrobić)

Filip: Łączenie*, nie scalanie

Mariusz: przeglądasz listę dwoma wskaźnikami Pamiętasz wskaźnik na poprzednika i na aktualny węzeł Jeżeli poprzedni większy od aktualnego to znaczy że rozpoczęła się nowa seria

Mariusz: To co pisaliśmy to było sortowanie przez podział a tam scalanie sprowadzało się do konkatenacji No ja mam inaczej napisane rozdzielanie ale możliwe że twoja wersja też będzie działać musiałbym to sprawdzić

Filip: Tak, moja implementacja jest niepoprawna, muszę się nad tym zastanowić

Mariusz: Wiesz co jak konstruujesz warunki to najpierw sprawdzaj czy wskaźnik jest różny od NULLa a dopiero porównuj wartości na które ten wskaźnik wskazuje wtedy będziesz miał pewność że nie otrzymasz segmentation fault z powodu dereferencji NULLa Zadaj sobie pytanie od której strony kompilator sprawdza wyrażenia logiczne Czy funkcję rozdzielającą nie dałoby się zaprojektować tak aby zmienna where przyjmowała tylko wartości 0 oraz 1 ? U mnie zmienna where przyjmuje tylko wartości zero i jeden no i mam jedną pętle while a w niej warunek if a tak to wygląda dość podobnie

Filip: Poprawiłem funkcję, wygląda na to, że działa, ale możesz jeszcze potestować, tylko troche koszmarnie wygląda w kodzie − może da się to jakoś zrefaktoryzować void ListSplit(struct TList* L, struct TList* A, struct TList* B) { int where = 0; struct TNode* temp = L−>head; ListInit(A); ListInit(B); while (temp != NULL) { int comp = temp−>data; temp = temp−>next; struct TNode* n = malloc(sizeof(*n)); n−>data = comp; n−>next = NULL; n−>prev = NULL; if (where % 2 == 0) { if (A−>head == NULL) { A−>head = n; } else { A−>tail−>next = n; n−>prev = A−>tail; } A−>tail = n; while (temp != NULL && comp <= temp−>data) { struct TNode* n = malloc(sizeof(*n)); n−>data = temp−>data; n−>next = NULL; n−>prev = NULL; A−>tail−>next = n; n−>prev = A−>tail; A−>tail = n; comp = temp−>data; temp = temp−>next; } } else { if (B−>head == NULL) { B−>head = n; } else { B−>tail−>next = n; n−>prev = B−>tail; } B−>tail = n; while (temp != NULL && comp <= temp−>data) { struct TNode* n = malloc(sizeof(*n)); n−>data = temp−>data; n−>next = NULL; n−>prev = NULL; B−>tail−>next = n; n−>prev = B−>tail; B−>tail = n; comp = temp−>data; temp = temp−>next; } } where++; } }

Filip: ListInit − wziąłem z twojego kodu co kiedyś w C++ podsyłałeś: To fragment twojego kodu template<class T> DoublyLinkedList<T>:oublyLinkedList() { setFirst(NULL); setLast(NULL); } Ja to przerobiłem na oddzielną funkcję, tak ona wygląda void ListInit(struct List* L) { L−>head = NULL; L−>tail = NULL; }

Filip: przy okazji, znalazłem twój kod z C i przekopiowałem, by potestować swoją funkcję, tutaj jest on https://pastebin.com/1ZcN5jku Znalazłem także wątek, co z Pytającym rozmawiałem chyba właśnie o tym sortowaniu: https://matematykaszkolna.pl/forum/387956.html

Filip: Ad 7.02 20:53 Tak, właśnie na tym wpadłem, ze względu na to iż próbowałęm wydobyć wartość temp−>data, chociaż już temp był NULLem − przez to min. wywalało mi program

Mariusz: Kiedyś na innym forum pisałem z jednym kolesiem o tym sortowaniu i to się "urodziło" z jego pseudokodu Koleś pomógł więcej niż Pytający Tutaj dałem kod przed poprawkami które sam wprowadziłem aby was przetestować tzn sprawdzić czy wskażecie miejsce w kodzie gdzie program się "wysypuje"

Filip: Jutro postaram się ten co napisałem kod zoptymalizować/poprawić, bo podejrzewam, że może troche tego być, ew inaczej podejść do problemu

Mariusz: Jak co to w C++ mam poprawiony kod ale spróbuj coś samemu wymyślić

Filip: A powiedz mi, czy wykorzystałeś do tego jedną czy dwie pętle while()? Bo zastanawiam się aby to zrobić tylko przy użyciu jednej pętli

Mariusz: Fazę rozdzielania mam zrealizowaną z użyciem jednej pętli while Fazę łączenia z użyciem dwóch pętli while (jedna pętla scala serie a druga całe listy)

Filip: void ListSplit(struct TList* L, struct TList* A, struct TList* B) { int where = 0; int was_change = 1; struct TNode* temp = L−>head; ListInit(A); ListInit(B); double comp; struct TList* q = NULL; while (temp != NULL) { if (where % 2 == 0) { q = A; } else { q = B; } if (was_change == 1) { comp = temp−>data; temp = temp−>next; struct TNode* n = malloc(sizeof(*n)); n−>data = comp; n−>next = NULL; n−>prev = NULL; if (q−>head == NULL) { q−>head = n; } else { q−>tail−>next = n; n−>prev = q−>tail; } q−>tail = n; } if (temp != NULL && comp <= temp−>data) { struct TNode* n = malloc(sizeof(*n)); n−>data = temp−>data; n−>next = NULL; n−>prev = NULL; q−>tail−>next = n; n−>prev = q−>tail; q−>tail = n; comp = temp−>data; was_change = 0; } else { was_change = 1; where++; continue; } temp = temp−>next; } }

Filip: Przychodzę z takim kodem, możesz potestować, ale na moje działa ok, jest jedna pętla while() Tutaj sie prosi dla czytelności kodu, by dopisać kolejne metody − dodawanie elementu do listy, oraz tworzącą nowy element

Mariusz: Wygląda ok choć rozwiązanie nie jest optymalne pamięciowo bo kopiujesz listę Po rozdzieleniu lista L mogłaby być pusta Skoro nie zwracasz informacji o tym czy po rozdzieleniu druga z list jest pusta to pamiętaj aby to sprawdzić w funkcji sortującej Co do dodatkowych funkcji to można je napisać Proponuję dopisać takie które operują na kolejce a co do funkcji tworzącej węzły to wedle twojego uznania jeśli uważasz że się przyda to ją napisz

Filip: Tylko pytanie jak wyeeliminować to kopiowanie listy cały czas? Po prostu rozpisać przypadek dla list A oraz dla listy B ?

Mariusz: Wykorzystując operacje na kolejce ( te co pisaliśmy podczas sortowania przez podział) wstawiasz węzeł zdjęty z listy L na początku do listy A Następnie wstawiasz kolejne węzły do listy A aż zajdzie przypadek prev−>data > curr−>data Gdy ten przypadek zajdzie zmieniasz listę do której będziesz wstawiał węzły Aby kontrolować to do której z list wstawiać węzły możesz wykorzystać jedną ze zmiennych typu int Te pomocnicze funkcje już pisaliśmy 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; } Patrz wpis z 16 sty 2021 18:44

Filip: Czy przypadkiem w dequeue() nie powinniśmy sciągać wierzchołka, ustawiając jego pola next i prev na NULL?

Filip: Tak samo w funkcji enqueue, czy w else nie powinno byc: L−>tail−>next = x; x−>prev = L−>tail

Filip: Tak wlasciwie nie ma to znaczenia tak aptrze teraz

Filip: void ListSplit(struct TList* L, struct TList* A, struct TList* B) { int where = 0; int was_change = 1; struct TNode* temp = L−>head; ListInit(A); ListInit(B); double comp; while (temp != NULL) { if (where % 2 == 0) { if (was_change == 1) { comp = temp−>data; temp = temp−>next; struct TNode* n = (struct TNode*)malloc(sizeof(*n)); n−>data = comp; n−>next = NULL; n−>prev = NULL; enqueue(A, n); } if (temp != NULL && comp <= temp−>data) { comp = temp−>data; struct TNode* n = (struct TNode*)malloc(sizeof(*n)); n−>data = comp; n−>next = NULL; n−>prev = NULL; enqueue(A, n); was_change = 0; } else { was_change = 1; where++; continue; } temp = temp−>next; } else { if (was_change == 1) { comp = temp−>data; temp = temp−>next; struct TNode* n = (struct TNode*)malloc(sizeof(*n)); n−>data = comp; n−>next = NULL; n−>prev = NULL; enqueue(B, n); } if (temp != NULL && comp <= temp−>data) { comp = temp−>data; struct TNode* n = (struct TNode*)malloc(sizeof(*n)); n−>data = comp; n−>next = NULL; n−>prev = NULL; enqueue(B, n); was_change = 0; } else { was_change = 1; where++; continue; } temp = temp−>next; } } } Pozmieniałem, używając funkcji enqueue(), natomiast mam problem, by ten fragment kodu: struct TNode* n = (struct TNode*)malloc(sizeof(*n)); n−>data = comp; n−>next = NULL; n−>prev = NULL; Zastąpić funkcją dequeue() − program nie działa prawidłowo, gdy powyższy kod zapisałem jako: struct TNode* n = dequeue(L); PS. Przerzuciłem się na pracę do vscode'a, którego mam skonfigurowanego pod C++, dlatego przed mallociem() zacząłem używać (struct TNode*)

Mariusz: void ListSplit(struct TList *L,struct TList *A, struct TList *B) { int comp; int wasChanged = 0; ListInit(A); ListInit(B); struct TNode *temp = dequeue(L); enqueue(A,temp); while(L−>head != NULL) { comp = temp−>data; temp = dequeue(L); if(comp > temp−>data) wasChanged = 1 − wasChanged; if(wasChanged) enqueue(B,temp); else enqueue(A,temp); } } A taka funkcja rozdzielająca może być ? Zmieniłem typ zmiennej comp na int bo taki u mnie był typ ze względu na uproszczone losowanie (losowanie dla double byłoby bardziej skomplikowane) Wg mnie zaproponowane przeze mnie rozwiązanie powinno działać i jest oszczędne pamięciowo bo nie kopiuje listy

Mariusz: Dodaj jeszcze warunek przed pierwszym wstawianiem aby przypadek brzegowy ci się zgadzał

Filip: No tak, ten twój kod dużo lepszy, jednak bym dodał pewną modyfikacje − jeden warunek [...] struct TNode* temp = dequeue(L); if (temp == NULL) return; [...] Co ty na taki warunek? W funkcji enqueue() nie sprawdzamy, czy temp == NULL, więc może by wypadało sprawdzić przed

Filip: Teraz zobaczyłem, że mówiłeś coś o tym we wpisie z 8 lut 20:25 − czy chodziło ci o ten warunek co powyżej?

Mariusz: Po tym jak zauważyłem że program nie będzie działał dla przypadku brzegowego to u siebie użyłem nieco innego warunku ale zaproponowany przez ciebie jest ok Ja u siebie mam negację zaproponowanego przez ciebie warunku ale zostań przy swojej propozycji bo też jest dobra

Filip: Mogłbyś przypomnieć co robimy dalej? Bo mamy już ten etap sortowania napisany: L − 14 13 15 14 1 12 3 1 Po podzieleniu listy: A − 14 | 14 | 3 B − 13 15 | 1 12 | 1 L − NULL Robi to nasza funkcja ListSplit() Jak rozumiem teraz musimy napisać funkcję, która połączy nam to tak? L − 13 14 15 | 1 12 14 | 1 3 A − NULL B − NULL No i tak właściwie to co po tym dalej robimy?

Mariusz: Powtarzasz w pętli fazę rozdzielania i łączenia aż do momentu gdy po wywołaniu funkcji rozdzielającej − u nas ListSplit() lista B będzie pusta Teraz trzeba się jednak skupić na napisaniu funkcji łączącej Listy łączysz seriami , łączenie następnych serii zaczynasz gdy skończą się aktualnie łączone serie Gdy skończy ci się seria na jednej z list wtedy pozostałe węzły z aktualnej serii wstawiasz do listy która będzie wynikiem łączenia

Filip: No właśnie to jest ciekawe... jak rozpoznamy, że przykładowo w liście A skończyła się pierwsza seria? Myslałem nad warunkiem if (temp−>data >= temp−>next−>data) tylko pytanie czy tak będzie zawsze, nie mogę znaleźć kontrprzykładu do mojej tezy

Filip: ok, jednak udało mi się znaleźć kontrprzykład, ten warunek będzie zły chociażby dla takiej listy L − 5 6 7 30 1 40 37

Mariusz: Może dać dwie flagi w których będziesz przechowywał informację o końcu serii Ja pierwsze węzły z listy pobieram poza pętlą i wtedy aby wykryć koniec serii porównuję wartość klucza z aktualnego węzła z wartością klucza poprzednika Mam też bardziej rozbudowany warunek if do wykrywania końca serii niż ten co zaproponowałeś Spróbuj pomyśleć jak zrealizować łączenie aktualnych serii Jak już będziesz wiedział jak łączyć serie to łączenie całych list będzie już stosunkowo łatwe

Mariusz: Po rozdzieleniu listy L nasz algorytm rozpozna tylko jedną serię na liście B Można spróbować zastanowić się jak zaprojektować algorytm aby poprawnie rozpoznawał liczbę serii ale nawet jeśli nasz algorytm rozpozna na liście B tylko jedną serię to możemy stracić co najwyżej stabilność sortowania

Filip: "i wtedy aby wykryć koniec serii porównuję wartość klucza z aktualnego węzła z wartością klucza poprzednika" Właśnie nie wiem jak to ma zadziałać, kontrprzykład podałem we wpisie 9 lut 00:13, chyba że dodajesz jeszcze jakieś warunki poza tym jednym

Mariusz: W tej instrukcji if mam warunek złożony z dwóch wyrażeń logicznych połączonych operatorem or tak aby nie wywalało segmentation fault podczas porównywania wartości klucza aktualnego węzła i wartości klucza poprzedniego węzła Tak porównując przedefiniujemy sobie serie − w twoim przykładzie na liście B Sprawdzę jak napisana przeze mnie funkcja łączy serie ale dla twojego przykładu najprawdopodobniej na liście B rozpozna ona tylko jedną serię

Mariusz: Wcześniej samodzielnie źle rozdzieliłem węzły i myślałem że to na liście B będziemy mieli sytuację że funkcja łącząca rozpozna tylko jedną serię U mnie też wykrywa tylko jedną serię na liście A Dzieje się tak dlatego że w funkcji łączącej wyszukuje serie po raz wtóry i obydwie serie na liście A powstałe w wyniku działania funkcji rozdzielającej tworzą jedną serię i dlatego funkcja łącząca rozpoznaje tylko jedną serię na liście A Możemy zaakceptować to że funkcja łącząca po raz drugi wyszukuje serie albo poszukać sposobu na odtworzenie oryginalnych serii

Filip: A tak właściwie, czy ma to jakieś duże znaczenie, jeśli serie rozpoznamy jako: A − 5 6 7 30 | 37 B − 1 40 Czy jako A − 5 6 7 30 37 B − 1 40 Można się zastanowić jak to wpłynie na ewentualnie łączenie i na całe sortowanie, ale nie wygląda na to, by to jakoś specjalnie obciążało. Więc może zostańmy przy tym, że jednym z warunków na wykrycie nowej serii będzie po prostu: if (temp−>next−>data <= temp−>data)

Filip: Bo właśnie chodziło mi o zmodyfikowanie struktury Tlist, dodać wskaźnik na następną serię Wtedy jak masz takie serie: A − 5 6 7 | 13 15 | 2 B − 1 14 15 | 2 8 | 12 To będziesz dokładnie wiedział, kiedy kończy/zaczyna się seria − jednak wymaga to modyfikacji większej ilośći kodu Więc chyba zostaniemy przy tym co napisałeś oraz z wpisu 9 lut 16:04

Mariusz: Już wcześniej pisałem że nie ma to większego znaczenia a jedyne co możemy stracić to stabilność sortowania czyli to że w przypadku węzłów z z takimi samymi wartościami kluczy ich kolejność na posortowanej liście może być różna niż na oryginalnej liście Sugerowałbym aby warunek do wykrywania końca serii skonstruować z użyciem operatora logicznego aby zapobiec błędowi segmentation fault

Filip: No tak, temp−>next != NULL, dobra coś dzisiaj popisze i będę podsyłał

Filip: Jak postępować w przypadku, gdy A lub B będą puste. Po prostu jak jedna lista jest pusta a druga nie jest pusta, to L = niepusta lista ?

Filip: Tak właściwie to nie bylo pytania, tylko B może być puste, wtedy mamy w liście A juz posortowane wartości

Filip: void MergeLists(struct TList* L, struct TList* A, struct TList* B) { if (B−>head == NULL) return; ListInit(L); struct TNode* tempA = dequeue(A); struct TNode* tempB = dequeue(B); struct TNode* valA = NULL; struct TNode* valB = NULL; int endA = 0; int endB = 0; while (A−>head != NULL || B−>head != NULL) { while (endA != 1 && endB != 1) { if (tempA−>data <= tempB−>data) { enqueue(L, tempA); valA = tempA; tempA = dequeue(A); if (tempA == NULL || tempA−>data < valA−>data) endA = 1; } else { enqueue(L, tempB); valB = tempB; tempB = dequeue(B); if (tempB == NULL || tempB−>data < valB−>data) endB = 1; } } if (endA == 1) printf("DIAS"); while (endA != 1) { enqueue(L, tempA); valA = tempA; tempA = dequeue(A); if (tempA == NULL || valA == NULL) endA = 1; else if (tempA−>data < valA−>data) endA = 1; } while (endB != 1) { enqueue(L, tempB); valB = tempB; tempB = dequeue(B); if (tempB == NULL || valB == NULL) endB = 1; else if (tempB−>data < valB−>data) endB = 1; } endA = 0; endB = 0; valA = NULL; valB = NULL; } } Podsyłam kod, który udało mi się napisać. Nie działa on jednak poprawnie − w sensie raz działa poprawnie, raz nie dodaje jednego elementu z serii do listy L, raz się wysypuje, może uda ci się znaleźć błąd, ja narazie go nie widzę

Filip: Tę linijkę kodu if (endA == 1) printf("DIAS"); możesz ominąć − używałem jej do testów i zapomniałem usunąc

Mariusz: Mój kod różni się w kilku miejscach while (A−>head != NULL || B−>head != NULL) Tutaj zamiast A−>head != NULL || B−>head != NULL mam tempA != NULL || tempB != NULL ponieważ zdjąłeś elementy z obydwu list ale ich nie wstawiłeś przed pętlą Tam gdzie ty masz endA = 0 endB = 0 ja mam endA = (tempA == NULL) endB = (tempB == NULL) Zastanawiam się czy to zwrócenie pustej instrukcji w przypadku gdy lista B jest pusta nie wpłynie jakoś na to sortowanie bo wg mnie w tym przypadku to na liście L powinny się znajdować węzły które przed wywołaniem funkcji były na liście A , lista A natomiast powinna być pusta

Filip: Zaraz zobaczę te warunki co napisałeś, odnośnie tego if'a() Tak teraz widzę, że są dwie opcje, co umieścić w jego ciele (1) Przekopiować listę A do listy L i listę A zrobić pustą (2) tego if'a wstawić tuż po zadeklarowaniu zmiennych mówiących o końcu listy i zrobić tak: int endA = tempA == NULL ? 1 : 0; int endB = tempB == NULL ? 1 : 0; tak właściwie chyba tak powinniśmy deklarować te zmienne

Mariusz: Tym operatorem trójargumentowym też można Ja w swoim kodzie w ogóle ten przypadek pominąłem ale ty możesz go wydzielić

Filip: void MergeLists(struct TList* L, struct TList* A, struct TList* B) { ListInit(L); struct TNode* tempA = dequeue(A); struct TNode* tempB = dequeue(B); struct TNode* valA = NULL; struct TNode* valB = NULL; int endA = tempA == NULL ? 1 : 0; int endB = tempB == NULL ? 1 : 0; while (tempA != NULL || tempB != NULL) { while (endA != 1 && endB != 1) { if (tempA−>data <= tempB−>data) { enqueue(L, tempA); valA = tempA; tempA = dequeue(A); if (tempA == NULL || tempA−>data < valA−>data) endA = 1; } else { enqueue(L, tempB); valB = tempB; tempB = dequeue(B); if (tempB == NULL || tempB−>data < valB−>data) endB = 1; } } while (endA != 1) { enqueue(L, tempA); valA = tempA; tempA = dequeue(A); if (tempA == NULL || valA == NULL) endA = 1; else if (tempA−>data < valA−>data) endA = 1; } while (endB != 1) { enqueue(L, tempB); valB = tempB; tempB = dequeue(B); if (tempB == NULL || valB == NULL) endB = 1; else if (tempB−>data < valB−>data) endB = 1; } endA = tempA == NULL ? 1 : 0; endB = tempB == NULL ? 1 : 0; valA = NULL; valB = NULL; } } Po zaimplementowaniu twoich uwag, kod wygląda na to, że działa, troche potestowałem i ani razu się nie wysypał, oraz dobrze "posortował" odpowiednie serie. Jednak zastanawiam się, czy nie da się inaczej zapisać tego fragmentu kodu: if (tempA == NULL || valA == NULL) endA = 1; else if (tempA−>data < valA−>data) endA = 1; Przykładowo próbowałem usunąc z tego if'a warunek valA == NULL, ponieważ jeżeli wejdziemy do tej pętli while, valA nie będzie NULL'em, i przerobić cały warunek na taki: if (tempA == NULL || tempA−>data < valA−>data) endA = 1; Jednak przy takim warunku kod się wysypuje

Mariusz: Pamiętasz na jakich danych ci się wysypuje bo ja właśnie taki warunek miałem i u mnie się nie wysypywał

Filip: A nie, działa poprawnie, coś musiało mi się przewidzieć, albo co innego powodowało problemy

Filip: No dobra, ten etap wygląda na zakończony, co dalej?

Mariusz: Teraz wystarczy napisać funkcję sortującą Pętla do{}while() będzie nieco wygodniejsza w użyciu niż pętla while(){} Można użyć jednej z dwóch Wywołujesz w pętli funkcje rozdzielającą i łączącą dopóki po wywołaniu funkcji rozdzielającej lista B będzie pusta

Mariusz: Funkcję sortującą już dość łatwo napisać Gdy już ją napiszesz można będzie zastanowić się nad usprawnieniem tego algorytmu np takim Gdybyśmy scalali do dwóch list zamiast do jednej to funkcję rozdzielającą można by było wywołać tylko raz Ten pomysł widziałem w książce Diksa i Ryttera 2.10.1 Scalanie wielofazowe z 4 plikami Załóżmy że bloki zostały rozłożone na pliki P0 i P1 Pliki P2 i P3 są początkowo puste i1 = 0; i2 = 1; // numery plików wejściowych , tzn otwartych do czytania j1 = 2; j2 = 3; // numery plików wyjściowych , tzn otwartych do pisania while jest wiecej niz jeden blok do (a) scal pierwszy blok na Pi1 z pierwszym blokiem na Pi2 i powstający blok zapisz na Pj1 (b) scal następny blok na Pi1 z następnym blokiem na Pi2 i powstający blok zapisz na Pj2 (c) powtarzaj kroki (a) i (b) (kładąc powstające bloki na przemian na pliki Pj1 i Pj2) aż zostanie osiągnięty koniec plików Pi1 i Pi2 (d) przewiń wszystkie pliki do początku; dodaj liczbę 2 mod 4 do i1,i2,j1,j2 odwracając w ten sposób rolę plików wejściowych

Filip: Funkcję sortującą napisałem tak: void sortList(struct TList* L, struct TList* A, struct TList* B) { while (1) { ListSplit(L, A, B); if (B−>head == NULL) return; MergeLists(L, A, B); } } Posortowana lista będzie w argumencie drugim, czyli dla wywołania sortList(A, B, C) Posortowana lista będzie w B

Filip: Tak właściwie można zmodyfikować ten kod na taki: void sortList(struct TList* L, struct TList* A, struct TList* B) { ListSplit(L, A, B); while (B−>head != NULL) { MergeLists(L, A, B); ListSplit(L, A, B); } } Jak by to wyglądało z pętlą do while?

Filip: Wydaje mi się, że ta druga wersja będzie także poprawna Pytanie: Kiedyś widziałem podrzucałeś tutaj na forum jakieś zadanie, by napisać grę z kulkami i zbiciem(?). Pamiętasz może i jak znajdziesz podrzuciłbyś? Mam wolne do 20, a bym coś popisał w kodzie. Chyba, że masz jeszcze inne ciekawe problemy/implementacje do napisania

Mariusz: Z do while to będzie wyglądało mniej więcej tak void ListSort(struct TList *L) { struct TList A; struct TList B; int isSorted; do { ListSplit(L,&A,&B); isSorted = (B.head == NULL); MergeLists(L,&A,&B); } while(!isSorted); } Jeśli chodzi o tę grę w kulki to kiedyś o niej pisałem gdy pisałem z filem o programowaniu Musiałbym poszukać bo nie pamiętam dokładnie numeru wątku Czy znasz C# ? Jest on jest dostarczany razem z Windowsem a także zdaje się można programować w nim grafikę bez doinstalowywania jakichś bibliotek Do C++ musiałbyś jakąś gotową bibliotekę graficzną doinstalować Spróbuje poszukać ten wątek w którym opisywałem założenia tej gry

Mariusz: To ten wątek https://matematykaszkolna.pl/forum/400297.html Ciebie powinien zainteresować mój wpis z 28 kwietnia 14:01

Filip: Właśnie na C# się nie znam, C++ trochę już nie pamiętam, myślałem aby sobie pójść bardziej w competetive programming, zacząć na stronie codeforces, oczywiście od trywialnych problemów i przechodzić coraz wyżej

Mariusz: Jeśli chodzi o mnie to ja w szkole miałem Javę a w C# to jak na razie jakieś proste programy w nim pisałem Co do tych kulek to do C++ musiałbyś doinstalować jakąś bibliotekę graficzną Tutaj też można by się zastanowić jaką bibliotekę wybrać dobrze by było z obsługą myszy tak jak np SFML ale może znajdziesz coś lepszego Patrzyłeś na założenia tej gry które wypisałem w tamtym wątku ? Masz jakiś pomysł na jej napisanie ?

Filip: Przypomina mi to, aby w tablicy sprawdzić, czy jest wolna droga z punktu A do B. Kiedyś pisałem przejście labiryntu tzn Szukanie drogi z A do B w labiryncie, tutaj podobnie będzie, tylko naszymi ścianami będą kulki − no i ew koniec planszy Jednak na jakiej zasadzie działa zbicie?

Filip: bool solveMaze(int x, int y, std::vector<std::vector<char>>& maze) { if (maze[x][y] == 'B') return true; if (x < 0 || x >= maze.size() || y < 0 || y >= maze.size() || maze[x][y] != ' ') return false; maze[x][y]; if (solveMaze(x, y − 1, maze)) return true; if (solveMaze(x + 1, y, maze)) return true; if (solveMaze(x, y + 1, maze)) return true; if (solveMaze(x − 1, y, maze)) return true; maze[x][y] = ' '; return false; } Kiedyś pisałem taki kod w C++, szuka on dowolnej drogi między dwoma punktami (A, B) w labiryncie, myśle że tutaj ten kod można wykrozystać, jednak trzeba go przerobić z C++ na C

Filip: Tam mi zjadło, zamiast maze[x][y]; powinno być maze[x][y] = '.'; //to jest oznaczenie drogi, mozna wybrac dowolny symbol

Mariusz: No tak jeśli będzie wolna droga oraz pole nie będzie zajęte to kulkę można przenieść z pola A do pola B Zbicie − sprawdzasz czy masz co najmniej pięć kulek tego samego koloru obok siebie w pionie , w poziomie bądź na jednej z dwóch diagonali Jeżeli znajdziesz takie kulki to je usuwasz a następnie zwiększasz licznik punktów Tutaj naszą planszą będzie tablica 9x9 np int board[9][9] − 0 to puste pole − niezerowa wartość to numer koloru

Filip: Moge tak w zasadzie napisać taki prototyb tej gry, w sensie bez tego "okienka", tylko przykładowo w konsolii gracz będzie podawać pole (x, y), na które chce posłać kulkę

Filip: Tutaj narazie widzę 3 funkcje − na pewno sprawdzająca czy nastąpiło zbicie, przemieszczająca kulkę, oraz rozstawiająca kulki na planszy

Filip: A kiedy gra się kończy?

Mariusz: Gdy zapełnimy całą planszę i nie będziemy mieć wolnego pola aby wylosować kulkę Na początku losujemy pięć kulek (liczba kolorów uzależniona od poziomu trudności) a później w każdy a następnie po każdym ruchu który nie jest zakończony zbiciem losowane są trzy kulki W sumie w wersji konsolowej zamiast te kolorowe kulki mogą być reprezentowane przez jakieś znaki Poziom trudności gry to np liczba użytych znaków

Filip: Hmm no dobra, czyli jak rozumiem będzie to wyglądać tak: 1. Losujemy kulkę (x5), którą reprezentują dwie liczby: a ∊ [0, 80] − położenie kulki na planszy b ∊ [1, liczbaKulek] − "kolor" kulki i umieszczamy na planszy 2. Gracz może przesunąć kulkę na dowolne − wolne pole na planszy, gdy jest do niego "droga" Teraz sprawdzamy czy nastąpiło bicie jeśli nastąpiło to usuwamy zbite kulki jeśli nie to losujemy kolejne 3 kulki i umieszczamy na planszy sprawdzamy, czy cała plansza jest zapełniona jeśli tak − koniec gry jeśli nie − wracamy do punktu 2

Mariusz: No w sumie ja bym tak widział tę grę A i przydałby się jakiś sposób na ominięcie losowania już zajętego pola Może jest jakiś lepszy pomysł na to niż powtórzenie losowania

Filip: Hmm, chyba zaczne od przerzucenia kodu z 11 lut 14:04 na C, i zobacze jakby to działało na planszy z kulkami

Filip: No właśnie nie wiem czy się da bez powtórzenia losowania tak szczerze, chyba losowanie będzie zrealizowane mniej więcej tak: void draw(int n, int a, int b) { for (int i = 0; i < n; i++) { while (...) {} } }

Filip: skoro plansza ma wymiary 9x9, to czy polozenie kulki nie powinismy losowac z przedzialu [0,89]?

Filip: nawet [0,88]

Mariusz: A czemu tak z przedziału [0,80] powinno wystarczyć Do czego potrzebujesz tych dodatkowych liczb ?

Filip: Skoro mamy planszę 9x9, to jak wylosujemy 88 − [8][8] 81 − [8][1] Gdybysmy losowali tylko do 80, nie byloby nic w ostatnim wierszu od 1 indeksu do 8

Mariusz: Niech a∊[0,80] wtedy indeksy mogłyby wyglądać tak [a/9][a%9]

Filip: Racja, ja myślałem, gdybyśmy losowali z przedziału a ∊ [0, 88] grid[a / 10][a % 10]

Filip: Losowanie napisałem tak: void draw(int n, int grid[9][9]) { for (int i = 0; i < n; i++) { int place = rand % 81; int colour = 1 + rand % n; //n − liczba kulek while (grid[place / 9][place % 9] != 0) { place = rand % 81; } grid[place / 9][place % 9] = colour; } }

Filip: Może zamiast wszędzie pisać 9 − wprowadzić zmienną globalną? #define gridSize 9

Mariusz: Tak to dobry pomysł z tą zmienną globalną Jeśli chodzi o tę funkcję losującą to może powinna ona przyjmować trzy parametry − liczba losowań − liczba kulek − plansza

Mariusz: #define gridSize 9 void draw(int n,int m,int grid[gridSize][gridSize]) { for(int i = 0; i < n; i++) { int place = rand()% gridSize*gridSize; int colour = 1 + rand() % m // m − liczba kulek while(grid[place / gridSize][place % gridSize] != 0) place = rand()% gridSize*gridSize; grid[place / gridSize][place % gridSize] = colour; } }

Mariusz: W sumie tak sobie pomyślałem że funkcja losująca mogłaby zwracać informację czy losowanie się powiodło tzn czy mamy miejsce na kulkę Jest też taka opcja aby ograniczyć funkcję draw do losowania tylko jednej kulki wtedy pętla for byłaby wykonywana poza funkcją draw

jc: Wprowadź zmienną pamiętającą aktualną liczbę wolnych pól (nie to będzie n). Losuj liczbę z przedziału [1,2,...,n]. Niech to będzie k. Zaznacz k−te wolne pole (możesz iść po kolei, omijając pola zajęte).

Filip: Czy liczba kulek nie będzie równa liczba losowań? Jeśli tak, trzeci argument wydaje się być zbędny

Filip: trzeci jako liczba kulek − nie trzeci w kolejności od lewej do prawej

Mariusz: No racja umieszczanie wylosowanej liczby będzie równie wolne jak dla listy ale powinno działać i chyba coś podobnego robiłem dla symulacji gry w lotto

Mariusz: Nie, liczba kulek zależy od wybranego poziomu trudności i zwykle różni się od liczby losowań Rozważ też propozycję jc na zrealizowanie losowania

jc: Przy kolejnych losowaniach liczba zajętych pól będzie rosła, ale po wykonaniu ruchu, liczba wolnych pól może wzrosnąć. Czy dopuszczasz losowanie, którego wynikiem będzie redukcja zajętych pól? Ja akurat wolę taką wersję.

Mariusz: Liczba wolnych pól wzrośnie gdy nastąpi zbicie wtedy liczby o tej samej wartości które tworzą linię (w pionie , poziomie i na jednej z dwóch diagonali) zostają usunięte Linię tworzy co najmniej pięć liczb o tej samej wartości stojące obok siebie W sumie do sprawdzania czy liczby tworzą linię oraz do usuwania linii chyba lepiej napisać oddzielne funkcje

Filip: Nawet kilka, można też rozbić funkcje sprawdzające, byśmy łącznie wtedy mieli 6 funkcji (1) checkRows() (2) checkCols() (3) checkDiagonal() (4) deleteRows() (5) deleteCols() (6) deleteDiagonal() No i w sumie jak dobrze myślę to jeszcze trzy funkcje sprawdzające czy jest zbicie w wierszy/kolumnie/na diagonali, zwracające 1 gdy jest − 0 gdy nie ma Tutaj ewentualnie będzie można się trochę pobawić i zrobić coś takiego void deleteRows(int (*checkRows)(int[][gridSize]), int grid[gridSize][gridSize]) { if ((checkRows)(grid) == 1) { ... } } jednak jest to już pewne kombinowanie, i nie wiem czy nie warto by zrobić tego if'a poza funkcją służącą do usuwania Co do propozycji jc, w kodzie bym to widział tak: // jedno losowanie int free = gridSize * gridSize; int place = rand() % free; int colour = 1+ rand() % m; // m − liczba kulek int temp = 0; int i = 0; while (temp != place) { if (grid[i / 9][i % 9] == 0) temp +=1; i++ } grid[temp / 9][temp % 9] = colour; Możecie dać znać czy poprawnie i co ew tutaj można poprawić

Mariusz: Jeżeli chodzi o free to będzie kolizja nazw Po wylosowaniu zmniejszasz liczbę wolnych pól Po zbiciu musisz pamiętać o jej zwiększeniu o liczbę kulek które usunąłeś Tutaj zakładasz że liczba wolnych pól jest większa od zera

Mariusz: Ja losowanie zaproponowane przez jc tak bym widział #define gridSize 9 void draw(int *n,int m,int grid[gridSize][gridSize]) { // m − liczba kulek // n − liczba wolnych pól // k − liczba odpowiadająca za pozycję losowanej kulki na planszy if(*n == 0) return; int counter=0; int k = rand()%(*n); int colour = 1 + rand()%m; while(counter != k) { if(grid[counter/9][counter%9] == 0) counter++; } grid[counter/9][counter%9] = colour; *n = *n−−; }

Filip: Mhm, racja, jednak ja założyłem, że pierw będę miał funkjcę, która sprawdza czy ma nastąpić koniec gry czy nie − dlatego już nie sprawdzam tego warunku: if (*n == 0) No tak, u mnie jednak zmienna jest zbędna i nie zmniejszam ilości wolnych pól

Mariusz: Jeśli chodzi o wyszukiwanie drogi to ja na początku myślałem nad jakimś algorytmem grafowym np wyszukiwanie najkrótszej ścieżki w grafie ale chyba ty znalazłeś lepszy sposób

Filip: Może ustalmy jakiś schemat postępowania, bo trochę chaotycznie idziemy Na razie mamy funkcję losująca, którą umieściłbym tak: int main() { [...] int n = gridSize * gridSize; int m = 5; // losujemy 5 kulek na początku for (int i = 0; i < 5; i++) draw(&n, 5, grid); } //główna pętla gry while (checkEnd(gridSize * gridSize, grid) != 1) { // tutaj następuje ruch na wolne pole, więc (załóżmy narazie, że gracz podaje (x, y) na które chce przesunąc kule o współrzędnych (x_p, y_p) while (canMove(x_p, y_p, x, y, grid) != 1) // przesuwamy // teraz sprawdzamy czy jest bicie [...] // jeśli tak [P[jesli jest zbicie na wierszu/kolumnie/diagonali − usuwamy // losujemy 3 kulki i umieszczamy je na planszy m = 3; for (int i = 0; i < m; i++) draw(&n, m, grid); } Ja bym to mniej więcej tak widział, daj znąc czy to ma tak wyglądać, funkcje losującą wygląda na to że mamy, trzeba tylko potestowąc funkcje checkEnd() bym napisał tak; int checkEnd(int n, int grid[gridSize][gridSize]) { for (int i = 0; i < n; i++) if (grid[i / 9][i % 9] == 0) return 0; return 1; }

Filip: Inaczej, powinniśmy zwracać informacje, czy umieszczanie się udało, przykładowo gdy losujemy trzy kulki, na planszy może być wolne 2 miejsca, więc położymy 2 i koniec gry

Mariusz: Zmienna pamiętająca liczbę liczbę wolnych pól zawiera informację czy należy skończyć grę liczbaWolnychPól == 0 − koniec gry Tak jest po każdym wylosowaniu kulki sprawdzamy czy nie nastąpiło zbicie Pamiętaj że diagonalę sprawdzasz w dwie strony

Mariusz: int main() { [...] int n = gridSize * gridSize; int m = 7; // liczba kulek od niej zależy poziom trudności gry, // w wersjach które widziałem dajemy graczowi możliwość wyboru jednej z trzech liczb // losujemy 5 kulek na początku for (int i = 0; i < 5; i++) draw(&n, 5, grid); } //główna pętla gry // Tutaj zmienna przechowująca liczbę wolnych pól zawiera informację czy skończyć grę while ( n != 0) { // tutaj następuje ruch na wolne pole, więc (załóżmy na razie, że gracz podaje (x, y) na które chce przesunąć kule o współrzędnych (xp, yp) while (canMove(xp, yp, x, y, grid) != 1) // przesuwamy // teraz sprawdzamy czy jest bicie [...] // jeśli tak [P[jesli jest zbicie na wierszu/kolumnie/diagonali − usuwamy // losujemy 3 kulki i umieszczamy je na planszy for (int i = 0; i < 3; i++) draw(&n, m, grid); } No na razie coś takiego mamy

Mariusz: draw(&n, 5, grid); Tutaj mamy oczywiście draw(&n, m, grid); bo m jest liczbą kulek poza tym przy warunku dla pętli for dajemy n > 0 i w głównej pętli też możemy dać n > 0

jc: Lata temu napisałem sobie coś takiego w javie. Losowanie działa tak, jak zasugerowałem. private int kulka (int k) { int m = 1 + Math.abs(p.nextInt ()) % n; n −−; for (int x = 1; x <= 9; x++) for (int y = 1; y <= 9; y++) { if ( c[x][y] == 0) m −−; if (m == 0) { c[x][y] = k; pole (x,y,k); return zmiana (x,y); } } return 0; } Dwie funkcje wewnątrz biorą się stąd, że dopuszczam, iż wylosowana kulka uzupełni jakiś układ do układu redukowalnego. n jest zmienną globalną oznaczającą liczbę wolnych miejsc.

Filip: Tak właściwie to nie wiem, czy nie lepiej trzymać wymiary planszy w dwóch różnych zmiennych, ze względu na to, iż po usunięciu przykładowo całego wiersza, zmieni się tylko wartość wierszy a kolumny nadal pozostaną takie same: 9x9 po usunięciu dowolnego wiersza 8x9

Mariusz: Podczas usuwania kulek zerujesz wartości tablicy a plansza nadal zostaje rozmiaru 9x9

Filip: W funkcji losującej, zamiast: *n = *n−−; Powinno być *n = −−*n; Natomiast nie wiem czemu, funkcja ta nie działa w pętli, w sensie pojedyńcze wywołanie działa, natomiast np pięciokrotne już nie

Filip: Mariusz wydaje mi się, że twoja funkcja jest niepoprawna, gdyż jeśli staniemy na elemencie niezerowym, program będzie leciał w nieskończoność

Filip: Pozostanę przy takiej wersji, które wydaje się działać void draw(int* n, int m, int grid[gridSize][gridSize]) { if (*n == 0) return; int place = rand() % (*n); int colour = 1 + rand() % m; int temp = 0; int i = 0; while (temp != place) { if (grid[i / 9][i % 9] == 0) temp++; i++; } grid[temp / 9][temp % 9] = colour; *n = −−*n; } Output (dla pierwszego losowania 5 kulek): Przed losowaniem: 81 [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] Po losowaniu: 76 [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 7 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 1 0 0 0 0 0 0 1] [0 0 5 0 0 0 0 0 0] [0 0 0 0 0 0 0 3 0]

Filip: Niestety nie mam też pewności czy ten kod co podałem odnośnie szukania drogi działa poprawnie − przełożyłem go na język C, jednak nie działa on poprawnie

Mariusz: Problem może być gdy z losowania dostaniesz zero wtedy funkcja nie wejdzie ci do pętli i wtedy nadpiszesz pierwszy element

Mariusz: A przeglądałeś jakieś algorytmy grafowe ? Może jakieś wyszukiwanie najkrótszych ścieżek w grafie by tutaj zadziałało

Filip: Pisałem kiedyś dfs'a w grafie ważonym dla listy sąsiedztwa aby szukał najkrótszej drogi z wierzchołka A do B, może to coś pomoże

Filip: Jeszcze sie zastanowie co moze byc nie tak z moja funkcja szukajaca drogi

Filip: Przede wszystkim wytestuje czy dziala na normalnych labiryntach

Mariusz: Funkcja losująca nie działa też poprawnie bo problem będzie gdy wylosujemy zero a grid[0][0] ≠ 0 to nie wejdzie nam do pętli i nadpisze nam wartość elementu grid[0][0] Wersja losowania napisana przez jc po poprawieniu indeksów będzie działać poprawnie tyle że wymaga wprowadzenia zmiennej globalnej

Filip: A nie dałoby się tego obejść, inicjalizując zmienną temp wartością −1? I później do indeksowania pomyśleć nad kombinacją zmiennych temp/i oraz 1?

Filip: Dlaczego przy rozwiązaniu jc musimy mieć zmienną globalną?

Mariusz: No w sumie w rozwiązaniu jc też nie musimy mieć zmiennej globalnej On swój program pisał w Javie a tam nie ma wskaźników ani referencji i dał zmienną globalną

Mariusz: Co do losowania to może takie coś void draw(int* n, int m, int grid[gridSize][gridSize]) { if (*n == 0) return; int place = rand() % (*n); int colour = 1 + rand() % m; int temp = 0; int i = 0; while(grid[temp /9][temp%9] != 0) temp++; while (place != 0 && temp != place) { if (grid[i / 9][i % 9] == 0) temp++; i++; } grid[temp / 9][temp % 9] = colour; *n = −−*n; } Oczywiście można też skorzystać z pomysłu jc

Filip: Na szybko skleiłem kod w C++ #include <iostream> #include <vector> #include <fstream> bool solveMaze(int x, int y, std::vector<std::vector<char>>& maze) { if (maze[x][y] == 'B') return true; if (x < 0 || x >= maze.size() || y < 0 || y >= maze.size() || maze[x][y] != ' ') return false; maze[x][y] = '.'; if (solveMaze(x, y − 1, maze)) return true; if (solveMaze(x + 1, y, maze)) return true; if (solveMaze(x, y + 1, maze)) return true; if (solveMaze(x − 1, y, maze)) return true; maze[x][y] = ' '; return false; } int main() { std::ifstream file("a.txt"); std::string s; std::vector<std::vector<char>> board; int i = 0; while (std::getline(file, s)) { board.emplace_back(); for (auto c : s) board[i].push_back(c); i++; } board[0][1] = ' '; solveMaze(0, 1, board); board[0][1] = 'A'; for (int i = 0; i < board.size(); i++) { for (int j = 0; j < board[0].size(); j++) { std::cout << board[i][j]; } std::cout << '\n'; } } Możesz się pobawić, jednak algorytm działa poprawnie, przykładowo znajduje droge bardzo dobrze: Output: (1) #A####### #. ### ## #..### ## ##.# # # ##. . # ###. ### # ###. ##### #. . . ### #. ### ### #B####### (2) #A####### #. ### ## #. . ### ## ##. # # # ##. . .B # ### ### # ### ##### # ### # ### ### ######## Czyli poprawnie znajudje droge, może coś zepsułem w przepisywaniu na C

Filip: Znalazłem rozwiązanie, jednak nie wiem czy ci się spodoba, podeśle ci rano, bo mam je troche rozwalone w kodzie (w sensie brzydki kod), po krótce: Jak widzisz te 9 (uznalem ze bedzie to liczba > m aby bylo bezpiecznie, to jest droga, mozna to zniwelowac − po wykonaniu funkcji clear() Przed ruchem: 81 [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 5] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 5 0 0 0 0 0 0] [0 0 0 0 0 4 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 7 0] 2 8 8 8 // z pozycji (2, 8), przenosze na pozycje (8,8) Po ruchu: 76 [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [9 9 9 9 9 9 9 9 9] [9 9 9 9 9 9 9 9 9] [9 9 9 9 9 9 9 9 9] [9 9 5 0 0 0 0 0 0] [9 9 0 0 0 4 0 0 0] [9 9 9 9 9 9 9 9 9] [0 0 0 0 0 0 0 7 5] Po wyczyszczenie naszej drogi (uzyciu funkcji clear()) [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 5 0 0 0 0 0 0] [0 0 0 0 0 4 0 0 0] [0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 7 5] Czyli jak widac udalo sie przeniesc

Filip: Tak wygląda fragment programu, oraz funkcji main() int canMove(int xStart, int yStart, int a, int grid[gridSize][gridSize]) { if (grid[xStart][yStart] == a) return 1; if (xStart < 0 || xStart >= gridSize || yStart < 0 || yStart >= gridSize || grid[xStart][yStart] != 0) return 0; grid[xStart][yStart] = a; if (canMove(xStart, yStart − 1,a, grid) == 1) return 1; if (canMove(xStart, yStart + 1, a, grid) == 1) return 1; if (canMove(xStart − 1, yStart, a, grid) == 1) return 1; if (canMove(xStart + 1, yStart, a, grid) == 1) return 1; grid[xStart][yStart] = 0; return 0; } void clear(int a, int grid[gridSize][gridSize]) { for (int i = 0; i < gridSize * gridSize; i++) if (grid[i / 9][i % 9] == a) grid[i / 9][i % 9] = 0; } int main() { [...] int xs, ys, xe, ye; scanf("%d %d %d %d", &xs, &ys, &xe, &ye); int a = grid[xs][ys]; grid[xs][ys] = 0; if (grid[xe][ye] == 0) { grid[xe][ye] = m + 3; if (canMove(xs, ys, m + 3, grid) == 1) grid[xe][ye] = a; else printf("brak drogi"); } else { printf("zly ruch"); } printf("\n\nPo ruchu: %d\n", n); clear(m + 3, grid); printGrid(grid); [...] }

Filip: Tak patrze, nie jest to do końca poprawne, bo gdy nie ma drogi/zły ruch powinnienem na końcu nadpisywać grid[xs][ys] = a; Generalnie algorytm działa wtedy, gdy zaczniemy od pola o wartości 0 − dlatego podmieniam grid[xs][ys], oraz gdy na grid[xe][ye] mamy wartość unikalną (tutaj wybrałem m + 3, gdyż taka wartość będzie tylko jedna na planszy)

Filip: No i oczywiście program się wcześniej gubił, ponieważ nie zaznaczałem aktualnej drogi, przez co, chodził można by powiedzieć, że w kółko, dlatego zaznaczam i później usuwam tę wartości w funkcji clear()

Filip: Funkcję printGrid() napisałem tak: void printGrid(int grid[gridSize][gridSize]) { for (int i = 0; i < gridSize * gridSize; i++) { if (i % 9 == 0) printf("[%d ", grid[i / 9][i % 9]); else if (i == (i / 9 + 1) * 8 + i / 9) printf("%d]\n", grid[i / 9][i % 9]); else printf("%d ", grid[i / 9][i % 9]); } }

Filip: Zła funkcja, jak dla mnie plansza będzie bardziej czytelna gdy będzie wyświetlana taką funkcją: void printGrid(int grid[gridSize][gridSize]) { printf(" "); for (int j = 0; j < gridSize; j++) printf("%d ", j + 1); printf("\n"); printf("\n"); for (int i = 0; i < gridSize * gridSize; i++) { if (i % 9 == 0) printf("%d %d ", i / 9 + 1, grid[i / 9][i % 9]); else if (i == (i / 9 + 1) * 8 + i / 9) printf("%d\n", grid[i / 9][i % 9]); else printf("%d ", grid[i / 9][i % 9]); } } Output: 1 2 3 4 5 6 7 8 9 1 6 3 0 2 0 0 6 3 6 2 0 1 0 1 1 4 0 4 7 3 0 0 1 0 3 1 4 5 5 4 2 0 5 6 3 7 5 7 0 5 4 3 0 3 4 0 0 5 7 6 1 0 3 6 0 3 0 0 3 7 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 4 0 9 0 0 0 0 0 0 0 0 0

Filip: A, plus dwa błędy − funkcja szukająca drogi zwraca 1 w przypadku, gdy nie ma drogi − jakiś błąd jest + program nie zawsze działa, czasem na losowaniu się już wysypuje

Filip: Dobra, szukanie drogi naprawiłem i teraz działa, pozostało to losowanie

Mariusz: void draw(int* n, int m, int grid[gridSize][gridSize]) { if (*n == 0) return; int place = rand() % (*n); int colour = 1 + rand() % m; int temp = 0; int i = 0; while(place == 0 && grid[temp /9][temp%9] != 0) temp++; while (place != 0 && temp != place) { if (grid[i / 9][i % 9] == 0) temp++; i++; } grid[temp / 9][temp % 9] = colour; *n = −−*n; } Sprawdź tę funkcję losującą Ostatecznie funkcję losującą można wziąć od jc , odrobinę ją modyfikując

Filip: Tak, ta działa

Filip: To w takim razie jak działa zbicie, jest to 5 jednakowych kulek w wierszu/kolumnie/diagonali? Gdy nastąpi takie zbicie to zerujemy cały wiersz/kolumne/diagonale? (nawet inne, różne kulki od zbitych?) Czy takie coś też nazwiemy zbiciem? 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0

Mariusz: Zerujemy tylko te które tworzą linię w wierszu , kolumnie , na diagonali , inne kulki zostawiamy (przy czym sprawdzasz obydwie diagonale) To może być co najmniej pięć kulek ale tych samych Tak takie coś co pokazałeś wymaga zbicia

Mariusz: Jak masz 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 To zerujesz jedynki na tej diagonali tylko w pierwszych pięciu wierszach Jeśli natomiast miałbyś 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 To zerujesz jedynki na diagonali tylko w pierwszych sześciu wierszach

Filip: Napisałem do sprawdzania na razie wierszy, nie wiem czy jest to optymalne, ale działa poprawnie: int checkCurrentRow(int row, int grid[gridSize][gridSize]) { for (int i = 0; i < 5; i++) { int check = 1; for (int j = 0; j < 4; j++) if (grid[row][i + j] == 0 || grid[row][i + j] != grid[row][i + j + 1]) check = 0; if (check == 1) return i; } return −1; } void checkRows(int* n, int grid[gridSize][gridSize]) { for (int i = 0; i < gridSize; i++) { int index = checkCurrentRow(i, grid); int ball = grid[i][index]; if (index != −1) while (index < gridSize && ball == grid[i][index]) { grid[i][index++] = 0; *n = −−*n; } } }

Filip: Odnośnie kolumn analogiczne, tylko zamieniamy miejsce w tablicy na które będziemy patrzeć int checkCurrentColumn(int column, int grid[gridSize][gridSize]) { for (int i = 0; i < 5; i++) { int check = 1; for (int j = 0; j < 4; j++) if (grid[i + j][column] == 0 || grid[i + j][column] != grid[i + j + 1][column]) check = 0; if (check == 1) return i; } return −1; } void checkColumns(int* n, int grid[gridSize][gridSize]) { for (int i = 0; i < gridSize; i++) { int index = checkCurrentColumn(i, grid); int ball = grid[index][i]; if (index != −1) while (index < gridSize && ball == grid[index][i]) { grid[index++][i] = 0; *n = −−*n; } } } teraz pozostaje napisać dla diagonali − jednak na razie nie mam pomysłu

Filip: Chyba rozdzielić będzie trzeba pętle, przykładowo w jednej zrobić sprawdzenie dla grid_ij, (1) sprawdzamy dla 4 <= i <= 0 oraz dla 4 <= j <= 9 (2) sprawdzamy dla 4 <= i < 9 oraz dla 1 <= j <= 4

Filip: Chodzi o to, by jedna pętla sprawdzała przykładowo diagonale i inne diagonale pod nią o długości >= 5, a druga diagonale nad główną o długości >= 5

Mariusz: Jak tam postępy ? Dało coś to rozdzielenie pętli ?

Filip: Narazie napisałem tylko dla głównej diagonali oraz diagonali pod nią samą: int checkCurrentDiagonal(int diagonal, int range, int grid[gridSize][gridSize]) { for (int i = 0; i < range; i++) { int check = 1; for (int j = 0; j < 4; j++) if (grid[diagonal + j][i + j] == 0 || grid[diagonal + j][i + j] != grid[diagonal + j + 1][i + j + 1]) check = 0; if (check == 1) return i; } return −1; } void checkDiagonals(int* n, int grid[gridSize][gridSize]) { for (int i = 4; i >= 0; i−−) { int range = 5; int index = checkCurrentDiagonal(i, range − i, grid); int ball = grid[i][index]; printf("%d %d\n", i, index); int k = 0; if (index != −1) while (i + k < gridSize && ball == grid[i + k][index]) { grid[i + k][index++] = 0; *n = −−*n; k++; } range++; } }

Filip: Tak właściwie, to aby sprawdzić diagonale nad główną przekątną, wystarczy zamienić oznaczenia wierszy na kolumny i odwrotnie, przykładowo zamiast grid[i + k][index], dać grid[index][i + k] k++ na k−− tak mi się przynajmniej zdaje, nie patrzyłem jednak czy to będzie działać

Filip: Ajj, zapomniałem o diagonalach w druga stronę może to w takim razie inaczej napiszę, zrobiłem tylko od lewej do prawej

Filip: No to ja tu narazie widzę 4 funkcje do sprawdzania: (1) 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 (2) 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 (3) 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 (4) 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Z czego przypadki (1) i (3) oraz (2) i (4) można by spróbować od siebie "uzależnić" i zrobić w jednej funkcji

Mariusz: I co udało ci się napisać te kulki ? Co do tego DFS to udało ci się go napisać ? Jeśli tak to byłby to niezły kontrprzykład na to co amerykańcy wypisują (widziałem ich wpisy że DFS znajduje ścieżkę jeśli istnieje ale nie jest ona najkrótsza a przynajmniej nie zawsze jest najkrótsza)

Filip: DFS znajduje dowolną ścieżkę (o ile istnieje) niekoniecznie najkrótszą. Przykładowo w grafach ważonych używa się algorytm Dijkstry. Jednak pytanie czy tutaj nam to się przyda, ponieważ zajmuje to trochę czasu − tutaj szybsze będzie znalezienie dowolnej drogi

Mariusz: "Pisałem kiedyś dfs'a w grafie ważonym dla listy sąsiedztwa aby szukał najkrótszej drogi z wierzchołka A do B, może to coś pomoże" Wpis z 12 lut 2021 23:48 Jakoś zmodyfikowałeś wtedy oryginalnego DFSa bo amerykańcy pisali w zasadzie to samo co ty w swoim wpisie z 21 lut 2021 21:34 Tutaj preferują użycie BFS i proponują użycie kolejki jako pomocniczej struktury danych tyle że pojedyncze operacje na tablicowej kolejce będą działały w czasie O(n) chyba że zastosujemy operacje modulo do indeksowania tablicy

Filip: Pisałem coś takiego, nie jest tutaj nic specjalnego, po prostu zmodyfikowany dfs i szukanie najkrótszej drogi z możliwych (zrobione klasycznie, wszystkie możliwe drogi, wybranie najmniejszej)− jednak nie wiem czy będzie to optymalne https://pastebin.com/sZsEXjbm W C jest kolejka? Czy samemu trzeba zaimplementować?

Mariusz: W C kolejkę trzeba samemu napisać , w C++ już jest gotowiec, w C# też jest gotowiec napisany na tzw cyklicznej tablicy (tablicę indeksujesz korzystając z operatora modulo )

Mariusz: 1. https://pastebin.com/TuZ1YRfp Powyższy program działa ale zastanów się na jakie funkcje mógłbyś podzielić funkcję sortującą a poza tym jak wyeliminować potrzebę rozdzielania pliku po każdym łączeniu 2. https://pastebin.com/N4FSrydb Tutaj masz program do wyznaczania otoczki wypukłej (Metodę znalazłem gdzieś w sieci i jest ona modyfikacją algorytmu Grahama Do implementacji funkcji sortującej użyłem twojej funkcji łączącej dwie listy) Tutaj nie udało mi się wyeliminować liczników które to ograniczają liczbę punktów z których budujemy otoczkę Masz jakiś pomysł na usunięcie liczników 3. Zastanawiałeś się nad napisaniem klasy liczb wymiernych (Napisana w C++ będzie wygodniejsza w użyciu niż w Javie bo w C++ mamy przeciążanie operatorów)

Mariusz: Masz pomysł na te trzy zadania ? W drugim zadaniu usunięcie tych liczników nie będzie aż takie trudne W pierwszym usunięcie fazy rozdzielania będzie wymagało trzeciego pliku pomocniczego Jeśli chodzi o trzecie zadanie to po napisaniu tej klasy można by np zilustrować kolejne etapy eliminacji Gaußa od której zaczynaliśmy ten wątek Tutaj liczby wymierne można by wyświetlać i wczytywać za pośrednictwem łańcuchów (przydałoby się napisać wtedy funkcje parseRational oraz toString) Można też użyć przeciążonych operatorów (w C++ bo w Javie nie ma takiej możliwości) W przypadku gdy może wystąpić dzielenie przez zero można by rzucić wyjątek W C++ mamy możliwość zrealizowania operacji arytmetycznych przeciążając operatory przez co klasa będzie wygodniejsza w użyciu Co do prywatnych metod to mogłaby się tu znaleźć np funkcja licząca nwd algorytmem Euklidesa

Philips: Jak widzisz wczoraj umiesciłem tutaj dwa wpisy z głównego konta, jednak dzisiaj ich już nie ma. Wygląda na to, iż nadal posiadam tam blokadę, jak wszystko się ustabilizuję to powróce