algorithmique

Embed Size (px)

Citation preview

Algorithmique, Arithmtique et Cryptographie 1.Quelques bases1 1-a :Affecter une variable1 1-b :Effectuer une somme1 1-c :La boucle SI ALORS2 2.Suites4 2-a :Algorithme suite arithmtique4 2-b :La boucle TANT QUE5 2-c :Tester un algorithme6 2-d :Programmation sur tableur6 3.Exercices dalgorithmique7 3-a :Faciles7 3-b :Plus srieux8 3-c :Difficiles8 3-d :Pour les champions9 4.Hrner9 5.Dichotomie11 6.Arithmtique12 6-a :Recherche des entiers n divisant 2n + 112 6-b :Problme du Spaghetti12 6-c :Un critre original de recherche de nombres premiers13 7.Suite de Syracuse13 8.Exercices Baccalaurat ES spcialit mathmatiques14 8-a :Agence de voyages14 9.Exercices Baccalaurat L spcialit mathmatiques15 9-a :Dichotomie15 9-b :Diagonales16 9-c :Fractale16 9-d :Divisibilit par 1318 9-e :Suites et logique18 9-f :Suite arithmtique19 9-g :Congruences modulo 719 9-h :Digicode20 9-i :A la photocopieuse21 9-j :Algorithme21 9-k :Vingt euros22 9-l :Time is money22 9-m :ISBN23 9-n :Anne bissextile23 9-o :Codage affine24 9-p :Palindrome25 9-q :Algorithme 125 9-r :Algorithme 225 9-s :Algorithme 326 10.Rfrences27 1. Quelques bases 1-a : Affecter une variable Qu'obtient-on l'cran lorsque l'on programme l'algorithme suivant ? (Tester l'algorithme pas pas) Demander A Demander B Affecter la valeur de A B Affecter la valeur de B A Afficher A Afficher B 1-b : Effectuer une somme Qu'obtient-on l'cran lorsque l'on programme les algorithmes suivants ? (Tester l'algorithme pas pas) exemple 1 : EntreDemander A TraitementAffecter la valeur de A S Faire 10 fois la procdure suivanteAffecter la valeur de S+1 S SortieAfficher S exemple 2 : Donner S la valeur 0 Dbut de la boucle Demander A Donner S la valeur S+A Recommencer au dbut de la boucle jusqu' ce que A=0 Afficher S 1-c : La boucle SI ALORS Pourunpolynmedonn 2( ) P x ax bx c = + + ,leprogrammesuivantaffichelediscriminantDetles solutions ventuelles. S'il n'y en a pas, il affiche "Pas de solutions". Complter l'algorithme : Demander A Demander Demander Affecter la valeur de .. D Afficher Si D>0 Alors affiche . Sinon Si D=0 Alors . Sinon . Voici cet algorithme traduit en langage machine : CommentairesTICASIO Ilfautavanttoutouvrirunepagepourcrirele programme.Lacalculatriceattendquevousdonniezunnomau programme.LecurseurestunA,cequiveutdire quellefonctionneenmodealphabtique,commeune machine crire. Vouspouvezmaintenantcommencerlcrituredu programme. Lacalculatricevousdemanderaderentrerlesvaleurs A, B et C et les gardera en mmoire. EllecalculeDeltaetlegardeenmmoiresouslenom de D. Elle affiche Delta. Si0 A >Alors affiche qu'il y a deux solutions. Ellecalculecesdeuxsolutionspuislesaffichesous forme de fraction. PRGM DELTA NEW Ecrire : DELTA Puis taper sur ENTER La calculatrice affiche : PROGRAM :DELTA :PROMPT A,B,C :B2-4AC D :DISP "DELTA",D :If D>0 :Then :Disp "2 sol" :Disp(- - ) /(2 ) B D AFrac, (- ) /(2 ) B D A +Frac :Else MENU PRGM NEW Ecrire : DELTA Puis taper sur EXE Lacalculatrice affiche : ====DELTA ==== "A?":? A. "B?":?B. "C?":?C. B2-4AC D. "D=":D If D>0. Then "2 sol". "X=":(- - ) (2 ) B D A Sinon Si0 A =Alors La calculatrice affiche qu'il y a une solution, Elle affiche cette solution Sinon Elle affiche qu'il n'y a pas de solution. Fin de la boucle Sialors. :If D=0 :Then :Disp"1sol", Disp - /(2 ) B AFrac :Else :Disp "0 sol" :End "Y=":(- ) (2 ) B D A + . Else If D=0. Then "1 sol". "X=":- (2 ) B A . Else "0 sol". I-End. I-End Quitteraprslederniermotduprogrammesansrien crire de plus. QUITEXIT Pour excuter le programme. TICASIO PRGM Choisir le programme DELTA puis ENTER La calculatrice affiche prgmDELTA Faire ENTER La calculatrice afficheA? Entrer la valeur de A, ENTER De mme avec B et C. A la fin la calculatrice affiche Done MENU PRGM Choisir le programme DELTA puis EXE La calculatrice afficheA? Entrer la valeur de A, EXE De mme avec B et C. A la fin la calculatrice affiche FIN O trouver les commandes pour crire les programmes ? TICASIO Commandes pour les caractres alphabtiques Les lettreset les guillemets " " sont sur le clavier de lacalculatriceetsobtiennentaveclatouche ALPHAcommetouslessymbolesenhautdroite des touches. A-LOCKbloquelacalculatriceenmode alphabtique. Attention !Les espaces quevousvoyez dans ce programme ne sont pas obtenus par la touche ALPHAde votreclavier mais sont naturellementassocisauxinstructionsdes touches de programmes. Leslettressontsurleclavierdelacalculatriceet sobtiennentaveclatoucheALPHAcommetous les symboles en haut droite des touches. A-LOCKbloquelacalculatriceenmode alphabtique.Lesguillemets""sontobtenusen appuyant sur ALPHA mais au bas de lcran. Attention !Les espaces quevousvoyez dansceprogrammenesontpasobtenuspar latoucheALPHA devotreclaviermais sont naturellement associs aux instructions des touches de programmes. Commandes pour les caractres mathmatiques / est la division * est la multiplication est le signe opratoire de la soustraction. A ne pasconfondreavec (-) quisemetendbutde calcul et dsigne le signe du premier nombre. > , = , < est dans le menu TEST. Frac est dans le menu MATH. estlesigneopratoiredelasoustraction.A ne pas confondre avec (-) quisemetendbutdecalculetdsignele signe du premier nombre. > est dans le menu PRGM REL. Enrglegnrale,penserappuyersurlaen bas droite de lcran si vous ne trouvez pas une commande. Commandes pour les instructions usuelles des programmes : sinscrit dans un programme chaque fois que vous tapez sur ENTER pour aller la ligne. Promptquipermetd'entrerlesvaleursetdeles mettreenmmoiresetrouvedanslemenuPRGM puis I/O.Utiliser aussi DISP "texte" suivi de INPUT var. sobtient en appuyant sur STO, en bas gauche de votre clavier de calculatrice. .sinscritdansunprogrammechaquefois que vous taper sur EXE pour aller la ligne. ? signifie invite moi entrer une valeur (sur certaines calculatrices se traduit par un ? lorsque le programme est excut) se trouve dans le menu PRGM (obtenu par SHIFT VARS) puis . estunordrequevousdonnezlacalculatrice etsignifie : affichelcranlavaleurcalcule (lorsquilsagitduncalcul).Ilsetrouveluiaussi dans le menu PRGM puis . est sur le clavier. Commandes particulires pour les boucles et les tests -IF(enfranaisSI),THEN(enfranais ALORS), ELSE (en franais SINON)-WHILE (TANT QUE) se trouvent dans le menu PRGM puis CTL (il s'agit des contrles). -IF(enfranaisSI),THEN(enfranais ALORS),ELSE(enfranaisSINON),I-End (fin de la boucle SI)-WHILE (TANT QUE) setrouventdanslemenu2ndPRGMpuisCOM (il s'agit des commandes). Pourrevenirunmenuprincipal,penserutiliser la touche 2nd QUIT. Pour revenir un menu principal, penser utiliser la touche EXIT. Pour effacer un programme. TICASIO 2nd mem choix 2 : mem Mgmt/Delchoix 7 : prgm Placerlecurseurdevantleoulesprogramme(s) effacer et appuyer sur enter puis DEL et YES. DanslemenuPROG,placerlecurseursurle programme effacer et choisir le menu DEL. 2. Suites 2-a : Algorithme suite arithmtique Leprogrammesuivantcalculelestermessuccessifsd'unesuitearithmtique,lorsqu'onentrelepremier terme u0, la raison et le nombre de termes souhaits. Demander0ula raison r le rang n du dernier terme. Pour i allant de 1 n Affecter la valeur deU r + U Afficher U Voici comment cet algorithme peut se traduire en langage machine : CommentairesTICASIO Disp "U0" Input U Prompt R Prompt N "U0":? U "R":? R "N":? N For 1 I To N TI : Pause permet d'arrter le dfilement des valeurs For(I,1,N) U+RU Disp U Pause End U+RU U Next 2-b : La boucle TANT QUE Le programme suivant donne l'criture en base B d'un nombre entier N crit en base 10. Exercice : Dterminer l'criture de 2123 en base 5. Donner les valeurs successives du dividende N, du quotient Q et du reste R. EtapesN (dividende)Q (quotient)R (reste) 2123 424 5 3 = +424 84 5 4 = +84 16 5 4 = +16 3 5 1 = +3 0 5 3 = +Qu'est ce qui provoque l'arrt de cette suite de divisions ? Autrement dit, quel est le test d'arrt ? La fonction INT de la calculatrice donne la partie entire d'un nombre. A l'aide de cette fonction, comment obtient-on le quotient de la division euclidienne de N par B ? En dduire le reste de la division. Complter l'algorithme : Demander Demander Affecter la valeur de N Q Tant que faire Affecter la valeur de . Q Affecter la valeur de . R Afficher . Affecter la valeur de . N Fin TantQue Voici comment cet algorithme peut se traduire en langage machine : CommentairesTICASIO Ilfautavanttoutouvrirunepagepourcrirele programme.Lacalculatriceattendquevousdonniezunnomau programme.LecurseurestunA,cequiveutdire quellefonctionneenmodealphabtique,commeune machine crire. Vouspouvezmaintenantcommencerlcrituredu programme. Lacalculatricevousdemanderaderentrerunevaleur NpuisunevaleurB.Ellestockeracesvaleursdansla mmoire N et dans la mmoire B.PRGM NEW Ecrire : BASE Puis taper sur ENTER La calculatrice affiche : PROGRAM :BASE :DISP "N" :INPUT N MENU PRGM NEW Ecrire : BASE Puis taper sur EXE La calculatrice affiche : ====BASE==== "N". ?N. Tant que le contenu de Q est strictement positif, la calculatrice remplace le nombre N par Q. Elle fait la division euclidienne de N parB et ne garde que la partie entire. Elle calcule le reste de la division euclidienne de N par B et le stocke dans la mmoire R. La calculatrice arrte le programme lorsque Q=0. :DISP "B" :INPUT B :NQ :While Q>0 :Int(N/B)Q :NQ*BR :Disp R :Pause :QN :End "B". ?B. NQ While Q>0. Int(N/B)Q. NQBR. R QN. WhileEnd. "FIN". Stop Quitteraprslederniermotduprogrammesansrien crire de plus. QUITQUIT 2-c : Tester un algorithme Voici un algorithme de passage de la base 10 la base B : DEBUT Nombre N Base B 0 I 0 A TANT QUE N > 0 IA+RESTE(N/B) 10 A QUOTIENT de la division de N par BN I+1 I FIN TANT QUE AFFICHER (A) FIN Questions : 1. Tester cet algorithme pour N =111 et B=5 (Ecrire toutes les tapes). 2. Prcisez ce que l'utilisateur obtient sur l'cran de la calculatrice pour un nombre N. 3. Cet algorithme fonctionne-t-il pour une base suprieure ou gale 10 ? Justifier. 2-d : Programmation sur tableur Vous pourrez utiliser la fonction MOD : =MOD(nombre ; diviseur) renvoie le reste d'une division. Voici une feuille de calcul sur tableur : ABC 1abreste 249984746252 34746252210 425221042 5210420 6420#DIV/0! 1. Que permet-elle de calculer ? 2. Quelle formule a t crite en A3, B3 et C2 ? 3. Comment obtient-on les rsultats dans les plages de cellules (A4 : A8) et (C3 : C8) ? Expliquez le message derreur qui apparat dans cette feuille. 3. Exercices dalgorithmique3-a : Faciles 1. Un programme carr Ecrireunprogrammequidemandeunnombrelutilisateur,puisquicalculeetaffichelecarrdece nombre. 2. Il suffira dun signe Ecrire un algorithme qui demande un nombre lutilisateur, et linforme ensuite si ce nombre est positif ou ngatif (on laisse de ct le cas o le nombre vaut zro). 3. La pendule Ecrivez un algorithme qui demande sous forme de nombres l'heure qu'il est (un nombre pour les heures, un pour les minutes et un pour les secondes). Cet algorithme indiquera ensuite s'il s'agit d'une heure valide ou non. 4. Roulez jeunesse ! Ecrire un algorithme qui demande lge dun enfant lutilisateur. Ensuite, il linforme de sa catgorie : Poussin de 6 7 ans Pupille de 8 9 ans Minime de 10 11 ans Cadet aprs 12 ans 5. Le distributeur de boissons chaudes Voici un distributeur de boissons chaudes Cet appareil peut servir du caf 0,50 euros, du cappuccino 0,80 euros et du th 0,60 euros. Lemonnayeur,ainsiquelacalculatriceintgreetlordinateursontentatdefonctionnementeton suppose que la machinecontient assez de boissons et de monnaie par la suite. Lembtant, cest que la machine na pas t programme A. Abordons les diffrents cas de figure 1. Imaginez un dbut de dialogue qui pourrait avoir lieu entre un client et la machine. 2. Sionnommepleprixpayeretslasommeinsredanslamachine,prcisezcequidevraitsepasser dans les cas de figures suivants : s < p, s = p, s > p. B. Algorithme 70#DIV/0!#DIV/0! 8#DIV/0!#DIV/0!#DIV/0! 1. Dterminerlesentres/sortiesdelalgorithmemettreenplace(L'algorithmeabesoindedonnesen entre, et fournit un rsultat en sortie).2. Crer un algorithme pour la machine. 3-b : Plus srieux 1. Boule de cristal Cet algorithme est destin prdire l'avenir, et il doit tre infaillible ! Il lira au clavier lheure et les minutes, et il affichera lheure quil sera une minute plus tard. Par exemple, si l'utilisateur tape 21 puis 32, l'algorithme doit rpondre : " Dans une minute, il sera 21 heure(s) 33 ". NB : on suppose que l'utilisateur entre une heure valide. Pas besoin donc de la vrifier.2. Premier degr EcrirelalgorithmequidemandelesdeuxparamtresAetBdunpolynmedupremierdegr.Le programme donnera ensuite le nombre et la valeur de la racine du polynme. 3. Deuxime degr EcrirelalgorithmequidemandelestroisparamtresA,BetCdunpolynmeduseconddegr.Le programme donnera ensuite le nombre et la valeur des racines du polynme. 4. Ttu Ecrire un algorithme qui demande lutilisateur un nombre compris entre 1 et 3 jusqu ceque la rponse convienne. 5. Jamais content Ecrire un algorithme qui demande un nombre compris entre 10 et 20, jusqu ce que la rponse convienne. Encasderponsesuprieure20,onferaapparatreunmessage:Pluspetit!,etinversement,Plus grand ! si le nombre est infrieur 10. 6. En srie Ecrireunalgorithmequidemandeunnombrededpart,etquiensuiteaffichelesdixnombressuivants. Par exemple, si l'utilisateur entre le nombre 17, le programme affichera les nombres de 18 27. 7. A table ! Ecrire un algorithme qui demande un nombre de dpart, et qui ensuite crit la table de multiplication de ce nombre, prsente comme suit (cas o l'utilisateur entre le nombre 7) : Table de 7 : 7 x 1 = 7 7 x 2 = 14 7 x 3 = 21 7 x 10 = 70 3-c : Difficiles 1. Elections Les lections lgislatives, en Laponie Mridionale, obissent la rgle suivante : lorsque l'un des candidats obtient plus de 50% des suffrages, il est lu ds le premier tour. en cas de deuxime tour, peuvent participer uniquement les candidats ayant obtenu au moins 12,5% des voix au premier tour. Vous devez crire un algorithme qui permette la saisie des scores de quatre candidats au premier tour. Cet algorithme traitera ensuite le candidat numro 1 (et uniquement lui) : il dira s'il est lu, battu, s'il se trouve enballottagefavorable(ilparticipeausecondtourentantarriventtel'issuedupremiertour)ou dfavorable (il participe au second tour sans avoir t en tte au premier tour). 2. Une somme de travail Ecrireunalgorithmequidemandeunnombrededpart,etquicalculelasommedesentiersjusquce nombre (sans utiliser la formule magique). Par exemple, si lon entre 5, le programme doit calculer : 1 + 2 + 3 + 4 + 5 = 15 3. Factorielle Ecrire un algorithme qui demande un nombre de dpart, et qui calcule sa factorielle. 4. Un exo qui assure Une compagnie d'assurance automobile propose ses clients quatre familles de tarifs identifiables par une couleur, du moins au plus onreux : tarifs bleu, vert, orange et rouge. Le tarif dpend de la situation du conducteur : unconducteurdemoinsde25ansettitulairedupermisdepuismoinsdedeuxans,sevoitattribuerle tarif rouge, si toutefois il n'a jamais t responsable d'accident. Sinon, la compagnie refuse de l'assurer. unconducteurdemoinsde25ansettitulairedupermisdepuisplusdedeuxans,oudeplusde25ans maistitulairedupermisdepuismoinsdedeuxansaledroitautariforanges'iln'ajamaisprovoqu d'accident, au tarif rouge pour un accident, sinon il est refus. unconducteurdeplusde25anstitulairedupermisdepuisplusdedeuxansbnficiedutarifverts'il n'est l'origine d'aucun accident et du tarif orange pour un accident, du tarif rouge pour deux accidents, et refus au-del Deplus,pourencouragerlafidlitdesclientsaccepts,lacompagnieproposeuncontratdelacouleur immdiatement la plus avantageuse s'il est entr dans la maison depuis plus d'un an. Ecrirel'algorithmepermettantdesaisirlesdonnesncessaires(sanscontrledesaisie)etdetraiterce problme. Avant de se lancer corps perdu dans cet exercice, on pourra rflchir un peu et s'apercevoir qu'il est plus simple qu'il nen a l'air (cela s'appelle faire une analyse !) 5. Perdu de recherche Ecrireunprogrammequifaitsaisirparlutilisateur20valeursdansuntableaude20cases,puisqui demande ensuite un 21me nombre. Le programme doit rechercher si ce nombre fait ou non partie des 20 valeurs prcdemment saisies dans le tableau. 3-d : Pour les champions 1. La date Ecrivezunalgorithmequiaprsavoirdemandunnumrodejour,demoisetd'annel'utilisateur, renvoie sil s'agit ou non d'une date valide. Cetexerciceestcertesdunmanquedoriginalitaffligeant,maisaprstout,enalgorithmiquecomme ailleurs, il faut connatre ses classiques ! Et quand on a fait cela une fois dans sa vie, on apprcie pleinement lexistence dun type numrique date dans certains langages). Il n'est sans doute pas inutile de rappeler rapidement que le mois de fvrier compte 28 jours, sauf si lanne est bissextile, auquel cas il en compte 29. Lanne est bissextile si elle est divisible par quatre. Toutefois, les annes divisibles par 100 ne sont pas bissextiles, mais les annes divisibles par 400 le sont. Ouf ! Undernierpetitdtail:vousnesavezpas,pourlinstant,exprimercorrectementenpseudo-codelide quun nombre A est divisible par un nombre B. Aussi, vous vous contenterez dcrire en bons tlgraphistes que A divisible par B se dit A dp B . 2. Pour la combine, on sarrangeEcrivezunprogrammequipartirdedeuxnombresnetp,calculelavaleurdesarrangementsetdes combinaisons de ces deux nombres. 4. Hrner Remarque : Soit P(x) un polynme de degr n. P(x) peut s'crire sous la forme suivante : ( )( )( ) ( ) ( )2 3 20 1 2 3 0 1 2 3 0 1 2 3... ... ... P x a a x a x a x a x a a x a x a x a x a x a = + + + + = + + + + = + + + +On peut utiliser cette forme pour calculer l'image d'un rel x0 par P. C'est la mthode de Hrner. Algorithme : Demander le degr n du polynme la valeur de x0 les coefficients du polynme. Affecter la valeur de an A Pour i allant de n 1 affecter la valeur de Ax+ai1 A Afficher A Voici comment cet algorithme peut se traduire en langage machine : CommentairesTICASIO prompt N,X"N" : ?N "X" : ?X TI : Vide la liste L1 du mode statistique.clrlist L1 casio:Annonceladimensiondelaliste (sur une GRAPH 35) N+1 Dim List1 Demandelescoefficientsdupolynme puis les met dans la liste 1. TI : L'utilisateur devra entrer les coefficients sous cette forme : {2 ; 1 ; 3} casio :donnerlescoefficientsdansl'ordre a0, a1, a2 Disp " { }0 1 2; ; ; ... a a a " input L1 for 1 I to N+1 "coef?":?List1[I] next remarque : les coefficients sont indics de 0 nmaisleslmentsdelalistesont numrots de 1 n+1. LorsqueIdcrmente,ilfautprciserle pas : 1 L1(N+1)A for (I, N+1, 2, 1) 1( 1) A X L I A + end Disp A List1[N+1]A for N+1 I to 2 step 1 List1[ 1] A X I A + Next A Questions : 1. Tester cet algorithme avec 2 3 4( ) 2 4 3 2 0, 5 P x x x x x = + + et 07 x = . 2. Ecrirecepolynmesouslaformeprsenteenintroductionpuisdterminerlenombred'oprations effectues (additions et multiplications) pour calculer P(7). 3. Compter le nombre d'oprations effectues pour le calcul suivant : 2 3 4(7) 2 4 7 3 7 2 7 0, 5 7 P = + + . 4. Ecrire l'algorithme qui permet de calculer l'image de x0 comme dans le calcul prcdent. TICASIO prompt N,X "N" : ?N "X" : ?X clrlist L1 N+1 Dim List1 Disp " { }0 1 2; ; ; ... a a a " input L1 for 1 I to N+1 "coef ?" : ?List[1] next L1(1)A for (I, 2,N+1) 11( )IL I X A A + end Disp A List1[1]A for 2 I to N+1 1List1[ ]II X A A + Next A Pour comparer les vitesses d'excution des deux programmes prcdents (calcul de l'image d'un nombre parunpolynme)surlescalculatricesTI,,onpourralesfairetourneraveclepolynmededegr100et dont tous les coefficients sont 10 : seq(10,K,1,101,1) (Avec X=2 ; 4 secondes avec Hrner et 7 secondes avec l'autre !) Pour information : Pour un polynme de degr n : Lenombred'oprationsavecl'criture 2 10 1 2 1...n nn na a x a x a x a x+ + + + + estdel'ordrede 22n,plus prcisment 232 2nn + . Le nombre d'oprations avec l'criture 0 1 2 3 1( ( ( ... ( )... )n na x a x a x a a xa+ + + + +est de l'ordre de 2n. 5. Dichotomie Le programme suivant donne un encadrement d'amplitude choisie d'une solution de l'quation f(x)=0. Il ncessite de connatre un intervalle o se situe la solution. Algorithme : Demander l'amplitude E les bornes de l'intervalles : A et B la fonction f. Tant que l'amplitude de l'intervalle [A;B] est suprieure E : Dterminer le centre de l'intervalle [A;B] Affecter cette valeur C. Regarder si la solution se situe dans l'intervalle [A ; C] ou [C ; B] Recommencer avec l'intervalle o se situe la solution.Afficher A et B. Voici comment cet algorithme peut se traduire en langage machine : CommentairesTICASIO TI : L'utilisateur entrera la fonction avec des guillemets. Par exemple : " 2X-3 " casio : L'utilisateur devra aller dans le mode GRAPHentrerlafonctionavantd'excuter le programme. casio : Pour calculer l'image de C par Y1 : CX Y1 Y input "Y1=", Y1 prompt E, A, B While abs(A-B)>E (A+B)/2 C if 1 1( ) ( ) 0 YC Y A sthen CB else "A":? A "B":? B "E":? E While Abs(A-B)>E:Do (A+B)/2 C CX Y1 Y AX Y1 Z CA end End Disp A, B If0 Y Z sThen CB Else CA IfEnd WhileEnd A B Stop Questions : 1. Tester cet algorithme pas pas avec0,1 E =;| | 0;2 I =;( ) 2 3 f x x = . Quelles sont les valeurs de A et B affiches ? 2.1, 4375 A=et1, 5 B = .a. Donner une valeur approche par excs 110de la solution. b. Donner une valeur approche par dfaut 110de la solution. c. Peut-on donner une valeur arrondie 110 de la solution avec ces valeurs de A et B ? Justifier. d. Quelle amplitude faut-il prendre pour avoir une valeur arrondie 110 de la solution ? 3. La solution de l'quation( ) 0 f x= est 32. Quelle instruction peut-on ajouter la fin du programme pour qu'il ne donne que A (ou que B) lorsque c'est la solution exacte ? 6. Arithmtique 6-a : Recherche des entiers n divisant 2n + 1 AlgorithmeDemander n Pour i allant de 1 n Si n divise 2n + 1alors afficher n Fin du Si Fin du Pour Cet algorithme est sduisant et simple mais .sur une machine classique, la division de 2n + 1 par n pose des problmes ds que n dpasse 50 (au passage, une premire analyse aurait permis de faire remarquer que les seules solutions possibles sont des nombres impairs). Il sagit donc de savoir comment exprimer le fait que n divise 2n + 1.http://pagesperso-orange.fr/gery.huvent/irem/ndivise2n+1.pdf 6-b : Problme du Spaghetti Je dispose dun spaghetti. Quelle est la probabilit quen le coupant en trois je puisse former avec les trois bouts obtenus un triangle ? Algorithme Initialisation de la variable R (nombre de succs) Demander le nombre dessais N Pour I allant de 1 N Essai ICouper le premier morceau de longueur X Couper le second morceau de longueur Y Calculer la longueur du troisime morceau Z Si le maximum de ces trois longueurs est infrieur ou gal 0,5 Alors Augmenter R de 1 Fin du Si Fin du Pour Afficher R/N Il reste savoir ce que signifie couper un spaghetti en trois. On peut en effet, le couper en deux puis couper lemorceaulepluslongendeux.Maisest-celaseulesolution ?Ilseraitdoncintressantdechercher diffrents modles et faire complter lalgorithme prcdent. 6-c : Un critre original de recherche de nombres premiers (Critre de Sundaram) On considre le tableau suivant : 471013161922 7121722273237 1017243138 13223140.. 162738.. 193245.. 2237.. OnmontrequesiNestdanscetableau2N+1estcomposetquesiNnyestpas2N+1estpremier. CommentbtirpartirdecetableaulalistedesnombrespremiersinfrieursougauxunentierA donn ? Vous trouverez tous les renseignements dans les deux textes suivants sur les nombres premiers :http://pagesperso-orange.fr/gery.huvent/irem/nbpremier_partie1.pdf http://pagesperso-orange.fr/gery.huvent/irem/nbpremier_partie2.pdf Dans le mme type de registre, quelques programmes et ides : http://ww3.ac-poitiers.fr/math/prof/objets/index.htm 7. Suite de Syracuse La suite de Syracuse est dfinie par 0u-eet1n si est pairPour tout, 2 3u 1 si est impairnnnunn uu+e = + 1. Calculer les premiers termes de la suite pour 01 u =;03 u = et 07 u = . On ne sait pas l'heure actuelle s'il existe un entier u0 pour lequel cette suite n'atteint jamais 1. 2. Ecrire un programme demandant u0 et n l'utilisateur et affichant toutes les valeurs 1 2; ; ... ;nu u u . 3. Ecrire un programme demandant u0 l'utilisateur et affichant toutes les valeurs 1 2, ,...,Nu u uo N est le plus petit entierk-etel que1ku = . 4. Modifier votre programme pour qu'il affiche en plus N et le plus grand lment de la squence (u0, ,uN) Rponses : 1. Pour 0 1 2 31: 4, 2, 1u u u u = = = = u0=1, u1=4, u2=2, u3=1 2.Demanderu0

Demander n Affecter la valeur de u0 U Pour i allant de 1 N Si U est pairAffecter la valeur de U/2 U SinonAffecter la valeur de 3U+1 U Fin Si Afficher U Fin de la boucle Afficher U 3. Demanderu0

Affecter la valeur de u0 U Tant que1 U = Si U est pair Affecter la valeur de U/2 U Sinon Affecter la valeur de 3U+1 U Fin Si Afficher U Fin Tant que 4.Demander u0

Affecter la valeur de u0 U Affecter la valeur 0 N Affecter la valeur de U V Tant que1 U =Affecter la valeur de N+1 N Si U est pair Affecter la valeur de U/2 U Sinon Affecter la valeur de 3U+1 U Fin Si Afficher U Si U>V Affecter la valeur de U V Fin Tant que Afficher V Afficher N 8. Exercices Baccalaurat ES spcialit mathmatiques 8-a : Agence de voyages Baccalaurat ES spcialit - Pondicherry avril 2009 Uneagencedevoyagesorganisediffrentesexcursionsdansunergiondumondeetproposelavisitede sites incontournables, nomms A, B, C, D, E et F. Cesexcursionssontrsumessurlegrapheci-dessousdontlessommetsdsignentlessites,lesartes reprsententlesroutespouvanttreempruntespourrelierdeuxsitesetlepoidsdesartesdsignele temps de transport (en heures) entre chaque site. 1. Justifier que ce graphe est connexe. 2. UntouristedsireallerdusiteAausiteFen limitant au maximum les temps de transport. a. Enutilisantunalgorithme,dterminerlaplus courte chane reliant le sommet A au sommet F. b. Endduireletempsdetransportminimalpour aller du site A au site F. 3. Untouristedsirantapprcierunmaximumde paysagessouhaitesuivreunparcoursempruntant toutes les routes proposes une et une seule fois. Siceparcoursexiste,ledcriresansjustifier;dans lecascontrairejustifierquuntelparcoursnexiste pas. 9. Exercices Baccalaurat L spcialit mathmatiques 9-a : Dichotomie Bac L, sp maths Centres trangers, juin 2009. On dfinit une fonction f sur lintervalle [a ; b]. 1. Vrifier que f sannule une seule fois sur [a ; b], eno . 2. On considre lalgorithme suivant : Entre : Introduire un nombre entier naturel n Initialisation : Affecter N la valeur n. Affecter A la valeur a. Affecter B la valeur b. Traitement : Tant que B A > 10N Affecter M la valeur 2A B + Affecter P le produit f(A) f(M) Si P>0, affecter A la valeur de M. Si0 P s , affecter B la valeur M. Sortie :Afficher A Afficher B. a. On a fait fonctionner cet algorithme pour n = 2. Complter le tableau donnant les diffrentes tapes. MP ABB A Initialisation01 Etape 1 Etape 2 b. Cet algorithme dtermine un encadrement de la solutionode lquation f(x) = 0 sur lintervalle [a ; b]. Quelle influence le nombre entier n, introduit au dbut de lalgorithme, a-t-il sur lencadrement obtenu ? 9-b : Diagonales Bac L, sp maths France mtro. & La Runion, sept. 2009 OnappelleDIAGONALEdunpolygonerguliertoutsegmentdedroitejoignantdeuxsommetsnon conscutifsdupolygone.Ainsi,untrianglequilatralnepossdeaucunediagonaleetuncarrenpossde deux. 1. Dansletableauci-dessoustracerencouleurtouteslesdiagonalesdespolygonesrguliers5,6,7,8 cts, puis indiquer leur nombre dans la ligne suivante. Danslasuitedelexercice,onadmetquelenombreddediagonalesdunpolygonergulierncts(n tant un entier naturel suprieur ou gal 3) est donn par la formule :( ) 32n nd= . 2. On cherche dterminer dans quels polygones rguliers le nombre d de diagonales est un multiple entier du nombre n de cts. a. Exploiter ce qui a t fait dans les questions prcdentes pour dire si chacune des propositions suivantes est VRAIE ou FAUSSE. Chaque rponse doit tre justifie. Proposition 1 : Il existe au moins un polygone rgulier pour lequel le nombre de diagonales est le double du nombre de cts. Proposition 2 : Quel que soit le polygone rgulier, le nombre de diagonales de ce polygone est le double du nombre de ses cts. Proposition 3 : Quel que soit le polygone rgulier, le nombre des diagonales de ce polygone est un multiple entier du nombre de ses cts. b. On considre lalgorithme suivant : Entre k est un entier naturel non nul. Initialisation Affecter n la valeur 3. Affecter d la valeur 0. Traitement Tant qued k n < , affecter n la valeur n +1. Calculer ( ) 32n n et affecter la valeur du rsultat d. Sortie Afficher n et d. Faire fonctionner lalgorithme pour k = 3. Interprter le rsultat obtenu en termes de nombres de cts et de diagonales dun polygone rgulier. c. Dmontrer que, pour un entier naturel non nul k donn,d k n = si et seulement si n = 2k +3. d. Dterminerlespolygonesrguliersdanslesquelslenombreddediagonalesestunmultipleentierdu nombre de cts. n345678 diagonales d02 9-c : Fractale Baccalaurat L spcialit France juin 2009 Oneffectueuncoloriageenplusieurstapesdun carr de ct de longueur 2 cm. Premire tape du coloriage : on partage ce carr en quatrecarrsdemmeaireetoncolorielecarr situenbasgauchecommeindiqusurlafigure ci-contre (la figure nest pas en vraie grandeur). Deuximetapeducoloriage :onpartagechaque carrnonencorecolorienquatrecarrsdemme aire et on colorie dans chacun, le carrsitu en bas gauche, comme indiqu sur la figure ci-contre. Onpoursuitlestapesducoloriageencontinuant le mme procd. Pourtoutentiernatureln,suprieurougal1,ondsigneparAnlaire,exprimeencm2,delasurface totale colorie aprs n coloriages. On a ainsi A1 = 1. La surface colorie sur la figure la 2metape du coloriage a donc pour aire A2. Les deux parties suivantes A et B de cet exercice peuvent tre traites de manire indpendante. Partie A 1. Calculer A2 puis montrer que 33716A = . 2. On considre lalgorithme suivant : Entre : P un entier naturel non nul. Initialisation : N = 1 ; U = 1. Traitement : Tant que NsP : Afficher U Affecter N la valeur N +1 Affecter U la valeur 5 1U4 2 +a. Faire fonctionner cet algorithme avec P = 3. b. Cet algorithme permet dafficher les P premiers termes dune suite U de terme gnral Un. Dire si chacune des deux propositions suivantes est vraie ou fausse. Justifier la rponse. Proposition 1 : Il existe un entier naturel n strictement suprieur 1 tel que Un = An. Proposition 2 : Pour tout entier naturel n suprieur ou gal 1, Un = An. Partie B On admet que, pour tout entier naturel n suprieur ou gal 1, 1314n nA A+= + . 1. On pose pour tout entier n suprieur ou gal 1,4n nB A = . a. Calculer B1. b. Montrer que pour tout entier n suprieur ou gal 1, 134n nB B+= . c. Quelle est la nature de la suite (Bn) ? d. Exprimer, pour tout entier n suprieur ou gal 1, le terme gnral Bn de la suite (Bn) en fonction de n. 2. Quel est le comportement de An lorsque n tend vers+? Justifier la rponse. Donner une interprtation de ce rsultat en rapport avec laire de la surface colorie. 9-d :Divisibilit par 13 Baccalaurat L spcialit Polynsie juin 2009 Pour tout nombre entier naturel n, on pose A(n) = 5n 1. Le but de lexercice est dtudier la divisibilit de A(n) par 13. 1. Calculer A(2), A(3), A(4). Sont-ils divisibles par 13 ? 2. On considre lalgorithme suivant : Entre : Saisir un nombre entier naturel non nul N. Initialisation : Affecter m la valeur N. Traitement : Tant que m >6 affecter m la valeur m 13. Sortie : Afficher n. a. Faire fonctionner lalgorithme avec N = 25 puis N = 125. b. Quobtiendrait-on en sortie si on faisait fonctionner cet algorithme avec N = 54 ? 3. a. Dmontrer que, pour tout nombre entier naturel k : 54k 1 modulo 13 54k+1 5 modulo 13 54k+2 1 modulo 13 54k+3 5 modulo 13 b. Application : Quel est le reste dans la division euclidienne de 52009 1 par 13 ? c. Pour quelles valeurs de lentier n, lentier A(n) est-il divisible par 13 ? 9-e :Suites et logique Baccalaurat L spcialit Am. du Nord juin 2009 Partie A On considre lalgorithme suivant : Entre : n est un entier naturel non nul Initialisation : Donner A et B la valeur 1 et K la valeur 0 Traitement : Tant que K < n, ritrer la procdure suivante donner A la valeur 4A donner B la valeur B + 4 donner K la valeur K +1 Sortie : Afficher A et B 1. Justifier que, pour n = 2, laffichage obtenu est 16 pour A et 9 pour B. Reproduire sur la copie et complter le tableau suivant : Valeur de n1234 Affichage pour A16 Affichage pour B9 2. Pour un entier naturel non nul quelconque n,lalgorithme affiche en sortie les valeurs des termes de rang n dune suite gomtrique et dune suite arithmtique. Donner le premier terme et la raison de chacune de ces suites. Partie B Voici quatre propositions : P1 : Pour tout n entier naturel, 4n > 4n +1 P2 : Pour tout n entier naturel, 4ns4n +1 P3 : Il existe au moins un entier naturel n tel que 4ns4n +1 P4 : Il existe un unique entier naturel n tel que 4ns4n +1 1. Pour chacune delles, dire sans justification si elle est vraie ou fausse. 2. Lune des trois dernires est la ngation de la proprit P1. Laquelle ? Partie C 1. Soit p un entier naturel non nul. a. Dvelopper et rduire 4(p + 1) + 1 4(4p + 1). b. En dduire lingalit 4(4p + 1) > 4(p + 1) + 1. 2. Dans cette question, toute trace de recherche, mme incomplte, ou dinitiative non fructueuse, sera prise en compte dans lvaluation. Pour quelles valeurs de lentier naturel n, a-t-on lingalit 4n > 4n +1 ? 9-f : Suite arithmtiqueBaccalaurat L spcialit - Liban juin 2009 On considre lalgorithme suivant : Entre : N est un entier naturel Initialisation :Donner P la valeur 0 Donner U la valeur 4 Donner S la valeur 4 Traitement : Tant que P < N Donner P la valeur P +1 Donner U la valeur 4+2P Donner S la valeur S +U Sortie : Afficher S 1. Faire fonctionner lalgorithme pour N = 5. On fera apparatre les diffrentes tapes du droulement de lalgorithme dans un tableau comme ci-dessous reproduire sur la copie. Valeur de PValeur de UValeur de S Initialisation044 tape 11610 tape 22 . . . . . . Affichage 2. On considre la suite (Un) dfinie sur par : Un+1 =Un +2 et U0 = 4. a. CalculerU1, U2 etU3. b. Soit p un nombre entier naturel. Donner, en fonction de p, la valeur deUp. Calculer U21. 3. On fait fonctionner lalgorithme pour N = 20, la valeur affiche par S est alors 504. Quelle est la valeur affiche par S si on fait fonctionner lalgorithme pour N = 21 ? 4. OnfaitfonctionnerlalgorithmepourunentiernaturelNquelconque.ExprimerlavaleurafficheS laide des termes de la suite (Un). 9-g : Congruences modulo 7 Baccalaurat L spcialit - FranceLa Runion septembre 2008 1. a. Dterminer le reste de la division euclidienne de 23 par 7. b. 23 et 26 sont-ils congrus modulo 7 ? Justifier la rponse. c. Dmontrer que, pour tout entier naturel n, 23n 1 (modulo 7).Que peut-on en dduire pour le reste de la division euclidienne de 22007 par 7 ? 2. On considre lalgorithme suivant : Entre : n est un entier naturel. Initialisation : Donner u la valeur initiale n. Traitement : Tant que u >7, affecter u la valeur u 7. Sortie : Afficher u. a. Faire fonctionner cet algorithme avec n = 25. b. Proposer deux entiers naturels diffrents qui donnent le nombre 5 en sortie. c. Peut-on obtenir le nombre 11 en sortie ? Justifier. d. Quobtient-on en sortie si on fait fonctionner cet algorithme avec le nombre 22007 ? Mme question avec le nombre 22008. Justifier. e. On a fait fonctionner cet algorithme avec un nombre a et on a obtenu en sortie le nombre 3. On a fait fonctionner cet algorithme avec un nombre b et on a obtenu en sortie le nombre 5. Si on fait fonctionner cet algorithme avec le nombre3 a b + , quobtiendra-t-on en sortie ? Justifier. 9-h : Digicode Baccalaurat L spcialit - FranceLa Runion septembre 2007 Uneentreprisederecyclagercupreunlotdedigicodesayanttousun clavier identique celui reprsent ci-contre. Chacun de ces digicodes a t programm pour fonctionner avecun code constitu de deux signes choisis parmi les douze figurant sur ce clavier. Par exemple A0, BB, 43 sont des codes possibles. Pour remettre en tat de fonctionnement un tel digicode, il faut retrouver son code. Pourfaciliterunetellerecherche,atinscritsurlebotierdechaque digicode unnombre R qui dpend du code. Cenombrea t obtenu dela manire suivante : Le code est considr comme un nombre crit en base 12. est le chiffre dix et le chiffre 11. Le nombre R inscrit sur le botier est le reste de la division euclidienne du code, converti en base 10, par 53. R est donc un nombre crit en base 10 et tel que0 53 R s < . 1. Combien y a-t-il de codes possibles ? 2. On suppose que le code dun digicode est . a. crire en base 10 le nombre dont lcriture en base 12 est ()douze. b. Dterminer le nombre R inscrit sur le botier de ce digicode. 3. Sur le botier dun digicode est inscrit le nombre R gal 25. Dmontrer que (21)douze peut tre le code de ce digicode. 4. On considre lalgorithme suivant : Entre : R un entier naturel. Initialisation : L liste vide ; n = 0. Traitement : Tant que 53n +Rs143, mettre dans la liste L la valeur de 53n + R puis ajouter 1 n. Sortie : Afficher la liste L. a. Faire fonctionner cet algorithme pour R = 25. b. OnsupposequelenombreRinscritsurlebotierdundigicodeest25.Quelssontlestroiscodes possibles de ce digicode ? 5. Diresilaffirmationsuivanteestvraieoufausse.Silaffirmationestconsidrecommefausse,en apporter la preuve. Affirmation :quellequesoitlavaleurdeRlalgorithmepermetdetrouvertroiscodesparmilesquelsse trouve le code secret. 9-i : A la photocopieuse Baccalaurat L spcialit - FranceLa Runion - juin 2008 Dans un lyce, un code daccs la photocopieuse est attribu chaque professeur. Cecodeestunnombrequatrechiffreschoisisdanslaliste{0,1,2,3,4,5,6,7,8,9},chaquechiffre pouvant tre rpt lintrieur dun mme code. Par exemple 0027 et 5855 sont des codes possibles. 1. Combien de codes peut-on ainsi former ? 2. Cecodepermetaussidedfinirunidentifiantpourlaccsaurseauinformatique.Lidentifiantest constitu du code quatre chiffres suivi dune cl calcule laide de lalgorithme suivant : Entre :N est le code quatre chiffres. Initialisation : Affecter P la valeur de N ; Affecter S la valeur 0 ; Affecter K la valeur 1. Traitement : Tant que Ks4 : Affecter U le chiffre des units de P ; Affecter K la valeur K +1 ; Affecter S la valeurS K U + ; Affecter P la valeur 10P U ; Affecter R le reste dans la division euclidienne de S par 7 ; Affecter C la valeur 7 R. Sortie la cl : Afficher C. a. Faire fonctionnerlalgorithme avecN = 2282 et vrifier quela clquilui correspond est 3. On prendra soin de faire apparatre les diffrentes tapes du droulement de lalgorithme (on pourra par exemple faire un tableau.). b. Danscettequestion,toutetrace derecherche,mmeincomplte,oudinitiativemmenonfructueuse,serapriseen compte dans lvaluation. Un professeur sidentifie sur le rseau informatique en entrant le code 4732 suivi de la cl 7. Laccs au rseau lui est refus. Le professeur est sr des trois derniers chiffres du code et de la cl, lerreur porte donc sur le premier chiffre du code (qui nest pas gal 4). Quel est ce premier chiffre ? 9-j : Algorithme daprs Bac L spcialit France juin 2007 On considre lalgorithme suivant : Entre :a un entier naturel. Initialisation : L liste vide Affecter la valeur a x. Traitement : Tant que x > 0 ; Effectuer la division euclidienne de x par 7 ; Affecter son reste r et son quotient q ; Mettre la valeur de r au dbut de la liste L ; Affecter q x. Sortie : Afficher les lements de la liste L. Faire fonctionner cet algorithme pour a = 486. On compltera le tableau ci-dessous : rqLx Initialisationvide486 Fin tape 1 Fin tape 2 . . . . . . . . . 9-k : Vingt euros On admet quon obtient le mme reste en divisant un nombre par 9 quen divisant la somme de ses chiffres par 9. Par exemple : 8 753 = 9729+5, le reste est donc 5. 8+7+5+3 = 23 = 29+5, le reste est galement 5. Sur les billets de banque en euros figure un code de 11 chiffres prcd dune lettre. On remplace la lettre par son rang dans lalphabet habituel comportant 26 lettres. On obtient ainsi un nombre 12 ou 13 chiffres et on cherche le reste de la division de ce nombre par 9. Ce reste est le mme pour tous les billets authentiques et vaut 8. Exemple : Code : s00212913862. Rang dans lalphabet de la lettre s ; 19. Nombre obtenu : 1900212913862. Reste pour ce billet : 8 1. Le code u01308937097 figure sur un billet de banque. a. Donner le nombre 13 chiffres correspondant ce code. b. Calculer le reste de la division par 9 de la somme des 13 chiffres de ce nombre. c. Que peut-on dire de ce billet ? 2. Surunbilletauthentiquefigurelecodes0216644810x,xpourledernierchiffre,illisible.Montrerque x + 42 est congru 8 modulo 9. En dduire x. 3. Sur un autre billet authentique la partie du code form par les 11 chiffres est 16122340242, mais la lettre qui les prcde est efface. On appelle n le rang dans lalphabet de la lettre efface. a. Dterminer les valeurs possibles de n. b. Quelles sont les possibilits pour la lettre efface ? 9-l : Time is money Baccalaurat L - Nouvelle-Caldonie - novembre 2005 Une horloge lectronique a t programme pour mettre un bip toutes les sept heures. Le premier bip est mis le 31 dcembre 2004 minuit. 1. a. quelle heure est mis le dernier bip du 1er janvier 2005 ? b. quelle heure est mis le premier bip du 2 janvier 2005 ? c. quelle heure est mis le dernier bip du 2 janvier 2005 ? d. quelle heure est mis le premier bip du 3 janvier 2005 ? Expliquer les rponses. 2. a. Montrer que : 24 3(modulo7). b. En dduire le reste de la division euclidienne de 224 par 7 et le reste de la division euclidienne de 324 par 7. Justifier les rponses. Complter le tableau suivant : n12345678910 Reste de la division euclidienne de n24 par 7 c. Expliquer pourquoi lhorloge met un bip minuit tous les 7 jours et tous les 7 jours seulement. 3. On rappelle que lanne 2005 est une anne non bissextile et comporte donc 365 jours. a. Dterminer le plus petit entier naturel a tel que : 365 a(modulo7). b. quelle date lhorloge mettra-t-elle un bip minuit pour la dernire fois en 2005 ?9-m : ISBN Baccalaurat L spcialit - Nouvelle-Caldonie - novembre 2004 Tous les ouvrages publis sont identifis par un numro ISBN (International Standard Book Number) qui indique la langue de publication, lditeur et la rfrence de louvrage chez cet diteur.Unnumro ISBN est constitu de neuf chiffres (cest--dire neuf entiers compris entre 0 et 9) suivis dun espace et dune cl. Cette cl est un chiffre ou la lettre X (le 10 en numration romaine). PourdterminerlacldunnumroISBNdontlesneufpremierschiffressontabcdefghi,oncalculele nombre N = a + 2b + 3c + 4d + 5e + 6f + 7g + 8h + 9i, puis on dtermine le nombre r compris entre 0 et 10 qui est congru N modulo 11.Si le nombre r est strictement infrieur 10, la cl est gale r ; si le nombre r est gal 10, la cl est X. 1. Vrifier que la cl du numro ISBN 190190340 0 est correcte. 2. Calculer la cl du numro ISBN dont les 9 premiers chiffres sont : 103241052. 3. Le quatrime chiffre du numro ISBN dun ouvrage est illisible. On le note d. La cl de ce numro est 4 et le numro se prsente ainsi : 329d12560 4. a. Montrer que : 4d 2 (modulo 11). b. En dduire le chiffre d. 4. Le premier chiffre et le neuvime chiffre du numro ISBN dun autre ouvrage sont illisibles. On les note a et i. La cl de ce numro est 9 et le numro se prsente ainsi : a32100501i. a. Montrer que a 29i (modulo 11). b. Donner deux valeurs possibles du couple (a ; i ). 9-n :Anne bissextile Baccalaurat L spcialit - Amrique du Sud - novembre 2004Uneannebissextilecompte366joursetuneannenonbissextile365jours.Uneanneestbissextilesi son numro est divisible par 4 sauf sil sagit dun sicle. Les sicles, annes dont le numro se termine par deux zros, ne sont, en gnral, pas bissextiles sauf si leur numro est divisible par 400. Quelque exemples : 1996 tait bissextile, 1997ne ltait pas, 1900 non plus mais 2400 le sera. 1. Trouver les deux entiers naturels a et b infrieurs ou gaux 6 tels que :365 a (modulo 7) et 366 b (modulo 7). 2. a. Ensupposantquelepremierjanvierduneannenonbissextilesoitunlundi,expliquerpourquoile premier janvier de lanne suivante sera un mardi. b. Si le premier janvier dune anne bissextile est un lundi, quel jour de la semaine sera le premier janvier de lanne suivante ? 3. Une priode de quatre annes conscutives compte N = 3365+1366 jours. Sans calculer N, justifier que N 5 (modulo 7). 4. Ensupposantquelepremierjanvierduneannesoitunlundi,queljourdelasemaineseralepremier janvier quatre ans plus tard ? Expliquer la rponse. Plus gnralement, pour une date donne, (par exemple le 1er janvier),chaque priode de 4 annes produit un dcalage de cinq jours dans le cycle des jours de la semaine. 5. Complter le tableau ci-dessous. Nombre de priodes de 4 annes J = nombre de jours de dcalage dans le cycle des jours de la semaine Reste de la division de J par 7 000 155 2103 3 4 5 6 7 6. a. Expliquer pourquoi lanne 2004 est bissextile. b. Sachant que le 29 fvrier 2004 tait un dimanche, quel jour de la semaine sera le 29 fvrier 2008 ? Quel jour de la semaine sera le 29 fvrier 2012 ? Expliquer les rponses. c. Quelle sera la prochaine anne o le 29 fvrier sera un dimanche ? Expliquer la rponse. 9-o : Codage affine Baccalaurat L spcialit Pondicherry avril 2005 SophieetMarcsenvoientrgulirementdesmessagesquilscodentafindenepasenrvlerlateneur nimporte qui. Sophie utilise le procd suivant : Tout dabord, chaque lettre de lalphabet, elle associe son rang dans lalphabet (ainsi 1 est associ A, 2 B, etc.). chaque lettre, elle associe donc un nombre entier x. Elle associe ensuite x un nouveau nombre entier y, en posant : y 3x + 5 (modulo 26) avec 0 s y s 25. Elle envoie enfin le message crypt sous forme dune suite de lettres en associant de nouveau au nombre y la lettre qui lui correspond dans lalphabet ( zro elle associera la lettre Z, 1 la lettre A, 2 la lettre B, etc. et 25 la lettre Y). 1. Vrifier quavec lamthode de Sophie : a. le nombre y associ la lettre E est 20, b. la lettre P est code par la lettre A. 2. Complter le tableau suivant. Lettre ABCDEFGHIJKLM rang x dans lalphabet12345 nombre y associ20 lettre envoye Lettre NOPQRSTUVWXYZ rang x dans lalphabet nombre y associ lettre envoyeA 3. Dcrypter ensuite laide de cette mthode le message : S F S T O T J R H M C T R H M F D P T J. 9-p :Palindrome Daprs TL sp maths, banque dexercices 2006On dit quun nombre est un palindrome dans un systme de numration sil peut tre lu de gauche droite ou de droite gauche en gardant la mme valeur. Par exemple, 34543 est un palindrome dans le systme de numration dcimale. 1. Le nombre 3773 est un palindrome. Quelle est son criture en base cinq ? Est-ce un palindrome en base cinq ? 2. a. Lenombre(2002)cinqestunpalindromeenbasecinq.Est-ceunpalindromedanslesystmede numration dcimale ? b. Tous les nombres de quatre chiffres qui sont des palindromes en base cinq sont-ils des palindromes dans le systme de numration dcimale ? 3. Onconsidreunnombredequatrechiffresquiestunpalindromedanslesystmedenumration dcimale. Il scrit abba. Etudier la divisibilit par 11 de ce nombre. 4. Ecrireunalgorithmepermettantdedtectersiunnombrede3chiffresestunpalindrome.Mme question avec un nombre de 4 chiffres. 9-q : Algorithme 1 Daprs TL sp maths, banque dexercices 2006Soit N un entier naturel non nul. On considre lalgorithme suivant : 1. Initialiser en donnant A et I la valeur de N. 2. Tant que I > 2, ritrer la procdure suivante :Donner I la valeur I 1 Donner A la valeur A I 3. Donner A la valeur A 1. 4. Afficher A. 1. Pour tout entier naturel N on note AN le nombre affich ltape 4 de cet algorithme. a. Calculer A1, A2, A3 et A4. b. Vrifier que A5 = 119. c. Calculer A10. 2. Pour chacune des propositions suivantes, dire si elle est vraie ou fausse en justifiant la rponse donne : a. AN est un nombre premier pour certaines valeurs de N. b. AN est un nombre premier pour nimporte quelle valeur de N. c. Quel que soit lentier naturel non nul N, si N est premier, alors AN est premier. d. Il existe AN premier tel que N nest pas premier. 3. Etudier la parit des nombres AN. 9-r : Algorithme 2 Daprs TL sp maths, banque dexercices 20061. On considre lalgorithme n1 suivant : Entre :n un entier naturel Initialisation : donner u la valeur initiale nTraitement : tant que u > 11 affecter u la valeur u 11 Sortie : afficher u a. Faire fonctionner cet algorithme pour n = 35 puis pour n = 55. b. Soit un entier naturel n quelconque. En imaginant que lon fasse fonctionner cet algorithme avec n, quel lien existe-t-il entre n et le nombre entier naturel u obtenu en sortie ? 2. On considre lalgorithme n2 suivant : Entre :a un lment de {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, b un lment de {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Traitement : affecter u la valeur a + 10b affecter v la valeur b + 10a affecter m la valeur v + 100u Sortie : afficher m a. Faire fonctionner cet algorithme pour a = 1 et b = 2, a = 2 et b = 1. b. Ecrire en base 10 le nombre m donn en sortie par cet algorithme pour deux nombres a et b quelconques mis en entre dans cet ordre. 3. Apartirdedeuxnombresaetbquelconques,lmentsdelensemble{1,2,3,4,5,6,7,8,9}, lalgorithmen2donneensortieunnombrem.Ondonnecenombremcommeentrelalgorithmen1. En crivant m en fonction de a et de b, expliquer pourquoi on obtient toujours 0 comme rsultat. 9-s : Algorithme 3 Daprs TL sp maths, banque dexercices 2006On considre lalgorithme suivant : Entre :X entier naturel, Y entier naturel non nul tel que X < Y , n entier naturel Initialisation : L liste vide ; Donner x et r la valeur de X, donner y la valeur de Y ; Traitement : Pour i=1 jusqu n Donner x la valeur de 10 r Calculer le quotient entier de x par y et laffecter q Calculer le reste de la division euclidienne de x par y et laffecter r Ajouter le contenu de q la liste L Sortie : Afficher L. 1. a. Quobtient-ondanslalisteLlorsquelonfaitfonctionnercetalgorithmeavecenentresX = 2, Y = 11 et n = 6 ? b. Interprter le contenu de la liste L relativement au quotient XY. 2. On sintresse dans cette question au cas o X = 5 et Y = 14. Onsouhaiteprogrammercetalgorithmeavecuntableurafindobtenirdesrsultatsanaloguesaux suivants : La valeur de X a t saisie en cellule B3 et celle de Y en cellule C3. a. Dans quelle plage de cellules retrouve-t-on le contenu de la liste L ? b. QuellesformulessaisirencelluleD3etE3silonsouhaitepouvoirlesrecopierrespectivementdansles plages de cellules D4:D15 et E4:E15 ? c. Quelle formule saisir en cellule B4 ? d. SilonrecopiedanslaplagedecellulesA16:E16lesformulessaisiesdanslaplagedecellules A15:E15 , quels contenus va-t-on obtenir ? e. A quelle valeur de n suffit-il de sarrter pour tre en mesure de prvoir la suite de tous les contenus des colonnes B, D et E ? Pourquoi ? 3. Onaprogrammsurtableurlalgorithmedonnendbutdexerciceetobtenulersultatsuivant. Malheureusement lors de la capture dcran les contenus de certaines cellules ont t effacs. Il manque en particulier des valeurs de X et Y. a. Quellecrituredcimaleillimiteduquotient XYpeut-ondonnergrceauxinformationsdonnespar cette capture ? b. Retrouver X et Y. Remarque : les fonctions utilises peuvent tre : la fonction partie entire note ENT (=ENT(x)), qui, tout nombre rel x associe lunique entier relatif n tel que1 n x n s < +; la fonction MOD : =MOD(nombre, diviseur) qui donne le reste de la division euclidienne dunombre par le diviseur. 10. Rfrences Un cours assez complet :http://www.ac-nancy-metz.fr/eco-gestion/eric_crepin/algo/exercices/presentation.htm Une introduction claire http://dept-info.labri.fr/ENSEIGNEMENT/INITINFO/initinfo/support.html Le cycle terminal en srie L (document daccompagnement) http://www.cndp.fr/archivage/valid/73366/73366-12310-16932.pdf http://icosaweb.ac-reunion.fr/RsrcPeda/Term/Docs/TerminaleLSpecialite/index.htm http://icosaweb.ac-reunion.fr/RsrcPeda/Term/Docs/TerminaleLSpecialite/Algo.htm Banque dexercices TL http://icosaweb.ac-reunion.fr/RsrcPeda/Term/Docs/TerminaleLSpecialite/L2006.pdf