[C++] Klasa wielomian i obliczanie miejsc zerowych


(system) #1

Witam, mam oto taki problem: Mam napisać program - klasę wielomian, który jest odpowiedzialny na wprowadzanie współczynników i stopnia wielomianu, wykonywać operacje na tych wielomianach +,-,*. Dodatkowo musi obliczać miejsca zerowe wielomianu... I tutaj pojawia się problem. Bo o ile z pomocą kolegi napisaliśmy te wszystkie założenia to nie umiemy sobie poradzić z oblicaniem miejsc zerowych...

Prosiłbym o pomoc, dziękuję za zainteresowanie. Pozdrawiam

Oto pliki programu:

main.cpp

#include 

#include "wielomian.h"

using namespace std;




int main()

{

	int stopien;

	cout<<"Podaj stopien wielomianu"<
	cin>>stopien;

	wielomian obiekt1(stopien);


	wielomian *wsk;

	wsk = new wielomian(10);



	cout<<"Podaj stopien  drugiego wielomianu"<
	cin>>stopien;

	wielomian obiekt2(stopien);

	cin>>obiekt2;


	cout<
	cout<

	cout<
	cout<

	*wsk=obiekt1-obiekt2;

	cout<
	cout<

if(obiekt1==obiekt2)

{

	cout<<"Wielomiany sa rowne"<
}

else

{

	cout<<"wielomiany sa rozne"<
}


cout<
cout<<*wsk;


	return 0;

}

wielomian.cpp

#include "wielomian.h"


using namespace std;


/ ****************************************

Konstruktor domyslny ! ! ! !

Jesli zostanie utworzony obiekt bez parametrow, to konstruktor domyslny zostanie wywolany.

Nie mialem pomyslu co w nim powinno sie znalezc, wiec zalozylem, iz jesli zostanie wywolany bez parametru, to stopien

wielomianu wynosic bedzie 1, czyli tak naprawde bedzie to prosta rownolegla do osi ox.

***************************************** /

wielomian::wielomian()

{

	stopien=0;

	wsp=new float[1];

	*wsp=3;

	losuj_wspolczynniki();

}



/ ***************************************

Konstruktor z jednym parametrem

Konstruktor ten przyjmuje tylko jeden parametr, stopien wielomianu, i dla zadanego stopnia, tworzy dynamiczna tablice

*************************************** /

wielomian::wielomian(int _stopien)

{

stopien=_stopien+1;

wsp=new float[stopien];

losuj_wspolczynniki();

}




/ ****************************************

Destruktor ! ! ! !

Zwalniamy w nim pamiec, czyli tablice wspolczynnikow

***************************************** /

wielomian::~wielomian()

{

	delete [] wsp;

}


/ ****************************************

Konstruktor kopiujacy ! ! ! !

Z obiektu wzor (wyslanego przez referencje! dla bezpieczenstwa dajemy slowko const, aby nie zmodyfikowac wzoru) kopiujemy 

wszystkie wartosci i przydzielamy je do nowego obiektu. Najpierw kopiujemy stopien, a nastepnie wskaznik na tablice floatow.

memcpy sluzy do skopiowania pamieci z jednego miejsca w drugie. Trzeci parametr to rozmiar pamieci do skopiowania

**************************************** /

wielomian::wielomian (const wielomian &wzor)

{

	stopien=wzor.stopien;

	wsp = new float [stopien];

	memcpy(wsp, wzor.wsp, (stopien*sizeof(float)));

}



void wielomian::losuj_wspolczynniki()

{

time_t t;

int i=0;

srand((unsigned) time(&t)); 


	while(i
	{

		*(wsp+i)=(float)(rand()%20-10); //Zakres -10 do 10

		i++;

	} 


}




/ ********************************************

Przeciazony operator << odpowiedzialny za wypisanie wzoru wielomianu

Wewnatrz niego znajduja sie 3 ify, sprawdzajace, czy dany wspolczynnik jest <, > lub = 0.

Potrzebne jest to, aby dobrze wypisac postac wielomianu

******************************************** /

ostream & operator<<(ostream &wyjscie, const wielomian & obiekt)

{

		int i=0;

	wyjscie<
		while(i
		{

		if(((*((obiekt.wsp)+i))>0) && i!=0)

			wyjscie<<"+"<<(*((obiekt.wsp)+i))<<"x^"<

		if(((*((obiekt.wsp)+i))>0) && i==0)

			wyjscie<<(*((obiekt.wsp)+i))<<"x^"<

		if((*((obiekt.wsp)+i))<0)

			wyjscie<<(*((obiekt.wsp)+i))<<"x^"<

		i++;

		} 

	wyjscie<
	return wyjscie;

}


/ ********************************************

Przeciazony zaprzyjazniony operator >> odpowiedzialny za wprowadzenie wzoru wielomianu

******************************************** /

istream & operator>>(istream &wejscie,  wielomian & obiekt)

{

	cout<
	for(int i=0; i
	{

		cout<<"x^"<
	wejscie >> *((obiekt.wsp)+i) ;

	}

	return wejscie;

}




/ ********************************************

Przeciazony operator + odpowiedzialny za dodawanie 2 wielomianow

W pierwszej kolejnosci sprawdza on, czy drugi wielomian, ktory dodajemy, jest stopnia mniejszego od pierwszego wielomianu

Jesli tak, to poprostu dodajemy, jesli nie, musimy skorzystac z wiekszej tablicy na wspolczynniki wielomianu

******************************************** /

wielomian wielomian::operator+ (wielomian & liczba)

	{

		int i=liczba.stopien;

		if(stopien>=liczba.stopien)

		{

			for(i=liczba.stopien; i>0; i--)

			{

				*(wsp+stopien - i)=(*(wsp+ stopien -i)) + (*((liczba.wsp)+liczba.stopien -i) );


			}


		}

		else

		{

			wielomian temp(liczba.stopien); //pomocniczy obiekt, aby nie stracic danych

			for(int i=liczba.stopien; i>=0; i--)

			{

				if(i>stopien)

				{

					(*((temp.wsp)+liczba.stopien - i))=(*((liczba.wsp)+liczba.stopien -i) );

				}

				else

				{

					(*((temp.wsp)+liczba.stopien - i))=(*(wsp+ stopien -i)) + (*((liczba.wsp)+liczba.stopien -i) );

				}

			}

				delete [] wsp;

				stopien=liczba.stopien;

				wsp = new float [liczba.stopien];

				memcpy(wsp, temp.wsp, (liczba.stopien*sizeof(float)));

		}


		return *this;

	}




/ ********************************************

Przeciazony operator - odpowiedzialny za dodawanie 2 wielomianow

W pierwszej kolejnosci sprawdza on, czy drugi wielomian, ktory odejmujemy, jest stopnia mniejszego od pierwszego wielomianu

Jesli tak, to poprostu odejmujemy, jesli nie, musimy skorzystac z wiekszej tablicy na wspolczynniki wielomianu

******************************************** /

wielomian wielomian::operator- (wielomian & liczba)

	{

		int i=liczba.stopien;

		if(stopien>=liczba.stopien)

		{

			for(i=liczba.stopien; i>0; i--)

			{

				*(wsp+stopien - i)=(*(wsp+ stopien -i)) - (*((liczba.wsp)+liczba.stopien -i) );


			}


		}

		else

		{

			wielomian temp(liczba.stopien); //pomocniczy obiekt, aby nie stracic danych

			for(int i=liczba.stopien; i>=0; i--)

			{

				if(i>stopien)

				{

					(*((temp.wsp)+liczba.stopien - i))=(*((liczba.wsp)+liczba.stopien -i) );

				}

				else

				{

					(*((temp.wsp)+liczba.stopien - i))=(*(wsp+ stopien -i)) - (*((liczba.wsp)+liczba.stopien -i) );

				}

			}

				delete [] wsp;

				stopien=liczba.stopien; wsp = new float [liczba.stopien];

				memcpy(wsp, temp.wsp, (liczba.stopien*sizeof(float)));

		}


		return *this;

	}






/ ***********************************

Przeciazony operator ==

sprawdzamy najpierw, czy stopien obu wielomianow jest rowny.

Jesli jest rozny, to wielomiany napewno nie sa sobie rowne, wiec odrazu mozemy zwrocic false

Jesli stopien jest rowny, to sprawdzamy pokolei ze soba wspolczynniki. Jesli jakis wspolczynnik jest rozny od wspolczynnika

drugiego wielomianu, konczymy petle. Jesli doszlismy do konca petli, oznacza to iz wielomiany sa sobie rowne. Wiec zwracamy true

*********************************** /

bool wielomian::operator== (wielomian & argument)

{

	if(stopien!=argument.stopien) { return false;}

	else

	{

		for(int i=0; i<=stopien; i++)

		{

			if((*(wsp+i)) != (*((argument.wsp)+i))) return false;

		}

		return true;

	}

}



/ *****************************************

Metoda odpowiedzialna za wprowadzenie przez uzytkownika recznie wszystkich wspolczynnikow wielomianu.

jesli wielomian ma miec inny stopien niz mial wczesniej, nalezy wywolac najpierw metode get_stopien();

***************************************** /

void wielomian::set_wsp()

{

	cout<<"Podaj wspolczynniki wielomianu"<
	for(int i=0; i
	{

		cout<<"x^"<
		cin>>(*(wsp+i));

		cout<
	}

}



/ *****************************************

Metoda odpowiedzialna zmiane stopnia wielomianu. Zmieniamy atrybut stopien, nastepnie usuwany poprzednia tablice wspolczynnikow,

a nastepnie tworzymy nowa tablice o zadanym rozmiarze, oraz wywolujemy metode losuj_wspolczynniki()

***************************************** /

void wielomian::get_stopien()

{

	cout<<"Podaj nowy stopien wielomianu"<
	cin>>stopien;

	stopien++;

	delete [] wsp;

	wsp = new float [stopien];

	losuj_wspolczynniki();


}



/ ******************************************

Przeciazony operator= przypisania

przepisuje stopien, oraz tablice, kopiujac wartosci wspolczynnikow

****************************************** /

wielomian wielomian::operator= (wielomian & argument)

	{

		this->stopien=argument.stopien;

		this->wsp = new float [stopien];

		memcpy(wsp, argument.wsp, (stopien*sizeof(float)));

		return *this;

	}

wielomian.h

#include 

#include 


using namespace std;



class wielomian

{

public:

	float *wsp;

	int stopien;


	wielomian();

	wielomian(int _stopien);

	wielomian (const wielomian &wzor);

	~wielomian();


	void losuj_wspolczynniki();

	void set_wsp();

	friend ostream & operator<<(ostream &wyjscie, const wielomian & obiekt);

	friend istream & operator>>(istream &wejscie,  wielomian & obiekt);

	wielomian operator+ (wielomian & liczba);

	wielomian operator- (wielomian & liczba);

	bool operator== (wielomian & argument);

	wielomian operator= (wielomian & argument);

	void get_stopien();

};

(system) #2

Schemat Hornera?

Taką tabelkę rysowałem liceum i mi się przypomniało ;p

@EDIT

http://matematyka.pisz.pl/strona/1401.html

Tutaj masz dokładnie opisany schemat jak co zrobić, tylko żeby miało miejsce zerowe w pktcie C reszta z dzielenia przez (x-c) musi być równa zero (podpunkt 4). Oczywiście możesz ten schemat zastosować dla x^n gdzie n>=3 bo dla n=2 łatwiej chyba to z deltą zrobić :wink:


(Tomek Matz) #3

dodam swoje trzy grosze do tematu ... generalnie to nie jest to zadanie na pięć minut :smiley:

gdybym ja to robił to zacząłbym od napisania kodu, który zwracałby wynik w sytuacji, gdy podany został:

  • wielomian stopnia 0, czyli brak miejsc zerowych

  • wielomian stopnia 1, czyli możliwe 1 miejsce zerowe (równanie liniowe)

  • wielomian stopnia 2, czyli możliwe 2 miejsca zerowe (równanie kwadratowe)

i to jest oczywiście proste

no ale dla wielomianów stopnia większego niż 2 zaczynają się schody ...

generalnie podzieliłbym sobie te wielomiany na dwa możliwe przypadki

1) wielomian z wyrazem wolnym

2) wielomian bez wyrazu wolnego

AD 1. W przypadku wielomianów z wyrazem wolnym trzeba by skorzystać ze schematu Horner'a i związanego z nim twierdzenia o pierwiastkach wymiernych wielomianu o wsp. całkowitych

  • czyli jest jakiś wejściowy wielomian

  • mnożymy współczynniki tego wielomianu tak, żeby uzyskać liczby całkowite

  • określamy jakie są potencjalne pierwiastki tego wielomianu z twierdzenia o pierwiastkach wymiernych wielomianu o wsp. całkowitych

  • schematem Hornera sprawdzamy, czy dany potencjalny pierwiastek jest faktycznym pierwiastkiem wielomianu. Jeśli nie jest to sprawdzamy kolejny potencjalny pierwiastek, jeśli natomiast jest no to mamy pierwsze miejsce zerowe i wejściowy wielomian rozbity na dwa mniejsze (z twierdzenia Horner'a można odczytać współczynniki nowych wielomianów)

  • teraz, gdy wejściowy wielomian mamy już rozbity na dwa mniejsze, bierzemy ten z tych dwóch mniejszych, którego miejsc zerowych jeszcze nie znamy. Najpierw należy spojrzeć jakiego stopnia jest ten wielomian. Jeśli pierwszego lub drugiego no to wszystko jasne, wiemy co z nim zrobić. Jeśli wciąż większego niż 2 no to stosujemy do niego ten sam mechanizm, co do wejściowego wielomianu, czyli Horner itd.

AD 2. No tutaj to generalnie jest gorzej. Pierwszy krok, który trzebaby robić to wyciągać przed nawias x o jak najwyższej potędze, czyli np jest sobie wielomian:

x^3 - 4 * x

wyciągamy przed nawias x i mamy już jedno miejsce zerowe i wielomian wejściowy rozbity na dwa mniejsze x i x^2 - 4

teraz dla tego mniejszego wielomianu, tj. x^2 - 4 możemy zastosować mechanizm wyszukiwania miejsc zerowych dla równań kwadratowych

oczywiście może się okazać, że nie zostanie nam wielomian stopnia 2, a jakiegoś wyższego. Wówczas trzeba zastosować mechanizm opisany w AD 1.


(floyd) #4

To może i ja dodam trzy grosze i przedstawię

algorytm znajdowania przybliżonej wartości miejsca zerowego funkcji w przedziale

1)Liczymy wartości funkcja na końcach przedziału a i b czyli znajdujemy wartości: f(a) i f(b)

2)Jeżeli f(a) i f(b) są tych samych znaków to w tym przedziale przedziale nie ma miejsc zerowych.

3) Znajdujemy wartość średnią c z przedziału według wzoru:

c=(a*f(b)-b*f(a))/(f(b)-f(a))

3) Liczymy wartość f© (z zadaną dokładnością) i sprawdzamy czy równa się zero

Jeżeli tak, to liczba c jest miejscem zerowym funkcji.

Jeżeli nie, to:

jeżeli f(a)*c<0 podstawiamy za b liczbę c (b=c) w przeciwnym przypadku podstawiamy za a liczbę c (a=c) i wracamy do punktu 1(czyli tworzymy pętlę którą należy opuścić gdy f©=0 (liczba c miejscem zerowym) lub gdy a=b z zadaną dokładnością i c<>0 - brak miejsca zerowego w przedziale)


([alex]) #5

Albo jest parzysta ilość miejsc zerowych.

Fajnie, a co zrobisz jeżeli w tym przedziale jest więcej niż jedno miejsce zerowe, właściwie dowolna ilość nieparzysta takich miejsc?


(floyd) #6

To tak jak robienie wykresu funkcji gdzie np. co 0,05 obliczamy wartości funkcji.

Np. wykonujemy wykres funkcji sin(x) dla argumentów np. od -20 do 20 i co 0,05 wyznaczamy wartości tej funkcji.

Jeżeli np. dla argumentu 3,10 wartość funkcji jest innego znaku niż dla wartości 3,15 to znaczy, że w tym przedziale <3,10 ; 3,15>jest miejsce zerowe funkcji( wykres funkcji przecina oś x)


([alex]) #7

Fajnie, tylko że dla sinusa to wiadomo jak się zachowa a z wielomianem nie. w przedziale 3.10 .. 3.15 mogą akurat być wszystkie miejsca zerowe tego wielomianu. Ba nawet mogą być wszystkie w przedziale 3.14159265 .. 3.14159266 a szukanie w nie wiadomo jakim przedziale z krokiem 1E-20 może potrwać naście lat.


(floyd) #8

Jeżeli chcemy posługiwać się metodami numerycznymi to zawsze w jakimś przedziale i w przybliżeniu. Wyznaczenie jednak np. pierwiastka równania z dokładnością do 15 cyfr po przecinku jest w praktyce wystarczające. Komputery czy kalkulatory posługują się właśnie metodami numerycznymi przy wszelkiego rodzaju obliczeniach.

Poczytaj choćby jeszcze tu o wyznaczaniu miejsc zerowych metodami numerycznymi:

http://www-users.mat.umk.pl/~piwosz/strony/17.htm

i jeszcze tu:

http://progs-jp.w.interia.pl/numerki2.htm


([alex]) #9

No właśnie poczytaj sobie to co podałeś i zastanów się czemu tam nie podano tak "świetnego" rozwiązania jakie zaproponowałeś w tym temacie wyżej.


(floyd) #10

A, gdzie ja napisałem o "świetnym" rozwiązaniu. Podałem tylko prosty przykład jak w pewnych sytuacjach można problem rozwiązać i zapewniam Cię, że to "świetne" rozwiązanie jak je ironicznie określasz nie jest moim wymysłem.

Jeszcze taka uwaga: Na tym, ale i innych forach pytający na ogól nie przedstawiają się, nie wiadomo zatem czy ma się do czynienia z gimnazjalistą czy studentem czwartego roku matematyki UW.

Jak wiadomo, nawet na to samo pytanie trochę inna powinna być odpowiedź siedmiolatkowi, inna gimnazjaliście, a jeszcze inna studentowi. Czasami z tego tytułu mogą wynikać różne nieporozumienia.

Widziałem już takie podpowiedzi siedmiolatkowi jak by był 30 latkiem po studiach informatycznych, ale to już tzw. koszta własne.


([alex]) #11

Uwzględniając fakt że przez 5 kolejnych postów nie jesteś w stanie pojąć że ten algorytm nie pasuje do wielomianu, nawet nie podejrzewam cie o wymyślenie czegokolwiek.


(floyd) #12

Dziękuję za miłe słowa. W internecie są przyjęte bardziej dosadne.


(Tomek Matz) #13

Ale się tu burza rozpętała :smiley: Swoją drogą jestem ciekaw jak do problemu podejdzie założyciel tematu.