Problème

Problème#

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 1

Déterminez $c_6$ et $c_7$.

BEGIN SOLUTION

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

END SOLUTION

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>.

using nombre = vector<int>;

Question 2

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.

/** 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;
    }
}

/// 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

Question 3

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

/// 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;
}

Question 4

On considère la fonction descriptionConway documentée ci-dessous:

/** 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}}$.

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

Question 5

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

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;
}

Question 6

$\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.

/// 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