[C로 쓴 자료구조론] 1장 연습문제-2번(Horner법칙) 풀이

 

 

 

 

문제

---

---

 

우선 Horner의 법칙을 간단하게 알아봅시다.

https://jackpot53.tistory.com/119

그냥 여기 보고 옵시다. 여기가 설명 제일 잘되어있는듯

 

 

한줄정리를 하자면 한 항씩 계산을 하자니 효율성이 떨어져서 다른 계산했던 값들을 다시 가져다 쓰는 방법입니다.

그냥 코드로 하나하나 설명하는 방법이 훨신 나을 것 같네요

 

#include <stdio.h>
#define MAX_SIZE 101

double horner(int *coeff, int n, int x);

int main() {

	int coeff[MAX_SIZE] = { 1, 2, 3, 4, 5 };	// 1 + 2x + 3x^2 + 4x^3 + 5x^4
	int n=5;									//몇차다항식인지 알려주는 상수
	double result, x;

	printf("x의 값은? ");
	scanf(" %lf", &x);

	result = horner(coeff, n, x);

	printf("다항식 ");
	for (int i = n - 1; i >= 0; i--) {
		if (i == 0) {
			printf("%d", coeff[i]);
			break;
		}
		if (coeff[i] == 0)
			continue;

		printf("%d*x^%d + ", coeff[i], i);
	}
	printf("에서 x = %.1f일때 다항식의 값은 %.1f입니다.", x, result);

	return 0;
}

double horner(int *coeff, int n, int x) {
	//n번의 덧셈과 n번의 곱셈으로 해결
	double result = coeff[n - 2] + coeff[n-1] * x;

	for (int i = n - 3; i >= 0; i--) {
		result = result * x + coeff[i];
	}

	return result;
}

 

일단 n차에 대해서 구현을 할 수도 있겠지만 귀찮아서 그냥 4차에 대해서 구현했읍니다...

n차는 입력받으면 끝인데 계수 입력받기가 귀찮아서...

아무튼 여기서 당연히 재귀함수꼴로 표현도 충분히 할 수 있을 것 같구요(for문 부분을 return으로)

마지막 출력시키는것도 신경을 조금 써서 작성했습니다.

 

horner함수가 잘 이해가 안된다면

이 과정을 구현한 것이니 참고하시면 좋을 것 같습니다.