Algorithmes
Introduit| English | Sens |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algorithme |
| flowchart/ˈfləʊtʃɑːt/ | organigramme |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudo-code |
| tracing/ˈtreɪsɪŋ/ | suivi |
| binary search/ˈbaɪnəri sɜːtʃ/ | recherche binaire |
| linear search/ˈlɪnɪə sɜːtʃ/ | recherche linéaire |
| efficiency/ɪˈfɪʃənsi/ | efficacité |
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.
Quelles conditions sont requises pour qu'une suite d'étapes soit un algorithme ? Choisissez toutes les réponses applicables.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Une procédure résolvant la tâche finie déclarée nécessite des étapes sans ambiguïté, des résultats corrects et une terminaison sur les entrées autorisées. La pseudocode et les organigrammes sont des représentations, pas des exigences d'utilisation d'un langage de programmation particulier.
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)
Reliez chaque forme d'organigramme à sa signification.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Utilisez des rectangles de processus, des losanges de décision et des terminaux début/fin comme indiqué ; l'entrée/sortie est normalement représentée par un parallélogramme. Étiquetez les branches de décision et les directions de flux.
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.
Recherche linéaire contre recherche binaire
Diviser par deux bat la vérification un par un, et l'écart s'élargit avec la taille de la liste.
En utilisant des bornes inclusives zéro-based et floor((low+high)/2), combien de comparaisons la recherche binaire utilise-t-elle pour trouver 7 dans [1,3,5,7,9,11] ?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Les indices centraux sont 2, 4, puis 3, avec les valeurs 5, 9 et 7. Trois comparaisons selon la convention spécifiée.
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.
Pour une liste déjà triée d'un million d'éléments, environ combien de comparaisons de valeur centrale la recherche binaire peut-elle nécessiter dans le cas pire ?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Chaque comparaison réduit de moitié la plage de recherche restante ; environ 20 comparaisons suffisent pour un million d'éléments ordonnés. Cela exclut tout coût de tri préalable.
Une recherche binaire fonctionne sur une liste non triée, mais plus lentement.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Sans l'ordre requis, éliminer une moitié peut faire manquer un élément présent. Certains cas peuvent par hasard réussir, mais la correction n'est pas garantie.
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.