TP : fractions unitaires et périodicité

Cet exercice est inspiré du problème 26 du projet Euler.

#include <vector>
#include <iostream>
using namespace std;
using tableau = vector<int>;

Une fraction unitaire est une fraction dont le numérateur est 1. Les représentations décimales des premières fractions unitaires sont données dans la table ci-dessous :

Fraction unitaire	représentation décimale
\(1/2\)	0.5
\(1/3\)	0.(3)
\(1/4\)	0.25
\(1/5\)	0.2
\(1/6\)	0.1(6)
\(1/7\)	0.(142857)
\(1/8\)	0.125
\(1/9\)	0.(1)
\(1/10\)	0.1

où 0.1(6) dénote \(0.166666...\), la séquence de un chiffre, 6, se répétant à l’infini. On peut y voir aussi que la représentation décimale de \(1/7\) a une période à six chiffres.

Problème (Euler 26) : déterminer la plus grande période pour une fraction unitaire dont le dénominateur est inférieur à 1000.

À vous de résoudre ce problème! Vous pouvez suivre les indications ci-dessous ou, pour un défi plus élevé, résoudre le problème entièrement par vous même.

Algorithme de division

• En s’inspirant de la manière dont vous faisiez des divisions à la main en primaire, écrivez une fonction fractionUnitaire qui calcule, grâce à des divisions euclidiennes successives, les \(k\) premières décimales de la fraction \(1/n\).

/** Fraction unitaire décimale par décimale.
 *  @param n un entier, dénominateur de la fraction calculée.
 *  @param k un entier, une précision.
 *  @return un tableau de taille k qui contient les k premières décimales de 1/n
 **/

/// BEGIN SOLUTION
tableau fractionUnitaire(int n, int k) {
    vector<int> resultat;
    resultat = vector<int>(k);
    int r = 1;
    for ( int i = 0; i < k; i++ ) {
        resultat[i] = 10 * r / n;
        r = 10*r % n;
    }
    return resultat;
}
/// END SOLUTION

fractionUnitaire(3, 10)[0]

Recherche d’un algorithme

• Exécuter la fonction précédente à la main pour n=7.

• Que remarque-t-on sur les valeurs successives de r.

Votre réponse ici

Implantation de la fonction

• En se basant sur la remarque précédente, inspirez-vous de la fonction factionUnitaire afin d’avoir une fonction qui pour un \(n\) donné calcule la taille de la période de \(1/n\). On pourra utiliser un tableau T de taille n, dont toutes les valeurs sont initialement -1, que l’on remplira de la sorte que T[i] = k si, dans la k-ième exécution de la boucle, \(r=i\).

int periode(int n) {
    /// BEGIN SOLUTION
    vector<int> restes;
    restes = vector<int>(n);
    vector<int> resultat;
    resultat = vector<int>(n);
    for ( int i = 0; i < n; i++ ){
        restes[i] = -1;
    }
    int r = 1;
    int i = 0;
    while ( restes[r] == -1 ){
        restes[r]   = i;
        resultat[i] = 10 * r / n;
        r = 10 * r % n;
        i++;
    }
	// Pour débogguer
    // for ( int j = restes[r]; j < i; j++ ){
    //     cout << resultat[j];
    // }
    // cout << endl;
    return i - restes[r];
    /// END SOLUTION
}

periode(999)

• Vous pouvez maintenant écrire un programme qui répond à la question posée en stockant dans une variable P la longueur de la plus grande période et dans une variable N le plus petit entier positif pour lequel cette période est atteinte.

/// BEGIN SOLUTION
int P = 0;
int N;
int candidat;
for ( int n = 2; n <= 1000; n++){
    candidat = periode(n);
    if (candidat > P){
        P = candidat;
        N = n;
    }
}
/// END SOLUTION

La longueur de la plus grande période est :

P

Le plus petit entier positif pour lequel elle est atteinte est :

N