Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
tc_info:2020_td_comp [2020/09/30 14:37] – pprea | tc_info:2020_td_comp [2020/09/30 15:57] (Version actuelle) – pprea | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ====== TD " | ||
+ | |||
+ | |||
+ | ===1. Addition === | ||
+ | |||
+ | Donnez deux algorithmes qui additionnent deux nombres entiers. | ||
+ | |||
+ | * Un premier qui est celui utilisé quand on fait une addition "à la main" [[2020_CPP_1-1|Indications]] | ||
+ | * Un deuxième qui utilise d' | ||
+ | |||
+ | Comparez les complexités de ces algorithmes. [[2020_cpp_1-3|Solution (important)]] | ||
+ | |||
+ | |||
+ | ===2. Puissance === | ||
+ | |||
+ | Donnez deux algorithmes, | ||
+ | |||
+ | Donnez leurs complexités. [[2020_cpp_2-2|Solution]] | ||
+ | |||
+ | Prouvez les. [[2020_cpp_2-3|Solution]] | ||
+ | |||
+ | |||
+ | ===3. Maximum d'un tableau === | ||
+ | |||
+ | Donnez deux algorithmes, | ||
+ | |||
+ | Comparez leurs fonctionnements. [[2020_cpp_3-3|Solution]] | ||
+ | |||
+ | |||
+ | ===4. Algorithme Mystère === | ||
+ | |||
+ | On considère l' | ||
+ | |||
+ | def $misterioso(A, | ||
+ | $\;\;\;\;$ # $A$ & $B$ sont des entiers positifs\\ | ||
+ | $\;\;\;\;$ $x \gets A ;\, y \gets B ;\, r \gets 1$ \\ | ||
+ | $\;\;\;\;$ # Ligne 1 \\ | ||
+ | $\;\;\;\;$ while $y \neq 0$: \\ | ||
+ | $\;\;\;\;$ $\;\;\;\;$ # Ligne 2 \\ | ||
+ | $\;\;\;\;$ $\;\;\;\;$ if $y$ impair: \\ | ||
+ | $\;\;\;\;$ $\;\;\;\;$ $\;\;\;\;$ $r \gets r \times x$\\ | ||
+ | $\;\;\;\;$ $\;\;\;\;$ $\;\;\;\;$ $y \gets y -1$ \\ | ||
+ | $\;\;\;\;$ $\;\;\;\;$ else:\\ | ||
+ | $\;\;\;\;$ $\;\;\;\;$ $\;\;\;\;$ $x \gets x\times x$\\ | ||
+ | $\;\;\;\;$ $\;\;\;\;$ $\;\;\;\;$ $y \gets y /2$\\ | ||
+ | $\;\;\;\;$ $\;\;\;\;$ # Ligne 3 \\ | ||
+ | $\;\;\;\;$ # Ligne 4 \\ | ||
+ | $\;\;\;\;$ return $r$\\ | ||
+ | |||
+ | |||
+ | Que fait cet algorithme | ||
+ | Justifiez votre réponse. [[2020_cpp_4-2|Réponse]] | ||
+ | |||
+ | |||
+ | Quelle sa complexité dans le cas le meilleur ([[2020_cpp_4-2-1|indication]]), | ||
+ | |||
+ | |||
+ | ===5. Tris Naïfs === | ||
+ | |||
+ | Prouvez les algorithmes de tris simples vus en cours (tri par sélection & tri par insertion) | ||
+ | |||
+ | [[2020_cpp_5-1|Indications]] | ||
+ | |||
+ | |||
+ | ===6. Palindromes === | ||
+ | |||
+ | Implémentez un algorithme récursif permettant de savoir si un tableau de caractères est un palindrome (un palindrome se lit "à l' | ||
+ | |||
+ | [[2020_cpp_6-1|Solution]] | ||
+ | |||
+ | |||
+ | ===7. Tours de Hanoï === | ||
+ | |||
+ | Les //tours de Hanoï// sont un célèbre casse tête qui consiste à déplacer $n$ disques de diamètres différents d'une tour de " | ||
+ | |||
+ | * on ne peut déplacer qu'un disque à la fois, | ||
+ | * on ne peut placer un disque sur un disque plus petit que lui. | ||
+ | |||
+ | On suppose que cette dernière règle est également respectée dans la configuration de départ. | ||
+ | |||
+ | |||
+ | Donnez un algorithme récursif permettant de résoudre le problème. Quelle est sa complexité? | ||
+ | |||
+ | [[2020_cpp_7|Indication]] | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||