Algoritmos
Introduzido| English | Significado |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algoritmo |
| flowchart/ˈfləʊtʃɑːt/ | fluxograma |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudocódigo |
| tracing/ˈtreɪsɪŋ/ | rastreamento |
| 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.
Quais são necessários para que uma sequência de passos seja um algoritmo? Selecione todos os aplicáveis.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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.
![Binary search for 7 in [1, 3, 5, 7, 9, 11]: first the middle index 2 holds 5 < 7, so go right; second, the middle index 4 holds 9 > 7, so go left; third, index 3 holds 7, found after three comparisons under this convention](/learn-media/gac_mathematics/assets/0404-binary-search-steps.png?v=1794647931)
Combine cada forma de fluxograma ao seu significado.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
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.
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.
Linear contra busca binária
Dividir pela metade supera verificar uma por uma, e a diferença aumenta com a lista.
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]?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Í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.
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?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.
Uma busca binária funciona em uma lista não ordenada, apenas mais lentamente.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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.