Jalan Rusak (masalah Logika)
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!

![Apa itu Linked List? [Bagian 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)



































