Exercices (pc1) Corrigé

1. On peut calculer successivement F_{1}, F_{2}, ⋯, F_{n} dans un tableau. On peut aussi procéder plus directement de la façon suivante. On part du fait que si h/k, h′/k′ sont tels que h/k < h′/k′ et que kh′ − hk′ = 1, alors les mêmes propriétés sont vraies des paires h/k, h′′/k′′ et h′′/k′′, h′/k′ où h′′/k′′ est le médian de h/k et h′/k′.

On utlise le type

typedef struct {
  int num;
  int den;
} rat;

La fonction suivante calcule les termes de F_{n} dans ]\frac{h}{k}, \frac{h′}{k′} [ en procédant de façon récursive.

void Farey(rat u, rat v,int n) {
  rat w;
  w.num=u.num+v.num;
  w.den=u.den+v.den;
  if (w.den<=n) {
    Farey(u,w,n);
    printf("%d/%d\n",w.num,w.den);
    Farey(w,v,n);
  }
}

Il est clair que l’on engendre ainsi que des éléments de F_{n}. On les obtient tous puisque tout terme est le médian de ses voisins.

2. Tout d’abord h′/k′ est réduite car

k′′h′ − k′h′′ = 1

Ensuite, on a par définition

\frac{k + n}{k′′} − 1 < f ≤ \frac{k + n}{k′′}

On en déduit que

0 ≤ n − k′′ < k′ ≤ n

et

0 < \frac{1 + (n − k′′)h′′}{k′′} < h′

Ainsi h′/k′ est dans la suite F_{n} (parce que h′, k′ > 0 et k ≤ n) et h′′/k′′ est le médiant de h/k et de h′/k′.

Le programme est donc :

rat Suivant(rat u, rat w,int n){
  int f;
  rat v;
  f=(u.den+n)/w.den;
  v.num=f*w.num-u.num;
  v.den=f*w.den-u.den;
  return v;
}