더북(TheBook)

icon_cakewalk 프로그램 17-2

 

가짜 동전을 찾는 알고리즘 ②

 

◉ 예제 소스 p17-2-fakecoin.py

# 주어진 동전 n개 중에 가짜 동전(fake)을 찾아내는 알고리즘

# 입력: 전체 동전 위치의 시작과 끝(0, n - 1)

# 출력: 가짜 동전의 위치 번호

 

# 무게 재기 함수

# a에서 b까지에 놓인 동전과

# c에서 d까지에 놓인 동전의 무게를 비교

# a에서 b까지에 가짜 동전이 있으면(가벼우면): -1

# c에서 d까지에 가짜 동전이 있으면(가벼우면): 1

# 가짜 동전이 없으면(양쪽 무게가 같으면): 0

def weigh(a, b, c, d):

    fake = 29 # 가짜 동전의 위치(알고리즘은 weigh( ) 함수를 이용하여 이 값을 맞혀야 함)

    if a <= fake and fake <= b:

        return -1

    if c <= fake and fake <= d:

        return 1

    return 0

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.