[코딩문제] : 두 물통 문제

You have two jugs: a 4-gallon jug and a 3-gallon jug. Neither of the jugs have markings on them. There is a pump that can be used to fill the jugs with water. How can you get exactly two gallons of water in the 4-gallon jug?

 

당신한테 물통 2개가 있는데, 4갤런짜리랑 3갤런짜리다. 2개 다 어떤 마킹같은건 안되있다. 옆에는 물통에 물을 가득

채울 수 있는 펌프가 있다. 4갤런짜리 물통에 2리터를 담을 수 있는가?

 

바로 다음 문제는

 

Generalize the problem above so that the parameters to your solution include the sizes of each jug 

and the final amount of water to be left in the larger jug.

 

큰 물통에 담길 물의 양과 각 물통의 크기를 파라미터화(변수로 받아서) 하여 위 문제를 일반화하여라.

 

두 물통 중 어느 물통에 담기든 어차피 버리고 담으면 그만이라,

나는 어떤 양의 물을 '담을 수 있는가'에 포커스를 두었다.

Recursion을 이용했다.

 

각 물통을 나타내는 클래스 Gallon

 

 

Recursion 함수인 sol_jug

 

두 물통을 가지고 할 수 있는 동작이 무엇이 있나 살펴보니 6가지 동작이 있었다.

두 물통 a,b가 있다고 하면

1. 물통 a에 물통 b의 물을 붓는다

2. 물통 b에 물통 a의 물을 붓는다

3. 물통 a를 가득 채운다

4. 물통 b를 가득 채운다

5. 물통 a를 비운다

6. 물통 b를 비운다

 

Recursion으로 함수를 호출하면서 각 모든 행동을 하게끔 했고,

중복되는 경우 return False로 함수 콜을 없앴다.

 

 

 

sol_jug의 나머지부분

 

 

 

 

메인함수. a, b는 물통의 크기이다.

0부터 9까지 4, 3 크기의 물통을 가지고 만들 수 있는 수들은 무엇일까 궁금했다.

 

0, 1, 2, 3, 4 를 만들 수 있는듯.

 

상식적으로 가장 큰 물통의 크기가 4니까 5이상의 수는 당연히 안될 것이다.

 

다른 경우를 볼까?

 

10, 7의 물통을 가지고 만들 수 있는 물의 양은?

 

다 만들 수 있는건가? 어떻게 이게 가능하지...