Aller au contenu

Devoir commun 2

Algorithmes avancés Sujet A

L'usage de la calculatrice n'est pas autorisé

Durée: 90 min

Exercice 1

Combien les tris par insertion et sélection effectuent (dans le pire des cas, sur un tableau de taille \(n\), à une constante près) :

  • d'opérations;

  • d'échanges d'éléments du tableau;

  • de comparaisons.

Choisir les réponses parmi : \(\log (n)\)  ; \(n\)  ; \(n\times \log (n)\) ; \(n^2\) .

Exercice 2

Combien de comparaisons doit on faire pour ranger (efficacement) un élément dans un tableau trié de \(n\)  éléments ?

Exercice 3

Faut-il adopter la recherche dichotomique ou la recherche linéaire pour chercher les éléments suivants ?

  1. 10 dans un tableau trié de taille 3.

  2. 'c' dans un tableau trié de taille 500.

  3. 5 dans un tableau non trié de taille 1000.

  4. le premier 'c' dans une chaîne de caractères.

Exercice 4

Donner une version modifiée de l'algorithme suivant pour qu'il trie les éléments dans l'ordre décroissant (à faire sur cette page, inutile de recopier totalement l'algorithme!)

VARIABLE

t : tableau d’entiers

i : nombre entier

j : nombre entier

k : nombre entier

DEBUT

j\(\leftarrow\)2

tant que j``<``=longueur(t):   //boucle 1

i\(\leftarrow\)j-1

k\(\leftarrow\)t[j]

tant que i``>``0 et que t[i]``>``k:   //boucle 2

t[i+1]\(\leftarrow\)t[i]

i\(\leftarrow\)i-1

fin tant que

t[i+1]\(\leftarrow\)k

j\(\leftarrow\)j+1

fin tant que

FIN

Exercice 5

Quelles affirmations sont correctes concernant les algorithmes gloutons ?

a. Il existe une définition formelle rigoureuse permettant de dire si un algorithme quelconque est glouton ou pas.

b. La méthode gloutonne est une approche permettant de concevoir des algorithmes.

c. Un algorithme glouton énumère en général toutes les solutions d'un problème pour trouver la meilleure.

d. Un algorithme glouton est généralement rapide par rapport à d'autres méthodes pour résoudre le problème.

e. Un algorithme glouton est généralement facile à implémenter par rapport à d'autres méthodes.

f. Les choix effectués par un algorithme glouton utilisent généralement un critère simple.

Exercice 6

Décrire le problème du sac à dos : entrées, objectif.

L'algorithme glouton est-il optimal ?

La Grenouille

Une grenouille souhaite traverser un étang de 20m de large en sautant sur des nénuphars. Les nénuphars forment une ligne perpendiculaire aux rives. Un tableau contient la distance de chaque nénuphar au bord de départ. Un saut ne peut pas excéder 1.1m

Proposer un algorithme calculant le nombre minimal de sauts que la grenouille doit réaliser pour traverser.

Corrigé 
Tab=[50,70,150,210,300,320,340,410,490,550,630,720,760,820,880,900,920]

def nbsaut(T):
    T=[0]+T
    i=0
    s=0
    while 1000-T[i]>110:
        k=1
        while T[i+k]-T[i]<=110 and i+k<len(T)-1:
            k=k+1
        i=i+k-1
        s=s+1
    return s+1

Le compte est bon

a. Écrire un programme qui prend en entrée une liste de chiffres distincts et retourne le plus grand nombre qui utilise chacun de ces chiffres une seule fois. Par exemple, \(f([3,1,5])\) renvoie \(531\).

b. Même question mais maintenant on suppose que l'entrée est une liste d'entiers positifs. Par exemple \(f([13,4,5])\) renvoie \(5413\).