[Exercises 7]
/*
The polynomials a(x)=x^(2n)+x^(2n-2)+...+x^(2)+x^(0) and b(x)=x^(2n+1)+x^(2n-1)+...+x^(3)+x cause Add to work very hard
a(x)=x^(2n)+x^(2n-2)+...+x^(2)+x^(0) 와 b(x)=x^(2n+1)+x^(2n-1)+...+x^(3)+x 다항식은 Add 함수가 작동하기 매우 힘들게 한다
For these polynomials, determine the exact number of times each statement will be executed
이러한 다항식들에 대해서는, 각 문장이 몇번 실행되는지 구해본다
*/
/*
Write a c++ function that evaluates a polynomial at a value x0 using the representation of this section
이 섹션에서 표현한 다항식에 x0를 대입했을 때의 결과값을 반환하는 함수를 작성하시오
*/
#include <iostream>
using namespace std;
int number = 0; //호출횟수
class Polynomial; //forward declaration
class Term
{
friend Polynomial;
friend ostream &operator<<(ostream &os, const Polynomial &c); //Term 클래스의 멤버 변수 참조 위해
private:
float coef;
int exp;
};
class Polynomial
{
private:
Term *termArray; //array of nonzero terms
int capacity;
int terms; //number of nonzero terms
public:
Polynomial()
{
capacity = 1;
terms = 0;
termArray = new Term[capacity];
}
void NewTerm(const float theCoeff, const int theExp)
{
//Add a new term to the end of termArray
if (terms == capacity)
{
//double capacity of termArray
capacity *= 2;
Term *temp = new Term[capacity]; //new array
copy(termArray, termArray + terms, temp);
delete[]termArray; //deallocate old memory
termArray = temp;
}
termArray[terms].coef = theCoeff;
termArray[terms++].exp = theExp;
}
Polynomial Add(Polynomial b)
{
//Return the sum of the polynomials *this and b
Polynomial c;
int aPos = 0, bPos = 0;
while ((aPos < terms) && (bPos < b.terms))
{
if (termArray[aPos].exp == b.termArray[bPos].exp)
{
float t = termArray[aPos].coef + b.termArray[bPos].coef;
if (t)
c.NewTerm(t, termArray[aPos].exp);
aPos++;
bPos++;
number++;
}
else if (termArray[aPos].exp < b.termArray[bPos].exp)
{
c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
bPos++;
number++;
}
else
{
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
aPos++;
number++;
}
}
//add in remaining terms of *this
for (;aPos < terms; aPos++)
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
//add in remaining terms of b(x)
for (;bPos < b.terms;bPos++)
c.NewTerm(termArray[bPos].coef, b.termArray[bPos].exp);
Term *temp = new Term[c.terms]; //new array
copy(c.termArray, c.termArray + c.terms, temp);
delete[]termArray;
c.termArray = temp;
return c;
}
Polynomial Multiplication(Polynomial b) //곱셈
{
Polynomial c;
c.NewTerm(0, 0);
for (int i = 0; i < terms; i++)
{
Polynomial temp;
for (int j = 0; j < b.terms; j++)
{
temp.NewTerm(termArray[i].coef*b.termArray[j].coef, termArray[i].exp + b.termArray[j].exp); //계수는 곱하고, 지수는 더하고
}
c = c.Add(temp);
}
return c;
}
float Eval(float x) //x 대입했을 때 결과값
{
float result = 0;
for (int i = 0; i<terms; i++)
{
float temp = 1; //곱셈이므로 temp는 1
for (int j = 0; j < termArray[i].exp; j++)
temp *= x; //지수 계산
result += (temp*termArray[i].coef);
}
return result;
}
//입출력
friend ostream &operator<<(ostream &os, const Polynomial &c);
friend istream &operator>>(istream &is, Polynomial &c);
};
ostream &operator<<(ostream &os, const Polynomial &c)
{
for (int i = 0; i<c.terms; i++)
if (c.termArray[i].coef != 0)
os << c.termArray[i].coef << "x^(" << c.termArray[i].exp << ") " << "+";
os << endl;
return os;
}
istream &operator>>(istream &is, Polynomial &c)
{
float coef;
int exp;
int newTerms;
cout << "입력할 개수: ";
is >> newTerms;
for (int i = 0; i < newTerms; i++)
{
cout << "계수, 지수 입력: ";
is >> coef >> exp;
c.NewTerm(coef, exp);
}
return is;
}
int main(void)
{
Polynomial p1, p2;
cin >> p1;
cin >> p2;
Polynomial p3 = p1.Add(p2);
cout << "Add의 문장이 실행된 횟수: " << number << endl;
return 0;
}
[Exercises 8]
/*
Develop a C++ class Polynomial that uses an STL vector instead of an array to hold the nonzero terms
계수가 0이 아닌 항들을 저장하는 배열 대신 STL 벡터를 사용하는 Polynomial 클래스를 정의한다.
You must include functions to add, subtract and multiply polynomials.
이 때, 더하기, 빼기, 곱하기 함수가 정의되어야한다.
Also, you must overload the input and output operators << and >> so that these work with objects of type Polynomial
또한, << 와 >> 연산자를 오버로드하여 다항식을 입출력 할 수 있어야한다.
*/
#include <iostream>
#include <vector>
using namespace std;
class Polynomial;
class Term
{
friend class Polynomial;
friend ostream &operator<<(ostream &output, const Polynomial &c);
private:
float coef;
int exp;
};
class Polynomial
{
private:
vector<Term> termArray;
public:
void NewTerm(const float theCoeff, const int theExp)
{
termArray.resize(termArray.size() + 1);
termArray[termArray.size() - 1].coef = theCoeff;
termArray[termArray.size() - 1].exp = theExp;
}
Polynomial Add(Polynomial b)
{
Polynomial c;
int aPos = 0, bPos = 0;
while ((aPos < termArray.size()) && (bPos < b.termArray.size()))
{
if (termArray[aPos].exp == b.termArray[bPos].exp)
{
float t = termArray[aPos].coef + b.termArray[bPos].coef;
if (t)
c.NewTerm(t, termArray[aPos].exp);
aPos++;
bPos++;
}
else if (termArray[aPos].exp < b.termArray[bPos].exp)
{
c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
bPos++;
}
else
{
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
aPos++;
}
}
for (;aPos < termArray.size(); aPos++)
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
for (;bPos < termArray.size(); bPos++)
c.NewTerm(termArray[bPos].coef, termArray[bPos].exp);
return c;
}
Polynomial Subtract(Polynomial b) //뺄셈, 덧셈과 크게 다르지 않다
{
Polynomial c;
int aPos = 0, bPos = 0;
while ((aPos < termArray.size()) && (bPos < b.termArray.size()))
{
if (termArray[aPos].exp == b.termArray[bPos].exp)
{
float t = termArray[aPos].coef - b.termArray[bPos].coef;
if (t)
c.NewTerm(t, termArray[aPos].exp);
aPos++;
bPos++;
}
else if (termArray[aPos].exp < b.termArray[bPos].exp)
{
c.NewTerm(-b.termArray[bPos].coef, b.termArray[bPos].exp);
bPos++;
}
else
{
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
aPos++;
}
}
for (;aPos < termArray.size(); aPos++)
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
for (;bPos < termArray.size(); bPos++)
c.NewTerm(-termArray[bPos].coef, termArray[bPos].exp);
return c;
}
Polynomial Multiply(Polynomial b)
{
Polynomial c;
c.NewTerm(0, 0);
for (int i = 0; i < termArray.size(); i++)
{
Polynomial temp;
for (int j = 0; j < b.termArray.size(); j++)
{
temp.NewTerm(termArray[i].coef*b.termArray[j].coef, termArray[i].exp + b.termArray[j].exp);
}
c = c.Add(temp);
}
for (int i = 0; i < c.termArray.size(); i++)
{
for (int j = i + 1; j < c.termArray.size(); j++)
{
if (c.termArray[i].exp == c.termArray[j].exp)
{
c.termArray[i].coef += c.termArray[j].coef;
c.termArray[j].coef = 0; //계수가 0일 때 출력 X
}
}
}
return c;
}
float Eval(float x)
{
float result = 0;
for (int i = 0; i < termArray.size(); i++)
{
float temp = 1;
for (int j = 0; j < termArray[i].exp; j++)
temp *= x;
result += (temp*termArray[i].coef);
}
return result;
}
friend ostream &operator<<(ostream &os, const Polynomial &c);
friend istream &operator>>(istream &is, Polynomial &c);
};
ostream &operator<<(ostream &os, const Polynomial &c)
{
for (int i = 0; i<c.termArray.size(); i++)
if (c.termArray[i].coef != 0)
os << c.termArray[i].coef << "x^(" << c.termArray[i].exp << ") " << "+";
os << endl;
return os;
}
istream &operator>>(istream &is, Polynomial &c)
{
float coef;
int exp;
int newTerms;
cout << "입력할 개수: ";
is >> newTerms;
for (int i = 0; i < newTerms; i++)
{
cout << "계수, 지수 입력: ";
is >> coef >> exp;
c.NewTerm(coef, exp);
}
return is;
}
//솔직히 바뀐거라고는 terms 대신 termArray.size()를 사용한다는게 전부인듯합니다
int main(void)
{
Polynomial p1, p2;
cout << "p1 다항식 입력" << endl;
cin >> p1;
cout << "p2 다항식 입력" << endl;
cin >> p2;
cout << "p1 다항식: " << p1 << endl;
cout << "p2 다항식: " << p2 << endl;
Polynomial p3 = p1.Add(p2);
cout << "p1+p2: " << p3 << endl;
Polynomial p4 = p1.Subtract(p2);
cout << "p1-p2: " << p4 << endl;
Polynomial p5 = p1.Multiply(p2);
cout << "p1*p2: " << p5 << endl;
cout << "p1에 2 대입 결과: " << p1.Eval(2) << endl;
return 0;
}
[Exercises 9]
/*
In an alternative representation of polynomials, we store the nonzero terms of all polynomials in a single array called termArray
다항식을 표기할 때, 우리는 계수가 0이 아닌 항을 termArray라는 일차원 배열에 저장한다.
Each element in termArray is of type Term, which we defined in the section.
termArray 배열에 저장되어있는 각 요소들은 이번 섹션에서 정의한 Term 클래스 타입이다.
Since the single array termArray is to be shared by all Polynomial object,
일차원 배열 termArray는 모든 다항식 객체들에게 공유되므로,
we declare it as a static class data member of Polynomial.
우리는 termArray 배열을 Polynomial 클래스의 스태틱 데이터 멤버로 정의한다.
The private data members of Polynomial are defined as follows:
Polynomial 클래스의 private 데이터 멤버들은 아래와 같다.
private:
static Term *termArray;
static int capacity;
static int free;
int start, finish;
where capacity is the size of the array termArray.
capacity는 termArray 배열의 크기이다.
The required definitions of the static class members outside the class definition are:
스태틱 클래스 멤버들은 클래스 멤버의 외부에서 정의되며 아래와 같다.
int Polynomial::capacity=100;
Term Polynomial::termArray=new Term[100];
int Polynomial::free=0; //location of next free location in termArray, termArray 배열의 가장 가까운 비어있는 칸
Consider the two polynomials a(x)=2x^(1000)+1 and b(x)=x^(4)+10x^(3)+3x^(2)+1.
a(x)=2x^(1000)+1 와 b(x)=x^(4)+10x^(3)+3x^(2)+1 이렇게 두 다항식이 있다.
These could be stored in the array termArray as shown in Figure 2.1
이들은 Figure 2.1에서 보여줬다싶이 termArray의 배열에 저장될 수 있다.
Note that a.start and b.start give the location of the first term of a and b respectively,
a.start와 b.start는 각각 a와 b의 다항식의 첫번째 위치를 알려준다
whereas a.finish and b.finish give the location of the last term of a and b.
반면, a.finish와 b.finish는 a 와 b의 다항식의 마지막 위치를 알려준다.
The static class member free gives the location of the next free location in the array termArray.
스태틱 클래스 멤버 free는 termArray 배열의 가장 가까운 비어있는 칸의 위치를 알려준다.
<중략>
Write and test C++ functions to input, output, add, multiply, and evaluate polynomials represented in this way
이러한 방식으로 입출력, 더하기, 곱하기, 그리고 대입하는함수를 작성해본다.
Use array doubling to increase the size at termArray whenever needed.
termArray 배열이 꽉 찼을 때마다 배열의 크기를 두배로 증가시켜라.
*/
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Term
{
friend class Polynomial;
private:
float coef;
int exp;
};
class Polynomial
{
private:
static Term *termArray;
static int capacity;
static int free;
int terms;
int start, finish;
void ClearTerm(int startPos, int endPos);
public:
Polynomial()
{
terms = 0;
}
void NewTerm(const float theCoeff, const int theExp)
{
if (free == capacity)
{
capacity *= 2;
Term *temp = new Term[capacity];
copy(termArray, termArray + free, temp);
delete[]termArray;
termArray = temp;
}
termArray[free].coef = theCoeff;
termArray[free++].exp = theExp;
terms++;
}
Polynomial Add(Polynomial b)
{
Polynomial c;
int aPos = start;
int bPos = b.start;
int aTerms = start + terms;
int bTerms = b.start + b.terms;
c.start = free;
while ((aPos < aTerms) && (bPos < bTerms))
{
if ((termArray[aPos].exp == termArray[bPos].exp))
{
float t = termArray[aPos].coef + termArray[bPos].coef;
if (t)
c.NewTerm(t, termArray[aPos].exp);
aPos++;
bPos++;
}
else if ((termArray[aPos].exp < termArray[bPos].exp))
{
c.NewTerm(termArray[bPos].coef, termArray[bPos].exp);
bPos++;
}
else
{
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
aPos++;
}
}
for (;aPos < aTerms;aPos++)
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
for (;bPos < bTerms;bPos++)
c.NewTerm(termArray[bPos].coef, termArray[bPos].exp);
c.finish = free - 1;
return c;
}
Polynomial Substract(Polynomial b)
{
Polynomial c;
int aPos = start;
int bPos = b.start;
int aTerms = start + terms;
int bTerms = b.start + b.terms;
c.start = free;
while ((aPos < aTerms) && (bPos < bTerms))
{
if ((termArray[aPos].exp == termArray[bPos].exp))
{
float t = termArray[aPos].coef - termArray[bPos].coef;
if (t)
c.NewTerm(t, termArray[aPos].exp);
aPos++;
bPos++;
}
else if ((termArray[aPos].exp < termArray[bPos].exp))
{
c.NewTerm(-termArray[bPos].coef, termArray[bPos].exp);
bPos++;
}
else
{
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
aPos++;
}
}
for (;aPos < aTerms;aPos++)
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
for (;bPos < bTerms;bPos++)
c.NewTerm(-termArray[bPos].coef, termArray[bPos].exp);
c.finish = free - 1;
return c;
}
Polynomial Multiply(Polynomial b)
{
Polynomial c;
int aPos = start;
int aTerms = start + terms;
int bTerms = b.start + b.terms;
c.start = free++;
for (; aPos < aTerms; aPos++)
{
Polynomial k, r;
r = c;
k.start = c.terms ? c.start + c.terms : (c.start + c.terms + 1);
for (int bPos = b.start; bPos < bTerms; bPos++)
{
float multiCoef = termArray[aPos].coef*termArray[bPos].coef;
int multExp = termArray[aPos].exp + termArray[bPos].exp;
k.NewTerm(multiCoef, multExp);
k.finish = free - 1;
}
r = r.Add(k);
c.finish = k.start - 1;
c.terms = r.terms;;
c.ClearTerm(c.start, k.finish);
}
return c;
}
int Display() //operator<<
{
int aPos = start;
for (;aPos <= finish; aPos++)
{
cout << termArray[aPos].coef << "x^(" << termArray[aPos].exp << ")";
if (aPos != finish&&termArray[aPos].coef > 0)
cout << " + ";
}
cout << endl;
return 0;
}
void GetData() //operator>>
{
start = free;
float theCoeff;
int theExp;
int pos = start;
int answer;
while (1)
{
cout << "계수, 지수: ";
cin >> theCoeff >> theExp;
NewTerm(theCoeff, theExp);
cout << "더 입력하시겠습니까?(Y=1/N=0): ";
cin >> answer;
if (termArray[pos].exp == 0 || answer == 0)
{
break;
}
else
pos++;
}
finish = pos;
}
};
void Polynomial::ClearTerm(int startPos, int endPos) //TermArray 배열 깔끔하게 정리
{
Term *temp = new Term[capacity];
Term *resultTerm = new Term[free - endPos];
copy(termArray + endPos + 1, termArray + free, resultTerm);
copy(termArray, termArray + startPos, temp);
copy(resultTerm, resultTerm + (free - endPos - 1), temp + startPos);
delete[]termArray;
delete[]resultTerm;
termArray = temp;
free = endPos;
finish = free - 1;
}
int Polynomial::capacity = 1;
Term *Polynomial::termArray = new Term[capacity];
int Polynomial::free = 0;
int main(void)
{
int choice;
Polynomial p1, p2;
cout << "p1 다항식 입력" << endl;
p1.GetData();
cout << "p2 닿항식 입력" << endl;
p2.GetData();
cout << "p1: ";
p1.Display();
cout << "p2: ";
p2.Display();
Polynomial p3 = p1.Add(p2);
cout << "p1+p2: ";
p3.Display();
Polynomial p4 = p1.Multiply(p2);
cout << "p1*p2: ";
p4.Display();
Polynomial p5 = p1.Substract(p2);;
cout << "p1-p2: ";
p5.Display();
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서,
https://stackoverflow.com/questions/26447122/comparing-two-polynomials-with-vectors-coefficients-c
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*8번 문제는 스택오버플로우를 참고했습니다.
*9번 문제는 http://jizard.tistory.com/73를 거의 따라 코딩했습니다.
*10, 11번은 생략했습니다
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.5 연습문제 (0) | 2017.07.31 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.4 연습문제 (0) | 2017.07.29 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.3 연습문제 1~6 (0) | 2017.07.28 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.2 연습문제 (0) | 2017.07.25 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.1 연습문제 (0) | 2017.07.25 |