연결하기

주간 챌린지 285

매주 Mohammad S. Anwar는 우리 모두가 두 가지 주간 작업에 대한 해결책을 생각해 낼 수 있는 주간 챌린지를 보냅니다. 내 솔루션은 먼저 Python으로 작성된 다음 Perl로 변환됩니다. 이는 우리 모두가 코딩을 연습할 수 있는 좋은 방법입니다.

도전, 나의 솔루션

작업 1: 연결 없음

일

경로 목록(@routes)이 제공됩니다.

더 이상 나가는 연결 없이 목적지를 찾는 스크립트를 작성하세요.

내 솔루션

이것은 매우 간단하므로 많은 설명이 필요하지 않습니다. 두 개의 목록을 계산했는데, 출발지는 경로 목록의 첫 번째 값을 갖고 목적지는 두 번째 값을 갖습니다.

그런 다음 목록 이해를 사용하여 출발지 목록에 없는 목적지를 찾고 이를 막다른 골목으로 저장합니다. 이 목록에 정확히 하나의 항목이 없으면 오류가 발생합니다.

def no_connection(routes: list) -> str:
    origins = [v[0] for v in routes]
    destinations = [v[1] for v in routes]
    dead_ends = [d for d in destinations if d not in origins]

    if len(dead_ends) > 1:
        raise ValueError(
            'There are multiple routes with no outgoing connection')

    if len(dead_ends) == 0:
        raise ValueError('All routes have an outgoing connection')

    return dead_ends[0]

예

$ ./ch-1.py B C C D D A
A

$ ./ch-1.py A Z
Z

작업 2: 변경하기

일

주어진 금액을 센트 단위로 잔돈으로 바꾸는 방법의 수를 계산하세요. 예를 들어 동전을 사용하여 페니, 니켈, 다임, 쿼터, 하프달러 등 총 가치가 주어진 금액과 같을 수 있는 방법은 몇 가지입니까? 코인 선택 순서는 상관없습니다.

• 1페니(P)는 1센트와 같습니다.
• 니켈(N)은 5센트입니다.
• 1다임(D)은 10센트와 같습니다.
• 쿼터(Q)는 25센트와 같습니다.
• 반달러(HD)는 50센트입니다.

내 솔루션

내 코드의 (현재 수정된) 버그로 인해 이 작업을 완료하는 데 예상보다 시간이 조금 더 걸렸습니다. Python과 Perl 모두 디버거가 있다는 것을 알고 있지만 때로는 print 문을 이길 수 없을 때도 있습니다 :)

재귀 함수를 사용해야 하는 작업을 수행한 지 꽤 오래되었습니다. 이 작업을 위해 남은 변경 사항과 마지막으로 사용된 동전을 가져오는 Making_change라는 재귀 함수가 있습니다. 첫 번째 호출에서는 남은_change 값을 입력으로 설정하고 last_coin 값을 None(Perl에서는 undef)으로 설정합니다.

각 호출은 가능한 코인을 반복하고 다음 세 가지 작업 중 하나를 수행합니다.

1. 코인 값이 last_coin 값보다 크면 건너뜁니다. 이렇게 하면 가능한 조합이 중복되지 않습니다.
2. 코인 값이 남은 잔돈과 같다면 유효한 해결책이 있는 것이므로 조합 값에 1을 더합니다.
3. 코인 값이 남은 값보다 적으면 사용한 코인만큼 남은 값을 줄여 함수를 다시 호출합니다.

조합 값은 업스트림으로 전달되므로 최종 반환에는 올바른 조합 수가 포함됩니다.

def making_change(remaining: int, last_coin: int | None = None) -> int:
    combinations = 0

    for coin in [1, 5, 10, 25, 50]:
        if last_coin and last_coin < coin:
            continue
        if coin == remaining:
            combinations += 1
        if coin < remaining:
            combinations += making_change(remaining-coin, coin)

    return combinations

재귀에는 제한이 있습니다. Perl은 재귀가 (100 깊이) [https://perldoc.perl.org/perldiag#Deep-recursion-on-subroutine-%22%25s%22]일 때 경고합니다. 이 값은 Perl을 다시 컴파일해야만 변경할 수 있습니다. 기본적으로 Python은 995회 재귀 후에 (ResursionError)[https://docs.python.org/3/library/Exceptions.html#RecursionError]를 발생시킵니다. 하지만 이 값은 런타임에 수정될 수 있습니다.

예

$ ./ch-2.py 9
2

$ ./ch-2.py 15
6

$ ./ch-2.py 100
292

위 내용은 연결하기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!