Jalan Rusak (masalah Logika)

Feb 16 2023
Masalah ini dipublikasikan di situs web Newton School, “Question of the day 9/jan/2023”. Pernyataan masalah: Newton ingin mencapai puncak tangga yang beberapa anak tangganya rusak (ia tidak dapat mengunjungi anak tangga tersebut).

Masalah ini dipublikasikan di situs web Newton School, “Question of the day 9/jan/2023”.

Pernyataan masalah:

Newton ingin mencapai puncak tangga yang beberapa anak tangganya rusak (dia tidak dapat mengunjungi anak tangga tersebut). Dia bisa menaiki 1 atau 2 anak tangga sekaligus.

Contoh tangga 15 anak tangga dengan anak tangga 3 dan 9 putus. Langkah-langkah yang valid untuk dikunjungi adalah: 1,2, 4,5,6,7,8, 10,11,12,13,14,15.

Salah satu cara yang mungkin untuk mencapai puncak tangga ini adalah dengan mengunjungi anak tangga: 2,4,5,7,8,10,12,14,15 (terkadang Newton menaiki 1 anak tangga dan lainnya ia menaiki 2 anak tangga).

Tujuan dari soal ini adalah untuk menemukan banyaknya cara berbeda yang ditempuh Newton untuk mencapai puncak tangga.

Di sini saya menunjukkan satu solusi:

Masalah ini mengingat "Deret Fibonacci". Tapi kenapa? Karena Anda hanya dapat mencapai satu langkah dari langkah-1 atau langkah-2, jumlah cara Anda dapat mencapai langkah adalah jumlah dari “cara Anda dapat mencapai langkah-1” + “cara Anda dapat mencapai langkah-2 ”.

Jadi, untuk mencapai langkah 1, Anda hanya memiliki 1 cara (memanjat dari tanah ke langkah 1); untuk mencapai langkah 2 Anda memiliki 2 cara (memanjat dari tanah langsung ke langkah 2 atau mendaki dari langkah 1), untuk mencapai langkah 3 Anda memiliki 3 cara (1 cara dari langkah 1 + 2 cara dari langkah 2), untuk mencapai langkah 4 Anda memiliki 5 cara (2 cara dari langkah 2 + 3 cara dari langkah 3), untuk mencapai langkah 5 Anda memiliki 8 cara (3 cara dari langkah 3 + 5 cara dari langkah 4) dan seterusnya hingga langkah terakhir.

Tapi ini persis dengan Deret Fibonacci! Ya, tapi masalah ini memiliki twist, "langkah-langkah yang rusak" telah ditambahkan. Oke, tidak masalah, karena Newton tidak dapat mengunjungi anak tangga yang rusak, tetapkan 0 cara untuk menjangkaunya.

Kembali ke contoh kita, dengan langkah 3 dan 9 terputus, kita memiliki "Urutan Patah Fibonacci" ini: 1, 2, 0, 2, 2, 4, 6, 10, 0, 10, 10, 20, 30, 50, 80.

Jadi, di tangga ini, Newton memiliki 80 cara berbeda untuk menaikinya.

Sekarang, Anda dapat mengimplementasikan Algoritma Urutan Pecah Fibonacci dalam bahasa pemrograman favorit Anda dan mengunggahnya ke situs web Newton School , yang memiliki banyak masalah keren untuk dipecahkan dalam sesi Question of the Day.

Selamat bersenang-senang!