Object-Oriented Data Structures # WEEK04 : Template Type / Tower of Hanoi puzzle

템플릿은 사용자가 템플릿 매개 변수에 대해 제공하는 인수를 기반으로 컴파일 시간에 일반 형식 또는 함수를 생성하는 구문

 

 

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:

char, int, 사용자 지정 유형 모두 가능

 

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

ostream&은 출력해주는 함수랑 비슷하대

 

게임을 위한 전체 기능을 직접 구현해보고자 함.

(스택 수 설정, 큐브 수 설정 등)

 

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하는 함수를 작성하겠다.

legalMove인지 확인해보고, 최대한 01,02,12라는 패턴에 맞춰 움직이고 싶다.

 

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.