Início / coding / Perguntas / 79371937
Accepted
ABGR
Asked: 2025-01-21 00:02:52 +0800 CST

Número de maneiras de chegar ao ponto A ao ponto B subindo um degrau, dois degraus ou três degraus de cada vez

  • 772

Eu estava resolvendo um teste em uma plataforma online e o problema era parecido com este.

Stuart tem que ir de um lugar para outro (A-> B) e ele pode pular 1 passo, 2 passos ou 3 passos de cada vez. Pode haver n número de paradas entre A e B.

Precisamos descobrir quantas maneiras ele pode fazer isso.

Eu sinto que isso é similar ao problema clássico de subir escadas com pouca diferença de que lá você finalmente tinha que chegar ao n-ésimo degrau, enquanto neste problema em particular você tem que descer, o que faz provavelmente n+1 degrau. Estou certo?

Então o código que escrevi é este:

function countWays(n) {
    
    if (n < 0) return 0;
    if (n === 0) return 1;
    if (n === 1) return 2; //If you have one stop-over, there's two ways to reach. One is take one jump and then one more. Second is take two jumps at once and reach the destination

    return countWays(n-1) + countWays(n-2) + countWays(n-3);
 
}

console.log(countWays(4))

Isso não foi aceito. Então, estou apenas me perguntando o que há de errado nisso. Eu deveria ter adicionado base case para n==2também?

if (n === 2) return 4

Isso ainda não adianta nada, pois n = 3retornaria 6, enquanto visualmente posso ver que haveria 7 maneiras se houvesse 3 paradas.

Outra pergunta que quero fazer é:

No caso clássico de escada, o caso base para n === 0seria 1. Ainda seria o mesmo aqui? Isso me confunde um pouco, pois quando não há mais degraus para subir, como o resultado pode ser 1. Por outro lado, aqui, quando n === 1você ainda tem um caminho que deve seguir para chegar ao destino.

Além disso, f(3)a lógica e a intuição dizem que deveria ser:

number of ways to reach first stopover + f(2)

E number of ways to reach first stopoverseria apenas um, já que só há uma maneira de fazer isso (dando um salto).

No entanto, não posso colocar if(n == 1) return 1no caso base, pois seria incorreto. Digamos que há apenas uma parada (n = 1), na verdade há duas maneiras de chegar:

  1. Pular 2 passos
  2. Pule 1 passo e depois mais um.

Então isso também está criando um pouco de confusão.

algorithm

1 respostas

  1. Best Answer

    Eu sinto que isso é similar ao problema clássico de subir escadas... enquanto que neste problema em particular você tem que descer, o que provavelmente dá n+1 passo. Estou certo?

    Sim.

    Eu deveria ter adicionado o caso base para n==2 também?

    Sim, ou você poderia adicionar mais facilmente o n == -1caso, porque ele representa o caso em que você chegou ao destino, e representa uma possibilidade (1). Isso parece estranho, mas é consistente com sua observação anterior de que a maneira como esse problema é declarado difere com 1 passo em comparação com a frase com a qual você estava mais acostumado. O caso em que n < -1é onde você ultrapassa o destino, e é quando você quer retornar 0. Na verdade, você não precisa de outros casos além da chegada exata ( n == -1) e da ultrapassagem ( n < -1). O resto decorre disso.

    Aqui está seu código adaptado:

    function countWays(n) {
    if (n < -1) return 0; // Overshooting: not a possibility.
    if (n === -1) return 1; // Destination reached: this is a possibility and thus counts as one.
    return countWays(n-1) + countWays(n-2) + countWays(n-3);
}

for (let n = 0; n < 5; n++) {
    console.log(n, countWays(n));
}

    Agora, isso não é eficiente, pois para n, você fará as mesmas chamadas recursivas repetidamente. Você pode usar a tabulação bottom up para ter uma solução eficiente:

    function countWays(n) {
    let [a, b, c] = [0, 0, 1];
    while (n-- > -1) {
        [a, b, c] = [b, c, a + b + c];
    }
    return c;
}

for (let n = 0; n < 5; n++) {
    console.log(n, countWays(n));
}

    • 1

relate perguntas