Polynomial Evaluation (다항식 값의 계산) - 전체 C 코드, 입력 데이터셋 및 출력 결과 포함

소개

다항식 p(x) = a0 + a1x + ... + anx^n (mod N) 이 주어졌을 때, 정수값 x0에 대해 p(x0)를 구하기 위한 세 가지 방법을 모두 구현하고, 주어지는 테스트 데이터에 대해 p(x0)의 값과 곱셈과 나눗셈의 수를 각각 구하여라.
(방법 1) x^i를 i가 even인지 odd인지에 따라 구분하여 계산하는 방법
(방법 2) Improved term-by-term
(방법 3) Honer's scheme

< 포함 사항 >
- polynomial_evaluation.cpp (전체 코드)
- ProgrammingReport1.hwp (보고서)
- p1data1~5.txt (입력데이터셋)
- p1data1~5.jpg (출력 결과)

목차

1. 문제 설명

2. 입출력의 예
(1) 입력 자료 형식의 예
(2) 출력 형식의 예 (각 방법에 대해)

3. 문제풀이 방법 (알고리즘)

4. 소스 코드

5. 수행 결과

6. 결과 분석 및 토의

본문내용

다항식의 계수를 저장해야 하는데, 계수가 몇 개가 들어올지 모르기 때문에 int형 배열을 사용하되 배열 포인터를 선언하고 malloc 함수로 동적 할당하여 사용하는 방식을 선택하였다. 또, 각 방법에 대하여 주어지는 x0에 대한 결과를 출력하여야 하므로 x0의 저장을 위해 마찬가지로 int 형 배열을 동적 할당하여 사용하는 방식을 택하였다.
방법 1의 경우 재귀함수 호출을 통해 x^i의 값을 구하였다. 재귀함수가 아니라 DP 형식으로 x^i의 값을 구할 수도 있지만 그렇게 되면 곱셈/나눗셈의 수를 셀 때 문제가 발생할 것이라 생각하여 재귀함수를 통해 구하는 방식으로 구현하였다. 재귀함수를 호출하는 중간에 곱셈이 여러 번 일어나게 되는데, 이 때 overflow나 underflow가 발생할 가능성이 있어 mod 연산을 통하여 overflow나 underflow가 발생하지 않도록 하였다. mod 연산의 경우 정수 연산이기 때문에 주석에도 적었듯 % 연산을 사용했다. 실수형의 경우, 즉 부동소수점 수의 경우에는 fmod() 함수를 사용하는 것을 권장한다.

참고자료

· 없음