Application

Problème 1 : Rotation d'image

Entrée :

  • Image

Sortie :

  • Rotation de 90° de l'image d'entrée

Idée :

  • L'image à faire tourner peut être divisée en quatre carreaux qui sont déplacés d'un quart de tour, puis pivotés récursivement.

Question

Réaliser une fonction Python pour résoudre le problème 1.

Vous devrez utiliser le module PIL. Consultez le premier indice pour plus d'informations sur les fonctions nécessaires dans ce module.

Afin de faciliter le travail, les images seront carrées, et leur côté sera une puissance de 2. Par exemple, l'image smiley ci-dessous :

smiley.tar.gz [gz]

Si vous coincez, le deuxième indice contient un code à compléter pour vous aider.

Indice

1
from PIL import Image
2
3
# Pour importer une image
4
une_image = Image.open("lien/vers/image.png")
5
6
# Pour connaître la taille de l'image
7
largeur = une_image.width
8
hauteur = une_image.height
9
10
# Pour connaître la valeur d'un pixel
11
un_pixel = une_image.getpixel((x, y))
12
13
# Pour remplacer un pixel par un autre
14
une_image.putpixel((i, j), un_pixel)
15
16
# Pour enregistrer une image
17
une_image.save("lien/vers/image_modif.png")
Indice
1
from PIL import Image
2
3
def rotation_image(image, depart_x, depart_y, taille):
4
    # Cas de base
5
    if taille == ???:
6
        return
7
    
8
    # Quelle est la taille des morceaux découpés ?
9
    taille_morceau = ???
10
    # On se retrouve avec 4 morceaux (de x à x+taille_m à x+taille, idem pour y)
11
    # On note les morceaux no (nord ouest), ne, so, se
12
13
    for i in range(depart_x, depart_x + taille_morceau):
14
        for j in range(depart_y, depart_y + taille_morceau):
15
            # On récupère un pixel de chaque morceau
16
            pixel_no = image.getpixel(???)
17
            pixel_ne = image.getpixel(???)
18
            pixel_se = image.getpixel(???)
19
            pixel_so = image.getpixel(???)
20
21
            # Et on les déplace d'un morceau, dans le sens horaire.
22
            image.putpixel(???, pixel_no)
23
            image.putpixel(???, pixel_ne)
24
            image.putpixel(???, pixel_se)
25
            image.putpixel(???, pixel_so)
26
27
    # Ensuite, on pivote récursivement chaque morceau
28
    rotation_image(image, ???, ???, taille_morceau) # NO
29
    rotation_image(image, ???, ???, taille_morceau) # NE
30
    rotation_image(image, ???, ???, taille_morceau) # SE
31
    rotation_image(image, ???, ???, taille_morceau) # SO
32
33
34
mon_image = Image.open("smiley.png")
35
rotation_image(mon_image, 0, 0, mon_image.width)
36
mon_image.save("smiley_edit.png")
Problème 2 : Tours de Hanoï
Entrée :
  • n, entier
Sortie :
  • déplacer n disques de la première tige à la troisième tige sachant qu'on ne déplacer qu'un disque à la fois, et qu'on ne peut pas poser un disque sur un disque plus petit
Idée :
  • Pour déplacer n disques de la première tour à la troisième tour, on peut déplacer n-1 disques de la première tour à la deuxième tour, déplacer le disque restant de la première tour à la troisième tour, et enfin déplacer les n-1 disques de la deuxième tour à la troisième tour.
Modèle d'une tour de Hanoï (avec huit disques)Informations[1]
Question
Réaliser une fonction Python pour résoudre le problème 2.
On utilisera une pile pour représenter une tour. En Python, on peut réaliser rapidement une pile avec les listes :
  • ma_pile = [] # Création d'une pile
  • ma_pile.append(valeur) # Empiler une valeur
  • valeur = ma_pile.pop() # Dépiler une valeur
Les valeurs indiquent le diamètre du disque (compris entre 1 et n).
Ainsi, une liste de trois piles permet de représenter les tours de Hanoï. Le premier indice détaille en profondeur cet aspect.
Réalisez ensuite l'algorithme grâce à l'idée énoncée. Le deuxième indice propose un code à trous.
Indice
1
# Initialisation du jeu
2
jeu = [
3
    [], # Première pile (pile 0)
4
    [], # Deuxième pile (pile 1)
5
    []  # Troisième pile (pile 2)
6
]
7
for i in range(n, 0, -1):
8
    # On ajoute d'abord le plus grand disque, de taille n
9
    jeu[0].append(i)
Indice
1
def deplacer_disques(jeu, nb_disques, depart, arrivee):
2
    """
3
    Fonction qui déplace des disques dans le jeu de Hanoï.
4
    :param jeu: Liste des piles
5
    :param nb_disques: Nombre de disques à déplacer
6
    :param depart: Pile d'où les disques vont être pris
7
    :param arrivee: Pile où les disques vont être déplacés
8
    :return:
9
    """
10
11
    # Calcul de la position intermédiaire, qui n'est ni l'arrivée ni le départ
12
    if depart != 0 and arrivee != 0:
13
        position_intermediaire = ???
14
    elif ???:
15
        position_intermediaire = ???
16
    else:
17
        position_intermediaire = ???
18
19
    if nb_disques == ???:
20
        # Cas de base
21
        disque = jeu[???].pop()
22
        jeu[???].append(disque)
23
    else:
24
        # On réalise l'idée du problème
25
        deplacer_disques(jeu, ???, ???, ???)
26
        deplacer_disques(jeu, ???, ???, ???)
27
        deplacer_disques(jeu, ???, ???, ???)
28
29
30
def hanoi(n):
31
    # Initialisation du jeu
32
    jeu = [
33
        [], # Première pile (pile 0)
34
        [], # Deuxième pile (pile 1)
35
        []  # Troisième pile (pile 2)
36
    ]
37
    for i in range(n, 0, -1):
38
        # On ajoute d'abord le plus grand disque, de taille n
39
        jeu[0].append(i)
40
41
    print(jeu)
42
    deplacer_disques(jeu, n, 0, 2)
43
    print(jeu)
44
45
46
hanoi(5)
Solution
1
def deplacer_disques(jeu, nb_disques, depart, arrivee):
2
    """
3
    Fonction qui déplace des disques dans le jeu de Hanoï.
4
    :param jeu: Liste des piles
5
    :param nb_disques: Nombre de disques à déplacer
6
    :param depart: Pile d'où les disques vont être pris
7
    :param arrivee: Pile où les disques vont être déplacés
8
    :return:
9
    """
10
11
    if depart != 0 and arrivee != 0:
12
        position_intermediaire = 0
13
    elif depart != 1 and arrivee != 1:
14
        position_intermediaire = 1
15
    else:
16
        position_intermediaire = 2
17
18
    if nb_disques == 1:
19
        # Cas de base
20
        disque = jeu[depart].pop()
21
        jeu[arrivee].append(disque)
22
    else:
23
        # On réalise l'idée du problème
24
        deplacer_disques(jeu, nb_disques-1, depart, position_intermediaire)
25
        deplacer_disques(jeu, 1, depart, arrivee)
26
        deplacer_disques(jeu, nb_disques-1, position_intermediaire, arrivee)
27
28
29
def hanoi(n):
30
    # Initialisation du jeu
31
    jeu = [
32
        [], # Première pile (pile 0)
33
        [], # Deuxième pile (pile 1)
34
        []  # Troisième pile (pile 2)
35
    ]
36
    for i in range(n, 0, -1):
37
        # On ajoute d'abord le plus grand disque, de taille n
38
        jeu[0].append(i)
39
40
    print(jeu)
41
    deplacer_disques(jeu, n, 0, 2)
42
    print(jeu)
43
44
45
hanoi(5)
Problème 3 : Multiplication
Entrées :
  • x, y entiers en binaire de taille \(2 \times n\)
Sortie :
  • \(x \times y\) en utilisant l'algorithme de Karatsuba
Idée :
  • Normalement, pour multiplier deux nombres, on multiplie chaque chiffre de x par y, en décalant avec un zéro, puis on additionne les résultats obtenus.
    Se renseigner sur la page Wikipédia.
Question
Réaliser une fonction Python pour résoudre le problème 3.
On utilisera des entiers, mais uniquement des opérateurs binaires :
  • bin(x) # Affiche l'écriture binaire de x
  • x<<n # Décale l'écriture de x en binaire vers la gauche en rajoutant des zéros
  • x>>n # Décale l'écriture de x en binaire vers la droite (et donc supprime des bits)
Vous pouvez débuter par calculer le nombre de bits d'un nombre entier. Voir solution 1.
Ensuite, il faut calculer les différentes valeurs a, b, c et d nécessaires à l'algorithme de Karatsuba. Vous pouvez consulter le premier indice pour vous aider à les calculer.
Enfin, il ne reste plus qu'à calculer récursivement les différentes valeurs nécessaires au calcul final. Voir solution 2.
Indice
Si x = 1001 1011 1001 0011, alors a = 1001 1011 et b = 1001 0011.
Ainsi, pour calculer la valeur de a, on doit supprimer les 8 derniers bits (avec l'opérateur >>) et pour calculer b, on doit supprimer les 8 premiers bits grâce au modulo % et à un nombre bien choisi.
Solution
1
def taille(x):
2
    """
3
    Taille du nombre binaire x
4
    :param x:
5
    :return:
6
    """
7
    n = 1
8
    while x > 0:
9
        x >>= 1
10
        n += 1
11
    return n
Solution
1
def karatsuba(x, y, n):
2
    """
3
    Réalise la multiplication x*y avec x et y de taille n
4
    :param x:
5
    :param y:
6
    :param n: Taille max entre x et y
7
    :return:
8
    """
9
    if n <= 1:
10
        return x * y
11
12
    n //= 2
13
    m = 1 << n
14
    a, b = x >> n, x % m
15
    c, d = y >> n, y % m
16
    ac = karatsuba(a, c, n)
17
    bd = karatsuba(b, d, n)
18
    abcd = karatsuba(a - b, c - d, n)
19
    return (ac << (2*n)) + ((ac + bd - abcd) << n) + bd
20
21
22
def taille(x):
23
    """
24
    Taille du nombre binaire x
25
    :param x:
26
    :return:
27
    """
28
    n = 1
29
    while x > 0:
30
        x >>= 1
31
        n += 1
32
    return n
33
34
35
def mult(x, y):
36
    n = max(taille(x), taille(y))
37
    return karatsuba(x, y, n)
38
39
40
print(mult(42, 69), 42*69)