Algorithms · Algoritmos
| English | Português |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algoritmo |
| flowchart/ˈfləʊtʃɑːt/ | fluxograma |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudocódigo |
| tracing/ˈtreɪsɪŋ/ | rastreio |
| binary search/ˈbaɪnəri sɜːtʃ/ | busca binária |
| linear search/ˈlɪnɪə sɜːtʃ/ | busca linear |
| efficiency/ɪˈfɪʃənsi/ | eficiência |
Say which inputs the procedure must handle
- An algorithm 算法 describes unambiguous steps for a task. A procedure solving a stated finite task must terminate and give the correct result for every allowed input.
- A successful trace on one input shows that case, not a proof for all inputs. Boundary and empty-input cases can expose errors that a typical example misses.
Diga quais entradas o procedimento deve lidar
- Um algoritmo descreve passos inequívocos para uma tarefa. Um procedimento resolvendo uma tarefa finita declarada deve terminar e fornecer o resultado correto para cada entrada permitida.
- Um rastreamento bem-sucedido em uma entrada mostra aquele caso, não uma prova para todas as entradas. Casos de fronteira e entrada vazia podem expor erros que um exemplo típico passa despercebidos.
Which are required for a sequence of steps to be an algorithm? Choose all that apply. · Quais são necessários para que uma sequência de passos seja um algoritmo? Selecione todos os aplicáveis.
A procedure solving the stated finite task needs unambiguous steps, correct results and termination on allowed inputs. Pseudocode and flowcharts are representations, not requirements to use a particular programming language. · Um procedimento que resolve a tarefa finita declarada precisa de passos inequívocos, resultados corretos e terminação nas entradas permitidas. Pseudocódigo e fluxogramas são representações, não requisitos para usar uma linguagem de programação específica.
Represent choices and updates clearly
- A flowchart 流程图 uses a decision diamond, process rectangle, input/output parallelogram and start/stop terminal, connected by directed flow arrows.
- Pseudocode 伪代码 describes the steps without requiring one implementation language. State assignment meaning, index origin, loop bounds and branch conditions before tracing.
Represente escolhas e atualizações claramente
- Um fluxograma usa um losango de decisão, retângulo de processo, paralelogramo de entrada/saída e terminal inicial/final, conectados por setas de fluxo direcionadas.
- Pseudocódigo descreve os passos sem exigir uma linguagem de implementação específica. Defina o significado da atribuição, a origem do índice, os limites do laço e as condições das ramificações antes de traçar.
Match each flowchart shape to what it means. · Combine cada forma de fluxograma ao seu significado.
Use process rectangles, decision diamonds and start/stop terminals as given; input/output is normally shown by a parallelogram. Label decision branches and flow directions. · Use retângulos de processo, losangos de decisão e terminais de início/fim conforme dado; entrada/saída é normalmente mostrada por um paralelogramo. Rotule os ramos de decisão e as direções do fluxo.
Record the actual variable values
- Tracing 追踪 follows the stated updates in order. A temporary variable may preserve a value that would otherwise be overwritten.
- Show low, high, middle and compared value for a binary search; show every changed variable for an arithmetic loop. Judge what the procedure does, not only its intended purpose.
Registre os valores reais das variáveis
- Traçagem segue as atualizações declaradas em ordem. Uma variável temporária pode preservar um valor que, de outra forma, seria sobrescrito.
- Mostre baixo, alto, meio e valor comparado para uma busca binária; mostre cada variável alterada para um laço aritmético. Julgue o que o procedimento realmente faz, não apenas seu propósito pretendido.
A specified binary-search convention. Use zero-based inclusive bounds and floor of their average for the middle. Searching for 7 in [1,3,5,7,9,11] compares index 2/value 5, index 4/value 9, then index 3/value 7. The comparison count is three under this convention.
Uma convenção especificada de busca binária. Use limites inclusivos baseados em zero e o piso da média dos limites para o índice médio. Ao buscar 7 em [1,3,5,7,9,11], compara-se o índice 2/valor 5, depois o índice 4/valor 9, e então o índice 3/valor 7. O número de comparações é três sob esta convenção.
Linear against binary search · Linear contra busca binária
Halving beats checking one at a time, and the gap widens with the list. · Dividir pela metade supera verificar uma por uma, e a diferença aumenta com a lista.
Using zero-based inclusive bounds and floor((low+high)/2), how many comparisons does binary search use to find 7 in [1,3,5,7,9,11]? · Usando limites inclusivos baseados em zero e floor((low+high)/2), quantas comparações a busca binária usa para encontrar 7 em [1,3,5,7,9,11]?
Middle indices are 2, 4, then 3, with values 5, 9 and 7. Three comparisons under the specified convention. · Índices centrais são 2, 4, depois 3, com valores 5, 9 e 7. Três comparações sob a convenção especificada.
Compare work under its assumptions
- A linear search 线性查找 can stop early but may inspect all n items. A binary search 二分查找 repeatedly halves a sorted search range and needs consistent bound updates.
- Efficiency 效率 describes how required work scales with input size under a defined model. Sorting first has its own cost; an unsorted input cannot rely on binary search's ordering guarantee.
Compare o trabalho sob suas premissas
- Uma busca linear pode parar cedo, mas pode inspecionar todos os n itens. Uma busca binária reduz repetidamente pela metade um intervalo ordenado de busca e requer atualizações consistentes de limites.
- Eficiência descreve como o trabalho necessário escala com o tamanho da entrada sob um modelo definido. Ordenar primeiro tem seu próprio custo; uma entrada não ordenada não pode confiar na garantia de ordenação da busca binária.
For an already sorted million-item list, approximately how many middle-value comparisons can binary search need in the worst case? · Para uma lista já ordenada de um milhão de itens, aproximadamente quantas comparações de valor central a busca binária pode precisar no pior caso?
Each comparison halves the remaining search range; about 20 comparisons suffice for a million ordered items. This excludes any cost of sorting beforehand. · Cada comparação reduz pela metade a faixa de busca restante; cerca de 20 comparações bastam para um milhão de itens ordenados. Isso exclui qualquer custo de ordenação prévia.
A binary search works on an unsorted list, just more slowly. · Uma busca binária funciona em uma lista não ordenada, apenas mais lentamente.
Without the required ordering, discarding a half can miss a present item. Some cases may happen to succeed, but correctness is not guaranteed. · Sem a ordenação necessária, descartar uma metade pode omitir um item presente. Alguns casos podem ter sucesso por acaso, mas a correção não é garantida.
Check zero and the last allowed index. Sheet 4.4 examines a sum loop using i less than n, which misses the last term. Its Euclidean trace also explains termination: each positive divisor is replaced by a smaller nonnegative remainder until zero is reached.
Verifique zero e o último índice permitido. A Folha 4.4 examina um laço de soma usando i menor que n, o que omite o último termo. Sua traçagem euclidiana também explica a terminação: cada divisor positivo é substituído por um resto não negativo menor até que zero seja alcançado.