[알고리듬] #60 노새와 당나귀

파이썬 실습창을 열 수 있습니다.실습창 열기

Euclid(유클리드)

 

 

노새와 당나귀

이 문제는 그리스의 유클리드(Euclid)가 지은 '그리스 시화집' 이라는 책에 있습니다.

노새와 당나귀가 터벅터벅 자루를 운반하고 있는데 노새가 너무도 짐이 무거워서 한탄을 합니다.
그러자 당나귀가 노새에게 말을 합니다.
"연약한 소녀가 울듯이 어째서 너는 한탄하고 있니?“
노새가 대답합니다.
“나는 너보다 더 많은 짐을 지고 있잖아.
너의 짐 한 자루만 내 등에다 옮겨 놓으면 내 짐은 너의 배가 되는 걸,
그렇지만 내 짐 한 자루를 네 등에 옮기면 나와 너의 짐은 같은 수가 되는 거다."

 

노새와 당나귀의 짐은 각각 몇 자루일까요?

 

1. 문제 분석

문제에서 다음을 유추할 수 있습니다.

• 노새와 당나귀가 지고있는 자루의 수는 양의 정수이다.
• 노새와 당나귀는 각각 한 자루 이상의 짐을 지고 있다.
• 자루 하나를 옮겨서 같아지거나 몇 배가 된다면 전체 자루의 수는 많지 않다.
  아무리 많아고 100자루를 넘지는 않을 것이다.

2. 알고리듬 설계

모든 경우를 조사해 보는 방법(brute force method)을 생각할 수 있습니다.

노새 1자루 일 때, 당나귀 1자루, 2자루, ... (100-1)자루
노새 2 자루 일 때, 당나귀 1자루, 2자루, ... (100-2)자루
:
노새 99 자루 일 때, 당나귀 1자루, 2자루, ... (100-99)자루

 

3. 코딩하기

코딩할 수 있겠습니까?

시간이 걸리더라도 스스로 코딩하여 보세요.

성공하여 학문의 기쁨(?)을 느껴보시기 바랍니다.

 

load=100                               # 노새와 당나귀 전체 자루 수
for mule in range(1,load):             # 노새가 지고 있는 자루 수
    for donky in range(1,load-mule):   # 당나귀가 지고 있는 자루 수
        c1=mule+1==(donky-1)*2         # 너의 짐 한 자루만 내 등에다 옮겨 놓으면 내 짐은 너의 배 
        c2=mule-1==donky+1             # 내 짐 한 자루를 네 등에 옮기면 나와 너의 짐은 같은 수
        if c1 and c2:
            print(mule, donky)
            
'''
답은 7과 5입니다.

3번 줄에서 range(1,load-mule)을 range(1, load)로 할 수 있습니다.
그러나  range(1,load-mule)와 같이하면 실행 시간을 줄일 수 있습니다.
'''

4. 문제의 확장

4-1   확장한 문제

노새와 당나귀가 한 자루의 짐을 옮겨 실어서 2배가  되는 문제를 확장하여

노새가 다음과 같이 대답하였다고 합시다.

“나는 너보다 더 많은 짐을 지고 있잖아.
너의 짐 X자루만 내 등에다 옮겨 놓으면 내 짐은 너의 Y배가 되는 걸.
그렇지만 내 짐 X자루를 네 등에 옮기면 나와 너의 짐은 같은 수가 되는 거다."

 

다음은 이 문제를 해결하는 코드입니다.

완성하여 주세요.

짐(자루)의 전체 개수는 100보다 작습니다.

 

test case 입니다.

번호	x	y	결과	설명
1	6	2	42  30	6자루를 옮겨 놓으면 2배가 되는 경우
2	11	3	55  33	11자루를 옮겨 놓으면 3배가 되는 경우
3	23	47	71  25	23자루를 옮겨 놓으면 47배가 되는 경우

 

x,y=6,2  # 6자루를 옮겨실어서 2배가 되는 경우
load=100
for mule in range(1,load):
    for donky in range(1,load-mule):
        c1 = ??????????????????
        c2 = ??????????????????
        if c1 and c2:
            print(x,y,mule, donky)
            
'''
답은 42, 30 입니다.

 

x,y=6,2  # 6자루를 옮겨실어서 2배가 되는 경우
load=100
for mule in range(1,load):
    for donky in range(1,load-mule):
        c1 = mule+x==(donky-x)*y
        c2 = mule-x==donky+x
        if c1 and c2:
            print(x,y,mule, donky)

 

4-2 '테스트 케이스' 만들기

'test case'는 어떻게 만들었을까?

모든 x, y에 대하여 조사하면 됩니다.

다음이 예입니다.

for x in range(1,100):         # 1번 줄과 2번 줄 추가
    for y in range(1,100):
        load=100
        for mule in range(1,load):
            for donky in range(1,load-mule):
                c1=mule+x==(donky-x)*y
                c2=mule-x==donky+x
                if c1 and c2:
                    print(x,y,mule, donky)

 

오늘도 수고하셨습니다.

끝없는 도전.

안녕!