다항식 프로그램 ( c++ )

[ 문제 ]

다항식 프로그램 작성

 

[ Input ]

입력에는 두 개의 식이 순서대로 입력된다. 첫 번째 식은 첫 줄에는 항의 개수 n (1<=n<=20)이 들어온다.  
다음 줄 부터는 최고차항 순서로 (계수, 차수)가 들어오며 공백으로 구분된다. 두 번째 식도 같은 방법으로 입력된다.

 

[ Output ]

먼저, 두 개의 식을 “(항의 개수) = 다항식”의 형식으로 각 줄에 출력한다. 이때 Sample Output에 맞추어 공백을 구분하는데 유의한다. 각 계수는 소수점 첫째자리 까지 출력하고 계수가 0인 항은 출력하지 않는다 (Sample Output 참고).
그리고 마지막줄에는 두 개의 다항식을 더하여 하나의 다항식으로 출력한다.

 

Sample Input

3
3 12
2 8
1 0
4
15 11
14 3
2 2
1 1

 

Sample Output

(3) = 3.0 x^12 + 2.0 x^8 + 1.0 x^0
(4) = 15.0 x^11 + 14.0 x^3 + 2.0 x^2 + 1.0 x^1
(7) = 3.0 x^12 + 15.0 x^11 + 2.0 x^8 + 14.0 x^3 + 2.0 x^2 + 1.0 x^1 + 1.0 x^0

 

Sample Input

4
3 12
2 8
10 3
1 0
3
15 12
-14 8
2 3

 

Sample Output

(4) = 3.0 x^12 + 2.0 x^8 + 10.0 x^3 + 1.0 x^0
(3) = 15.0 x^12 + -14.0 x^8 + 2.0 x^3
(4) = 18.0 x^12 + -12.0 x^8 + 12.0 x^3 + 1.0 x^0

 

Sample Input

4
10 5
32 4
2 3
5 2
5
1 12
2 10
3 5
4 3
5 2

 

Sample Output

(4) = 10.0 x^5 + 32.0 x^4 + 2.0 x^3 + 5.0 x^2
(5) = 1.0 x^12 + 2.0 x^10 + 3.0 x^5 + 4.0 x^3 + 5.0 x^2
(6) = 1.0 x^12 + 2.0 x^10 + 13.0 x^5 + 32.0 x^4 + 6.0 x^3 + 10.0 x^2

 

 

 

[ 소스코드 ]

#include <cstdio>
#include <iostream>

using namespace std;

#define MAX_DEGREE 80

int degreeArr[MAX_DEGREE]; // degree 입력 배열

class polynomial{
    float coef[MAX_DEGREE]; // 계수 입력 배열 
    int polyNum[MAX_DEGREE]; // 차수 입력 배열

    public:
    int degree;
    polynomial(){
        degree = 0;
    }

    void read(int num){
        scanf("%d",&degree);
        degreeArr[num] = degree;
        for(int i=0; i<degree; i++){
            scanf("%f %d",coef+i, polyNum+i);
        }
    }

    void display(int num){
        printf("(%d) = ",num);
        for(int i=0; i<degree; i++){
            if(i == degree-1){
                printf("%.1f x^%d", coef[i], polyNum[i]);
            }
            else printf("%.1f x^%d + ", coef[i], polyNum[i]);
        }
        printf("\n");
    }

    void add( polynomial a, polynomial b){

        /* 
        차수가 큰 다항식을 자신으로 복사 후 나머지 계수를 자기 계수 배열에
        차수를 맞춰 더한다.

        - 해결할 문제
        1) degree 순이 아닌 높은 차수 순으로 정렬

        - 해결 과정
        1) c에 a를 복사한다.
        2) b의 차수 배열과 c의 차수 배열을 비교해서 c에 넣어준다.
        3) 넣어주는 조건
            > c 차수가 b의 차수보다 큰 경우 b의 해당 원소 앞에 넣어준다.
            > c 차수 배열의 마지막 원소보다 b의 차수가 작다면 뒤로 배열을 다 넣어준다.
            > c 차수와 b차수가 같은 경우 b의 해당 계수을 더해준다.
        */
        *this = a; // c = a의 degree 와 polyNum 이 복사됨
        int degreeCnt = 0;

        for(int i=0; i<b.degree; i++){ // b를 순환

            for(int j=0; j<degree; j++){ // c에서 제 자리를 찾기 위해 c를 순환
                if(polyNum[j] < b.polyNum[i]){ //b의 차수가 c의 차수보다 큰 경우
                    int insertPoef = b.polyNum[i];
                    int insertCoef = b.coef[i];
                    for(int k=degree; k >= j; k--){
                        coef[k+1] = coef[k];
                        polyNum[k+1] = polyNum[k];
                    }
                    polyNum[j] = insertPoef;
                    coef[j] = insertCoef;
                    degreeCnt++; // degree 증가 카운트를 해놓고 반복문이 끝나면 degree에 더해준다.
                    j = j+1; // 자릿수가 늘어남에 따라 j도 증가
                    break;
                }
                else if(polyNum[j] == b.polyNum[i]){ //b와 c의 차수가 같은 경우
                    coef[j] += b.coef[i];
                    break; // 더 해주는게 반복되지 않게 종료시켜줌
                }
            }
            degree += degreeCnt;
            degreeCnt = 0;
        }
    }

    bool isZero(){
        return degree == 0;
    }

    void negate(){
        for(int i=0; i<degree ;i++) coef[i] = -coef[i];
    }
};

int main(){
        polynomial a,b,c;
        a.read(0);
        b.read(1);
        c.add(a,b);

        int num = c.degree;

        a.display(degreeArr[0]);
        b.display(degreeArr[1]);
        c.display(num);
        return 0;
}