Perguntas[algorithm](coding)

Tenho várias listas que preciso combinar. Cada uma dessas listas tem uma ordem, e cada ordem é consistente com a ordem da lista original. (Por consistente, quero dizer que cada lista pode ser reproduzida removendo itens da lista original, sem reorganizar nenhum item .)

Meu problema é que não tenho a lista original e tenho que reproduzi-la o mais fielmente possível usando as listas parciais que tenho.

Por exemplo, considere as seguintes listas ordenadas:

a = ["first", "fourth", "fifth", "sixth", "eighth", "sophomore", "junior"]
b = ["second", "third", "fourth", "sixth", "seventh", "eighth", "freshman", "sophomore", "senior"]
c = ["first", "second", "freshman", "sophomore", "junior", "senior"]
...
partial_lists = [a, b, c, ...]

A partir dessas três listas, é possível recuperar a lista original. Em alguns casos, porém, isso pode não ser possível. De qualquer forma, quero criar uma lista merged_listque merged_listpreserve a ordem de cada uma das listas parciais. (Ou seja, qualquer lista parcial especificada poderia, teoricamente, ser reconstruída merged_listusando apenas merged_list.remove()operações.) É seguro assumir que cada lista parcial não contém duplicatas e merged_listtambém não deve conter nenhuma duplicata.

Para este exemplo, merged_listseria["first", "second", "third", "fourth", "fifth", "sixth", "seventh", "eighth", "freshman", "sophomore", "junior", "senior"]

Existe um algoritmo eficiente que pode lidar com isso para um número arbitrário de listas parciais?

Entendo que podemos reconstruir uma árvore binária a partir de sua travessia em ordem E (pós-ordem OU pré-ordem).

No entanto, eu me pergunto se reconstruí-lo a partir de sua travessia de pós-ordem E pré-ordem também é possível?

No problema clássico de soma de subconjuntos, há um conjunto S e um alvo t, e o objetivo é encontrar um subconjunto de S cuja soma seja t. Esta variante tem uma solução em tempo pseudopolinomial.

Em uma variante do problema da soma de subconjuntos, o objetivo é encontrar todos os subconjuntos de S cuja soma é t. Esta variante não possui solução em tempo pseudopolinomial; veja as respostas aqui: Obtendo todos os subconjuntos do problema da soma de subconjuntos em Python usando Programação Dinâmica . Um dos comentários explica que, no pior caso, quando você tem N zeros e a soma necessária também é zero, você precisará gerar todos os 2^n - 1 subconjuntos - portanto, não é possível obter um resultado melhor que O(2^n).

E se não diferenciarmos entre dois itens do mesmo valor (de modo que, se dois conjuntos forem compostos de alguns itens com os mesmos valores, eles serão considerados o mesmo conjunto) --- qual é a complexidade de tempo de execução para gerar todos os diferentes subconjuntos com soma t?

Olá, tentei resolver o problema abaixo por 5 horas, mas não consegui encontrar a resposta. O título desta pergunta é "Classificação em Linear", então presumo que a resposta ideal deva ter complexidade de tempo O(n). A pergunta está escrita abaixo.

===================================================

Você tem um array de n inteiros originalmente ordenado em ordem crescente. No entanto, até ⌊√n/2⌋ trocas arbitrárias foram feitas entre pares de elementos no array. Consequentemente, no máximo √n elementos podem estar fora de suas posições corretas. Você deve reordenar este array em ordem crescente usando um algoritmo com a menor complexidade de tempo possível.

===================================================

O que descobri até agora é que, se você conseguir encontrar quais elementos estão na posição errada em O(n), a ordenação em si também deve assumir O(n). Mas não sei mais o que fazer :(

Algoritmo LinearSort(A):

n ← length(A)
misplacedIndices ← empty set

// Step 1: Identify indices of potentially misplaced elements
   misplacedIndices.add(i) // Do this somehow(!!!!)


// sort indices in ascending order -> takes O(√n · log(√n))
misplacedIndices ← sorted(misplacedIndices)

// Step 2: Separate misplaced elements from correctly placed ones
misplacedList ← empty list
remainderList ← empty list
for i ← 0 to n - 1 do:
    if i ∈ misplacedIndices then:
        misplacedList.append(A[i])
    else:
        remainderList.append(A[i])
end for

// Sort the misplaced elements (only up to O(√n) elements)
sort(misplacedList)  // Time complexity: O(√n · log√n)

// Step 3: Merge the two sorted lists (remainderList and misplacedList)
result ← empty list
i ← 0, j ← 0
while i < length(remainderList) and j < length(misplacedList) do:
    if remainderList[i] ≤ misplacedList[j] then:
        result.append(remainderList[i])
        i ← i + 1
    else:
        result.append(misplacedList[j])
        j ← j + 1
end while

// Append any remaining elements from either list
while i < length(remainderList) do:
    result.append(remainderList[i])
    i ← i + 1
end while

while j < length(misplacedList) do:
    result.append(misplacedList[j])
    j ← j + 1
end while

return result

Examine o pseudocódigo da página da Wikipedia sobre ordenação por inserção :

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

Por favor, explique por que isso é afirmado na literatura :

The number of exchanges used by insertion sort is equal to the number of 
inversions in the array, and the number of compares is at least equal to 
the number of inversions and at most equal to the number of inversions
plus the array size minus 1.

Uma troca de elemento adjacente (ou seja, do ' elemento selecionado atual ', com aqueles no subarray ordenado (ou seja, começando da extremidade esquerda do array original)) removeria apenas uma inversão.
Embora para uma lista dada de elementos, introduzir uma troca pode adicionar muitas inversões; digamos para a lista: 123, trocando o elemento 3com o elemento 1, que introduz 3inversões.
E o número de comparações necessárias é três:

i=1:<2,3>, i=2:<1,3>, <1,2>

Além disso, o número de inversões é três na lista:321

Esse número de inversões também é dado por nC2, onde né o tamanho da lista.

Digamos, para uma lista de tamanho ordenada reversamente 4: 4321, tenha seis inversões: <4,3>,<4,2>,<4,1>,<3,2>,<3,1>,<2,1>, que também é o número de 2-subconjuntos, de um n-conjunto. Em ambos os problemas, devido à ausência de ordenação envolvida, tenha o número de combinações a serem contadas.

As etapas (comparações+trocas) envolvidas na aplicação da ordenação por inserção à lista ordenada inversamente <4321>são:

1. i ← 1, j ← 1, A[0] > A[1]:    swap A[1] and A[0], j ← 0:     <3421>
2. i ← 2, j ← 2, A[1] > A[2]:    swap A[2] and A[1], j ← 1:     <3241>
          j ← 1, A[0] > A[1]:    swap A[1] and A[0], j ← 0:     <2341>
3. i ← 3, j ← 3, A[2] > A[3]:    swap A[3] and A[2], j ← 2:     <2314>
          j ← 2, A[1] > A[2]:    swap A[2] and A[1], j ← 1:     <2134>
          j ← 1, A[0] > A[1]:    swap A[1] and A[0], j ← 0:     <1234>

Mas, não consigo entender quando o número máximo de comparações é igual a number of inversions + array size -1; quanto ao pior caso de uma matriz de classificação reversa, de tamanho n; o número de inversões é igual a nC2.

De onde viriam as demais comparações, ou seja, 'n-1'as comparações?

A literatura mencionada acima afirma que a fonte dessas 'n-1'comparações é:

additional compare might happen for the value of `i` from `1` to `n-1` (when `a[i]` does not reach the left end of the array).

Há confusão causada pela parte, entre colchetes; como o que se quer dizer com: (when a[i] does not reach the left end of the array).
Este caso pode significar o caso de listas, onde o 'primeiro elemento' (i=0)está em sua posição final, digamos: 1423. Ou em outras palavras, fala sobre all the possiblecomparações, incluindo aquela em que há noinversão.

Digamos que, para 1423, há duas inversões, mas é preciso ter comparações extras de: <1,4>, <1,2>, <1,3>, <2,3>. Mas, essas são então quatro comparações, não três (tamanho da matriz: 4 menos 1).

Também não estou claro sobre o texto usado na literatura, pois tal comparação não é mostrada explicitamente no algoritmo.

A mesma literatura lista seu código C++ para Insertion-sort aqui , que também não mostra explicitamente nenhuma comparação desse tipo.

Uma nova ferramenta de geração de código recebe apenas uma entrada - n, o tamanho de um array de entrada. A ferramenta deve então gerar um programa de árvore de decisão simples que contém 2 tipos de nós:

• nó de decisão com comparação estrita
• nó de saída (folha)

O nó de decisão compara dois elementos de uma matriz de entrada usando 1 de 3 operadores - <, =, >. Combinações desses operadores NÃO são permitidas. Usar operadores booleanos extras como NOT, AND, OR também não é permitido.

Um nó de saída especifica quais elementos retornar do array de entrada. Esses elementos devem ter todos o mesmo valor e esse valor é o mínimo de todo o array de entrada.

Até agora, tentei usar uma abordagem baseada em pilha que gera código correto para array de entrada de comprimento 2, mas falha para cada comprimento maior. A saída se parece com isso:

if input[0] < input[1]:
    return input[0]
else:
    if input[0] == input[1]:
        return input[0, 1]
    else:
        return input[1]

Aqui está meu código:

Node.kt

import ComparisonOperator.*

enum class ComparisonOperator {
    LESS_THAN, EQUALS, GREATER_THAN
}

class Node (
    val trueBranch: Node? = null,
    val falseBranch: Node? = null,
    val operator: ComparisonOperator = LESS_THAN,
    val indices: IntArray = intArrayOf()
)

imprimir.kt

import TaskType.*

enum class TaskType {
    PROCESS_NODE,
    PROCESS_ELSE
}

data class StackEntry(val node: Node, val indent: Int, val taskType: TaskType)

fun generatePythonCode(root: Node): String {
    val builder = StringBuilder()
    val stack = ArrayDeque<StackEntry>()
    stack.addLast(StackEntry(root, 0, PROCESS_NODE))

    while (stack.isNotEmpty()) {
        val entry = stack.removeLast()
        val node = entry.node
        val indent = entry.indent
        val indentStr = "    ".repeat(indent)

        when (entry.taskType) {
            PROCESS_NODE -> {
                if (node.trueBranch == null) {
                    // Leaf node: output the return statement.
                    val indices = node.indices.joinToString(", ")
                    builder.append(indentStr).append("return input[").append(indices).append("]\n")
                } else {
                    // Decision node: output an if statement.
                    val left = "input[${node.indices[0]}]"
                    val right = "input[${node.indices[1]}]"
                    val op = when (node.operator) {
                        ComparisonOperator.LESS_THAN -> "<"
                        ComparisonOperator.EQUALS -> "=="
                        ComparisonOperator.GREATER_THAN -> ">"
                    }
                    builder.append(indentStr).append("if ").append(left).append(" $op ").append(right).append(":\n")
                    // Push the false branch as an else task (it will add the "else:" line).
                    stack.addLast(StackEntry(node.falseBranch!!, indent, PROCESS_ELSE))
                    // Then push the true branch for processing with increased indent.
                    stack.addLast(StackEntry(node.trueBranch, indent + 1, PROCESS_NODE))
                }
            }
            PROCESS_ELSE -> {
                // For an else task, output the "else:" line and then process the node.
                builder.append(indentStr).append("else:\n")
                stack.addLast(StackEntry(node, indent + 1, PROCESS_NODE))
            }
        }
    }
    return builder.toString().trimEnd()
}

codegen.kt

import ComparisonOperator.*

enum class FrameType {
    EQUALITY,
    MERGE
}

// Each frame holds the current candidate groups (each a List<Int>).
// When the number of candidate groups is 1, a leaf (output) node is produced.
// Otherwise, two candidate groups are extracted and processed.
data class Frame(
    val candidates: List<List<Int>>,
    val type: FrameType,
    var step: Int = 0,
    var group1: List<Int>? = null,
    var group2: List<Int>? = null,
    var rest: List<List<Int>> = emptyList(),
    // For a MERGE frame, we need:
    // branchTrue: result for candidate list [group1] + rest.
    // branchEquality (i.e. the nested equality decision) will be built from two subbranches.
    // For an EQUALITY frame, we only need branchTrue and branchFalse.
    var branchTrue: Node? = null,
    var branchFalse: Node? = null,
    // Temporary field to hold a generated child result.
    var tempResult: Node? = null
)

// The function generateMinProgram builds the decision tree (as Node objects) that, when interpreted,
// returns the indices of all occurrences of the minimum element from the input array.
// It uses a brute-force backtracking strategy based on a stack.
fun generateMinProgram(n: Int): Node {
    // Assume n >= 2. Initially, each candidate group is a single index.
    val initialCandidates = (0 until n).map { listOf(it) }
    val stack = ArrayDeque<Frame>()
    // The outermost decision is always a MERGE.
    stack.add(Frame(candidates = initialCandidates, type = FrameType.MERGE))

    // The iterative DFS: process the frames until the root decision is built.
    var result: Node? = null

    while (stack.isNotEmpty()) {
        val current = stack.last()
        // If the candidate list has only one candidate group, create a leaf (output) node.
        if (current.candidates.size == 1) {
            // This candidate group represents the indices that are equal to the minimum.
            result = Node(
                trueBranch = null,
                falseBranch = null,
                // For output nodes the operator value is not used.
                operator = LESS_THAN,
                indices = current.candidates.first().toIntArray()
            )
            stack.removeLast()
            if (stack.isNotEmpty()) {
                // Propagate the result to the parent frame.
                stack.last().tempResult = result
            } else {
                // No parent exists; this would happen if n==1 (but we assume n>=2).
                return result
            }
            continue
        }

        // Otherwise, there is at least a decision to be made.
        when (current.type) {
            FrameType.MERGE -> {
                // MERGE frame has three main phases.
                when (current.step) {
                    0 -> {
                        // Initialize: pick the first two candidate groups.
                        current.group1 = current.candidates[0]
                        current.group2 = current.candidates[1]
                        current.rest = if (current.candidates.size > 2) current.candidates.subList(2, current.candidates.size) else emptyList()
                        // Process the "true" branch for the primary decision:
                        // if input[group1[0]] < input[group2[0]] then the winner is group1.
                        val trueCandidates = listOf(current.group1!!) + current.rest
                        // New frame for processing the "true" branch.
                        stack.add(Frame(candidates = trueCandidates, type = FrameType.MERGE))
                        current.step = 1
                    }
                    1 -> {
                        // Coming back from the "true" branch.
                        current.branchTrue = current.tempResult
                        current.tempResult = null
                        // Next, process the nested equality decision.
                        // Create a new EQUALITY frame.
                        // For equality: if input[group1[0]] == input[group2[0]], then we merge group1 and group2.
                        // The candidate list becomes [group1 U group2] + rest.
                        val merged = current.group1!! + current.group2!!
                        val eqCandidates = listOf(merged) + current.rest
                        stack.add(Frame(candidates = eqCandidates, type = FrameType.EQUALITY))
                        current.step = 2
                    }
                    2 -> {
                        // Returning from the equality branch's "true" part (for the equality decision).
                        // In a MERGE frame, we now go to process the "false" branch of the nested equality:
                        current.branchTrue = current.branchTrue // holds nothing new; we now reuse the equality structure.
                        // For the "false" branch of the equality decision (i.e. when input[group1[0]] is not equal to input[group2[0]])
                        // we take group2 as the winner. Candidate list becomes [group2] + rest.
                        val falseCandidates = listOf(current.group2!!) + current.rest
                        stack.add(Frame(candidates = falseCandidates, type = FrameType.EQUALITY))
                        current.step = 3
                    }
                    3 -> {
                        // Coming back from the equality frame "false" branch.
                        current.branchFalse = current.tempResult
                        current.tempResult = null
                        // Build the nested equality decision node.
                        // This node has operator EQUALS and compares the same indices from group1 and group2.
                        val eqNode = Node(
                            trueBranch = current.tempResult ?: run {
                                // The true branch result is already stored in branch from the equality frame "true",
                                // which was set when processing the equality frame. In this MERGE frame, we expect the equality
                                // decision to have been constructed by processing the two equality branches.
                                // Here we use current.branchTrue that was computed in step 2.
                                current.branchTrue
                            },
                            falseBranch = current.branchFalse,
                            operator = EQUALS,
                            indices = intArrayOf(current.group1!![0], current.group2!![0])
                        )
                        // Build the primary decision node.
                        val mergeNode = Node(
                            trueBranch = current.branchTrue,
                            falseBranch = eqNode,
                            operator = LESS_THAN,
                            indices = intArrayOf(current.group1!![0], current.group2!![0])
                        )
                        stack.removeLast() // Done with current MERGE frame.
                        if (stack.isNotEmpty()) {
                            stack.last().tempResult = mergeNode
                        } else {
                            return mergeNode
                        }
                    }
                }
            }
            FrameType.EQUALITY -> {
                // EQUALITY frame has two phases.
                when (current.step) {
                    0 -> {
                        // In an EQUALITY frame the comparison is always on the two groups that formed the candidate list.
                        // Since we always pass a candidate list with at least one candidate, if there are at least two,
                        // then we perform a decision test.
                        current.group1 = current.candidates[0]
                        current.group2 = current.candidates[0] // In an equality frame candidate list is built from either merged groups or single group2.
                        // For an EQUALITY frame, if there is more than one candidate group then we consider the first two.
                        // However, in our usages we've built the candidate list so that its size should be 1.
                        // To support a generic approach we check:
                        if (current.candidates.size >= 2) {
                            current.group2 = current.candidates[1]
                            current.rest = if (current.candidates.size > 2) current.candidates.subList(2, current.candidates.size) else emptyList()
                        } else {
                            // If candidate list size is 1, then we are at a leaf even in an equality frame.
                            val leaf = Node(
                                trueBranch = null,
                                falseBranch = null,
                                operator = EQUALS,
                                indices = current.candidates.first().toIntArray()
                            )
                            stack.removeLast()
                            if (stack.isNotEmpty()) {
                                stack.last().tempResult = leaf
                            } else {
                                return leaf
                            }
                            continue
                        }
                        // Process the "true" branch of the equality decision:
                        // If input[group1[0]] == input[group2[0]], then the result candidate list remains as-is.
                        // (In our usage, for the equality branch, candidate list is already merged.)
                        val trueCandidates = current.candidates
                        stack.add(Frame(candidates = trueCandidates, type = FrameType.EQUALITY))
                        current.step = 1
                    }
                    1 -> {
                        // Return from the "true" branch.
                        current.branchTrue = current.tempResult
                        current.tempResult = null
                        // Process the "false" branch:
                        // In our usage, the "false" branch for an EQUALITY decision comes from a candidate list built for group2.
                        // We expect that candidate list to have a single candidate group.
                        val falseCandidates = if (current.candidates.size >= 2) {
                            // Use the second candidate alone alongside any remaining candidates.
                            listOf(current.candidates[1]) + current.rest
                        } else {
                            current.candidates
                        }
                        stack.add(Frame(candidates = falseCandidates, type = FrameType.EQUALITY))
                        current.step = 2
                    }
                    2 -> {
                        // Return from the "false" branch.
                        current.branchFalse = current.tempResult
                        current.tempResult = null
                        // Build the equality decision node.
                        val eqNode = Node(
                            trueBranch = current.branchTrue,
                            falseBranch = current.branchFalse,
                            operator = EQUALS,
                            indices = intArrayOf(current.candidates[0][0], if (current.candidates.size >= 2) current.candidates[1][0] else current.candidates[0][0])
                        )
                        stack.removeLast()
                        if (stack.isNotEmpty()) {
                            stack.last().tempResult = eqNode
                        } else {
                            return eqNode
                        }
                    }
                }
            }
        }
    }
    // Should never reach here.
    return result!!
}

principal.kt

fun main() {
    val root = generateMinProgram(2)
    val code = generatePythonCode(root)
    println(code)
}

Não estou pedindo para você consertar meu código. Em vez disso, o que estou procurando é uma descrição de um algoritmo de alto nível e suas estruturas de dados. Talvez uma solução de backtracking seja suficiente?

Também é um problema XY porque o que eu realmente preciso é de uma resposta para a pergunta Como podemos derivar a fórmula para os nós de decisão estrita mínima na matriz Minimum-Finding? que não teve muitas visualizações, então estou tentando descobrir a fórmula forçando brutamente a etapa de geração de código.

Estou trabalhando em um problema de otimização para encontrar uma região que maximize uma certa função objetivo, estou usando um conjunto de coordenadas de pixel para manter o controle da região, e para cada passo adicionarei ou removerei um pixel no limite para ver se a função objetivo aumenta ou não. Espero que a região seja conectada, há alguma estrutura de dados que possa decidir rapidamente se remover um pixel tornaria a região desconectada? Aqui, assumimos que um pixel está conectado a seus quatro vizinhos.

E uma pergunta paralela: e se eu esperar que a região seja sempre simplesmente conectada? Por simplesmente conectada, quero dizer que não há buraco, e adicionar um pixel pode criar um buraco.

Estou procurando um algoritmo de busca de caminho que tenha algumas propriedades:

1. A velocidade é muito necessária, e uma vez que um objetivo é selecionado, um caminho subótimo precisa ser feito rapidamente, e então pode ser melhorado durante o movimento. Isso me faz pensar que preciso de um " algoritmo a qualquer momento "
2. O ambiente tem outros atores nele, e então muda constantemente . Isso me faz pensar em um algoritmo baseado em D* ou D* Lite , para que o caminho possa ser rapidamente substituído.

Esses dois requisitos me indicaram o Anytime D* , que parece funcionar bem, exceto pelo meu requisito final:

3. O caminho retornado deve ser rápido de seguir e direto . Caminhos produzidos pelo Campo D* são ótimos exemplos.

Existe um algoritmo que combina os aspectos desses dois algoritmos (Anytime D* e Field D*)? Se não, é possível incluir as melhorias do Anytime D* no Field D*? Ou estou esquecendo de algo e já tenho o que preciso?

Estou escrevendo isso mais tarde à noite no meu tempo, então não poderei responder a nada por algumas horas. Espero ter contexto suficiente.

Obrigado por toda e qualquer ajuda!

Existe um algoritmo que produz um embaralhamento eficiente de um uint32 em um uint32 diferente que resulta em um mapeamento 1:1 quando recebe uma semente aleatória alterável?

Minha orientação inicial sobre isso é um algoritmo em que a semente expressa de alguma forma quais bits reorganizar no número (de modo que 0000 0101 se torne 0100 1000 com a semente [0->6, 2->3]), mas não tenho certeza de como gerar uma maneira de fazer esse embaralhamento de forma eficiente.

Algumas restrições:

• A produção do algoritmo para realizar o embaralhamento a partir da semente não precisa ser muito rápida
• Na verdade, executar o shuffle em um uint32 deve ser rápido
• Não deve haver repetições na saída para uma semente fornecida (um uint32 exclusivo produz um uint32 exclusivo)

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.