---
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
kernelspec:
  display_name: C++17
  language: C++17
  name: xcpp17
rise:
  auto_select: first
  autolaunch: false
  centered: false
  controls: false
  enable_chalkboard: true
  height: 100%
  margin: 0
  maxScale: 1
  minScale: 1
  scroll: true
  slideNumber: true
  start_slideshow_at: selected
  transition: none
  width: 90%
---

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-8871e65d0c07dba2"}}

# TP : fractions unitaires et périodicité

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-f9a970f036e2b3bd"}}

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

```{code-cell}
---
nbgrader:
  grade: false
  grade_id: cell-2aa694517c39cd0c
  locked: true
  schema_version: 3
  solution: false
  task: false
---
#include <vector>
#include <iostream>
using namespace std;
using tableau = vector<int>;
```

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-cdbee297fc69d2bc"}}

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.

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-cdbee297fc69d2bd"}}

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

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-3ce9050810fd9ba3"}}

À 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.

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-36cd2483e21543b6"}}

## Algorithme de division

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-c0f2e00a250998df"}}

- 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$.

```{code-cell}
---
nbgrader:
  grade: false
  grade_id: cell-2aa694517c39cd0d
  locked: true
  schema_version: 3
  solution: false
  task: false
---
/** 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
 **/
```

```{code-cell}
---
nbgrader:
  grade: false
  grade_id: cell-07a129546cc1cbfc
  locked: false
  schema_version: 3
  solution: true
  task: false
---
/// 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
```

```{code-cell}
fractionUnitaire(3, 10)[0]
```

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-03108fe73c1fd2f8"}}

## Recherche d'un algorithme

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-73afe13495aefcbe"}}

- Exécuter la fonction précédente à la main pour `n=7`.
- Que remarque-t-on sur les valeurs successives de `r`.

+++ {"nbgrader": {"schema_version": 3, "solution": true, "grade": true, "locked": false, "task": false, "points": 0, "grade_id": "cell-5fdeea9d6c4a011e"}}

Votre réponse ici

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-8d91e2dc34b9067d"}}

## Implantation de la fonction

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-2cd128856bfbb333"}}

- 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$.

```{code-cell}
---
nbgrader:
  grade: false
  grade_id: cell-d19fd418b56ea721
  locked: false
  schema_version: 3
  solution: true
  task: false
---
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
}
```

```{code-cell}
periode(999)
```

```{code-cell}

```

+++ {"nbgrader": {"schema_version": 3, "solution": false, "grade": false, "locked": true, "task": false, "grade_id": "cell-74b54337048a5622"}}

- 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.

```{code-cell}
---
nbgrader:
  grade: false
  grade_id: cell-d8a205c6a3ba699d
  locked: false
  schema_version: 3
  solution: true
  task: false
---
/// 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 :

```{code-cell}
P
```

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

```{code-cell}
N
```