leçon 1: départ, nombres entiers et algorithme d'Euclide

Je travaille dans l'environnement cygwin sous Windows, python (version 2) y est par défaut, et j'édite mes fichiers python avec emacs.
Sinon, python (version 2) s'installe sous windows 7: ici. Lancer IDLE (Python GUI). 

Le fichier python contenant ce qui suit est là.



sh-4.1$ python
Python 2.7.3 (default, Dec 18 2012, 13:50:09) 
[GCC 4.5.3] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 

# Tout ce qui est après un dièse est considéré par python
# comme un commentaire, donc ignoré

# L'algorithme d'Euclide

# 1. La division euclidienne

# 1.1. Le quotient

# on définit une fonction quotient qui prend deux arguments a et b (1ere ligne)
# puis on teste la condition logique a<b (ligne 2)
# si la condition est vérifiée, alors on exécute ce qui suit les 2 points,
# qui consiste à donner la valeur dans cas de quotient(a,b) (ligne 3)
# si la condition n'est pas vérifiée, on exécute ce qui suit
# le mot-clé else (ligne 4): le résultat est obtenu en calculant
# la fonction quotient pour les arguments a-b et b.
# Il s'agit d'un calcul récursif, comme lorsque l'on définit une
# suite par récurrence: u_n+1 = f(u_n).

# pour exécuter la définition de la fonction qui suit, la copier
# et la coller sur la ligne de commande de python, puis finir par
# un retour chariot (Entrée)

def quotient(a,b):
  if a<b:  return 0
  else: return 1+quotient(a-b,b)

quotient(7,2)

# les entiers de python ne sont pas bornés

quotient(500000000000000000000000000000,21111111111111111111111111111)

quotient(-7,2)

# problème, on a pas traité les nombre négatifs, redéfinissons la fonction

def quotient(a,b):
  if a<0: return - quotient(-a,b)
  elif b<0: return - quotient(a,-b)
  elif a<b: return 0
  else: return 1+quotient(a-b,b)

quotient(7,2)
quotient(-7,2)
quotient(7,-2)
quotient(-7,-2)

# remarquer les tests successifs: 
# if ...:... elif ...:... elif ...:... else:...

# 1.2. Le reste

def reste(a,b):
  return a-b*quotient(a,b)

reste(7,2)
reste(-7,2)
reste(7,-2)
reste(-7,-2)


# cette définition du reste et du quotient pour les nombres négatifs n'est pas la seule possible...

# 2. L'algorithme d'Euclide

# il consiste à diviser a par b, ce qui donne un reste b1,
# s'il est non nul on divise b par b1, ce qui donne un reste b2,
# puis ainsi de suite jusqu'à arriver à un reste nul.
# Le dernier reste non nul est alors le pgcd de a et b.

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

pgcd(6,4)
pgcd(24,15)
pgcd(24543543543,155435434)

# on peut, en se servant des quotients dans cet algorithme,
# calculer les coefficients de Bezout u et v tels que
# u a + v b = pgcd(a,b)
# le resultat de cette fonction est une liste à deux éléments uv=[u,v]
# on accède au premier par la syntaxe uv[0] et au second par uv[1]

def bezout(a,b):
  if b==0: return [1,0]
  else:
    uv= bezout(b,reste(a,b))
    return [uv[1],uv[0]-uv[1]*quotient(a,b)]

bezout(3,4)
bezout(8,5)    

# 3. Un exemple avec la suite de Fibonacci

# on définit cette suite par
# f_0 = 0 et f_1 = 1, f_n+2 = f_n+1 + f_n
# posons fib(n) = f_n

def fib(n):
  if n==0: return 0
  elif n==1: return 1
  else: return fib(n-1)+fib(n-2)

fib(10)

# le pgcd de f_a et f_b est f_c où c est le pgcd de a et b

pgcd(fib(18),fib(27))
fib(9)

Exercices:
1. programmer une fonction qui calcule la factorielle d'un entier n
2. programmer une fonction qui calcule la suite de Collatz:
si $u_n$ est pair, $u_{n+1} = \cfrac {u_n} 2$, sinon $u_{n+1} = 3 u_n+1$.