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

// REMPLACER CETTE LIGNE PAR VOTRE RÉPONSE

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.

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) {
    // REMPLACER CETTE LIGNE ET LA SUIVANTE PAR VOTRE RÉPONSE
    throw std::runtime_error("À faire");
}

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.

// REMPLACER CETTE LIGNE PAR VOTRE RÉPONSE

La longueur de la plus grande période est :

P

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

N