Algorithms · Algorithmes
| English | Français |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algorithme |
| flowchart/ˈfləʊtʃɑːt/ | diagramme de flux |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudocode |
| tracing/ˈtreɪsɪŋ/ | tracé |
| 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.
Indiquez quelles entrées la procédure doit gérer
- Un algorithme décrit des étapes non ambiguës pour une tâche. Une procédure résolvant une tâche finie déclarée doit s'arrêter et donner le bon résultat pour toute entrée autorisée.
- Une trace réussie sur une seule entrée montre ce cas, pas une preuve pour toutes les entrées. Les cas limites et les entrées vides peuvent révéler des erreurs qu'un exemple typique omet.
Which are required for a sequence of steps to be an algorithm? Choose all that apply. · Quelles conditions sont requises pour qu'une suite d'étapes soit un algorithme ? Choisissez toutes les réponses applicables.
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. · 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.
Représentez clairement les choix et les mises à jour
- Un organigramme utilise un losange de décision, un rectangle de traitement, un parallélogramme d'entrée/sortie et une borne de début/fin, reliés par des flèches de flux dirigées.
- Pseudocode décrit les étapes sans imposer une implémentation en langage spécifique. Définissez la signification des affectations, l'origine des indices, les bornes de boucle et les conditions de branchement avant de tracer.
Match each flowchart shape to what it means. · Reliez chaque forme d'organigramme à sa signification.
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. · 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.
Enregistrez les valeurs réelles des variables
- Tracage suit les mises à jour déclarées dans l'ordre. Une variable temporaire peut conserver une valeur qui serait autrement écrasée.
- Montrez le bas, le haut, le milieu et la valeur comparée pour une recherche binaire ; montrez chaque variable modifiée pour une boucle arithmétique. Évaluez ce que fait la procédure, pas seulement son but prévu.
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.
Une convention spécifiée de recherche binaire. Utilisez des bornes inclusives indexées à partir de zéro et la partie entière de leur moyenne pour le milieu. Chercher 7 dans [1,3,5,7,9,11] compare l'indice 2/valeur 5, l'indice 4/valeur 9, puis l'indice 3/valeur 7. Le nombre de comparaisons est trois selon cette convention.
Linear against binary search · Recherche linéaire contre recherche binaire
Halving beats checking one at a time, and the gap widens with the list. · Diviser par deux bat la vérification un par un, et l'écart s'élargit avec la taille de la liste.
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]? · 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] ?
Middle indices are 2, 4, then 3, with values 5, 9 and 7. Three comparisons under the specified convention. · 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.
Comparez les travaux sous leurs hypothèses
- Une recherche linéaire peut s'arrêter tôt mais peut inspecter tous les n éléments. Une recherche binaire divise successivement par deux un intervalle de recherche trié et nécessite des mises à jour cohérentes des bornes.
- Efficacité décrit comment le travail requis évolue avec la taille de l'entrée selon un modèle défini. Trier d'abord a son propre coût ; une entrée non triée ne peut compter sur la garantie d'ordre de la recherche binaire.
For an already sorted million-item list, approximately how many middle-value comparisons can binary search need in the worst case? · 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 ?
Each comparison halves the remaining search range; about 20 comparisons suffice for a million ordered items. This excludes any cost of sorting beforehand. · 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.
A binary search works on an unsorted list, just more slowly. · Une recherche binaire fonctionne sur une liste non triée, mais plus lentement.
Without the required ordering, discarding a half can miss a present item. Some cases may happen to succeed, but correctness is not guaranteed. · 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.
Vérifiez zéro et le dernier indice autorisé. La fiche 4.4 examine une boucle de somme utilisant i inférieur à n, ce qui omet le dernier terme. Son tracé euclidien explique aussi la terminaison : chaque diviseur positif est remplacé par un reste non négatif plus petit jusqu'à ce que zéro soit atteint.