[Exercises 1]
/*
Write a C++ function to make an in-place reversal of the order of elements in the array list.
list라는 배열의 요소를 거꾸로 뒤집는 함수를 작성한다.
That is, the function should transform list such that following the transformation, list[i] contaions the element originally in list[n-i-1]th
즉, 이 함수는 list[i]가 list[n-i-1]번째의 요소를 갖도록 해야한다.
where n is the total number of elements in list.
n은 list 배열의 전체크기이다.
The only additional space available to your function is that for simple variables.
이 함수에서 허용되는 추가 공간은 하나의 요소를 담을 수 있는 공간 뿐이다.
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void reverse(int list[], int len)
{
for (int i = 0; i < len/2; i++)
{
int temp = list[i];
list[i] = list[(len - i) - 1];
list[(len - i) - 1] = temp;
}
}
int main(void)
{
srand((unsigned)time(NULL));
int list[10];
cout << "list 배열 출력" << endl;
for (int i = 0; i < 10; i++)
{
list[i] = rand() % 100 + 1;
cout << list[i] << " ";
}
cout << endl;
reverse(list, sizeof(list)/sizeof(int));
cout << "변환 후 list 배열 출력" << endl;
for (int i = 0; i < 10; i++)
{
cout << list[i] << " ";
}
cout << endl;
return 0;
}
[Exercises 2]
/*
An m*n matrix is said to have a saddle point if some entry a[i][j] is the smallest value in row i and the largest value in column j
m*n 이중배열에서 i가 i 열의 가장 작은 요소이고 j가 j 행의 가장 큰 요소일 때 a[i][j]가 안장점이라고 불리운다.
Write a C++ function that determines the location of a saddle point if one exists.
안장점이 존재한다면 찾아내는 함수를 작성한다.
*/
#include <iostream>
using namespace std;
const int MAX = 100;
bool saddlePoint(int matrix[MAX][MAX], int n) //존재 여부부터 알아야하니 bool 반환
{
for (int i = 0; i < n; i++)
{
int minRow = matrix[i][0], col=0;
for (int j = 1; j < n; j++)
{
if (minRow > matrix[i][j])
{
minRow = matrix[i][j];
col = j; //그 때의 행
}
}
int k;
for (k = 0; k < n; k++)
if (minRow < matrix[k][col]) //행 중에서는 제일 커야하기 때문에 성립하지않다면 break;
break;
if (k == n)
{
cout << "안장점: " << minRow;
return true;
}
}
return false;
}
int main(void)
{
int matrix[MAX][MAX] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
cout << "이차원 배열 출력" << endl;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
cout << matrix[i][j] << " ";
}
cout << endl;
}
if (saddlePoint(matrix, 3) == false)
cout << "안장점은 존재하지 않는다" << endl;
cout << endl;
return 0;
}
[Exercises 3]
/*
When all the elements either above or below the main diagonal of a square matrix are zero, the the matrix is said to be triangular.
정사각형의 대각선을 기준삼아 위쪽이나 아래쪽이 모두 0으로 채워져있다면, 이차원배열은 삼각형 모양이라고 한다.
Figure 2.8 shows a lower and an upper triangular matrix.
Figure 2.8에서는 위의 설명과 같은 그림을 그려놓았다.
In a lower triangular matrix, a, with n rows, the maximum number of nonzero terms in row i is i+1.
아래 삼각형 모양 이차원 배열에서는 i열에서 0이 아닌 요소는 최대 i+1 개이다.
Hence the total number of nonzero terms is n(n+1)/2.
즉, 0이 아닌 요소들의 갯수의 총합은 n(n+1)/2개이다.
For large n it would be worthwhile to save the space taken by the zero entries in the upper triangle.
n이 클 경우 0으로 채워진 위쪽 삼각형의 공간을 아끼는 편이 좋을 것이다.
Obtain an addressing formula for elements a(i)(j) in the lower triangle if this lower triangle is stored by rows in an array b[n(n+1)/2] with a[0][0] being stored in b[0].
아래 삼각형 모양 이차원 배열에서 a[0][0]가 b[0]에 저장되고 이런식으로 열에 따라 b[n(n+1)/2]에 저장될 때 a[i][j]의 주소를 반환하는 공식을 세워본다.
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main(void)
{
int N;
cout << "N*N 이차원 배열에서 N의 값은?";
cin >> N;
int **LTM = new int*[N]; //lowTriangularMatrix
for (int i = 0; i < N; i++)
LTM[i] = new int[i + 1]; //아래 삼각형 모양(공간 낭비 최소화)
for (int i = 0; i < N; i++)
{
for (int j = 0; j < i + 1; j++)
{
LTM[i][j] = rand() % 10 + 1;
cout << LTM[i][j] << " ";
}
cout << endl;
}
for (int i = 0; i < N; i++)
delete[]LTM[i];
delete[]LTM;
return 0;
}
[Exercises 4]
/*
Let a and b be two lower triangular matrices, each with n rows.
a랑 b는 n열을 갖는 아래 삼각형 이차원배열이다
The total number of elements in the lower triangles is n(n+1)
아래 삼각형 이차원배열의 요소 갯수는 n(n+1)개 이다.
Devise a scheme to represent both the triangles in an array c[n][n+1].
a와 b를 c[n][n+1] 배열에 한번에 나타낼 수 있도록 한다
*/
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int main(void)
{
int N;
srand((unsigned)time(NULL));
cout << "N 입력: ";
cin >> N;;
int **a = new int*[N];
for (int i = 0; i < N; i++)
a[i] = new int[i + 1]; //아래 삼각형
int **b = new int*[N];
for (int i = 0; i < N; i++)
b[i] = new int[i + 1];
cout << "a 출력" << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < i + 1; j++)
{
a[i][j] = rand() % 100 + 1; //0이 아니게
cout << a[i][j] << " ";
}
cout << endl;
}
cout << endl << "b 출력" << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < i + 1; j++)
{
b[i][j] = rand() % 100 + 1; //0이 아니게
cout << b[i][j] << " ";
}
cout << endl;
}
int **c = new int*[N];
for (int i = 0; i < N; i++)
c[i] = new int[N+1]; //c[N][N+1]
cout << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N+1; j++)
{
c[i][j] = 0; //초기화
}
cout << endl;
}
cout << endl;
int cnt = N-1, num = N;
for (int i = 0; i < N; i++) //a 이차원배열을 거꾸로 저장한다
{
for (int j = i+1; j < (N + 1); j++)
{
if(cnt >= 0)
{
c[i][j] = a[num-1][cnt];
cnt -= 1;
}
else
{
num -= 1;
cnt = (N-1)-i;
c[i][j] = a[num-1][cnt];
cnt -= 1;
}
}
}
cout << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < i+1; j++)
{
c[i][j] = b[i][j];
}
}
cout << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N + 1; j++)
{
cout << c[i][j] << " ";
}
cout << endl;
}
for (int i = 0; i < N; i++)
{
delete[]a[i];
delete[]b[i];
delete[]c[i];
}
delete[]a;
delete[]b;
delete[]c;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서,
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.2 연습문제 (0) | 2017.08.11 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.8 연습문제 5~9 (0) | 2017.08.04 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.6 연습문제 (0) | 2017.07.31 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.5 연습문제 (0) | 2017.07.31 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.4 연습문제 (0) | 2017.07.29 |