TP : fractions unitaires et périodicité#

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

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

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 et la suivante par le code adéquat
throw runtime_error("Code non implanté");

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) {
    // Remplacer cette ligne et la suivante par le code adéquat
    throw runtime_error("Code non implanté");
}

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 et la suivante par le code adéquat
throw runtime_error("Code non implanté");

La longueur de la plus grande période est :

P

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

N