gistfile1.txt

package Chap6_Sorting;

class Term implements Comparable<Term>{
	double coef;           // 계수
	int    exp;            // 지수

	Term(){}
	//--- 생성자(constructor) ---//
	Term(double coef, int exp) {
		this.coef = coef;  this.exp = exp; 
	}

	//--- 신체검사 데이터를 문자열로 반환 --//
	@Override
	public String toString() {
		return coef + "x**" + exp + " ";
	}
	@Override
	public int compareTo(Term d2) { //지수가 같으면 계수로 비교
		return d2.exp - exp;
	}
}

public class train_실습과제6_3_Merge정렬다항식 {
	// --- 배열 요소 p[idx1]와 p[idx2]의 값을 교환 ---//
	static void merge(Term[] p, int lefta, int righta, int leftb, int rightb ) {
		Term temp[] = new Term[30];
		int i = lefta, j = leftb, k = 0;
		
		// 두 부분 배열을 비교하면서 병합
		while (i <= righta && j <= rightb) {
			if (p[i].compareTo(p[j]) <= 0) {
				temp[k++] = p[i++];
			} else {
				temp[k++] = p[j++];
			}
		}
		
		// 왼쪽 배열의 남은 요소 복사
		while (i <= righta) {
			temp[k++] = p[i++];
		}
		
		// 오른쪽 배열의 남은 요소 복사
		while (j <= rightb) {
			temp[k++] = p[j++];
		}
		
		// temp 배열을 원래 배열로 복사
		for (i = lefta, k = 0; i <= rightb; i++, k++) {
			p[i] = temp[k];
		}
	}

	// --- 병합 정렬(재귀 버전)---//
	static void MergeSort(Term[] p, int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2;
			MergeSort(p, left, mid);        // 왼쪽 부분 정렬
			MergeSort(p, mid + 1, right);   // 오른쪽 부분 정렬
			merge(p, left, mid, mid + 1, right);  // 병합
		}
	}
	
	static void ShowPolynomial(String msg, Term[] x, int count) {
		System.out.print(msg);
		
		int length = (count == -1) ? x.length : count;
		
		for (int i = 0; i < length; i++) {
			if (x[i] != null && x[i].coef != 0) {
				if (i > 0 && x[i].coef > 0) {
					System.out.print(" + ");
				} else if (x[i].coef < 0) {
					System.out.print(" ");
				}
				System.out.print(x[i].coef + "x**" + x[i].exp);
			}
		}
		System.out.println();
	}
	
	static int AddPolynomial(Term[]p1, Term[]p2, Term[]result) {
		int p = 0, q = 0, r = 0;
		
		// 두 다항식을 순회하면서 덧셈 수행
		while (p < p1.length && q < p2.length) {
			if (p1[p].exp > p2[q].exp) {
				result[r++] = new Term(p1[p].coef, p1[p].exp);
				p++;
			} else if (p1[p].exp < p2[q].exp) {
				result[r++] = new Term(p2[q].coef, p2[q].exp);
				q++;
			} else { // 지수가 같은 경우
				double coefSum = p1[p].coef + p2[q].coef;
				if (coefSum != 0) { // 계수 합이 0이 아닌 경우만 추가
					result[r++] = new Term(coefSum, p1[p].exp);
				}
				p++;
				q++;
			}
		}
		
		// p1의 남은 항 복사
		while (p < p1.length) {
			result[r++] = new Term(p1[p].coef, p1[p].exp);
			p++;
		}
		
		// p2의 남은 항 복사
		while (q < p2.length) {
			result[r++] = new Term(p2[q].coef, p2[q].exp);
			q++;
		}
		
		return r; // 결과 다항식의 항 개수 반환
	}
	
	static int addTerm(Term[]p, Term term, int currentTerms) {
		// 같은 지수를 가진 항이 있는지 검색
		for (int i = 0; i < currentTerms; i++) {
			if (p[i].exp == term.exp) {
				p[i].coef += term.coef; // 계수만 합산
				return currentTerms;
			}
		}
		
		// 같은 지수가 없으면 새로운 항 추가
		p[currentTerms] = new Term(term.coef, term.exp);
		return currentTerms + 1;
	}
	
	static int MultiplyPolynomial(Term[]p1, Term[]p2, Term[]result) {
		int terms = 0;
		
		// 모든 항의 조합을 곱셈
		for (int i = 0; i < p1.length; i++) {
			for (int j = 0; j < p2.length; j++) {
				double newCoef = p1[i].coef * p2[j].coef;
				int newExp = p1[i].exp + p2[j].exp;
				Term newTerm = new Term(newCoef, newExp);
				terms = addTerm(result, newTerm, terms);
			}
		}
		
		return terms;
	}
	
	static double EvaluatePolynomial(Term[]p, int pTerms, double value) {
		double result = 0.0;
		
		// 각 항을 계산하여 합산
		for (int i = 0; i < pTerms; i++) {
			result += p[i].coef * Math.pow(value, p[i].exp);
		}
		
		return result;
	}
	
	public static void main(String[] args) {
		Term[] p1 = {
				new Term(1.5, 3),
				new Term(2.5, 7),
				new Term(3.3, 2),
				new Term(4.0, 1),
				new Term(2.2, 0),
				new Term(3.1, 4),
				new Term(3.8, 5),
		};
		Term[] p2 = {
				new Term(1.5, 1),
				new Term(2.5, 2),
				new Term(3.3, 3),
				new Term(4.0, 0),
				new Term(2.2, 4),
				new Term(3.1, 5),
				new Term(3.8, 6),
		};
		int nx = p1.length;

		ShowPolynomial("다항식 p1 = ", p1, -1);
		ShowPolynomial("다항식 p2 = ", p2, -1);
		MergeSort(p1, 0, p1.length - 1); // 배열 p1를 병합정렬
		MergeSort(p2, 0, p2.length - 1); // 배열 p2를 병합정렬
		ShowPolynomial("정렬후 다항식 p1 = ", p1, -1);
		ShowPolynomial("정렬후 다항식 p2 = ", p2, -1);

		Term[] result = new Term[20];
		for (int i = 0; i < result.length; i++)
			result[i] = new Term();

		int resultTerms = AddPolynomial(p1, p2, result);//다항식 덧셈 result = p1 + p2
		ShowPolynomial("덧셈후 다항식 result = ", result, resultTerms);
		
		Term[] result2 = new Term[30];
		for (int i = 0; i < result2.length; i++)
			result2[i] = new Term();

		resultTerms = MultiplyPolynomial(p1, p2, result2);//다항식 곱셈 result = p1 * p2
		MergeSort(result2, 0, resultTerms - 1); // 배열 result2를 병합정렬
		ShowPolynomial("곱셈후 다항식 result = ", result2, resultTerms);
		
		double resultValue = EvaluatePolynomial(result2, resultTerms, 1.5);//다항식 값 계산 함수 z(1.5) 값 계산
		System.out.println("\nresult = " + resultValue);
	}
}