Machineboy空
Object-Oriented Data Structures # WEEK04 : Template Type / Tower of Hanoi puzzle 본문
Object-Oriented Data Structures # WEEK04 : Template Type / Tower of Hanoi puzzle
안녕도라 2024. 2. 6. 12:14템플릿은 사용자가 템플릿 매개 변수에 대해 제공하는 인수를 기반으로 컴파일 시간에 일반 형식 또는 함수를 생성하는 구문
4.1 Template Types
A template type is a special type that can take on different types when the type is initialized.
std::vector uses a template type:
std::vector
std::vector standard library class that provides the functionality of a dynamically growing array with a "templated" type. Key ideas:
Defined in | #include <vector> |
Initialization | std:: vector<T> v; |
Add to (back) of array | ::push_back(T); v.push_back(4); |
Access specific element | ::operator[](unsigned pos); v[0] |
Number of elements | ::size() |
Template Type
When initializing a "templated"type, the template type goes inside of <> at the end of the type name:
std::vector<char> v1;
std::vector<int> v2;
std::vector<uiuc::Cube> v3;
capacity is shrink or growed as we needed.
4.2 Tower of Hanoi - Introduction
classical puzzle in computer science.
Consider the Tower of Hanoi problem, where multiple cubes must be transferred to a new location in such a way that a larger cube cannot be placed on top of a smaller cube:
최대한 slowly move largest cube to the right
Programmatic Structure
The Tower of Hanoi problem involves three district entitles(자격?) that must be represented in code:
- we have these cubes with diff rent size and color
- three individual stacks
- in game, there're stacks, in stacks, there're cubes
Building the Tower of Hanoi Game
A new class must be created to represent each of the stacks in the Tower of Hanoi game:
A single stack must contain:
- An vector of cubes
- Operations(연산) to interact with the top of the stack
큐브 두 개를 동시에 이동할 순 없고
- push_back
- removeTop
- peekTop
- size
게임을 위한 전체 기능을 직접 구현해보고자 함.
(스택 수 설정, 큐브 수 설정 등)
Building the Tower of Hanoi Game
Finally, the game is built from the components we have already built:
- An array of three stacks
- The initial state has four cubes in the first stack
하노이의 탑 해결하기 위한 초기 세팅은 완료.
4.3 Tower of Hanoi - Solution 1
solution 1: 직접 옮겨보고, 패턴을 찾아서, 그것이 legal move인지 판단한 후 최대한 패턴에 맞춰 움직이도록!
strategies of repetition inside the move order
idk intuition to why this work
pattern이 actually work and help하는지 test하는 함수를 작성하겠다.
So, one of the beautiful things about computer science is the fact that this is not the only correct answer.
It didn't really intuitively come to me, and that's in this solusion isn't the solution that it would approach first. I think this is a solution that's simplest to code.
I want to talk about the solution that I find more beautiful, and allows you to see another way to solve the exact same problem, and both solutions are going to get the right answer.
4.4 Tower of Hanoi - Solution2
솔루션 2: 레이어를 reveal 해가며 cube를 move
I think of a master plan on what I want to do, and then I divide that master plan into several sub plans that helps me achieve the goal I'm looking for.
master plan | entire tower move 0 to 2 |
sub plan 1 | 위의 3 블록을 spare stack으로 옮긴다. |
sub plan 2 | 가장 아랫 큐브를 2로 옮긴다. |
slowly ignore the part of the tower,
making only small moves that we know exactly how to do,
and by following the pattern,
we can eventually get a solution.