---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
kernelspec:
  display_name: C++17
  language: C++17
  name: xcpp17
---
# Problème

:::{exercice} Problème
:points: 30
:::

John Conway, prolifique mathématicien anglais (1937-2020), est connu
du grand public pour le jeu de la vie. Il a étudié une suite d'entiers
maintenant connue sous le nom de «suite de Conway» comme suit.
La *description de Conway* d'un entier $n$ est l'entier que l'on
obtient phonétiquement en annonçant les chiffres de $n$. Ainsi,
- L'entier $1$ s'annonce comme «un $1$»; sa description de Conway est
  donc l'entier $11$,
- L'entier $11$ s'annonce comme «deux $1$»; sa description de Conway
  est donc l'entier $21$,
- L'entier $21$ s'annonce comme «un $2$, un $1$»; sa description de
  Conway est donc l'entier $1211$,

En partant de l'entier $1$, on construit par récurrence une suite
$(c_n)_{n\in \mathbb N}$ en définissant $c_{n+1}$ comme la description
de Conway de $c_n$. Ses premiers termes sont:
$$ c_0=1, \quad c_1 = 11, \quad c_2=21, \quad c_3= 1211, \quad
c_4=111221, \quad c_5=312211. $$

**Remarque:** il a été prouvé que la suite de Conway est composée de
nombres ne s'écrivant qu'avec les chiffres 1, 2 ou 3, avec jamais plus
de trois chiffres identiques consécutifs.

:::{question}
:points: 2
:temps: 6
:::

Déterminez $c_6$ et $c_7$.

BEGIN SOLUTION

$c_6=13112221$ et $c_7=1113213211$.

END SOLUTION

:::{endquestion}
:::

Informatiquement, on représentera ici $c_n$ sous la forme d'un tableau
d'entiers représentant ses chiffres. Ainsi $c_3=1211$ sera représenté
par le tableau `vector<int>({1,2,1,1})`. Pour alléger les notations,
nous définirons donc un alias `nombre` pour `vector<int>`.

```{code-cell}
:tags: [remove-cell]

#include <vector>
using namespace std;
```

```{code-cell}
using nombre = vector<int>;
```

{raw:latex}`\enlargethispage{2ex}`

:::{question}
:points: 7
:temps: 6
:::

Sept erreurs se sont glissées dans le code de la fonction suivante,
dont des erreurs de syntaxe, de type et de logique. Entourez les
erreurs et réécrivez le code de la fonction en les corrigeant.

``` c++
/** La fonction egalite4
 * @param t1 un tableau d'entiers de taille >=4 représentant les chiffres d'un nombre
 * @param t2 un tableau d'entiers de taille >=4 représentant les chiffres d'un nombre
 * @return vrai si les quatre premiers chiffres des deux tableaux coïncident; faux sinon
 **/
int egalite4(nombre t1, nombre t2){
    for ( i = 0, i <= 4, i++ ) {
        if ( t1[i] = t2[i] )
            return true
        else
            return false;
    }
}
```

```{code-cell}
/// BEGIN SOLUTION
bool egalite4(nombre t1, nombre t2) { // type de retour
    for (int i = 0; i < 3; i++) { // int manquant, borne incorrecte, points virgules
        if ( t1[i] != t2[i] )     // on ne peut conclure que si les valeurs sont distinctes
            return false;
    }
    return true;                  // point virgule final
}

/// END SOLUTION
```

```{code-cell}
:tags: [remove-cell]

CHECK( egalite4({2,1,1,3,2,1}, {2,1,1,3,3,2}) );
CHECK( not egalite4({1,2,3,1}, {1,3,2,1}) );
CHECK( not egalite4({1,2,3,1}, {1,3,2,2}) );
```

:::{endquestion}
:::


:::{question}
:points: 3
:temps: 4
:::

On considère la fonction `mystère` ci-dessous. Complétez sa
documentation en précisant ce qu'elle calcule.

```{code-cell}
/// BEGIN SOLUTION
/** La fonction mystère
 * @param t un tableau d'entiers
 * @return une copie de t, en excluant toutes les valeurs après un éventuel premier 0
 **/
/// END SOLUTION
nombre mystère(nombre t){
    nombre t2;
    for ( int n = 0; n < t.size() and t[n] > 0; n++ ) {
        t2.push_back(t[n]);
    }
    return t2;
}
```

:::{endquestion}
:::

:::{question}
:temps: 2
:::

On considère la fonction `descriptionConway` documentée ci-dessous:
``` c++
/** La fonction descriptionConway
 * @param t un tableau d'entiers représentant un nombre n
 * @return la description de Conway de n, représentée par un tableau d'entiers
 **/
```

Pour vérifier le bon fonctionnement de cette fonction, on a commencé
par écrire les instructions ci-dessous. Ajoutez deux autres tests en
utilisant les termes suivants de la suite $(c_n)_{n\in\mathbb{N}}$.

```{code-cell}
:tags: [remove-cell]

nombre descriptionConway(nombre c) {
    nombre d;
    for ( auto chiffre: c ) {
        if ( d.size() > 0 and chiffre == d[d.size()-1] )
            d[d.size()-2] ++;
        else {
            d.push_back(1);
            d.push_back(chiffre);
        }
    }
    return d;
}
```

```{code-cell}
CHECK( descriptionConway({1}) == nombre({1, 1}) );
CHECK( descriptionConway({1, 1}) == nombre({2, 1}) );
/// BEGIN SOLUTION
CHECK( descriptionConway({2, 1}) == nombre({1, 2, 1, 1}) );
CHECK( descriptionConway({1, 2, 1, 1}) == nombre({1, 1, 1, 2, 2, 1}) );
/// END SOLUTION
```

% CHECK( descriptionConway({1,1,1,2,2,1}) == nombre{3,1,2,2,1,1} );

:::{endquestion}
:::

:::{question}
:temps: 12
:::

$\clubsuit$ Complétez la définition ci-dessous de la fonction `descriptionConway`:

``` c++
nombre descriptionConway(nombre c) {
    nombre d;
    for ( auto chiffre: c ) {
        /// BEGIN SOLUTION
        if ( d.size() > 0 and chiffre == d[d.size()-1] )
            d[d.size()-2] ++;
        else {
            d.push_back(1);
            d.push_back(chiffre);
        }
        /// END SOLUTION
    }
    return d;
}
```

:::{endquestion}
:::

{raw:latex}`\clearpage`

:::{question}
:temps: 15
:::

$\clubsuit$ La suite de Conway vérifie la propriété suivante: à partir
de $c_7$, les termes de la suite $(c_n)$ commencent cycliquement par
$1113$, $3113$ et $1321$. Ainsi,
- $c_7$ est représenté par un tableau commençant par `{1, 1, 1, 3, ...}`,
- $c_8$ est représenté par un tableau commençant par `{3, 1, 1, 3, ...}`,
- $c_9$ est représenté par un tableau commençant par `{1, 3, 2, 1, ...}`,
- $c_{10}$ est représenté par un tableau commençant par `{1, 1, 1, 3, ...}`,
- $c_{11}$ est représenté par un tableau commençant par `{3, 1, 1, 3, ...}`.

Proposez une fonction `bool cycleConway(int n)` utilisant tout ou
partie des fonctions précédentes et vérifiant la propriété ci-dessus
pour tous les termes $c_k$ pour $7\leqslant k\leqslant n$. Si $n<7$,
la fonction devra renvoyer le booléen vrai.

```{code-cell}
:tags: [remove-cell]

/** La fonction cycleConway
 * @param n un nombre entier
 * @return un booléen : true si c_k (7≤k≤n) débute cycliquement par "1113", "3113" et "1321", false sinon
 **/
```

```{code-cell}
/// BEGIN SOLUTION
bool cycleConway(int n) {
    if ( n < 7 ) { return true; }
    nombre t = {1}; 
    // t représente c_0
    for (int i = 0; i < 7; i++) { 
        t = descriptionConway(t);
    } 
    // t représente maintenant c_7
    for (int i = 7; i <= n; i++) {
        // t représente maintenant c_i
        if ( ( i % 3 == 1 and not egalite4(t, nombre{1,1,1,3}) ) or
             ( i % 3 == 2 and not egalite4(t, nombre{3,1,1,3}) ) or
             ( i % 3 == 0 and not egalite4(t, nombre{1,3,2,1}) ) )
            return false;
        t = descriptionConway(t);
    }
    return true;
}
/// END SOLUTION
```

```{code-cell}
:tags: [remove-cell]

CHECK( cycleConway( 7) );
CHECK( cycleConway(13) );
CHECK( cycleConway(21) );
```

:::{endquestion}
:::

% {raw:latex}`\clearpage`
%
% :::{question}
% :temps: 5
% :::
%  
% Complétez la fonction ci-dessous:
%  
% ```{code-cell}
% /** La fonction proportions123
%  * @param t un tableau d'entiers
%  * @return le tableau [p1, p2, p3] des proportions de 1, de 2 et de 3 dans t
%  **/
% ```
%  
% ```{code-cell}
% using proportions = vector<double>;
% ```
%  
% ```{code-cell}
% proportions proportions123(nombre t){
%     proportions p123 = {0, 0, 0};
%     /// BEGIN SOLUTION
%     // on reprend le principe de la fonction compteDes (exo3 TD6)
%     for ( auto chiffre : t )
%         p123[chiffre - 1]++;
%     /// et on normalize pour avoir la moyenne
%     for ( int i = 0; i < p123.size(); i++)
%         p123[i] /= t.size();
%     /// END SOLUTION
%     return p123;
% }
% ```
%  
% :::{endquestion}
% :::
%  
% :::{question}
% :temps: 12
% :::
%  
% Lorsque $n$ devient grand, il y a en moyenne $50\%$ de chiffres 1,
% $31\%$ de chiffres 2 et $19\%$ de chiffres 3 dans l'écriture d'un
% terme $c_n$.
%  
% On suppose que l'on dispose d'une fonction `presqueEgaux(t1, t2,
% epsilon)` qui teste si deux tableaux `t1` et `t2` de même taille sont
% égaux terme à terme, à `epsilon` près.
%  
% ```{code-cell}
% :tags: [remove-cell]
%  
% /** La fonction presqueÉgaux
%  * @param t un tableau d'entiers
%  * @param2 t2 un tableau d'entiers
%  * @param3 epsilon un flottant double
%  * @return un booléen : false si les tableaux n'ont pas la même taille ou que 
%  * leurs valeurs sont à un même indice distinctes d'au moins epsilon ; true autrement
%  **/
% bool presqueÉgaux(vector<double> t, vector<double> t2, double epsilon);
% ```
%  
% ```{code-cell}
% :tags: [remove-cell]
%  
% bool presqueÉgaux(vector<double> t, vector<double> t2, double epsilon){
%     if ( t.size() != t2.size() ){ return false; }
%     for (int i=0;i<t.size();i++){
%         if ( t[i]-t2[i] < -epsilon || t[i]-t2[i] > epsilon ){ return false; }
%     }
%     return true;
% }
% ```
%  
% ```{code-cell}
% :tags: [remove-cell]
%  
% vector<double> tt = proportions123({1,1,1,1,1,1,2,2,2,3});
% CHECK( presqueÉgaux( tt, {0.6,0.3,0.1}, 0.01) == true );
% CHECK( presqueÉgaux( tt, {0.59,0.3,0.11}, 0.01) == false );
% ```
%  
% Proposez une fonction `proportions123Atteinte(epsilon)` qui renvoie le
% premier indice $n$ de sorte que la proportion de $1$, $2$ et $3$ du
% terme $c_n$ soit à epsilon près les proportions fournies.
%  
% ```{code-cell}
% :tags: [remove-cell]
%  
% /** La fonction proportions123Atteinte
%  * @param epsilon un nombre réel strictement positif
%  * @return un entier, premier indice de sorte les proportions de 1, 2 et 3 du terme c_n soient 
%  * égales aux proportions fournies à epsilon près
%  **/
% ```
%  
% ```{code-cell}
% /// BEGIN SOLUTION
% int proportions123Atteinte(double epsilon){
%     vector<double> cible = {.5, .31, .19};
%     nombre t = {1};
%     int n;
%     for ( n = 0; not presqueÉgaux(proportions123(t), cible, epsilon); n++ ){
%         t = descriptionConway(t);
%     }
%     return n;
% }
% /// END SOLUTION
% ```
%  
% **Remarque:** rien ne dit que les termes d'après respecteront toujours
% à epsilon près ces proportions.
%  
% :::{endquestion}
% :::

:::{endexercice}
:::