Fractions irréductibles

Instruction conditionnelle Boucle for Boucle while Listes

Objectif

Classement des fractions irréductibles par rapport à la somme de leur numérateur et de leur dénominateur.

Cet exercice ainsi que sa correction est proposé par Philippe Moutou. Il enseigne au lycée Henri IV à Paris.

Exercice

On veut parcourir l'ensemble des rationnels strictement positifs en rangeant les fractions $\displaystyle\frac{a}{b}$ dans l'ordre de la somme $s=a+b$ et, pour une même valeur de $s$ , dans l'ordre de $a$ .

L'idée est d'aller jusqu'à une certaine fraction $\displaystyle Q=\frac{A}{B}$ et d'afficher le nombre $N$ et le pourcentage $p$ des fractions irréductibles inférieures ou égales à $Q$ .

Avec $\displaystyle Q=\frac{2}{5}$ , les 17 fractions rangées jusqu'à $Q$ étant : $\displaystyle\frac{1}{1}$ , $\displaystyle\frac{1}{2}$ , $\displaystyle\frac{2}{1}$ , $\displaystyle\frac{1}{3}$ , $\displaystyle\frac{2}{2}$ , $\displaystyle\frac{3}{1}$ , $\displaystyle\frac{1}{4}$ , $\displaystyle\frac{2}{3}$ , $\displaystyle\frac{3}{2}$ , $\displaystyle\frac{4}{1}$ , $\displaystyle\frac{1}{5}$ , $\displaystyle\frac{2}{4}$ , $\displaystyle\frac{3}{3}$ , $\displaystyle\frac{4}{2}$ , $\displaystyle\frac{5}{1}$ , $\displaystyle\frac{1}{6}$ et $\displaystyle\frac{2}{5}$ parmi lesquelles 4 sont simplifiables ( $\displaystyle\frac{2}{2}$ , $\displaystyle\frac{2}{4}$ , $\displaystyle\frac{3}{3}$ , $\displaystyle\frac{4}{2}$ ). On doit obtenir $N=13$ et $\displaystyle Q=\frac{13}{17}$ . Jusque-là, on peut se passer des listes mais on souhaite obtenir l'affichage des fractions irréductibles dans l'ordre numérique croissant.

Corrigé

def pgcd(a,b):
  reste=a%b
  if reste==0:
    return b
  else:
    return pgcd(b,reste)

def insere(a,b,L):
  rg,val=0,a/b
  for e in L:
    if e[2]>val:
      break
    else:
      rg=rg+1
  L.insert(rg,[a,b,val])

def denombre(n,d):
  som,tot,rang,irr,red=2,0,0,[],[]
  while som<=n+d:
    num,denom=1,som-1
    while num<som:
      PGCD=pgcd(num,denom)
      if PGCD==1:
        rang=rang+1
        insere(num,denom,irr)
      else:
        insere(num,denom,red)
      tot=tot+1
      if num==n and denom==d:
        return rang,tot,PGCD,irr,red
      num=num+1
      denom=denom-1
    som=som+1

a,b=2,6
rng,tot,gcd,Lirr,Lred=denombre(a,b)
if gcd==1:
  print('{}/{} : fraction irreductible numero {}'.format(a,b,rng))
else:
  print('{}/{} : fraction simplifiable numero {}'.format(a,b,tot-rng))
print('Nombre de fractions inferieures ou egales : {}'.format(tot))
print('Ratio irreductibles : {}%'.format(round(rng/tot*100,1)))
print('Fractions irreductibles par ordre croissant :')
for f in Lirr:
  print('{}/{}'.format(f[0],f[1]),end=' ')
print('\nFractions simplifiables par ordre croissant :')
for f in Lred:
  print('{}/{}'.format(f[0],f[1]),end=' ')

Il faut, pour ce programme, utiliser un module qui détermine le pgcd de deux entiers : pgcd en est une version récursive. La fonction denombre passe en revue les fractions concernées dans l'ordre du dénombrement et enregistre celles qui sont irréductibles dans une liste qu'il faut obtenir triée dans l'ordre numérique. Pour cette raison, j'enregistre les fractions sous la forme de listes de 3 éléments [a,b,d] où d est une valeur décimale (notation flottante des nombres réels) et j'insère la nouvelle fraction au bon endroit en me servant de d pour les ranger.

L'insertion proprement dite est confiée à la fonction insere qui détermine le rang de l'élément qui a une valeur décimale dépassant pour la première fois celle de l'élément à insérer. Remarquez que la liste irr peut être modifiée dans une autre partie que celle où elle a été déclarée sans qu'il soit nécessaire de renvoyer la dite liste par un bloc return. Ce n'était pas demandé mais le programme construit également la liste triée red des fractions réductibles et donne pour une telle fraction, son rang parmi les fractions réductibles.