Aller au contenu

Exercices⚓︎

Exercice 1

Écrire une fonction récursive puissance(x, n) qui calcule le nombre \(x^n\).

🐍 Script Python
1
2
3
4
5
def puissance(x, n):
    if n == 0:
        return 1
    else:
        return x * puissance(x, n-1)

Exercice 2 ❤

On rappelle que le PGCD (plus grand diviseur commun de deux nombres) vérifie la propriété suivante : si la division euclidienne de \(a\) par \(b\) s'écrit \(a = b \times q + r\), alors \(pgcd(a,b)=pgcd(b,r)\).

Cette propriété est à la base de l'algorithme d'Euclide

Exemple : \(pgcd(24,18)=pgcd(18,6)=pgcd(6,0)\), donc \(pgcd(24,18)=6\)

Écrire un algorithme récursif pgcd(a,b).

🐍 Script Python
1
2
3
4
5
def pgcd(a, b):
    if b == 0:
        return a
    else:
        return pgcd(b, a%b)

Exercice 3

La conjecture de Syracuse (ou de Collatz) postule ceci :

Prenons un nombre \(n\) : si \(n\) est pair, on le divise par 2, sinon on le multiplie par 3 puis on ajoute 1. On recommence cette opération tant que possible. Au bout d'un certain temps, on finira toujours par tomber sur le nombre 1.

  1. Ecrire une fonction récursive syracuse(n) écrivant tous les termes de la suite de Syracuse, s'arrêtant (on l'espère) à la valeur 1.
  2. On appelle «temps de vol» le nombre d'étapes nécessaires avant de retomber sur 1. Modifier la fonction précédente afin qu'elle affiche le temps de vol pour tout nombre n.

1.

🐍 Script Python
1
2
3
4
5
6
7
8
def syracuse(n):
    print(n)
    if n == 1:
        return None
    if n % 2 == 0:
        return syracuse(n // 2)
    else:
        return syracuse(3*n + 1)

Remarque : comme notre fonction syracuse ne renvoie pas de valeur numérique (elle ne fait qu'afficher une valeur), le return du test de parité est en fait inutile.

Mais le return du cas de base est lui primordial pour que le code s'arrête !

🐍 Script Python
1
2
3
4
5
6
7
8
def syracuse(n):
    print(n)
    if n == 1:
        return None
    if n % 2 == 0:
        syracuse(n // 2)
    else:
        syracuse(3*n + 1)
2.
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def syracuse(n, t=0):
    print(n)
    t += 1
    if n == 1:
        print('temps de vol :', t)
        return None
    if n % 2 == 0:
        syracuse(n // 2, t)
    else:
        syracuse(3*n + 1, t)

Exercice 4

Reproduire le dessin suivant, à l'aide du module turtle.

turtle est un hommage au langage LOGO inventé par Seymour Papert au MIT à la fin des années 60.

🐍 Script Python
1
2
3
4
5
6
7
from turtle import *
def carre(c):
    for k in range(4):
        forward(c)
        right(90)
# à vous
carre(200)
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from turtle import *
def carre(c):
    for k in range(4):
        forward(c)
        right(90)

def base(c):
    carre(c)
    forward(c/2)
    right(45)

def trace(c, n):
    if n == 0 :
        return None
    else :
        base(c)
        c = c/(2**0.5)
        return trace(c, n-1)

trace(200, 5)

Exercice 5

Proposer une nouvelle fonction récursive puissance_mod(x, n) qui calcule le nombre \(x^n\). Pour optimiser la fonction déjà construite à l'exercice 1, utiliser le fait que :

  • si \(n\) est pair, \(a^n=(a \times a)^{n/2}\)
  • sinon \(a^n=a \times (a \times a)^{(n-1)/2}\)
🐍 Script Python
1
2
3
4
5
6
7
8
def puissance_mod(x, n):
    if n == 0 :
        return 1
    else :
        if n % 2 == 0:
            return puissance_mod(x*x, n//2)
        else :
            return x*puissance_mod(x*x, (n-1)//2)

Exercice 6

Écrire un algorithme récursif recherche(lst, m) qui recherche la présence de la valeur m dans une liste triée (par ordre croissant) lst.

Cette fonction doit renvoyer un booléen.

Aide :

Les techniques de slicing (hors-programme) permettent de couper une liste en deux :

🐍 Script Python
>>> lst = [10, 12, 15, 17, 18, 20, 22]
>>> lst[:3]
[10, 12, 15]
>>> lst[3:]
[17, 18, 20, 22]

🐍 Script Python
1
2
3
4
5
6
7
8
def recherche(lst, m):
    """Si la liste n'est pas triée"""
    if lst==[]:
        return False
    if lst[0]==m:
        return True
    else:
        return recherche(lst[1:], m)
Si la liste est triée, il faut trouver un slicing bien plus efficace.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def recherche(lst, m):
    print(lst) # pour voir la taille de la liste diminuer (facultatif)
    if lst==[]:
        return False
    if len(lst) == 1:  #cas de base
        if lst[0] == m:
            return lst[0]==m
    else :              #cas récursif
        mid = len(lst)//2
        if lst[mid] > m:
            return recherche(lst[:mid],m)
        else:
            return recherche(lst[mid:],m)

Exercice 7

On considère le jeu des Tours de Hanoï. Le but est de faire passer toutes les assiettes de A vers C, sachant qu'une assiette ne peut être déposée que sur une assiette de diamètre inférieur.

Une version jouable en ligne peut être trouvée ici.

  1. S'entraîner et essayer d'établir une stratégie de victoire.
  2. Observer les images ci-dessous :

Écrire une fonction récursive hanoi(n, depart, inter, arrivee) qui donnera la suite d'instructions (sous la forme " A vers C") pour faire passer une pile de taille n de A vers C en prenant B comme intermédiaire.

  • Exemple 1:
    🐍 Console Python
    hanoi(1, "A", "B", "C")
    donne:
    🐍 Console Python
    A vers C
  • Exemple 2:
    🐍 Console Python
    hanoi(2, "A", "B", "C")
    donne:
    🐍 Console Python
    A vers B
A vers C
B vers C
  • Exemple 3:
    🐍 Console Python
    hanoi(3, "A", "B", "C")
    donne:
    🐍 Console Python
    A vers C
A vers B
C vers B
A vers C
B vers A
B vers C
A vers C
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def hanoi(n, depart, inter, arrivee):
    """ n : nombre d'assiettes dans la pile
    # depart : la pile de départ("A", "B" ou "C")
    # inter : la pile intermédaire("A", "B" ou "C")
    # arrivee : la pile d'arrivée ("A", "B" ou "C") """

    if n == 1 :
        print(depart + " vers " + arrivee)
    else :
        hanoi(n-1, depart, arrivee, inter) 
        print(depart + " vers " + arrivee)
        hanoi(n-1, inter, depart, arrivee)

hanoi(3, "A", "B", "C")

Exercice 8

Cet exercice a pour objectif le tracé du flocon de Von Koch.

L'idée est de répéter de manière récursive la transformation ci-dessous : chaque segment de longueur l donne naissance à 4 segments de longueur l/3, en construisant une pointe de triangle équilatéral sur le deuxième tiers du segment.

1) Créer une fonction récursive floc(n, l) qui trace à une «profondeur» n un segment de longueur l. Indications

  • l'instruction de tracé n'a lieu que quand n vaut 0.
  • l'étape n fait 4 appels sucessifs à l'étape n-1.
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
from turtle import forward, left, right, speed, mainloop

def floc(n, l):
    # à vous

speed(0)

floc(3,400)

mainloop() # lance le gestionnaire de fenetres

2) Créer une fonction triangle(n, l) qui trace le flocon complet.

Exercice 9

Exercice de diffusion récursive sur Capytale

image

Bac⚓︎

Exercice 4 du sujet Amérique du Nord J1

correction Q1.a.

Proposition 3

correction Q1.b.

txt[0] vaut 'b'
txt[taille-1] vaut 'r'
interieur vaut 'onjou'

correction Q2.

🐍 Script Python
1
2
3
def test_palindrome():
    assert palindrome("kayak") == True
    assert palindrome("canoe") == False
On teste les deux cas possibles.

correction Q3.
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def palindrome_imperatif(txt):
    if len(txt) < 2:
        return True
    i = 0
    j = len(txt)-1
    while i<j:
        if txt[i] != txt[j]:
            return False
        i += 1
        j -= 1
    return True
correction Q4.a.
🐍 Script Python
1
2
3
4
5
6
def complementaire(txt):
    comp = {"A":"T", "T":"A", "G":"C", "C":"G"}
    sol = ""
    for c in txt:
        sol += comp[c]
    return sol
correction Q4.b

"GATCGTCTAGCA" n'est pas un palindrome donc "GATCGT" n'est pas palindromique.

correction Q4.c
🐍 Script Python
1
2
3
def est_palindromique(txt):
    txt_total = txt + complementaire(txt)
    return palindrome(txt_total)
Bibliographie
  • Numérique et Sciences Informatiques, Terminale, T. BALABONSKI, S. CONCHON, J.-C. FILLIATRE, K. NGUYEN, éditions ELLIPSES.
  • Prépabac NSI, Terminale, G.CONNAN, V.PETROV, G.ROZSAVOLGYI, L.SIGNAC, éditions HATIER.