Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Examen d’algorithmique Mercredi 20 décembre 2006 Les différentes parties sont i

Examen d’algorithmique Mercredi 20 décembre 2006 Les différentes parties sont indépendantes. Lisez tout le sujet avant de commencer N’hésitez pas à travailler sur un brouillon avant de recopier ! L’opérateur modulo (reste de la division entière) sera noté avec le symbole pour- cent (%). En plus de vos algorithmes, donnez des commentaires sur ce que vous faites. De même, si vous n’avez pas toutes les étapes d’un problème, rajoutez un texte ex- plicatif de ce qui manque. Documents autorisés : cours, TD. 1 Le crible d’Ératosthène Le crible d’Ératosthène est algorithme permettant de trouver facilement les nombres premiers. 1.1 Présentation du sujet Nombres premiers Un nombre premier est un nombre qui n’est divisible de ma- nière entière que par 1 ou par lui-même. Par exemple 3, 5, 11,. . .sont premiers alors que 4 (divisible par 2), 9 (divisible par 3),. . .ne le sont pas. Principe On considère les nombres de 2 à N. Le premier (2) est premier, tous ces multiples ne sont donc pas premiers (4, 6, . . .) et sont éliminés. On s’intéresse en- suite au prochain nombre qui n’a pas été éliminé (3) et on élimine tous ces multiples (3,6 qui a déjà été éliminé, 9,. . .). Le prochain nombre non éliminé est 5 et on réitère l’opération (on élimine ainsi 15, 25, . . .les autres multiples de 5 sont aussi multiples de 2 et on été éliminés.) L’opération s’arrête lorsque l’on est arrivé à l’élément N. Le tableau 1 présente l’application de cette méthode pour les 10 premiers entiers. 1.2 Travail à faire Proposez un programme qui afﬁche les nombres entiers dans l’intervalle 1..N N est demandé à l’utilisateur (maximum 100). 1 TAB. 1 – Le crible d’Ératosthène pour les 10 premiers entiers Itération Liste des nombres description de l’opération 0 2,3,4,5,6,7,8,9,10 Initialisation des éléments de 2 à N 1 2,3,4,5,6,7,8,9,10 2 est premier, élimination des ces multiples 2 2,3,4,5,6,7,8,9,10 3 est premier, élimination des ces multiples 3 2,3,4,5,6,7,8,9,10 5 est premier, aucun multiple dans l’inter- valle considéré 4 2,3,4,5,6,7,8,9,10 7 est premier, aucun multiple dans l’inter- valle considéré 5 2,3,4,5,6,7,8,9,10 Plus aucun nombre non rayé dans l’inter- valle, ﬁn de l’algorithme Pour cela vous utiliserez un tableau de N cases (et pas N −1). Dans ce tableau vous placerez 0 si le nombre est premier, 1 sinon. Commencez à chercher les nombres premiers à partir de 2. 1.3 Correction VAR i,j,n : ENTIER tab[100] : ENTIER DEBUT AFFICHER ‘‘Jusqu’à quel nombre voulez-vous rechercher les nombres premiers ?’’ LIRE n POUR i DE 2 A n SI tab[i]=0 ALORS AFFICHER ‘‘Le nombre i est premier’’ POUR j DE (i+1) A n SI (tab[j]=0) ET (tab[j]%i=0) tab[j]=1 FSI FPOUR FSI FPOUR FIN 2 2 Chiffre de César 2.1 Présentation du sujet L’un des plus vieux code secret est le chiffre de César. Il consiste en un décalage circulaire de l’alphabet utilisé. Le tableau 2 présente le codage obtenu pour un décalage de 4 positions de l’alphabet. Le mot “BAC” est codé “FEG”. TAB. 2 – Un exemple du chiffre de César Lettre à coder A B C D E F G . . . Y Z Lettre après codage E F G H I J K . . . C D 2.2 Travail à faire On stocke dans le tableau CHAINE_A_CODER la chaîne de caractères à encoder. Elle est remplie, vous n’avez pas à demander à l’utilisateur de la saisir. Cette chaîne fait une longueur déﬁnie par la variable LONGUEUR_CHAINE. Cette chaîne de carac- tères ne contient que des majuscules. Proposez un programme qui encode CHAINE_A_CODER et afﬁche le résultat. Le nombre de lettre de décalage est demandé à l’utilisateur. Plusieurs solutions sont possibles, vous pouvez utiliser : – un tableau de 26 lettres, ou – l’opérateur modulo et la valeur de la lettre ’A’, – ou toute autre solution. . . Si vous avez le temps, vous pouvez proposer deux solutions, un bonus sera accordé. 2.3 Correction VAR i,d : ENTIER NOUVELLE_CHAINE[LONGUEUR_CHAINE] : CARACTERES DEBUT AFFICHER ‘‘Donnez le nombre de lettres de décalage ’’ LIRE d POUR i DE 1 A LONGUEUR_CHAINE NOUVELLE_CHAINE[i] = (CHAINE_A_CODER[i]+d) % 26 AFFICHER NOUVELLE_CHAINE[i] FPOUR FIN Le code en C est un peu plus compliqué car il faut prendre en compte le code ASCII de la lettre A. 3 3 Suite de Conway 3.1 Présentation L’élément n de la suite de Conway est construite en “lisant” l’élément n −1. Généralement, on utilise 1 comme élément initial. On obtient par exemple (tab. 3) : TAB. 3 – Les premiers termes de la suite de Conway Itération “Lecture” Valeur 1 État initial 1 2 “Un un” 11 3 “Deux un” 21 4 “ Un deux, un un” 1211 5 “Un un, un deux, deux un” 111221 6 “ Trois un, deux deux, un un” 312211 . . . . . . . . . 3.2 Travail à faire En utilisant deux tableaux d’entiers, proposez un algorithme qui afﬁche les n premiers termes (n est demandé à l’utilisateur) de la suite de Conway. En partant de l’itération n contenue dans le tableau 1, vous construisez l’itéra- tion n + 1 dans le tableau 2 et vous l’afﬁchez. Ensuite, vous recopiez le tableau 2 dans le tableau 1 pour construire l’itération suivante. Il ne s’agit que d’un problème de comptage d’éléments. . . 3.3 Correction VAR tableau1[50], tableau2[50] : ENTIER longueur1, longueur2 : ENTIER i,j,k,m : ENTIER valeur, occurence, nb_iter : ENTIER DEBUT tableau1[0]=1; longueur1=1; AFFICHER ‘‘Combien d’itération ?’’ LIRE nb_iter POUR m DE 1 A nb_iter valeur=tableau1[0] occurence=1 longueur2=0 POUR i DE 1 A longueur1-1 4 SI tableau1[i]=tableau1[i+1] occurence = occurence +1 SINON tableau2[longueur2] = occurence longueur2 = longueur2 + 1 tableau2[longueur2] = valeur valeur = tableau1[i+1] occurence = 1 FSI SI tableau1[longueur1] != valeur occurence=1 valeur = tableau1[longueur1] FSI tableau2[longueur2] = occurence longueur2 = longueur2 + 1 tableau2[longueur2] = valeur valeur = tableau1[i+1] POUR i DE 1 A longueur2 tableau1[i] = tableau2[i] AFFICHER tableau2[i] FPOUR longueur1=longueur2 FPOUR FPOUR 5 uploads/S4/ sujet-et-correction.pdf