Algoritmos
Introducido| English | Significado |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algoritmo |
| flowchart/ˈfləʊtʃɑːt/ | diagrama de flujo |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudocódigo |
| tracing/ˈtreɪsɪŋ/ | seguimiento |
| binary search/ˈbaɪnəri sɜːtʃ/ | búsqueda binaria |
| linear search/ˈlɪnɪə sɜːtʃ/ | búsqueda lineal |
| efficiency/ɪˈfɪʃənsi/ | eficiencia |
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.
¿Cuáles son necesarios para que una secuencia de pasos sea un algoritmo? Elija todas las que correspondan.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Un procedimiento que resuelva la tarea finita declarada necesita pasos inequívocos, resultados correctos y terminación para las entradas permitidas. El pseudocódigo y los diagramas de flujo son representaciones, no requisitos para usar un lenguaje de programación particular.
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)
Relacione cada forma de diagrama de flujo con su significado.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Use rectángulos de proceso, rombos de decisión y terminales de inicio/fin como se indica; la entrada/salida normalmente se muestra mediante un paralelogramo. Etiquete las ramas de decisión y las direcciones de flujo.
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.
Búsqueda lineal contra búsqueda binaria
Dividir a la mitad supera revisar uno por uno, y la diferencia aumenta con la lista.
Usando límites inclusivos basados en cero y floor((low+high)/2), ¿cuántas comparaciones usa la búsqueda binaria para encontrar 7 en [1,3,5,7,9,11]?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Los índices medios son 2, 4, luego 3, con valores 5, 9 y 7. Tres comparaciones bajo la convención 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 una lista ya ordenada de un millón de elementos, ¿aproximadamente cuántas comparaciones de valor medio puede necesitar la búsqueda binaria en el peor caso?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Cada comparación reduce a la mitad el rango de búsqueda restante; unas 20 comparaciones bastan para un millón de elementos ordenados. Esto excluye cualquier costo de ordenación previa.
La búsqueda binaria funciona en una lista desordenada, solo que más lentamente.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Sin el ordenamiento requerido, descartar la mitad puede omitir un elemento presente. Algunos casos pueden tener éxito por casualidad, pero la corrección no está garantizada.
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.