Membuat perhubungan

Cabaran Mingguan 285

Setiap minggu Mohammad S. Anwar menghantar Cabaran Mingguan, peluang untuk kita semua mencari penyelesaian kepada dua tugas mingguan. Penyelesaian saya ditulis dalam Python terlebih dahulu, dan kemudian ditukar kepada Perl. Ini cara yang bagus untuk kita semua mempraktikkan beberapa pengekodan.

Cabaran, Penyelesaian saya

Tugasan 1: Tiada Sambungan

Tugasan

Anda diberi senarai laluan, @laluan.

Tulis skrip untuk mencari destinasi tanpa sambungan keluar lagi.

penyelesaian saya

Ini agak lurus ke hadapan jadi tidak memerlukan terlalu banyak penjelasan. Saya mengira dua senarai, asal mempunyai nilai pertama daripada senarai laluan manakala destinasi mempunyai nilai kedua.

Saya kemudian menggunakan pemahaman senarai untuk mencari destinasi yang tiada dalam senarai asal dan menyimpannya sebagai dead_ends. Saya membangkitkan ralat jika tidak terdapat satu item dalam senarai ini.

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]

Contoh

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

$ ./ch-1.py A Z
Z

Tugasan 2: Membuat Perubahan

Tugasan

Hitung bilangan cara untuk membuat perubahan bagi jumlah tertentu dalam sen. Dengan menggunakan syiling cth. Penny, Nickel, Dime, Quarter dan Separuh dolar, dalam berapa banyak cara yang berbeza boleh jumlah nilai sama dengan jumlah yang diberikan? Pesanan pemilihan syiling tidak penting.

• Satu sen (P) bersamaan dengan 1 sen.
• Nikel (N) bersamaan dengan 5 sen.
• Sepeser pun (D) bersamaan dengan 10 sen.
• Suku (Q) bersamaan dengan 25 sen.
• Setengah dolar (HD) bersamaan dengan 50 sen.

penyelesaian saya

Disebabkan pepijat (kini telah diperbaiki) dalam kod saya, ini mengambil masa lebih lama untuk diselesaikan daripada yang saya harapkan. Saya tahu kedua-dua Python dan Perl mempunyai penyahpepijat, tetapi kadang-kadang anda tidak boleh mengalahkan kenyataan cetakan :)

Sudah agak lama kami tidak mempunyai tugasan yang memerlukan penggunaan fungsi rekursif. Untuk tugasan ini, saya mempunyai fungsi rekursif yang dipanggil making_change yang mengambil baki perubahan, dan syiling yang terakhir digunakan. Panggilan pertama menetapkan baki_tukar nilai kepada input dan nilai last_coin kepada Tiada (undef dalam Perl).

Setiap panggilan berulang melalui syiling yang mungkin, dan melakukan salah satu daripada tiga perkara:

1. Jika nilai syiling lebih besar daripada nilai last_coin, kami melangkaunya. Ini memastikan bahawa kami tidak menduplikasi kemungkinan gabungan.
2. Jika nilai syiling adalah sama dengan baki perubahan, kami mempunyai penyelesaian yang sah, jadi saya menambah satu pada nilai gabungan.
3. Jika nilai syiling kurang daripada nilai baki, saya panggil fungsi itu semula dengan nilai baki dikurangkan dengan syiling yang digunakan.

Nilai gabungan dihantar ke huluan supaya pulangan akhir akan mempunyai bilangan gabungan yang betul.

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

Terdapat had untuk pengulangan. Perl akan memberi amaran apabila rekursi adalah (100 dalam)[https://perldoc.perl.org/perldiag#Deep-recursion-on-subroutine-%22%25s%22]. Nilai ini hanya boleh diubah dengan menyusun semula Perl. Secara lalai, Python akan menaikkan (ResursionError)[https://docs.python.org/3/library/exceptions.html#RecursionError] selepas 995 ulangan, walaupun nilai ini boleh diubah suai pada masa jalan.

Contoh

$ ./ch-2.py 9
2

$ ./ch-2.py 15
6

$ ./ch-2.py 100
292

Atas ialah kandungan terperinci Membuat perhubungan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!