1. Compléter la fonction suivante pour qu'elle retourne \(a^{n}\) où \(a\) est supposé de type numérique et n est un entier naturel (on vérifiera que n est bien positif ou nul).

   def puiss(a, n):
       if n ==0:
           ??
       return a * puiss(??, ??)
   

2. Que provoque l'appel puiss(2, -1)? Pourquoi?
3. Modifier votre fonction pour qu'elle fonctionne avec n entier de signe quelconque.

1. Écrire une fonction itérative (c'est à dire qui utilise des boucles) calc_tn_iterative acceptant un unique argument n que l'on supposera entier positif ou nul et qui retourne \(T_{n}\).
2. Un étudiant ajoute le test ci-dessous.
   1. Vérifier que le second échoue mais pas le premier.
   2. Expliquer pourquoi le premier test est tout de même dangereux et ne doit pas être écrit ainsi puis réécrire ce test autrement.

Compléter la fonction calc_tn_recursive suivante pour qu'elle retourne elle aussi \(T_{n}\).

def calc_tn_recursive(n):
    if ??:
        ??
    return ?? * calc_tn_recursive(??)

• L[a:b] désigne la sous-liste de L (en fait une copie superficielle de la sous-liste de L) constitutuée des éléments d'indice i vérifiant a<=i<b.
• L[a:] (équivalent à L[a:len(L)] mais à privilégier) désigne la sous-liste de L (en fait une copie superficielle de la sous-liste de L) constitutuée des éléments d'indice i vérifiant a<=i.
• L[:b] (équivalent à L[0:b] mais à privilégier) désigne la sous-liste de L (en fait une copie superficielle de la sous-liste de L) constitutuée des éléments d'indice i vérifiant i<b.

1. Vérifier que le code ci-dessous affiche l'image donnée encore en-dessous

   import  matplotlib.pyplot as plt
   fig, axes = plt.subplots()
   axes.set_xlim(-3, 3)
   axes.set_ylim(-3, 3)
   
   disque = plt.Circle((0, 0), 1, color="r")
   axes.add_artist(disque)
   circle = plt.Circle((0, 0), 2, fill=False, color="b")
   axes.add_artist(circle)
   
   
   plt.show()
   

   

2. Compléter le programme itératif ci-dessous afin qu'il affiche l'image ci-dessous où les cercles bleus sont de rayon \(1\), \(2\) et \(3\) et les petits disques sont de rayon \(0,2\). On pourra penser aux racines \(n\)-ièmes de l'unité

   import  matplotlib.pyplot as plt
   from math import pi, cos, sin
   
   fig, axes = plt.subplots()
   axes.set_xlim(-5, 5)
   axes.set_ylim(-5, 5)
   
   nbr_sat_min, nbr_sat_max = 3, 5
   R_min, delta_R = 1, 1
   diam_sat = 0.2
   
   R = R_min
   for n in range(nbr_sat_min, nbr_sat_max+1): # boucle sur les grands cercles
       circle = plt.Circle((0, 0), R, color="b", fill=False)
       axes.add_artist(circle)
       for k in range(??): # boucle sur les petits disques du grand cercle
           theta = ??
           x, y = ?? * cos(??), ?? * sin(??)
           disque = plt.Circle((??, ??), ??, color="r")
           axes.add_artist(disque)
       R += delta_R
   
   plt.show()
   

   

1. Modifier le programme récursif suivant pour qu'il affiche l'image ci-dessous (où à la taille des cinq satellites et leur distance à leur planète est chaque fois divisée par \(3\), où le diamètre de l'étoile initiale est de \(0.3\) et la distance à ses planètes de \(1\)).

   import  matplotlib.pyplot as plt
   from ?? import pi, cos
   
   fig, axes = plt.subplots()
   axes.set_xlim(-2, 2)
   axes.set_ylim(-2, 2)
   
   nbr_sat_par_planete = 5
   
   def trace(x_centre, y_centre, profondeur, profondeur_max, diametre, dist_a_planete):
       ?? ??:
           disque = plt.Circle((x_centre, y_centre), diametre, color="r")
           axes.add_artist(disque)
           for k in range(??):
               theta = ??
               x, y = ?? + ?? * cos(??), ?? + ?? * sin(??)
               trace(??, ??, ??, ??, ??, ??)
   
   trace(??, ??, ??, ??, ??, ??)
   plt.show()
   

   

Créer un programme recursif qui affiche l'image ci-dessous. Aides:

• Le centre de gravité d'un triangle se situe aux deux-tiers de chaque médiane en partant de son sommet.
• les hauteurs d'un triangle équilatéral de côté \(a\) sont de longueur \(a\times\sqrt{3}/2\).

Modifier votre programme pour qu'il affiche

1. On souhaite écrire une fonction perm_set admettant un unique paramètre n et qui retourne la liste des permutation de l'intervalle d'entiers \(\iinterff{1}{n}\). Ainsi l'appel perm_set(3) doit retourner

   [[3, 2, 1], [3, 1, 2], [2, 3, 1], [1, 3, 2], [2, 1, 3], [1, 2, 3]]
   

   Écrire une telle fonction récursive. Remarque: on pourra utiliser les méthodes append et insert du type list.

2. 1. Vérifier que le programme suivant affiche l'image donnée ci-dessous.

      import matplotlib.pyplot as plt
      
      def plot_as_image(rect_array):
          plt.imshow(rect_array)
      
      L = [
           [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
           [0,1,1,1,1,1,0,0,1,1,1,1,0,0,0,0,0],
           [0,1,0,0,0,0,1,1,0,0,0,0,1,0,0,0,0],
           [0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
           [0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
           [0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0],
           [0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0],
           [0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0],
           [0,0,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0],
           [0,0,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0],
           [0,0,0,0,1,1,1,0,0,0,0,1,1,0,0,0,0],
           [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
      
      plot_as_image(L)
      plt.show()
      

      

   2. Compléter et déboguer la fonction fill du script suivant suivante pour qu'elle remplisse de 1 la zone délimitée par des 1 et contenant L[x][y] (où x et y sont les premiers arguments de la fonction L) dans le tableau L.

      import matplotlib.pyplot as plt
      
      def plot_as_image(rect_array):
          plt.imshow(rect_array)
      
      L = [
           [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
           [0,1,1,1,1,1,0,0,1,1,1,1,0,0,0,0,0],
           [0,1,0,0,0,1,1,1,1,0,0,1,1,0,0,0,0],
           [0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
           [0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0],
           [0,1,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0],
           [0,0,0,1,0,0,1,1,1,1,1,0,0,0,0,0,0],
           [0,0,0,1,1,0,1,0,0,0,0,1,1,0,0,0,0],
           [0,0,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0],
           [0,0,0,0,1,0,1,0,0,0,1,0,0,1,0,0,0],
           [0,0,0,0,1,1,1,0,0,0,0,1,1,0,0,0,0],
           [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
      
      def fill(i, j, rect_array):
          if ??:
              ??
          n = len(rect_array)
          p = len(rect_array[0])
          ??
          rect_array[i][j] = 1
          delta_pos = [[1,0],[0,1],[-1,0],[0,-1]]
          for di, dj in delta_pos:
              i2, j2 = i+di, j+dj
              if  0 <= i2 < n and 0 <= j2 < p:            
                  fill(??, ??, ??)
      
      fill(4, 6, L) # Agit par effets de bord
      plot_as_image(L)
      plt.show()
      

   3. Pouvez-vous justifier la terminaison de votre fonction fill ci-dessus?

1. Écrire une fonction récursive est_pseudo_sous_chaine_iter qui renvoie True si si son second argument est une pseudo sous-chaîne du premier et False sinon.

Écrire une fonction qui accepte en argument une chaîne de caractères de longueur \(n\) dont les caractères sont "X", "Y", "F", "+" ou "-" et qui si \(r=1/n\) affiche une chaîne polygônale obtenue (remarque: à chaque instant on met à jour un point donné par ses coordonnées et une direction donnée par un vecteur)

• en partant du point de coordonnées \((0,0)\) avec la direction pointée par \(\vcol{1,0}\);
• en lisant la chaîne de caractère de gauche à droite;
• en avançant de \(r\) si le caractère courant est \(F\) (pour «forward»);
• en tournant de \(90\) degrés (resp. de \(-90\) degrés) si le carctère est \(+\) (resp. \(-\));
• en ne faisant rien (si ce n'est passer au caractère suivant) si le caractère est \(X\) ou \(Y\).

Ainsi l'appel plot_L_system("F+F-F-FF-FF+F") donne

La chaîne du dragon à l'ordre \(n\) est définie ainsi

• La chaîne du dragon à l'ordre \(0\) est "FX"
• La chaîne du dragon à l'ordre \(n+1\) est définie ainsi:
  • on parcourt les caractères de la chaîne du dragon à l'ordre \(n\) de la gauche vers la droite
  • si on croise un "X" on le remplace par "X+YF+"
  • si on croise un "Y" on le remplace par "FX-Y"
  • sinon on garde le symbole tel quel.

Ainsi la chaine du dragons

• à l'ordre \(1\) est
• à l'ordre \(2\) est

Vérfier qu'après 15 itérations vous obtenez le L-système suivant