TP : fractions unitaires et périodicité

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
Contenu