Broken Ways (problema di logica)

Questo problema è stato pubblicato sul sito web della Newton School, "Domanda del giorno 9/gen/2023".

Dichiarazione problema:

Newton vuole raggiungere la cima di una scala che ha dei gradini rotti (non può visitare quei gradini). Può salire 1 o 2 gradini alla volta.

Esempio di una scala di 15 gradini con i gradini 3 e 9 rotti. I passi validi da visitare sono: 1,2, 4,5,6,7,8, 10,11,12,13,14,15.

Un modo possibile per raggiungere la cima di questa scala è visitare i gradini: 2,4,5,7,8,10,12,14,15 (a volte Newton ha salito 1 gradino e altre ne ha saliti 2).

Lo scopo del problema è trovare il numero di modi diversi in cui Newton può raggiungere la cima della scala.

Qui mostro una soluzione:

Questo problema ricorda la “Sequenza di Fibonacci”. Ma perché? Perché dal momento che puoi raggiungere un passaggio solo dal passaggio 1 o dal passaggio 2, il numero di modi in cui puoi raggiungere un passaggio è la somma di "modi in cui puoi raggiungere il passaggio 1" + "modi in cui puoi raggiungere il passaggio 2 ”.

Quindi, per raggiungere il gradino 1, hai solo 1 modo (salire da terra al gradino 1); per raggiungere lo step 2 hai 2 modi (salire da terra direttamente allo step 2 o salire dallo step 1), per raggiungere lo step 3 hai 3 modi (1 via dallo step 1 + 2 vie dallo step 2), per raggiungere lo step 4 hai hai 5 vie (2 vie dal punto 2 + 3 vie dal punto 3), per raggiungere il punto 5 hai 8 vie (3 vie dal punto 3 + 5 vie dal punto 4) e così via fino all'ultimo punto.

Ma questa è esattamente la sequenza di Fibonacci! Sì, ma questo problema ha una svolta, sono stati aggiunti "passi interrotti" . Ok, nessun problema, poiché Newton non può visitare i gradini rotti, basta impostare 0 modi per raggiungerli.

Tornando al nostro esempio, con i passaggi 3 e 9 interrotti, abbiamo questa "sequenza interrotta di Fibonacci" : 1, 2, 0, 2, 2, 4, 6, 10, 0, 10, 10, 20, 30, 50, 80.

Quindi, su questa scala, Newton ha 80 modi diversi per salirla.

Ora puoi implementare l'algoritmo di sequenza spezzata di Fibonacci nel tuo linguaggio di programmazione preferito e caricarlo sul sito Web della Newton School , che ha molti problemi interessanti da risolvere nella sessione Domanda del giorno.

Divertiti!