Remerciez-le!

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

Série de révision BAC 2008-2009 atis.clicforum.com Collectée par Khaled KACHBOU

Série de révision BAC 2008-2009 atis.clicforum.com Collectée par Khaled KACHBOURI – atis.clicforum.com 1 Série de révision BAC 2008/2009 50 exercices atis.clicforum.com Algorithmique & Programm@tion 4ème Sc.Info Exercice1 La fonction d’Ackermann est définie par : Analyser et déduire l’algorithme récursif qui permet de renvoyer la valeur de la fonction d'Ackermann pour un couple (i,j) donné. Exercice2 L’un des plus vieux code secret est le chiffre de César. Il consiste en un décalage circulaire de N positions de l’alphabet utilisé. Exemple: Lettres à coder : A B C D E F G . . . Y Z Pour un décalage circulaire de 4 positions : Lettres après codage : E F G H I J K . . . C D Le mot “BAC” est codé “FEG”. Travail à faire Proposer un module qui permet d'encoder une chaîne de caractères passée en paramètres suivant le principe des chiffres de César Exercice 3 Ecrire l'analyse d'une fonction qui permet de calculer et retourner une valeur approchée de à 10-4 près, en utilisant la formule suivante : Ackermann (0, j) = j + 1 Ackermann (i, 0) = Ackermann (i-1, 1) Ackermann (i, j) = Ackermann (i-1, Ackermann (i, j-1)) Série de révision BAC 2008-2009 atis.clicforum.com Collectée par Khaled KACHBOURI – atis.clicforum.com 2 Exercice4 Soit la fonction suivante : Questions : 1- Exécuter la fonction pour j=7. 2- Quel est le rôle de cette fonction ? 3- Ecrire l’algorithme d’une fonction qui permet de renvoyer une valeur approchée de π à 10-5 près, en utilisant la formule Zêta de Riman : π2/6 = 22/(22-1) x 32/(32-1) x 52/(52-1) x 72/(72-1) x 112/(112-1) … N.B : 2, 3, 5, 7, 11 sont des nombres premiers. Exercice5 Un nombre d'Armstrong est un entier naturel qui est égal à la somme des cubes de ces chiffres. Ainsi 153 est un nombre d'Armstrong car 13 + 53 + 33 = 1 + 125 + 27 = 153. Proposez un module récursif qui permet de vérifier si un entier N est un nombre d'Armstrong ou non. Exercice6 Ecrivez l'algorithme de la fonction permettant de calculer exp(x), (x est un réel). On supposera que l'erreur d'évaluation E est un paramètre de la fonction. exp(x) = 1 + x + x2/2! + x3/ 3! + ... + xn/ n! + ... 0) Début Fonction inconnue (j : entier) : entier 1) N j 2) Répéter N N+1, k 2, v vrai Tant que (k <= N div 2) et (v) faire Si (N mod k = 0) alors V Faux Sinon k k+1 FinSi Fin Tant que Jusqu’à (V) 3) inconnue N 4) Fin inconnue Série de révision BAC 2008-2009 atis.clicforum.com Collectée par Khaled KACHBOURI – atis.clicforum.com 3 Exercice7 Un serveur de noms (DNS) permet d’associer une adresse IP à chaque URL. Dans un réseau, on associe une adresse IP unique à chaque machine. Mais si une adresse est facile à manipuler par un ordinateur, elle est difficile à mémoriser par un humain. Le serveur de noms DNS permet de trouver l’adresse IP à partir du nom (URL) de la machine (ou inversement). Pour résoudre un nom en adresse IP, la méthode la plus simple consiste à mettre tous les noms des machines et leurs adresses associés dans un fichier. Exemple : Chaque machine est définie par 3 champs : 192.168.1.1 site1.org 1 127.0.0.1 localhost.localdomain 0 194.146.255.213 atis.clicforum.com 100 196.168.50.20 www.footsite1.com 20 • Le premier champ est l’adresse IP, • Le deuxième champ est le nom (URL) de la ressource (site web, image…) • Le troisième champ désigne la distance (nombre de machines) entre le serveur et la machine cible. Dans la suite, on suppose que le serveur de noms sauvegarde ces informations dans le fichier "hosts.dat" enregistré sous le dossier "C:\config". Les opérations effectuées par le serveur de noms sont les suivantes : - Chercher l’adresse IP d’une ressource donnée : Si elle existe, on afficherait son adresse IP, sinon on afficherait le message "la ressource est indisponible". - Ajouter les informations d’une nouvelle machine : Si des nouvelles machines viennent se connecter au réseau alors le serveur ajoute celles ci à la fin du fichier "hosts.dat". - Supprimer les informations d’une machine : Si une machine se déconnecte du réseau, le serveur supprimerait les informations relatives à cette machine. On se propose d’écrire un programme qui offre un menu permettant d’exécuter l’une des opérations: - "A" : Pour ajouter une nouvelle machine à la fin du fichier. - "R" : Pour chercher l’adresse IP d’un nom URL donné. - "S" : Pour supprimer une machine du réseau. - "T" : Pour trier les machines selon l’ordre croissant de la distance par rapport au serveur. Le tri se fait au niveau de la mémoire centrale. Une fois triées, les données seront remises au fichier d’origine. - "Q" : Pour quitter le programme. Travail demandé : Série de révision BAC 2008-2009 atis.clicforum.com Collectée par Khaled KACHBOURI – atis.clicforum.com 4 1- Quelles sont les structures de données adéquates à la résolution de ce problème. 2- Analyser le problème en le décomposant en modules et en déduire l’algorithme du programme principal. 3- Analyser chacun des modules envisagés précédemment et en déduire les algorithmes correspondants. Exercice8 E étant un ensemble à n éléments, on appelle combinaison de p éléments de E toute collection non ordonnée de p éléments distincts de E. On note le nombre de combinaisons de p éléments parmi n. On a : Ecrire une fonction récursive permettant de calculer les combinaisons Cnp en se servant de la relation suivante : C(0,p)=1 C(p,p)=1 C(n,p) = C(n-1,p) + C(n-1,p-1) Exercice9 On veut compresser un fichier d'entiers binaires (contenant des 0 et des 1). Le principe de compression est le suivant : Si le fichier contient : 00000011111000, La compression nous donne : 605130 Et se lit : on a 6 zéros, 5 uns et 3 zéros. Ecrire un programme Pascal qui permet de créer et remplir un fichier nommé "source.fch" par N entiers binaires (N est un nombre aléatoire compris entre 4 et 100), puis compresser ce fichier dans un fichier résultat nommé "compress.fch" en utilisant le principe ci-dessus et l'afficher. Série de révision BAC 2008-2009 atis.clicforum.com Collectée par Khaled KACHBOURI – atis.clicforum.com 5 ISBN A12-41213104-92651027-5 Exercice10 L'ISBN (International Standard Book Number) est un numéro qui permet d'identifier le titre d'un livre. Ce numéro est formé de 20 caractères regroupés en 4 parties : • La première correspond à la zone linguistique qui est un nombre de 3 chiffres hexadécimaux distincts, et qui commence obligatoirement par une lettre : Exemples : A12 pour Arabe FB2 pour Français • Les deux autres parties (indiquant l'éditeur et le numéro d'ordre dans la production de l'éditeur) sont formés uniquement par des chiffres : 8 chiffres par partie. • La dernière partie (chiffre ou lettre) correspond à la clé de contrôle : La clé est le reste de la division d'un nombre intermédiaire N par 11 en utilisant la règle de divisibilité. - Si ce reste est non nul et formé d’un seul chiffre, la clé sera égale au reste. - Si ce reste est 10 la clé sera notée X. - Si le reste est 0 la clé sera égale à la somme des chiffres de la représentation binaire de la première partie Le nombre intermédiaire N est obtenu en regroupant les deux chiffres de même position de la 2 ème et la 3 ème partie de numéro de l'ISBN suivis des deux chiffres de la position suivante jusqu'à ajouter les deux chiffres de la 8 ème position. Exemple1 : Numéro saisie : A12-41213104-92651027 Numéro affecté au livre : A12-41213104-92651027-5 Sur l'exemple1 A12-41213104-92651027, le calcul intermédiaire donne N : 4912261531100247 et 4912261531100247 a pour reste 5 dans la division par 11, la clé est donc 5. Exemple2 : Numéro saisie : A12-41213104-92651022 Numéro affecté au livre : A12-41213104-92651022-4 Sur l'exemple2 A12-41213104-92651022, le calcul intermédiaire donne N:4912261531100242 et 4912261531100242 a pour reste 0 dans la division par 11, d’où on effectue la somme des chiffres de la représentation binaire de A12. Série de révision BAC 2008-2009 atis.clicforum.com Collectée par Khaled KACHBOURI – atis.clicforum.com 6 NB : La règle de divisibilité d’un entier N par 11 : S1 = Somme des chiffre d’indices impairs et S2 = somme des chiffres d’indices pairs S = ABS(S1-S2) Si S mod 11=0 alors N est divisible par 11 Exp : 50312 mod 11 = abs ((2+3+5)-(1+0)) mod 11 = 9 Travail à faire : On veut écrire un programme permettant de saisir le numéro ISBN d’un livre, déterminer la clé affectée à ce numéro et afficher le numéro final du livre. - Décomposer ce problème en modules. - Analyser chacun des modules. - En déduire les algorithmes et les tableaux des déclarations. Exercice11 Soit l’algorithme suivant : 0) Début Inconnu 1) Associer (f1, "Fichier1.dat") 2) Associer (f2, "Fichier2.dat") 3) Ouvrir (f1) 4) Recréer (f2) 5) Tant que Non Fin_Fichier (f1) Faire Tant que Non Fin_Ligne (f1) Faire Lire (f1, ch) Ecrire (f2, ch) Fin Tant uploads/Industriel/ serie-d-x27-algorithme-50-exercice 1 .pdf