Donner le nombre d'instructions exécutées par le code ci-dessous. On attend un nombre, pas une formule en N !

Donnez votre réponse sous la forme d'un nombre, sans aucun espace ou aucune ponctuation.

Exemples de réponses correctement rédigées - mais fausses 😉 - : 

488

Exemples de réponses mal rédigées : 

il y a 488 instructions exécutées

Le code à analyser :

i ← 2

j ← 2*j

FPour

Voici un extrait d'algorithme qui porte sur l'intervalle d'entiers [a, b] :

UnSurDeux ← vrai

Tant que (a ≤ b) faire

m ← (a+b) DIV 2

Si UnSurDeux Alors

a ← m+1

Sinon

b ← m-1

FSi

UnSurDeux ← non UnSurDeux

FTQ

Sous l'hypothèse que N représente le nombre d'entiers de a à b (N = b-a+1), choisissez la formule de sa complexité en temps (pour information, il n'y a pas de cas pire que les autres).

Voici une fonction récursive qui calcule le plus grand élément d'un tableau entre les indices deb et fin (deb ≤ fin) :

fonction MaxTab (↓ T : TTableau, ↓ deb : entier, ↓ fin : entier) : entier

Variable 

milieu, M1, M2 : entier

Début

Si deb = fin alors

Afficher ("Coucou")

Sinon

milieu ← (deb+fin) DIV 2

retourner M2

Sinon

retourner M1

FSi

FSi

Fin

Si le tableau Tab = [7, 4, 5] est indicé à partir de 1

et si on appelle la fonction comme suit :

M ← MaxTab (Tab, 1, 3)

combien de fois le message "Coucou" s'affichera-t-il ?

0,9.N² - 4.N + 3 = O (N²)

Voici une procédure récursive. Ne cherchez pas à savoir ce qu'elle fait : elle ne fait rien de cohérent. Considérez qu'elle résout un problème qui porte sur un intervalle non vide [D, F] (D ≤ F) d'un tableau :

procedure P (↓ T : TTableau, ↓ D : entier, ↓ F : entier)

Début

Si ...    // Une ou plusieurs exceptions

...

...

Sinon  // Cas général

Si T [D] > T [D+1] 

P (T, D+1, F-1)

Sinon

P (T, D, F-2)

FSi

FSi

Fin

Compte tenu du cas général, sélectionnez les exceptions les plus probables.

Donner le nombre d'instructions exécutées par le code ci-dessous. On attend un nombre, pas une formule en N !

Donnez votre réponse sous la forme d'un nombre, sans aucun espace ou aucune ponctuation.

Exemples de réponses correctement rédigées - mais fausses 😉 - : 

488

Exemples de réponses refusées : 

il y a 488 instructions exécutées

Le code à analyser :

i ← 16

S ← S + i

FTQ

La taille du problème résolu par la portion de code ci-dessous est N.

En appliquant les conventions du cours, choisissez la meilleure formule

pour le nombre d'instructions exécutées dans le pire des cas.

Nota : les tableaux sont indicés à partir de 1.

i ← 1

S ← 0

Tant que i≤ N Faire

Si T [i] < 0 alors

S ← S + T [i]

T [i] ←T [i] * 2

FSi

i ← i + 2

FTQ

En appliquant les conventions du cours, donnez le nombre

d'instructions exécutées par la portion de code ci-dessous dans le pire

des cas. La taille du problème est N.

S  ← 0

Pour i décroissant de N à 2 Faire

Si T [i] > 0 alors

S ← S + T [i]

Si T [i] > T [i - 1] Alors

S ← S - 1

FSi

FSi

FPour

100.N² + 4.N+3 

et 

1/100.N² - 4.N-3 

ont le même ordre de grandeur.