- Ecrire une fonction récursive qui peut être utilisée
pour afficher toutes les suites d'entiers positifs avec avec n comme dernier
élément et telles que chaque élément est un multiple
de l'élément précédent.
(Par exemple pour n=10 les suites sont
10
1 10
2 10
5 10
1 2 10
1 5 10
)
(Votre fonction pourrait très bien avoir d'autres paramètres;
par exemple elle pourrait avoir deux paramètres auxiliaires T,i et
afficher les i premiers éléments du tableau T après chaque
suite; il suffirait ensuite de l'appeler avec i=0 pour obtenir l'affichage
souhaité.)
- Etant donné un tableau T de n éléments T[0],...
T[n-1], on souhaite calculer l'ordre du plus grand
sous-ensemble des éléments qui est déjà trié,
c'est-à-dire le plus grand i tel qu'il existe une suite 0 < =
x1 < x2 < ... < xi < = n-1 avec T[x1] < = T[x2]
< = ... < = T[xi]. Afin de faire ceci, on calcule pour
chaque j l'ordre du plus grand sous-ensemble qui vérifie la propriété
énoncée et aussi xi=j.
Décrire comment la programmation dynamique peut aider à
faire ce calcul de façon efficace.
- On sait que n est un entier positif et que f et g sont deux fonctions
vérifiant f(i)=O(p(i)) et g(i)=O(q(i)). En utilisant la notation O(),
mais sans mention de f ou de g, exprimer les meilleurs majorants possibles
sur le nombre d'exécutions de w++, x++, y++ et z++ par le code suivant:
for (i=0;i<f(n);i++)
for (j=0;j<i;j++) w++;
for (i=0;i<f(n);i++) x++;
for (i=0;i<g(n);i++) x++;
for (i=0;i<f(n);i++)
for (j=0;j<g(n);j++) y++;
j=1;
for (i=0;i<f(n);i++) j*=2;
for (i=0;i<j;i++) z++;
- D'écrire l'algorithme Knuth-Morris-Pratt de recherche des occurrences
d'une chaîne de caractères dans une autre en précisant
en détail comment il trouve les occurrences de abcabcdab
en abracadabrabcabcdabcabcdab
- Ecrire une fonction qui libère l'espace utilisé par
une structure composée de noeuds, reliés par deux pointeurs
P1 et P2 dans chaque noeud. Un noeud contient aussi deux champs i et j qui
contiennent 0 à l'appel de la fonction. Le paramètre de la
fonction est un pointeur vers un noeud et la fonction doit appliquer free()
une fois à chaque noeud accessible à partir de ce pointeur.
La fonction peut parcourir la structure deux fois; le premier parcours
peut calculer dans le champ i de chaque noeud le nombre de pointeurs au noeud
et le deuxième parcours peut décrémenter i à
chaque visite à un noeud et libérer le noeud quand i atteint
0.