TP : fractions unitaires et périodicité
Contents
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 tableauT
de taillen
, dont toutes les valeurs sont initialement -1, que l’on remplira de la sorte queT[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 variableN
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