- Un tableau T numéroté de 0 à n contient
des éléments qui sont ou blanc ou noir et
je veux calculer efficacement le nombre de noir. Cette tâche
est simplifiée par le fait qu'il existe probablement de grandes intervalles
qui sont uniformément blancs ou noirs et par une fonction disponible
couleur(g,d) qui donne la couleur de l'intervalle [g..d] comme
blanc ou noir si tout l'intervalle est de la même
couleur et comme gris sinon.
Ecrire une fonction récursive nombre(g,d) qui calcule le
nombre de noir pour l'intervalle [g..d] en utilisant couleur()
et en divisant l'intervalle en deux parties tant qu'il est gris.
- le nombre de chiffres 1 dans le développement binaire d'un
entier positif n est (le nombre pour n/2) plus (1 si n est impair).
Ecrire une boucle qui calcule ce nombre pour tous les entiers entre 1 et
1000 par programmation dynamique et comparer l'efficacité de cette
méthode avec la méthode naive qui calcule le nombre pour chaque
entier indépendamment.
- Le code donné est censé calculer combien de nombres
premiers sont facteur de n. Donner des invariants des deux boucles (extérieure
et intérieure) qui pourraient être utilisés pour démontrer
que le code est correct.
m=n;
compteur=0;
for (f=2;f<=m;f++)
{
if (m%f==0)
{
compteur++;
do m=m/f; while (m%f==0);
}
}
- L'algorithme de Strassen multiplie deux matrices (
) et (
) de la façon suivante:
P1=(A12-A22)(B21+B22);
P2=(A11+A22)(B11+B22);
P3=(A11-A21)(B11+B12);
P4=(A11+A12)B22;
P5=A11(B12-B22);
P6=A22(B21-B11);
P7=(A21+A22)B11;
C11=P1+P2-P4+P6;
C12=P4+P5;
C21=P6+P7;
C22=P2-P3+P5-P7;
pour obtenir le produit (
)
- Démontrer que l'élément C11 est correctement
calculé.
- Combien de multiplications d'éléments de base (par
exemple des float) sont effectuées quand cet algorithme est
utilisé récursivement pour multiplier deux matrices de taille
- 2 ×2
- 4 ×4
- 8 ×8
- Une liste est construite de structures qui contiennent un champs prochain
qui est un pointeur vers une structure du même type. On veut décider
si une liste est ``normale'' (terminée par un pointeur nul) ou ``circulaire''
(une structure contient un pointeur vers une autre qui est déjà
dans la liste). Pour faire ça on va utiliser la méthode de
deux pointeurs qui parcourent la liste dans une boucle où l'un se
déplace deux fois plus vite que l'autre. Si la liste est circulaire,
après un certain temps, les deux pointeurs seront dans le cycle et
forcément le plus vite va rattraper l'autre; sinon le plus vite
va arriver au pointeur nul.
Ecrire la fonction qui décide si une liste (donnée
par un paramètre pointeur) est circulaire ou non.