[C++ Fundamentals of Data Structures/C++ 자료구조론(이석호)] 1.5 알고리즘 명세 연습문제 (01 ~ 05)

1. Horner의 법칙을 사용하여 다항식을 계산하는 C++ 프로그램을 작성하라.

#include <iostream>
using namespace std;

double horner(int size, int x, double* arr);
//size의 크기를 갖는 다항식 arr에 x를 대입한 결과를 반환하는 horner함수

int main(void)
{
    double arr[] = { 1, 2, 3, 4 };
    //1+2x+3x^2+4x^3 다항식 생성

    int size, x; //size: 다항식의 수, x:x0의 값
    double res; //결과값을 저장하는 용도

    x = 2; //다항식 f(x)에 2를 대입한 f(2)를 구하는 과정이다.
    size = sizeof(arr) / sizeof(double); // 다항식의 항의 갯수 저장

    res = horner(size, x, arr);
    cout << "결과: " << res << endl;
    
    return 0;
}

double horner(int n, int x, double* arr)
{
    double res = 0;

    //n번의 곱셈과 n번의 덧셈으로 결과 산출하는 것이 horner법칙의 핵심개념

    for (int i = 0; i < n; i++)
    {
        // 한 번의 곱과 덧셈으로 이루어진 과정이 n-1번 이루어짐
        // 항이 4개인 다항식은 3번의 덧셈과 곱셈만으로 결과값 추출 가능
        res = res * x + arr[(n - 1) - i]; //result는 곱셈과 덧셈 반복하며 점차 값이 커짐
        cout << "f(" << i << ") =" << res << endl; // 과정 출력
    }
    return res;
}


/*
    arr=[1.2.3.4]
    다항식 : 1+x(2+x(3+x(4)))

    for(int i = 0; i < 4 ; i++)
        i = 0
            res=0*2 + a[3-0] = 0 + 4 = 4
            //출력 : f(0) = 4
        i = 1
            res=4*2 + a[3-1] = 8 + 3 = 11
            //출력 : f(1) = 11
        i = 2
            res=11*2 + a[3-2] = 22 + 2 = 24
            //출력 : f(2) = 24
        i = 3
            res=24*2 + a[3-3] = 48 + 1 = 49
            //출력 : f(3) = 49
 */

* 참고 :  https://mattlee.tistory.com/m/42, https://jaimemin.tistory.com/126
 
 
 
 
2. n개의 변수가 주어졌을 때, 이 변수들이 가질 수 있는 가능한 모든 진리 값의 조합을 구하고자 한다.
예를 들어 n=2이면 true, true;true, false;false, true;false, false와 같은 네가지 경우가 존재한다. 이를 구하는 프로그램을 작성하라.

#include <iostream>
#include <cmath>
using namespace std;

void Combinations(int* arr, int n);

int main() {
	int n;
	int arr[100]; //충분히 크게
	cout << "n의 값을 입력하세요 : ";
	cin >> n;
	if (n <= 0)
		return -1;
	Combinations(arr, n);

	int k = 3 >> 1;
	cout << k;
}

void Combinations(int*arr, const int n) {
	int m = pow(2, n); //2^n : 전체 경우의 수
	int i;

	for (i = 0; i < m; i++) {
		arr[i] = i;
	}

	for (i = 0; i < m; i++) {
		for (int j = n - 1; j >= 0; j--) {
			int k = arr[i] >> j; //arr[i]/2^j 단, 결과 값은 정수
			if (k & 1)
				cout << "True ";
			else
				cout << "False ";
		}
		cout << endl;
	}
}

 

* 밑에는 코드 해석

 

* 참고 : https://jaimemin.tistory.com/126
* 2회독 할 때 https://dokhakdubini.tistory.com/186님 풀이도 공부하기

 

 

3. 원소 2, 4, 6, 8, 10, 12, 14, 16, 18, 20에 대해 x=1, 3, 13, 21을 탐색할 때 다음 코드의 수행 순서를 추적하라.
 

 

 

 

 

 

4. 정수 값 x, y, z를 감소하지 않는 순서로 출력하는 C++프로그램을 작성하라. 사용한 방법의 연산 시간은 얼마인가?

#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

void Sort(int* arr, const int n);

int main() {
	int n = 3;
	int i, x;
	int arr[3];

	time_t start = time(NULL);

	cout << "x,y,z의 값을 입력하세요. ";

	for (i = 0; i < n; i++) {
		cin >> x;
		arr[i] = x;
	}

	Sort(arr, 3);

	for (i = 0; i < n; i++)
		cout << arr[i] << " ";

	time_t end = time(NULL);

	cout << endl << "소요시간 : " << double(end - start) << endl;
}

void Sort(int* arr, const int n) {
	for (int i = 0; i < n; i++) {
		int j = i;
		for (int k = i + 1; k < n; k++) {
			if (arr[k] < arr[j])
				j = k;
		}
		swap(arr[i], arr[j]);
	}
}

 

* 소요시간 3초 걸림.

* 더 줄이는 연습 해야될 듯 .. ;-;

 

 

 

 

5. 정렬되지 않은 배열 a[0:n-1]에서 원소 x를 탐색하는 C++ 함수를 작성하라.

x가 존재하면 배열에서 x의 가장 왼쪽 위치리의 것을 반환하고 그렇지 않으면 -1을 반환한다.

 

#include <iostream>
using namespace std;

int Search(int* arr, int n, int x);

int main() {
	int arr[8] = { 2,5,6,3,7,18,3,10 };
	int x; //탐색할 값
	int n = sizeof(arr) / sizeof(arr[0]); //배열의 원소 개수 (배열 길이)

	cout << "탐색할 x 값을 입력하세요 : ";
	cin >> x;

	if (Search(arr, n, x) == -1)
		cout << "x는 배열에 존재하지 않는다." << endl;
	else
		cout << "x는 배열의 " << Search(arr, n, x) << "번째에 존재한다." << endl;
}

int Search(int* arr, int n, int x) {
	for (int i = 0; i < n; i++) {
		if (arr[i] == x)
			return i;
	}
	return -1; //못 찾을 경우
}

 

* 참고 : https://jaimemin.tistory.com/126