[Exercises 5]
/*
Another kind of sparse matrix that arises often in practice is the tridiagonal matrix.
3중 대각행렬은 희소행렬을 연습하는 와중에 자주 등장한다.
In this square matrix, all elements other than those on the major diagonal and on the diagonals immediately above and below this one are zero.
3중 대각행렬에서는 중심 대각선과 중심 대각선을 기준으로 +1 위 아래로 있는 대각선을 제외하고는 다 0이다.
If the elements in the band formed by these three diagonals are represented by rows in an array, x, with a[0][0] being stored in b[0],
a[0][0]가 b[0]에 저장되어있고 a의 열에 따라 나타나는 x를 통해 삼중 대각행렬의 요소가 형성된다면,
obtain an algorithm to determine the value of a[i][j], 0<=i, j<n form the array x
x의 행렬로부터 a[i][j]의 요소를 구하는 알고리즘을 구한다.
*/
b1 c1 0 ........ 0
a2 b2 c2 ....... 0
0 a3 b3 c3 .....0
..................
..................
0..........a(n) b(n)
<삼차 대각 행렬>
a[0, 0]=b[0]
a[0, 1]=b[1]
a[1, 0]=b[2]
a[1, 1]=b[3]
a[1, 2]=b[4]
a[2, 1]=b[5]
.
.
.
a[i, j]=b[2i+j]
[Exercises 6]
/*
A square band matrix a(n, a) is an n*n matrix in which all the nonzero terms lie in a band centered around the main diagonal
정방 밴드 행렬이란 n*n 행렬 안에 0이 아닌 요소들이 중심 대각선을 중심으로 모여있는 행렬을 일컫는다.
The band includes a-1 diagonals below and above the main diagonal and also the main diagonal.
정방 밴드 행렬에는 중심대각선과 중심대각선을 기준으로 a-1개의 위 아래 대각선들을 포함한다.
*/
(a)How many elements are there in the band of a(n, a)
(a) a(n, a)에 몇개의 요소들이 있는가 ?
-> 2(n(a - 1) - (a)(a - 1) / 2) + n = 2na - n - a ^ 2 + a
(b) What is the relationship between i and j for elements a(i, j) in the band of a(n, a)
(b) a(n, a)의 정방밴드행렬 안에 있는 원소 a(i, j)에서 i와 j는 어떤 관계인가 ?
->i, j < n일 경우 아래 밴드에서는 j < i < j + a이고, 위에 밴드에서는 i < j < i + a
(c) 생략
[Exercises 8]
/*
There are a number of probelms, known collectively as "random walk" problems, that have been of longstanding interest to the mathematical community
수학계에서는 "불규칙한 걸음" 이라는 문제에 상당히 긴 관심을 보여왔었다.
All but the most simple of these are extremely difficult to solve and for the most part they remain largely unsolved.
이 문제들 중 가장 간단한 문제가 가장 풀기 어렵기 때문에 대부분이 해결되지 않은채 남겨져있다.
One such problem may be stated as
그 중 하나를 예로 들자면,
A cockroach is placed on a given square in the middle of a tile floor in a rectangular room of size n*m tiles.
n*m 사이즈의 직사각형 방 타일에 바퀴벌레가 위치한다.
The bug wanders randomly from tile to tile throughout the room.
바퀴벌레는 타일에서 타일로 불규칙한 움직임으로 움직인다.
Assuming that he may move from his present tile to any of the eight tiles surrounding him with equal probability,
벽에 부딪히지 않는 이상 동서남북, 북동, 북서, 남동, 남서 방향 중 한 방향(모두 동일한 확률)으로 이동한다는 가정하에
how long will it take him to touch every tile on the floor at least once.
방 안의 모든 타일을 한번씩 밟는데 얼만큼의 시간이 걸릴지 계산한다.
(중략)
Write a program to perform the specified simulation experiment.
위에 적혀있는대로 프로그램을 돌릴 수 있도록 코드를 작성한다.
Your program must:
프로그램은 아래의 요구사항을 충족시켜야한다.
(a) handle all values of n and m, 2<n<=40, 2<=m<=20
(a) n은 2 초과 40 이하이고 m은 2 이상 20 이하이다.
(b) perform the experiment for (1) n=15, m=15, starting point:(9, 9) and (2) n=39, m=19 starting point(0, 0)
(b) 두번의 실험을 진행한다. (1) n=15, m=15이고 시작점이 (9, 9)일 때와 (2) n=39, m=19이고 시작점이 (0, 0)일 때 진행한다
(c) have an iteration limit, that is, a maximum number of squares the bug may enter during experiment.(a maximum of 50000 is appropriate for this exercise)
(c) 바퀴벌레가 한번의 시뮬레이션당 밟을 수 있는 최대 타일수를 정한다.(여기서는 50000이 적당하다)
(d) for each experiment, print (1) total number of legal moves that the cockroach makes and (2) the final count array
(d) 각 실험마다, (1) 바퀴벌레가 정당하게 이동한 수를 출력하고 (2) 각 타일을 몇 번 밟았는지 출력한다
*/
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <Windows.h>
#include <iomanip> //setw 위해
using namespace std;
bool Completed_move(int **arr); //모든 타일을 밟았는지
bool bug_move(int x, int &imove, int &jmove); //바퀴벌레 움직임
void initialize(int **arr);
bool Inside_room(int imove, int jmove); //방안에 있는지
bool display(int **arr, int counter);
int m, n; //전역변수
int main(void)
{
srand((unsigned)time(NULL));
int **arr;
int x, imove, jmove, counter = 0;
cout << "직사각형의 가로:(2~40) ";
cin >> m;
while (m > 40 || m < 2)
{
cout << "재입력" << endl << "2~40 사이: ";
cin >> m;
}
cout << "직사각형의 세로:(2~20) ";
cin >> n;
while (n > 20 || n < 2)
{
cout << "재입력" << endl << "2~20 사이: ";
cin >> n;
}
cout << "시작점 입력: ";
cin >> imove >> jmove;
arr = new int*[m];
for (int i = 0; i < m; i++)
arr[i] = new int[n];
initialize(arr);
while ((!Completed_move(arr)) && (counter < 50000))
{
do
{
x = rand() % 7;
} while (bug_move(x, imove, jmove)==0);
arr[imove][jmove]++;
counter++;
}
cout << "바퀴벌레의 움직임: " << counter << endl;
if (display(arr, counter))
cout << "모든 타일을 밟았습니다" << endl;
else
cout << "실패했습니다" << endl;
return 0;
}
bool Completed_move(int **arr)
{
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (arr[i][j] == 0)
return false;
return true;
}
bool bug_move(int x, int &imove, int &jmove)
{
int idirection[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int jdirection[8] = { 1, 1, 1, 0, -1, -1, -1, 0 };
int itotal = imove + idirection[x], jtotal = jmove + jdirection[x];
if (Inside_room(itotal, jtotal)) //움직임을 가세했을 때 여전히 방 안이여야한다
{
imove = itotal;
jmove = jtotal;
return true;
}
return false;
}
void initialize(int **arr)
{
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
arr[i][j] = 0;
}
bool Inside_room(int imove, int jmove)
{
if (imove >= m || imove < 0 || jmove >= n || jmove < 0)
return false;
else
return true;
}
bool display(int **arr, int counter)
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < m; j++)
cout << setw(4) << arr[i][j]<<" ";
cout << endl;
}
cout << endl;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
if (!arr[i][j])
return false;
}
return true;
}
[Exercises 9]
/*
Chess provides the setting for many fascinating diversions that are quite independent of the game itself
체스는 체스 내에서 독립적으로 흥미로운 설정들을 제공한다.
Many of these are based on the strange L-shaped move of the knight.
이 중 다수는 다소 이상하게 L자 모양으로 움직이는 나이트가 배경이다.
A classical example is the problem of the knight's tour, which has captured the attention of mathematicians and puzzle enthusiasts since the beginning of the eighteenth century.
대표적인 예로는 나이트의 움직임이 있다.(1800년대 초에 많은 수학자들과 퍼즐 열광자들의 관심을 받았다)
Briefly stated, the problem is to move the knight, beginning from any given square on the chessboard, in such a manner that it travels successively to all 64 squares, touching each square once and only once.
간단히 설명하자면, 나이트의 움직임은 체스판 위 무작위의 위치에서 시작해서 모든 타일을 단 한번씩만 밟는 경우이다.
It is convenient to represent a solution by placing the numbers 1, 2, .... , 64 in the squares of the chessboard indicating the order in which the squares are reached.
나이트가 밟는 타일마다 순서대로 1,2, ..., 64로 표시해주면 좀 더 편리하다.
Note that it is not required that the knight be able to reach the initial position by one move move;
64개의 타일을 다 밟고 나서 다시 시작점으로 돌아올 필요가 없다.
(중략)
An algorithm to solve the knight's tour problem using Warnsdoff's rule is described below
Warnsdoff의 규칙대로 나이트의 움직임 알고리즘을 풀기위해서는 아래의 조건을 따라야한다.
(a) Initialize chessboard
(a) 체스판을 초기화한다
(b) Set starting position
(b) 시작점을 설정한다
(c) Loop
(c) (d)~(g)의 단계를 m이 64가 될 때까지 반복한다
(d) Form set of possible next squares
(d) 나이트가 움직일 수 있는 타일들을 판별한다.
(e) Test special cases
(e) 특별한 경우를 시험해본다.(npos=0일 경우 실패를 알리고 다음 단계로 넘어간다, npos=1일 경우 min=0이라고 하고 (g) 단계로 넘어간다)
(f) Find next square with minimum number of exits
(f) 다음 이동 때 도달할 수 있는 타일 중 한번도 밟지 않았고 모든 시뮬레이션 결과 제일 적게 밟히는 타일을 찾는다
(g) Move Knight
(g) 나이트를 움직인다
(h) Output
(h) 결과를 출력한다. 체스판도
*/
#include <iostream>
using namespace std;
#define N 8
typedef struct
{
int x;
int y;
}chess_moves;
void printBoard(int board[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout << board[i][j] << "\t";
cout << endl;
}
cout << endl;
}
bool MovePossible(chess_moves next_move, int board[N][N])
{
int i = next_move.x;
int j = next_move.y;
if ((i >= 0 && i < N) && (j >= 0 && j < N) && (board[i][j] == 0)) //다음으로 움직일 수 있는가
return true;
return false;
}
bool findTour(int board[N][N], chess_moves move_KT[], chess_moves curr_move, int move_count)
{
chess_moves next_move;
if (move_count == N*N - 1)
return true; //모든 타일을 방문했다면
for (int i = 0; i < N; i++)
{
next_move.x = curr_move.x + move_KT[i].x; //현재 움직임과 나이트의 움직임을 합친결과 다음을 예측
next_move.y = curr_move.y + move_KT[i].y;
if (MovePossible(next_move, board))
{
board[next_move.x][next_move.y] = move_count + 1; // 순서
if (findTour(board, move_KT, next_move, move_count + 1) == true) //움직일 수 있다면 참
return true;
else
{
board[next_move.x][next_move.y] = 0;
}
}
}
return false;
}
void knightTour()
{
int board[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
board[i][j] = 0; //초기화
chess_moves move_KT[8] = { {2,1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1} };
chess_moves curr_move = { 0, 0 }; //시작점
if (findTour(board, move_KT, curr_move, 0) == false)
{
cout << endl << "나이트의 움직임 실패" << endl;
}
else
{
cout << "나이트의 움직임 성공" << endl;
printBoard(board);
}
}
int main(void)
{
knightTour();
cout << endl;
cout << "*숫자는 나이트가 움직인 순서" << endl;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서,
http://www.csegeek.com/csegeek/view/tutorials/algorithms/backtrack/backtrack_part3.php,
http://www.cplusplus.com/forum/beginner/39837/
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*8번 문제는 http://www.cplusplus.com/forum/beginner/39837/를 풀다가 링크를 참고해서 완성했습니다
*9번 문제는 http://www.csegeek.com/csegeek/view/tutorials/algorithms/backtrack/backtrack_part3.php 여기 있는 코드를 그대로 가져왔습니다.(나중에 기회가 된다면 직접 작성하겠습니다. 알고리즘 자체는 8번과 비슷했습니다)
*7번 문제는 5, 6번 문제와 너무 비슷했기 때문에 생략했습니다
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.3 연습문제 (0) | 2017.08.11 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.2 연습문제 (0) | 2017.08.11 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.8 연습문제 1~4 (0) | 2017.08.03 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.6 연습문제 (0) | 2017.07.31 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.5 연습문제 (0) | 2017.07.31 |