Série de révision BAC 2008-2009 atis.clicforum.com Série de révision BAC 2008/2

Série de révision BAC 2008-2009 atis.clicforum.com Série de révision BAC 2008/2009 atis.clicforum.com 50 exercices Algorithmique & Programm@tion 4ème Sc.Info Exercice1 La fonction d’Ackermann est définie par : Ackermann (0, j) = j + 1 Ackermann (i, 0) = Ackermann (i-1, 1) Ackermann (i, j) = Ackermann (i-1, Ackermann (i, j-1)) Analyser et déduire l’algorithme récursif qui permet de renvoyer la valeur de la fonct ion 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 ci rculaire 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 ch e 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 a pprochée de près, en utilisant la formule suivante : à 10-4 Collectée par Khaled KACHBOURI – atis.clicforum.com 1 Série de révision BAC 2008-2009 atis.clicforum.com Exercice4 Soit la fonction suivante : 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 F inSi Fin Tant que Jusqu’à (V) 3) inconnue N 4) Fin inconnue 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 rè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 remiers. 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. Pro osez un module récursif qui ermet de vérifier si un entier N est un nombr e d'Armstrong ou non. Exercice6 Ecrivez l'algorithme de la fonction ermettant de calculer ex (x), (x est un réel) . On su  osera que l'erreur d'évaluation E est un aramètre de la fonction. ex (x) = 1 + x + x2/2! + x3/ 3! + ... + xn/ n! + ... Collectée ar Khaled KACHBOURI – atis.clicforum.com 2 Série de révision BAC 2008-2009 atis.clicforum.com Exercice7 Un serveur de noms (DNS) ermet d’associer une adresse IP à chaque URL. Dans un réseau , on associe une adresse IP unique à chaque machine. Mais si une adresse est facil e à manipuler par un ordinateur, elle est difficile à mémoriser par un humain. Le serv eur 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 consi ste à 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 127.0.0.1 194.146.255.213 196.168.50.20 site1.org localhost.localdom ain atis.clicforum.com www.footsite1.com 1 0 100 20 • Le premier champ est l’adresse IP, • Le deuxième champ est le nom (URL) de la ressourc e (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 nom s sauvegarde ces informations dans le fichier "hosts.dat" enregistré sous le dossi er "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". - A jouter les informations d’une nouvelle machine : Si des nouvelles machines viennen t se connecter au réseau alors le serveur ajoute celles ci à la fin du fichier "host s.dat". - Supprimer les informations d’une machine : Si une machine se déconnecte du réseau, l e serveur supprimerait les informations relatives à cette machine. On se propose d’écr ire un programme qui offre un menu permettant d’exécuter l’une des opérations: - "A" : P our ajouter une nouvelle machine à la fin du fichier. - "R" : Pour chercher l’adress e IP d’un nom URL donné. - "S" : Pour supprimer une machine du réseau. - "T" : Pour tr ier 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 rem ises au fichier d’origine. - "Q" : Pour quitter le programme. Travail demandé : Collectée par Khaled KACHBOURI – atis.clicforum.com 3 Série de révision BAC 2008-2009 atis.clicforum.com 1- Quelles sont les structures de données adéquates à la résolution de ce problème. 2- Ana lyser le problème en le décomposant en modules et en déduire l’algorithme du programme p rincipal. 3- Analyser chacun des modules envisagés précédemment et en déduire les algori thmes correspondants. Exercice8 E étant un ensemble à n éléments, on appelle combinaison de p éléments de E toute collecti non ordonnée de p éléments distincts de E. On note le nombre de combinaisons de p élément s parmi n. On a : Ecrire une fonction récursive permettant de calculer les combinaisons Cnp en se se rvant 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. Ecr ire 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 c ompresser ce fichier dans un fichier résultat nommé "compress.fch" en utilisant le p rincipe ci-dessus et l afficher. Collectée par Khaled KACHBOURI – atis.clicforum.com 4 Série de révision BAC 2008-2009 atis.clicforum.com Exercice10 L ISBN (International Standard Book Number) est un numéro qui ISBN A12-41213104-92651027-5 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 édi teur 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) corre spond à 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 d e la première partie Le nombre intermédiaire N est obtenu en regroupant les deux chi ffres de même position de la 2 ème et la 3 ème partie de numéro de l ISBN suivis des deu x chiffres de la position suivante jusqu à ajouter les deux chiffres de la 8 ème pos ition. 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 p ar 11, la clé est donc 5. Exemple2 : Numéro saisie : A12-41213104-92651022 Numéro affe cté au livre : A12-41213104-92651022-4 Sur l exemple2 A12-41213104-92651022, le ca lcul intermédiaire donne N:4912261531100242 et 4912261531100242 a pour reste 0 dan s la division par 11, d’où on effectue la somme des chiffres de la représentation bina ire de A12. Collectée par Khaled KACHBOURI – atis.clicforum.com 5 Série de révision BAC 2008-2009 atis.clicforum.com NB : La règle de divisibilité d’un entier N par 11 : S1 = Somme des chiffre d’indices im 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 et S2 = somme des chiffres d’indices pairs Travail à faire : On veut écrire un programme permettant de saisir le numéro ISBN d’un l ivre, déterminer la clé affectée à ce numéro et afficher le numéro final du livre. Décompo ce problème en modules. Analyser chacun des modules. En déduire les uploads/Industriel/ serie-d-algorithme-50-exercice.pdf

Tags
Industrielatis.clicforum.com fonction nombre fichier ecrire
Documents similaires
  • 24
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager