Définissez et implantez l'algorithme correspondant à la spécification suivante :
On entre un entier N au clavier. Si N est strictement positif, on affiche la somme et la moyenne des entiers entrés jusqu'à présent. Sinon, on s'arrête.
Quelle est la complexité en temps de votre programme ? Sa complexité en espace ?
Exo 2 : Tri par sélection itérée du minimum
Classement d'un talbeau T par ordre croissant, an appliquant le principe suivant. Un parcours du tableau permet de rechercher le plus petit élément qui est alors permuté avec le premier. On recommence avec le tableau ayant le premier élément en moins.
Explicitez cet algorithme et implantez-le.
Quelle est la complexité en temps de votre programme ? Sa complexité en espace ?
Exo 3 : Tri par compression/décompression
On veut trier par ordre croissant un tableau T de N entiers tous inférieurs ou égaux à MAX. L'idée est la suivante. Dans un premier temps, on comprime T dans un nouveau tableau T', en comptant le nombre d'occurences dans T des entiers de 0 à MAX. Dans un second temps, on décompresse T'en T trié.
Explicitez cet algorithme et implantez-le.
Quelle est la complexité en temps de votre programme ? Sa complexité en espace ?
Exo 4 : Le crible d'Eratosthène
Parmiles N premiers nombres entiers non nuls, déterminez ceux qui sont premiers à l'aide du principe suivant. Soit P un tableau contenant les entiers de 1 à N. On supprime tous les multiples d'un élément
non déjà supprimé à partir du carré de . On
recommence. A la fin du traitement, les nombres restant sont premiers.
Précisez cette idée sur un exemple (N = 16).
Explicitez cet algorithme et implantez-le.
Quelle est la complexité en temps de votre programme ? Sa complexité en espace ?