Conception d'algorithmes et résolution de problèmes

Le cycle de développement logiciel 程序开发生命周期 is the set of stages used to make a program. There are four stages.

Analyse

En analyse, vous comprenez le problème. Deux compétences clés aident :

• abstraction 抽象 — conserver uniquement les détails importants et ignorer le reste ;
• décomposition 分解 — diviser un grand problème en petites parties plus faciles à gérer.

Conception

En conception, vous planifiez la solution, souvent en utilisant la décomposition. Vous pouvez représenter les parties sous forme de sous-systèmes 子系统 dans un diagramme structurel 结构图 (un diagramme qui divise un système en petites boîtes).

Codage et test

En codage, vous écrivez le code du programme. Vous utilisez un test itératif 迭代测试 — testez de petites parties encore et encore au fur et à mesure de leur construction. En test, vous exécutez l'ensemble du programme avec des données de test 测试数据 pour vérifier qu'il fonctionne correctement.

Vous pouvez planifier une solution de trois manières principales.

• non diagramme structurel — montre les parties d'un système et comment elles s'emboîtent ;
• non organigramme 流程图 — un diagramme utilisant des boîtes et des flèches pour montrer les étapes dans l'ordre ;
• pseudo-code 伪代码 — étapes écrites en anglais simple, semblable à du code (pas un vrai langage).

Un algorithme 算法 is a set of steps, in the right order, that solves a problem. Every algorithm can be split into three parts :

• entrée 输入 — les données qui entrent ;
• traitement 处理 — le travail effectué sur les données ;
• sortie 输出 — le résultat qui sort.

Cela s'appelle la décomposition en entrées, traitements et sorties. Par exemple, pour « trouver la moyenne de trois notes » : les entrées sont les trois notes ; le traitement consiste à les additionner et à diviser par 3 ; la sortie est la moyenne.

Lorsqu'une donnée est saisie, vous la vérifiez pour réduire les erreurs.

La validation vérifie que les données sont sensées et respectent les règles. Elle ne peut pas vérifier que les données sont vraies, seulement qu'elles sont autorisées.

Verification 核实 vérifie que les données ont été copiées ou saisies correctement (aucune erreur de frappe). Deux méthodes :

• visual check 目视检查 — une personne compare les données saisies avec l'original ;
• double entry 双重输入 — les données sont saisies deux fois et les deux copies sont comparées.

Une trace table 追踪表 enregistre la valeur de chaque variable à mesure qu'un algorithme s'exécute, étape par étape. Elle vous aide à :

• vérifier qu'un algorithme fonctionne correctement ;
• déterminer ce que fait un algorithme en le suivant avec des données données.

Exemple : tracez cet algorithme avec l'entrée 5.

INPUT N
Total ← 0
FOR I ← 1 TO N
    Total ← Total + I
NEXT I
OUTPUT Total

Le tableau de traçage montre que l'algorithme additionne 1 à n. Avec l'entrée 5, la sortie est 15.

Worked example. Tracez cet algorithme et donnez la sortie.

X ← 20
Count ← 0
WHILE X > 1
    X ← DIV(X, 2)
    Count ← Count + 1
ENDWHILE
OUTPUT Count

DIV ne donne que la partie entière d'une division. Prenez une ligne par passage : x devient 10 (count 1), puis 5 (count 2), puis 2 (count 3), puis 1 (count 4). Maintenant x > 1 est faux, donc la boucle s'arrête et la sortie est 4. Deux habitudes protègent ces points : testez la condition avant chaque passage plutôt qu'après, et écrivez une nouvelle ligne pour chaque passage — essayer de garder les valeurs en tête est ce qui fait échouer les traces.

Test data est les données que vous utilisez pour tester un programme. Il existe quatre types que vous devez connaître.

Vous devez connaître ces algorithmes courants.

Recherche linéaire

Une recherche linéaire 线性查找 vérifie chaque élément d'une liste, un par un, jusqu'à ce qu'il trouve la valeur souhaitée ou atteigne la fin.

Found ← FALSE
FOR I ← 0 TO 9
    IF List[I] = SearchValue
      THEN
        Found ← TRUE
    ENDIF
NEXT I
OUTPUT Found

Tri à bulles

Un bubble sort 冒泡排序 met une liste en ordre. Il compare chaque paire d'éléments côte à côte et les échange s'ils sont dans le mauvais ordre. Il répète cela jusqu'à ce qu'aucun échange ne soit nécessaire.

FOR I ← 0 TO 8
    IF List[I] > List[I + 1]
      THEN
        Temp ← List[I]
        List[I] ← List[I + 1]
        List[I + 1] ← Temp
    ENDIF
NEXT I

Totaliser et compter

• totalling 求和 — continuer à ajouter des valeurs à un total cumulatif (Total ← Total + Value).
• counting 计数 — ajouter 1 à un compteur à chaque fois qu'un événement se produit (Count ← Count + 1).

Maximum, minimum and average

• pour trouver le maximum 最大值 : conserver la plus grande valeur vue jusqu'à présent.
• pour trouver le minimum 最小值 : conserver la plus petite valeur vue jusqu'à présent.
• pour trouver la moyenne 平均值 : diviser le total par le nombre de valeurs.

Total ← 0
FOR I ← 0 TO 9
    Total ← Total + List[I]
NEXT I
Average ← Total / 10
OUTPUT Average

• Apprenez les quatre étapes du cycle de vie : analyse → conception → codage → test. Abstraction conserve uniquement les détails importants ; décomposition divise un problème en parties plus petites.
• Validation vérifie que les données sont cohérentes (vérifications de plage, longueur, type, présence, format) ; verification vérifie qu'elles ont été correctement copiées (visual check ou double entry).
• Apprenez les quatre types de données de test : normale (accepté), abnormal (rejeté), extreme (la plus grande/la plus petite encore autorisée), boundary (les valeurs de part et d'autre d'une limite).
• Pour comprendre ce qu'un algorithme fait, remplissez une trace table — notez la valeur de chaque variable à chaque étape.
• Connaissez les algorithmes standards : recherche linéaire (vérifier chaque élément tour à tour) et bubble sort (échanger les paires côte à côte jusqu'à ce qu'aucun échange ne soit nécessaire).