TP : récursivité
Article mis en ligne le 30 novembre 2016 par C GIBERT
Imprimer cet article logo imprimer
Programme récursif = programme qui s’appelle lui-même.

Exercice 1

La factorielle de n notée n ! est le nombre n ! = n * (n-1) * (n-2) * ... * 2 * 1

Ecrire un programme récursif qui effectue le calcul de n !, n étant un nombre donné par l’utilisateur ;

n=int(input())

def fact(n):
   ....
   ....

print(fact(n))

Exercice 2

Écrire une procédure récursive qui demande un nombre positif à l’utilisateur et ne retournera ce nombre que s’il est positif. Sinon, demander à l’utilisateur de recommencer.

def entree_positive():
   try:
      n = int(input())
   except:
      ...
   if ... :
       ...
   else:
       ...

nombre = entree_positive()
print(nombre)

Notez bien que l’on veut pouvoir affecter le résultat de la procédure à une variable (voir ci-dessus). Le test ne doit pas afficher None.

Exercice 3

Écrire une fonction récursive qui calcule le produit de deux entiers positifs, puis une autre qui élève un nombre flottant à une puissance entière.

Exercice 4

Le jeu des tours de Hanoï comprend trois axes. L’axe de gauche contient un empilement de disques de diamètres décroissants. Le but du jeu est de déplacer l’empilement sur l’axe de droite en respectant les règles suivantes : les disques sont déplacés un par un ; un disque ne doit jamais être posé sur un disque plus petit.

Proposez une solution algorithmique au problème pour l’empilement de n disques.

Exercice 5

Exercice 6

Les méthodes de tri par sélection, par insertion ou à bulles trouvent leur limite lorsque la taille du tableau est grande. Le tri fusion est une méthode qui s’avère beaucoup plus efficace pour des grands tableaux. Elle repose sur un principe très général de l’algorithmique qui se nomme diviser pour régner. Le principe consiste à remplacer le problème par deux problèmes similaires mais plus petits. Il est alors fréquent que la résolution des deux problèmes plus petits prennent beaucoup moins de temps à résoudre que le seul gros problème de départ. Bien sûr il faudra aussi un peu de temps pour fabriquer la solution du gros problème à partir des solutions des deux petits problèmes.

1 - Nous allons illustrer la méthode en triant par fusion un jeu de 32 cartes :

  • L’élève n° 1 partage le jeu de cartes en deux tas égaux et donne l’un des tas à l’élève n° 2 et l’autre à l’élève n° 3.
  • Les élèves n° 2 et n° 3 font de même. Le premier donne ses tas aux élèves n° 4 et n° 5, le second aux élèves n° 6 et n° 7.
  • Les élèves qui viennent de recevoir les cartes font encore de même et donnent leurs tas (4 cartes) aux élèves restants (n° 8 à n° 15).
  • Les élèves qui viennent de recevoir 4 cartes trient maintenant ces cartes par ordre décroissant (as au dessus du roi, etc). En cas de hauteur identique appliquez la rèlge pique au-dessus de cœur, au-dessus de carreau, au-dessus de trèfle).
  • Chacun rend ensuite son tas à l’élève qui le lui a donné.
  • Les élèves qui viennent de récupérer leur deux tas doivent maintenant rassembler ces deux tas en un seul bien ordonné. C’est l’étape de fusion des deux tas.
  • Chacun rend ensuite son tas à l’élève qui le lui a donné.
  • Les élèves n° 2 et n° 3 fusionnent à leur tour leurs deux tas et rendent le tas ordonné à l’élève n° 1.
  • L’élève n° 1 termine le travail en fusionnant les deux tas.

Avez-vous bien compris ce principe ????

2. Pour mettre en œuvre le tri fusion dans un programme l’une des tâches à réaliser est de fusionner deux tableaux ordonnés en un seul tableau ordonné.

  • Proposez une fonction fusion (écrite en pseudo-code) qui à partir de deux tableaux ordonnés, l’un nommé gauche de taille G et l’autre nommé droite de taille D crée un nouveau tableau ordonné de taille G+D.
  • Proposez une fonction récursive tri-fusion (écrite en pseudo-code) qui trie un tableau table passé en argument. Cette fonction utilisera en particulier la fonction fusion ci-dessus.
  • Codez et mettez au point votre programme.
  • Comparez les temps d’exécution avec ceux des tris par sélection ou par insertion.

Exercice 7

La figure ci-dessous est appelée tapis de Sierpinski. C’est un exemple de figure fractale. Un tapis de Sierpinski est constitué par l’assemblage de huit tapis de taille trois fois plus petite.

Dessiner un tapis de Sierpinski, c’est très simple :

  • Si le tapis est très petit (inférieur à ? pixels) on dessine un carré rouge (personne de verra la triche).
  • Si le tapis est grand, on dessine 8 tapis trois fois plus petits.

1. Rédigez l’algorithme en pseudo-code. 2. Programmez l’algorithme en Python et testez-le.

on partira sur une base :

import Image        # Pour lire et écrire des images dans un fichier
import numpy as np  # Pour manipuler des tableaux de nombres


def sierp(taille):
   pixels = np.zeros((taille, taille, 3), dtype=np.uint8)
 
   def sie(debutx,debuty, pas):
       ....
       ....
   sie(0,0,taille)
   return pixels

pixels =sierp(243)
image = Image.fromarray(pixels)
image.save('u:/sierpinski.jpg')

Dans la même rubrique :

Identification

Calendrier

avril 2019
lunmarmerjeuvensamdim
1234567
891011121314
15161718192021
22232425262728
293012345
Évènements à venir
Pas d'évènements à venir

Articles les plus vus

Statistiques du site

  • Nombre total de visites :
    213397 visiteurs
  • Aujourd'hui :
    8 visiteurs
  • Nombre de pages visitées :
    296221 pages
  • Actuellement en ligne :
    14 visiteurs
  • Ce site contient :
    204 articles
  • Dernier article paru :
    "Cross Solidaire 2019"
    le 9 avril 2019
puce Contact puce Espace rédacteurs puce squelette puce RSS puce Valid XHTML 1.0 Strict
Site réalisé sous SPIP
avec le squelette ESCAL-V2
Version : 2.6.7 [61555]