Algorithme et arithmétique

Merci !

Annales corrigées
Classe(s) : Tle S | Thème(s) : Arithmétique
Type : Exercice | Année : 2013 | Académie : Amérique du Nord
 
Unit 1 - | Corpus Sujets - 1 Sujet
 
Algorithme et arithmétique
 
 

Arithmétique

Corrigé

38

Ens. de spécialité

matT_1305_02_11C

 

Amérique du Nord • Mai 2013

Exercice 2 • 5 points

Partie A

On considère l’algorithme suivant :

 

Variables

a est un entier naturel

b est un entier naturel

c est un entier naturel

Initialisation

Affecter à c la valeur 0

Demander la valeur de a

Demander la valeur de b

Traitement

Tant que a> b

Affecter à c la valeur c + 1

Affecter à a la valeur a − b

Fin de Tant que

Sortie

Afficher c

Afficher a

 

>1. Faire fonctionner cet algorithme avec a= 13 et b= 4 en indiquant les valeurs des variables à chaque étape.

>2. Que permet de calculer cet algorithme ?

Partie B

À chaque lettre de l’alphabet, on associe, grâce au tableau ci-dessous, un nombre entier compris entre 0 et 25.

 

A

B

C

D

E

F

G

H

I

J

K

L

M

0

1

2

3

4

5

6

7

8

9

10

11

12

 
 

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

13

14

15

16

17

18

19

20

21

22

23

24

25

 

On définit un procédé de codage de la façon suivante :

Étape 1 : À la lettre que l’on veut coder, on associe le nombre m correspondant dans le tableau.

Étape 2 : On calcule le reste de la division euclidienne de 9m+ 5 par 26 et on le note p.

Étape 3 : Au nombre p, on associe la lettre correspondante dans le tableau.

>1. Coder la lettre U.

>2. Modifier l’algorithme de la partie A pour qu’à une valeur de m entrée par l’utilisateur, il affiche la valeur de p, calculée à l’aide du procédé de codage précédent.

Partie C

>1. Trouver un nombre entier x tel que 9x ≣ 1 [26].

>2. Démontrer alors l’équivalence :

9m + 5 ≣ p [26] ⇔ m ≣ 3p −15 [26].

>3. Décoder alors la lettre B.

Durée conseillée : 60 min.

Les thèmes clés

Algorithmique • Arithmétique.

Nos coups de pouce

Partie A

>1. Interprétez convenablement la boucle « Tant que » : on répète les calculs tant que la condition indiquée est vérifiée.

>2. Observez les résultats en sortie de l’algorithme pour faire le lien avec les entrées et avoir ainsi une idée du rôle de l’algorithme.

Partie B

>1. Déterminez la valeur de m associée à la lettre U et appliquez alors le procédé de codage indiqué.

Partie C

>1. Essayez de deviner une valeur de x qui convient ou appliquer le théorème de Bézout et l’algorithme d’Euclide.

>2. Démontrez cette équivalence à l’aide d’une double implication. Utilisez le résultat de la question précédente pour démontrer l’une de ces implications.

>3. Déterminez la valeur de p associée à « B » puis utilisez l’équivalence de la question précédente pour réaliser le décodage et retrouver ainsi la valeur de m.

Corrigé

partie a

>1. Faire fonctionner un algorithme

 

Départ

Étape 1

Étape 2

Étape 3

a

13

9

5

1

b

4

4

4

4

c

0

1

2

3

 

À l’étape 3, on observe que a<b donc la boucle « tant que » s’arrête, s’affichent alors les résultats a= 1 et c= 3.

>2. Identifier le rôle d’un algorithme

Cet algorithme permet d’obtenir le reste et le quotient de la division euclidienne de a par b.

En sortie de l’algorithme, le reste de cette division euclidienne de a par b est donné par la variable a, le quotient est donné par la variable c.

partie b

>1. Utiliser un algorithme

Le nombre m associé à la lettre U est m= 20. On a alors . Or . Le reste de la division euclidienne de 185 par 26 est donc p= 3. La lettre associée à 3 est la lettre D.

La lettre U est donc codée par la lettre D.

>2. Modifier un algorithme existant pour répondre à un problème posé

 

Variables

m est un entier naturel

p est un entier naturel

Initialisation

Demander la valeur de m

Traitement

Affecter à p la valeur

Tant que

Affecter à p la valeur

Fin Tant que

Sortie

Afficher p

 

partie c

>1. Utiliser les congruences pour trouver une solution possible pour une équation

9 et 26 sont premiers entre eux. D’après le théorème de Bézout, il existe des entiers relatifs u et v tels que . On cherche u et v à l’aide de l’algorithme d’Euclide.

Donc 9 - 1 = 8 et .

On obtient finalement , ce qui donne u= 3 et v=- 1. On a ainsi la relation , ce qui permet d’obtenir [26], donc x= 3.

>2. Démontrer une équivalence à l’aide d’une double implication

On démontre tout d’abord que  [26]  [26] puis que .

  • Première implication

puis

or [26] donc .

On a ainsi démontré la première implication :.

  • Deuxième implication

or et d’après la question 1..

On obtient donc :

et finalement .

On a ainsi démontré la deuxième implication : .

Conclusion : .

>3. Utiliser une équivalence

Le nombre associé à la lettre B est p= 1.

Pour décoder la lettre B, il faut retrouver la valeur de m. En utilisant l’équivalence de la question précédente, on a donc soit . On obtient ainsi m= 14 ce qui correspond à la lettre O. Le décodage de la lettre B donne donc la lettre O.