Discussion :

[lionelus]

Bonjour,

J'ai un exercice à faire qui consiste à écrire un triangle de sierpinsky avec des étoiles ou dièses en mode récursif comme ceci:


Je réfléchis à un moyen de le faire avec un tableau en deux dimensions ou une liste de liste, ce qui serait vraisemblablement le plus facile mais sans succès.

Je vous demande votre aide pour m'aider à résoudre ce problème.

Merci par avance.

[YCL-1]

Bonjour,

Je suppose que l'idée de l'exercice n'est pas de reproduire le triangle d'une longueur fixe tel que présenté sur l'image mais plutôt de permettre de recréer ce triangle selon la longueur désirée, ce qui est déjà plus compliqué.

Dans le premier cas effectivement un simple print de 8 lignes et c'est fini, ou depuis une liste près-remplie, mais sans notion de calcul.

Dans le second cas, il faut d'abord comprendre l'algorithme permettant de recréer ces combinaisons.

Premier constat c'est un enchaînement binaire, de dièses et d'espaces.

On peut donc commencer par écrire ces combinaisons en chiffre.

La représentation étant binaire je vais l'écrire en binaire et ce sera plus simple d'étudier cette suite dans l'ordre croissant :

suite = [0b1, 0b11, 0b101, 0b1111, 0b10001, 0b110011, 0b1010101, 0b11111111]

La formule mathématique a l'air assez compliquée Sierpiński's triangle (Pascal's triangle mod 2) :

mais le principe pour le traduire en programmation est plus simple :

plutôt que de partir sur une manipulation binaire d'un nombre qui sera très lourd à lire, bien que certainement plus performant, je préfère utiliser une liste dont les éléments sont indexables plus simplement que les bits dans un nombre.


1) On démarre d'une liste vide notée ligne
2) Pour chaque numéro de ligne noté n:

3) Si la ligne précédente contient au moins deux éléments:

4) Chaque élément de la ligne précédente, hormis le premier élément, sera le résultat de l'opération ou-exclusif (vrai si a et b sont différents) sur l'élément et son élément en position - 1 (y compris le premier élément)

Exemple :
si ligne précédente : [1, 1] on aura : [1, 0]
Premier élément inchangé: 1
1 (pos) identique à 1 (pos-1): 0

[1, 0, 1] donnera: [1, 1, 1]
Premier élément inchangé: 1
0 (pos) différent de 1 (pos-1): 1
1 (pos) différent soit 0 (pos-1): 1


[1, 1, 1, 1, 1, 1, 1, 1] donnera 1 (inchangé car premier élément) puis que des zéro

5) Puis on rajoute en dernier élément : 1
[1, 0] donnera [1, 0, 1]

Voici ce que ça donne en traduction Python sur un range n de 32 lignes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
ligne = []
for n in range(32): # { Pour chaque ligne
    nouvelle_ligne = ligne[:] # Copie des éléments de la ligne précédente
    if len(nouvelle_ligne) >= 2: #*{ Si au moins deux éléments
        for position in range(1, len(nouvelle_ligne)): # { Pour chaque élément hormis le premier
            nouvelle_ligne[position] = ligne[position] ^ ligne[position - 1] # Ou exclusif élément et élément - 1
        # } for
    # } if
    nouvelle_ligne.append(1) # Ajout dernier élément: 1
    print("".join([[" ", "#"][item] for item in nouvelle_ligne]))
    ligne = nouvelle_ligne
# } for

Et on obtient :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#
##
# #
####
#   #
##  ##
# # # #
########
#       #
##      ##
# #     # #
####    ####
#   #   #   #
##  ##  ##  ##
# # # # # # # #
################
#               #
##              ##
# #             # #
####            ####
#   #           #   #
##  ##          ##  ##
# # # #         # # # #
########        ########
#       #       #       #
##      ##      ##      ##
# #     # #     # #     # #
####    ####    ####    ####
#   #   #   #   #   #   #   #
##  ##  ##  ##  ##  ##  ##  ##
# # # # # # # # # # # # # # # #
################################

Très intéressant comme exercice.

Je vous laisse trouver comment retourner les éléments dans l'ordre décroissant.

[lionelus]

Merci beaucoup pour votre réponse.
Cela m'a beaucoup aidé.