DS 2 (MP2I 2022-2023) — Décoder les Codeglyphes

Devoir surveillé · MP2I · 2022-2023 · partie IV du DS 2 (4 h au total)

Cours : Programmation impérative

Autres parties : I–II. Correction de programmes · III. Planifier sa route

Décoder les Codeglyphes

Tout au long de votre périple, votre exploratrice, Nicode, déchiffre des stèles contenant d'étranges caractères, les Codeglyphes :

Après avoir passé beaucoup de temps sur le déchiffrage, vous comprenez que tout repose sur votre interprétation de quatre Codeglyphes que l'on vous donne ici sous forme déchiffrée :

Premier Codeglyphe :

#include <stdio.h> int m
ain(void) {int t[]={1,1,
0,4,1,2,1,5,0,8,0,4,0,2,
0,4};for(int i=0;i<16;i=
i+2)printf("%c",'A'+10*t
[i]+t[i+1]);}

Deuxième Codeglyphe :

#include <stdio.h> int m
ain(void){int t[]={3,0,1
3,18,11,21,23,21,24,24,4
};int b=t[3]/2;int a=t[b
]-t[b+1];for (int i=0;i<
=b+1;i++){int b=t[i];if(
t[i]>a)b=t[t[i]-a];prin
tf("%c",'A'+b);}}

Troisième Codeglyphe :

let rec f x xx=if x=0 th
en [] else x mod xx::f(x
/xx)xx and g ll l1 l=mat
ch ll with []->0|x::xx->
x*l1+g xx(l*l1) l in pri
nt_int(g(f 73 4)1 3)

Quatrième Codeglyphe (une partie n'est pas déchiffrée) :

Question 23

On vous demande, pour ces quatre programmes :

• de les présenter sous une forme lisible et acceptée par un compilateur. Cela peut passer par le renommage des variables ou fonctions.
• de dérouler leur exécution, attention pour le quatrième programme, vous devez deviner le bout de code non déchiffré.
• d'expliquer ce que fait le programme dans des termes simples.

Indication : on rappelle que les caractères sont dans l'ordre alphabétique depuis 'A'. Ainsi 'A'+3 est le caractère 'D'.

Corrigé

1. Premier programme :

   #include <stdio.h>
   
   int main(void) {
       int t[]={1,1,0,4,1,2,1,5,0,8,0,4,0,2,0,4};
   
       for(int i=0;i<16;i=i+2) {
           printf("%c",'A'+10*t[i]+t[i+1]);
       }
   }
   

   On comprend ainsi que ce programme va lire le numéro dans l'alphabet, en commençant à \(A = 0\), écrit en décimal sur deux cases consécutives de \(t\). Ainsi, les numéros de lettres sont \(11,4,12,15,8,4,2,4\) ce qui correspond à LEMPIECE.

2. Deuxième programme :

   #include <stdio.h>
   
   int main(void) {
       int t[]={3,0,13,18,11,21,23,21,24,24,4};
       int b=t[3]/2; // 18/2=9
       int a=t[b]-t[b+1]; // t[9]-t[10]=24-4=20
   
       for (int i=0;i<=b+1;i++){
           int c=t[i]; // on change le nom
           if(t[i]>a)
               c=t[t[i]-a];
           printf("%c",'A'+c);
       }
   }
   

   Ici, le plus simple semble de faire un tableau de valeurs :

   \(i\)	\(t[i]\)	\(t[i]-a\)	\(t[t[i]-a]\)	\(c\)	'A' + c
   0	3			3	D
   1	0			0	A
   2	13			13	N
   3	18			18	S
   4	11			11	L
   5	21	1	0	0	A
   6	23	3	18	18	S
   7	21	1	0	0	A
   8	24	4	11	11	L
   9	24	4	11	11	L
   10	4			4	E

   et on lit donc DANSLASALLE.

3. Troisième programme :

   let rec f x xx =
     if x=0
     then []
     else x mod xx
          :: f (x/xx) xx
   and g ll l1 l =
     match ll with
     | []->0
     | x::xx-> x * l1 + g xx (l*l1) l
   in print_int (g (f 73 4) 1 3)
   

   qu'on peut rendre plus lisible en nommant les variables de manière raisonnable :

   let rec decompose n base =
     if n=0
     then []
     else n mod base :: decompose (n/base) base
   and compose ecriture puissance base =
     match ecriture with
     | []->0
     | chiffre::ecriture'-> chiffre * puissance
                           + compose ecriture' (base*puissance) base
   in print_int (compose (decompose 73 4) 1 3)
   

   On voit alors qu'il s'agit de décomposer 73 en base 4 et d'en déduire le nombre en base 3 en lisant cette écriture.

   Ainsi \(73\) donne la liste [1;2;0;1] qui correspond en base 3 à \(1 + 2 \times 3 + 27 = 34\).

4. Quatrième programme :

   #include <stdio.h>
   
   void d(char s[], int k) {
       for(int i=0;i<10;i++)
           s[i]='A'+(((s[i]-'A')+k)%26);
   }
   
   int main(void){
       char s[]="MLDLCXZTCP";
       d(s,???);
       printf(s);
   }
   

   On comprend que la fonction d est un décalage vers la droite de \(k\) unités. Il suffit alors de chercher tous les décalages jusqu'à obtenir une valeur signifiante.

   \(k\)	\(s\)
   0	MLDLCXZTCP
   1	NMEMDYAUDQ
   2	ONFNEZBVER
   3	POGOFACWFS
   4	QPHPGBDXGT
   5	RQIQHCEYHU
   6	SRJRIDFZIV
   7	TSKSJEGAJW
   8	UTLTKFHBKX
   9	VUMULGICLY
   10	WVNVMHJDMZ
   11	XWOWNIKENA
   12	YXPXOJLFOB
   13	ZYQYPKMGPC
   14	AZRZQLNHQD
   15	BASARMOIRE
   16	CBTBSNPJSF
   17	DCUCTOQKTG
   18	EDVDUPRLUH
   19	FEWEVQSMVI
   20	GFXFWRTNWJ
   21	HGYGXSUOXK
   22	IHZHYTVPYL
   23	JIAIZUWQZM
   24	KJBJAVXRAN
   25	LKCKBWYSBO

   On pouvait donc lire BASARMOIRE (pour \(k = 15\)).

5. Au final, la phrase cachée est LEMPIECEDANSLASALLE34BASARMOIRE.

Une fois les quatre programmes compris, vous avez pu découvrir l'emplacement du M-PIece ! Comme un vrai pirate, vous avez alors partagé le trésor avec tout l'équipage.