Aller au contenu

Introduction décente à l'orienté objet ?

Yozz

Par Yozz
dans Science et technologie

Messages recommandés

Brock

Brock

Posté
Posté

 

macho ! Retourne à tes magazines coquins

 

mon magazine coquin est au travail et ne rentre que ce soir :(

Nirvana

Nirvana

Posté
Posté

Je ne sais pas si ça a vraiment à voir avec l'orienté objet, mais puisqu'on est dans un fil de programmation...

 

Dans le cadre de mon cours d'algorithmique, on nous demande de "coder" un couple de nombres entiers (x, y) avec un seul entier, et inversement (à partir d'un entier naturel, faire un "décodage" qui permet d'obtenir les deux entiers x et y). Voilà l'illustration du problème :

 

c1P4a77.png

 

Le point d'origine, avec les coordonnées (0, 0), se trouve sur la diagonale n = 1, et se retrouve codé par l'entier 0. Ensuite, on a le point (0, 1), qui est codé par l'entier 1 (vu que c'est le "suivant" quand on parcours le graphique) et le point (1, 0) codé par l'entier 2 (ces deux derniers points se trouvent sur la diagonale n = 2. Ensuite, on revient en bas à droite, et à chaque fois on remonte en diagonale vers la gauche, comme sur une espèce de "spirale carrée".

 

Bref, je crois avoir réussi à programmer ça en Python :

 

#!/usr/bin/python3

# Codage de deux entiers naturels vers un seul entier
# Programme testé avec Python 3.3
# (Le changement de type int -> long est géré automatiquement depuis Python 3.0)

def codage(x, y):
    
    # "Numéro" de la diagonale sur laquelle se trouve le point (x, y)
    # Le point (0, 0) se trouve sur la "diagonale" 1
    # Les points (0, 1) et (1, 0) forment la diagonale 2
    # Et ainsi de suite pour les points (0, i) et (i, 0), i >= 0
    n = x + y + 1

    # Nombre total de points situés sur la diagonale n et sur les précédentes :
    # (D'après la formule pour calculer la somme des n premiers nombres entiers)
    # http://www.les-suites.fr/somme-des-n-premiers-entiers.htm
    z = n * (n + 1) / 2

    # Nombre entier représentant le couple (x, y):
    return z - x

# Test :
print(codage(0,0)) 
print(codage(1,0))
print(codage(0,1))
print(codage(2,0))
print(codage(1,1))
print(codage(0,2))
print(codage(3,0))
print(codage(2,1))

 

Le résultat :

 

 

>>> 
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0

 

De même, pour le "décodage" :

 

 

#!/usr/bin/python3

# Décodage d'un entier naturel k vers deux entiers naturels x et y
# Programme testé avec Python 3.3
# (Le changement de type int -> long est géré automatiquement depuis Python 3.0)

def decodage(k):
    
    # Numéro n de la "diagonale" sur laquelle se trouve le point (x, y)
    # Le point (0, 0) se trouve sur la "diagonale" 1
    # Les points (0, 1) et (1, 0) forment la diagonale 2
    # Et ainsi de suite pour les points (0, i) et (i, 0), i >= 0
    n = 1
    while k > n * (n + 1) / 2 - 1:
        n += 1

    # Nombre total de points situés sur la diagonale n et sur les précédentes :
    # (D'après la formule pour calculer la somme des n premiers nombres entiers)
    z = n * (n + 1) / 2

    # Calcul de l'entier x :
    x = z - k - 1

    # Calcul de l'entier y (d'après l'équation n = x + y + 1)
    y = n - x - 1

    return([x,y])

# Test :
for u in range(10):
    print(str(u) + " ---> " + str(decodage(u)))

 

Résultat :

 

 

>>> 
0 ---> [0.0, 0.0]
1 ---> [1.0, 0.0]
2 ---> [0.0, 1.0]
3 ---> [2.0, 0.0]
4 ---> [1.0, 1.0]
5 ---> [0.0, 2.0]
6 ---> [3.0, 0.0]
7 ---> [2.0, 1.0]
8 ---> [1.0, 2.0]
9 ---> [0.0, 3.0]

 

Maintenant, et c'est là que ça se complique. J'ai un arbre binaire composé de racines ( R ) et de feuilles ( f ), comme suit, et représenté par le schéma suivant : R1(R2 (f, f )), R3(R4(f, f ), f ), soit R R f f R R f f f

 

T47DWzK.png

 

 

On remplace les feuilles (de gauche à droite) par des nombres entiers naturels pris au hasard, selon la suite T = t0, t1, t2, ... , tk  (suite de longueur k+1). Exemple : T = (5, 12, 9, 8, 82)
 
yygaOcS.png
Et, en utilisant le codage vu ci-dessus, je dois remplacer les racines par le codage de leurs feuilles, comme ceci :
 
x9KT1PE.png
On suppose qu'en entrée, les données sont cohérentes (la chaîne de caractères représente vraiment un bon schéma, et il y a autant de f dans le schéma que d'entiers dans la suite), donc pas besoin de programmer la vérification du schéma.
 
Comment on fait pour programmer le codage (qui prend en argument un schéma S et une suite T de nombre entiers), d'abord de façon itérative puis de façon récursive ? 

 

Nirvana

Nirvana

Posté
Posté

C'est quoi exactement ton problème ?

 

Je ne vois pas ce que le prof veut dire par 'itératif' et 'récursif', et je ne sais pas trop comment parcourir ma liste schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f'] sans m'emmêler les pinceaux.

 

Re-edit : Bon, je suis arrivé à ça :

 

def codageArbre(schema, suite):
    tempList = []
    for i in range(len(schema)):

        # Si on tombe sur une branche qui engendre une racine
        if (schema[i] == 'R' and schema[i + 1] == 'R'):
            tempList.append(schema[i])  # Ajout à la nouvelle liste
            
        # Si on tombe sur une branche contenant deux feuilles
        if schema[i] == 'R' and schema[i + 1] == schema[i + 2] == 'f':
            x = suite.pop(0)
            y = suite.pop(0)

            # On effectue le codage de ces deux nombres puis on ajoute le résultat à tempList
            z = codage(x, y)
            tempList.append(z)

        # Si le dernier élément de la liste est une feuille
        if(schema[i] == 'f' and (i + 1) == len(schema)):
            x = suite.pop(0)
            tempList.append(x)
            
    return tempList # Affichage du résultat

schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
suite = [5, 12, 9, 8, 82]

print(codageArbre(schema, suite))

 

Comme résultat, ça me donne

 

['R', 166.0, 'R', 162.0, 82]
>>>

 

Mais je n'arrive pas à aller plus loin...

Noob

Noob

Posté
Posté

Itératif c'est ce que tu fais, je prend un tableau que je parcours à l'aide de l'index en augmentant un compteur.

 

Récursif si tu sais pas, ça ce sera peut-être pas très clair ce que je vais dire, m'enfin c'est lorsque une fonction se rappel elle-même.

Exemple la suite de Fibonacci est définie récursivement, le terme f(i) par la somme de deux résultats précédents f(i-1) + f(i-2).

Voici une façon simple de le calculer, évidemment c'est apppelé naïf car le temps d'exécution explose très très rapidement.

http://fr.wikipedia.org/wiki/Suite_de_Fibonacci#Algorithme_r.C3.A9cursif_na.C3.AFf

 

Dans cette exemple tu peux voir deux parties dans le code : une condition qui dit stop on retourne et une autre qui rappelle la fonction récursivement pour un autre sous-problème On dit que f(i-1) et f(i-2) sont les sous problèmes de f(i).

Dans le cas d'un arbre on dirait r1 = explorefilsGauche r2 explorefilsDroit et après on calcule un truc en fonction de r1 et r2.

Ceci m'amène à la question suivante : Es-tu sûr que tu peux te contenter d'utiliser des tableaux et ne pas devoir construire un arbre binaire ? Donc avec un classe Arbre et une classe noeud ?

 

Ensuite si je lis ton schéma et que je compare à ton résultat afficher, il y a clairement une bulle. le 82 devrait resté seul.

Nirvana

Nirvana

Posté
Posté

Je crois avoir fini le calcul itératif, mais j'ai l'impression d'avoir fait quelque chose de très sale (le prof a dit que ça pouvait se faire en 25 lignes grand maximum, minimum 10) :

 

#!/usr/bin/python3

# Codage de deux entiers naturels vers un seul entier
# Programme testé avec Python 3.3
# (Le changement de type int -> long est géré automatiquement depuis Python 3.0)

def codage(x, y):
    
    # "Numéro" de la diagonale sur laquelle se trouve le point (x, y)
    # Le point (0, 0) se trouve sur la "diagonale" 1
    # Les points (0, 1) et (1, 0) forment la diagonale 2
    # Et ainsi de suite pour les points (0, i) et (i, 0), i >= 0
    n = x + y + 1

    # Nombre total de points situés sur la diagonale n et sur les précédentes :
    # (D'après la formule pour calculer la somme des n premiers nombres entiers)
    z = n * (n + 1) / 2

    # Nombre entier représentant le couple (x, y):
    return z - x

# Test :
print("codage(0, 0) --->\t" + str(codage(0, 0)))
print("codage(1, 0) --->\t" + str(codage(1, 0)))
print("codage(0, 1) --->\t" + str(codage(0, 1)))
print("codage(2, 0) --->\t" + str(codage(2, 0)))
print("codage(1, 1) --->\t" + str(codage(1, 1)))
print("codage(0, 2) --->\t" + str(codage(0, 2)))
print("codage(3, 0) --->\t" + str(codage(3, 0)))
print("codage(2, 1) --->\t" + str(codage(2, 1)))

def codageArbre(schema, suite):

    tempList = []

    for i in range(len(schema)):
       
        # Si on tombe sur une Racine
        if (i + 1) < len(schema) and schema[i] == 'R':
          
             # Si elle engendre une autre Racine
            if schema[i + 1] == 'R':
                tempList.append(schema[i])           # On l'ajoute à la tempList

            # Si elle engendre une feuille
            if schema[i + 1] == 'f':
                x = suite.pop(0)                    # On prend les deux premiers nombres dans la suite
                y = suite.pop(0)
                z = codage(x, y)                    # On les code
                tempList.append(z)                  # On les ajoute à la tempList
                
            # Si elle engendre au moins un nombre
            if type(schema[i + 1]) == float or type(schema[i + 1]) == int:

                # Si son deuxième enfant est une racine
                if schema[i + 2] == 'R':
                    tempList.append(schema[i])

                # Si elle engendre un deuxième nombre
                if type(schema[i + 2]) == float or type(schema[i + 2]) == int:
                    x = schema[i + 1]
                    y = schema[i + 2]
                    z = codage(x, y)
                    tempList.append(z)

        # Si je tombe sur un nombre qui n'a pas d'enfant et dont le frère est une racine
        if (i + 1) < len(schema):
            if type(schema[i]) == float or type(schema[i]) == int:
                if schema[i + 1] == 'R':
                    tempList.append(schema[i])

        
        # Si on tombe sur le dernier élément et qu'il s'agit d'une feuille
        if (i + 1) == len(schema) and schema[i] == 'f':
            x = suite.pop(0)
            tempList.append(x)
            
    return tempList

schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
suite = [1, 2, 3, 4, 5]

print("\nSchéma de départ :")
print(schema)

print("\nSuite de départ :")
print(suite)

arbre1 = codageArbre(schema, suite)
print("\nRESULTAT PREMIERE ETAPE :")
print(arbre1)

arbre2 = codageArbre(arbre1, suite)
print("\nRESULTAT DEUXIEME ETAPE :")
print(arbre2)

arbre3 = codageArbre(arbre2, suite)
print("\nRESULTAT TROISIEME ETAPE :")
print(arbre3)

 

En résultat, j'ai ça (j'ai changé la suite parce que ça donnait des résultats peu lisibles dès qu'on dépasse 10)

 

codage(0, 0) --->	1.0
codage(1, 0) --->	2.0
codage(0, 1) --->	3.0
codage(2, 0) --->	4.0
codage(1, 1) --->	5.0
codage(0, 2) --->	6.0
codage(3, 0) --->	7.0
codage(2, 1) --->	8.0

Schéma de départ :
['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']

Suite de départ :
[1, 2, 3, 4, 5]

RESULTAT PREMIERE ETAPE :
['R', 9.0, 'R', 33.0, 5]

RESULTAT DEUXIEME ETAPE :
['R', 9.0, 747.0]

RESULTAT TROISIEME ETAPE :
[286894.0]
>>>

J'ai pas compris, pour l'histoire du 82.

 

 

 

Ceci m'amène à la question suivante : Es-tu sûr que tu peux te contenter d'utiliser des tableaux et ne pas devoir construire un arbre binaire ? Donc avec un classe Arbre et une classe noeud ?

 

Le prof n'a pas parlé de construire de classes (c'est un cours d'algorithmique très "simple", on n'est pas censés construire de classes),  je crois qu'on doit juste utiliser des tableaux.

Noob

Noob

Posté
Posté

Je crois avoir fini le calcul itératif, mais j'ai l'impression d'avoir fait quelque chose de très sale (le prof a dit que ça pouvait se faire en 25 lignes grand maximum, minimum 10) :

J'ai pas compris, pour l'histoire du 82.

 

1° J'ai aucun doute qu'on peu le faire en beaucoup moins de ligne, là j'ai un truc à faire avant ce soir, mais j'y jetterais peut-être un oeil.

2° Avant dans le résultat tu n'avais pas un 82 en dernier mais un f et le quatrième nombre était 271 je crois.

 

EDIT: tertio, t'as pas l'impression qu'il faudrait que tu utilise une boucle vers la fin ?

Parce que si tu à un arbre dont la hauteur est de 5 tu fais comment ?

Nirvana

Nirvana

Posté
Posté

EDIT: tertio, t'as pas l'impression qu'il faudrait que tu utilise une boucle vers la fin ?

Parce que si tu à un arbre dont la hauteur est de 5 tu fais comment ?

 

Je n'ai pas vérifié,Tu as parfaitement raison, mais de toute façon le programme ne marchait pas (j'ai essayé avec un schéma différent, plus court) Du coup, j'ai pratiquement tout réécrit en utilisant une boucle while et ça a l'air de marcher, en plus de prendre moins de lignes :

 

 

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# Codage de deux entiers naturels vers un seul entier
# Programme testé avec Python 3.3
# (Le changement de type int -> long est géré automatiquement depuis Python 3.0)

def codage(x, y):
    
    # "Numéro" de la diagonale sur laquelle se trouve le point (x, y)
    # Le point (0, 0) se trouve sur la "diagonale" 1
    # Les points (0, 1) et (1, 0) forment la diagonale 2
    # Et ainsi de suite pour les points (0, i) et (i, 0), i >= 0
    n = x + y + 1

    # Nombre total de points situés sur la diagonale n et sur les précédentes :
    # (D'après la formule pour calculer la somme des n premiers nombres entiers)
    z = n * (n + 1) / 2

    # Nombre entier représentant le couple (x, y):
    return z - x

# Test sur quelques couples d'entiers :
print("codage(0, 0) --->\t" + str(int(codage(0, 0))))
print("codage(1, 0) --->\t" + str(int(codage(1, 0))))
print("codage(0, 1) --->\t" + str(int(codage(0, 1))))
print("codage(2, 0) --->\t" + str(int(codage(2, 0))))
print("codage(1, 1) --->\t" + str(int(codage(1, 1))))
print("codage(0, 2) --->\t" + str(int(codage(0, 2))))
print("codage(3, 0) --->\t" + str(int(codage(3, 0))))
print("codage(2, 1) --->\t" + str(int(codage(2, 1))))

def codageArbre(schema, suite):

    # On remplace les f par les nombres qui leur correspondent
    for i in range(len(schema)):
         if schema[i] == 'f':
              schema[i] = suite.pop(0)

    # Tant qu'on n'a pas uniquement le résultat final du codage
    while len(schema) > 1:
        for i in range(len(schema)):             # On parcourt le schéma
            
                if schema[i] == 'R':             # Si on tombe sur une Racine

                    # Si son premier enfant est un nombre
                    if type(schema[i + 1]) == int or type(schema[i + 1]) == float:

                        # Si son second enfant est aussi un nombre
                        if type(schema[i + 2]) == int or type(schema[i + 2]) == float:

                            # On remplace la racine par le codage de ses enfants
                            schema[i] = codage((schema[i + 1]), (schema[i + 2]))

                            schema.pop(i + 1)   # On retire les feuilles du schéma
                            schema.pop(i + 1)
                            break               # On sort de la boucle pour éviter les erreurs et on recommence
                        
    return schema

schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
suite = [1, 2, 3, 4, 5]

print("\nSchéma de départ :\t" + str(schema))
print("Suite de départ :\t" + str(suite))
arbre1 = codageArbre(schema, suite)
print("\nRÉSULTAT DU CODAGE :\t" + str(int(arbre1[0])))

 

 

 

Résultat :

 

codage(0, 0) --->	1
codage(1, 0) --->	2
codage(0, 1) --->	3
codage(2, 0) --->	4
codage(1, 1) --->	5
codage(0, 2) --->	6
codage(3, 0) --->	7
codage(2, 1) --->	8

Schéma de départ :	['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
Suite de départ :	[1, 2, 3, 4, 5]

RÉSULTAT DU CODAGE :	286894
>>>

 

 

Ca reste une méthode itérative, me trompe-je ?

Noob

Noob

Posté
Posté

Je n'ai pas vérifié, mais de toute façon le programme ne marchait pas (j'ai essayé avec un schéma différent) Du coup, j'ai pratiquement tout réécrit en utilisant une boucle while et ça a l'air de marcher, en plus d'être plus court :

 

En fait c'est ta boucle while qui manquait, tu avais besoin d'appeler plusieurs fois codageArbre, ce qui n'était pas correct.

Si je comprends bien, je viens d'utiliser une méthode récursive, cette fois ?

Est-ce que dans codageArbre tu rappelles codageArbre ? Si oui alors c'est récursif sinon ça ne l'est pas.

Indice: il te reste la boucle for.

Nirvana

Nirvana

Posté
Posté

Est-ce que dans codageArbre tu rappelles codageArbre ? Si oui alors c'est récursif sinon ça ne l'est pas.

Indice: il te reste la boucle for.

 

Je m'en étais rendu compte tout seul, en fait (effectivement, c'est itératif) , je n'avais pas vu ton message quand j'ai édité le mien   ;) Merci de ton aide et désolé pour les questions de noob (no pun intended).

Nirvana

Nirvana

Posté
Posté

Au fait, je viens de recevoir ma note pour le projet de Java dont j'avais parlé plus tôt :

 

 

 

Bonsoir,

Vous avez obtenu 15/20 au projet de rattrapage du 1er semestre.

Bravo, le code développé donne le résultat escompté (à l'exception de la présentation mot/fréquence ou la virgule demandée est devenue une double tabulation).
Vous avez su exploiter les notions développées durant les séances précédentes. Votre code est correctement organisé et commenté.

Quelques remarques pour progresser :
- Le code de la méthode ajoutermot(String) pourrait être replacé dans la méthode mot(String) car c'est sa seule utilisation. Pour vous faire aider d'Eclipse : Clic droit sur l'appel à la méthode ajoutermot(mot), puis menu Refactor → Inline...
- la méthode hashToList() aurait pu ne pas prendre de paramètre car la map passée en paramètre est un attribut d'instance directement accessible
Autre possibilité : la méthode hashToList() crée, remplit et renvoie la liste des MotFreq. Cette liste est gérée comme une variable locale de la méthode afficheTetes et n'a plus besoin d'être déclarée comme un attribut d'instance.
- Dans la méthode afficheTetes(int), si n > nombre de mots dans la liste, une exception  ArrayIndexOutOfBoundsException est lancée.
Pour éviter ce problème potentiel :
int max = Math.min(n, motfreq.size()) ;
for (int i=0 ; i<max ; i++) {" 

 

Merci pour votre aide, c'est aussi grâce à vous.

Noob

Noob

Posté
Posté

Je m'en étais rendu compte tout seul, en fait (effectivement, c'est itératif) , je n'avais pas vu ton message quand j'ai édité le mien   ;) Merci de ton aide et désolé pour les questions de noob (no pun intended).

 

No worries, par contre c'est pour la suite que je pense que ça va être cracra.

Donc maintenant que tu à fait l'exo itératif pour passer au récursif il faut considérer la chose suivante :

 

Parcourir un tableau de façon récursive proprement, c'est un peu délicat, car à moins d'avoir le compteur en paramètre, il faudrait qu'il représente un arbre complet (par la gauche) à tous les niveaux.

C'est à dire qu'on pourrait déterminer l'indice d'un noeud de l'arbre par la relation à son parent: le noeud n est à l'indice i sont fils gauche est à l'indice 2*i et le fils droit à 2*i+1 avec la racine à i = 1.

Or c'est bien gentil ce que je raconte mais c'est pas ton cas.

 

Donc il te reste deux choix : Soit tu bricoles un compteur comme paramètre de chaque appelle à codageArbreRec.

Soit tu fais le grand plongeon et avant de lancer l'encodage tu crées toi-même la structure en arbre.

Donc avec une classe noeud qui aura deux autres noeuds comme fils gauche et files droit.

Dans ce cas tu n'auras plus qu'à parcourir ton arbre récursivement pour produire l'encodage. Au choix ou selon la consigne de ton prof évidemment.

Nirvana

Nirvana

Posté
Posté

 

No worries, par contre c'est pour la suite que je pense que ça va être cracra.

Donc maintenant que tu à fait l'exo itératif pour passer au récursif il faut considérer la chose suivante :

 

Parcourir un tableau de façon récursive proprement, c'est un peu délicat, car à moins d'avoir le compteur en paramètre, il faudrait qu'il représente un arbre complet (par la gauche) à tous les niveaux.

C'est à dire qu'on pourrait déterminer l'indice d'un noeud de l'arbre par la relation à son parent: le noeud n est à l'indice i sont fils gauche est à l'indice 2*i et le fils droit à 2*i+1 avec la racine à i = 1.

Or c'est bien gentil ce que je raconte mais c'est pas ton cas.

 

Donc il te reste deux choix : Soit tu bricoles un compteur comme paramètre de chaque appelle à codageArbreRec.

Soit tu fais le grand plongeon et avant de lancer l'encodage tu crées toi-même la structure en arbre.

Donc avec une classe noeud qui aura deux autres noeuds comme fils gauche et files droit.

Dans ce cas tu n'auras plus qu'à parcourir ton arbre récursivement pour produire l'encodage. Au choix ou selon la consigne de ton prof évidemment.

 

 

Je pense avoir réussi la version récursive de mon programme - apparemment c'était l'affaire de trois lignes à remplacer/rajouter, dites-moi si je me trompe (vu que c'était plus simple que ce que tu viens de dire)  :

 

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# Codage de deux entiers naturels vers un seul entier naturel
# Puis codage récursif d'un arbre binaire composé d'entiers et de racines

# Programme écrit et testé en Python, version 3.3.0
# (Le changement de type int -> long est géré automatiquement depuis Python 3.0)

#------------------------------------------------------------------------------

# Calcul du nombre entier codant le couple (x, y)

# Le point (0, 0) se trouve sur la "diagonale" n = 1
# Les points (0, 1) et (1, 0) forment la diagonale n = 2
# Et ainsi de suite pour les points (0, i) et (i, 0), i >= 0

# Pour calculer le nombre total z de points situés sur l'ensemble
# de la diagonale n et des diagonales précédentes, on utilise la formule pour
# calculer la somme des n premiers nombres entiers
# (http://www.les-suites.fr/somme-des-n-premiers-entiers.htm)

def codage(x, y):
    
    n = x + y + 1           # Indice de la diagonale n
    z = n * (n + 1) / 2     # Nombre total de points
    return z - x

# Test sur quelques couples d'entiers :
print("codage(0, 0) --->\t" + str(int(codage(0, 0))))
print("codage(1, 0) --->\t" + str(int(codage(1, 0))))
print("codage(0, 1) --->\t" + str(int(codage(0, 1))))
print("codage(2, 0) --->\t" + str(int(codage(2, 0))))
print("codage(1, 1) --->\t" + str(int(codage(1, 1))))
print("codage(0, 2) --->\t" + str(int(codage(0, 2))))
print("codage(3, 0) --->\t" + str(int(codage(3, 0))))
print("codage(2, 1) --->\t" + str(int(codage(2, 1))))

#-------------------------------------------------------------------------------

# Codage d'un arbre de façon récursive

# On remplace d'abord les 'f' par les nombres qui leur correspondent
# dans la suite. Puis, si le tableau ne contient que le résultat final
# (s'il est de longueur 1), on le renvoie tel quel. Sinon, on lance
# le traitement récursif : on parcourt le schéma, puis, si on tombe
# sur une Racine, on vérifie si ses enfants sont des nombres (int ou float).
# Alors, on remplace la Racine par le codage de ses enfants, puis
# on retire (pop) les feuilles de l'arbre. On sort de la boucle (break) 
# pour éviter les erreurs, et on applique à nouveau la fonction à l'arbre
# qu'on vient d'obtenir (c'est là qu'a lieu la récursivité).

def codageRecursif(schema, suite):

    for i in range(len(schema)):
         if schema[i] == 'f':
              schema[i] = suite.pop(0) 
    if len(schema) == 1:
        return schema
    else:
        for i in range(len(schema)):
            if schema[i] == 'R':
                if type(schema[i + 1]) == int or type(schema[i + 1]) == float:
                    if type(schema[i + 2]) == int or type(schema[i + 2]) == float:
                        schema[i] = codage((schema[i + 1]), (schema[i + 2]))
                        schema.pop(i + 1)
                        schema.pop(i + 1)
                        break
        schema = codageRecursif(schema, suite)      # Récursivité
        return schema

schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
suite = [1, 2, 3, 4, 5]

print("\nSchéma de départ :\t" + str(schema))
print("Suite de départ :\t" + str(suite))
arbre1 = codageRecursif(schema, suite)
print("\nRÉSULTAT DU CODAGE RÉCURSIF:\t" + str(int(arbre1[0])))

 

 

Résultat : 

 

codage(0, 0) --->	1
codage(1, 0) --->	2
codage(0, 1) --->	3
codage(2, 0) --->	4
codage(1, 1) --->	5
codage(0, 2) --->	6
codage(3, 0) --->	7
codage(2, 1) --->	8

Schéma de départ :	['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
Suite de départ :	[1, 2, 3, 4, 5]

RÉSULTAT DU CODAGE RÉCURSIF:	286894
>>>
Noob

Noob

Posté
Posté

C'est juste, mais c'est très très itératif en fait. Tu as remplacé une boucle while par un appel récursif ce qui est ok, mais en pratique tu ne divise jamais ton problème.

De plus tu refais plusieurs fois la partie dans le premier if à chaque appel récursif, tu effectues le même travail N fois en fait.

Je m'attendrais typiquement à deux appels récursif, un pour traiter la partie gauche de la racine (et donc des sous-racine) et un autre pour la partie droite.

 

Du moins c'est comme ça que j'ai compris ton problème, ça demanderais confirmation auprès de ton prof.

 

Noob

Noob

Posté
Posté

Il y a le 4A qui est sorti il y a deux ans les quatres sont disponibles en un seul coffret sur amazon.

Pour donner le ton, il commence par la définition d'une machine théorique pour laquelle il définit un assembleur.

En fait non, il commence par des maths discrètes (les pires, on les entend pas arriver).

Nirvana

Nirvana

Posté
Posté

Pour mon devoir, on m'a envoyé la version d'un étudiant de l'an dernier, qui l'a fait en C++. Ca m'a fait peur, comme ça, parce que son programme a l'air immense (plus de 300 lignes) et compliqué par rapport au mien (il y a des racines carrées et tout...), et la syntaxe de C++ a l'air horrible :

 

http://pastebin.com/906witQc

Noob

Noob

Posté
Posté

Ah ben tiens voilà qui est intéressant, ce qui te concerne c'est à la ligne 200.

 

Si tu regarde bien la fin c'est exactement ce que j'avais en tête (234-237).

Deux appels récursifs dont on stocke le résultat dans des variables temporaires et retourne le codage à partir de ces deux.

Et ce qui est intéressant et que je tu devrais vérifier sur papier, c'est que selon le code il y a un moyen assez simple pour séparer le problème en deux.

 

En entrée tu as une liste qui représente un schéma et ce que tu veux, c'est  diviser ce schéma (moins le premier élément qui est la racine) en deux parties, la partie gauche de l'arbre et la droite. En fait les deux sous-arbres.

Et la partie qui lui permet de faire ça c'est la boucle while. le premier if est absolument inutile (il suffit de remplacer le break par une condition dans le while), ce qui compte c'est la suite des lignes 212 à 231.

 

En faisant ça il sépare parfaitement en deux listes les noeuds du sous-arbre de gauche et du sous-arbre de droite et il appelle récursivement en passant les sous-arbre en paramètre.

T'as plus qu'à faire pareil en python là.

Si t'es chaud en 15 minutes c'est plié. Python c'est super pour ça.

Nirvana

Nirvana

Posté
Posté

Ah ben tiens voilà qui est intéressant, ce qui te concerne c'est à la ligne 200.

 

Si tu regarde bien la fin c'est exactement ce que j'avais en tête (234-237).

Deux appels récursifs dont on stocke le résultat dans des variables temporaires et retourne le codage à partir de ces deux.

Et ce qui est intéressant et que je tu devrais vérifier sur papier, c'est que selon le code il y a un moyen assez simple pour séparer le problème en deux.

 

En entrée tu as une liste qui représente un schéma et ce que tu veux, c'est  diviser ce schéma (moins le premier élément qui est la racine) en deux parties, la partie gauche de l'arbre et la droite. En fait les deux sous-arbres.

Et la partie qui lui permet de faire ça c'est la boucle while. le premier if est absolument inutile (il suffit de remplacer le break par une condition dans le while), ce qui compte c'est la suite des lignes 212 à 231.

 

En faisant ça il sépare parfaitement en deux listes les noeuds du sous-arbre de gauche et du sous-arbre de droite et il appelle récursivement en passant les sous-arbre en paramètre.

T'as plus qu'à faire pareil en python là.

Si t'es chaud en 15 minutes c'est plié. Python c'est super pour ça.

 

Bon, on est au milieu de la nuit et je suis crevé, mais je crois que je comprends enfin où tu veux en venir avec cette histoire de partie gauche et de partie droite :) J'essaierai de coder ça dans le courant de la journée. Merci !

Nirvana

Nirvana

Posté
Posté

Je ne me suis pas encore attaqué à la récursivité, mais j'ai bricolé une fonction pour construire l'arbre, c'est bien à un truc comme ça que tu pensais ?

 

#!/usr/bin/python3
# -*- coding: utf-8 -*-

# Codage de deux entiers naturels vers un seul entier naturel
# Puis codage récursif d'un arbre binaire composé d'entiers et de racines

# Programme écrit et testé en Python, version 3.3.0

#------------------------------------------------------------------------------

# Calcul du nombre entier codant le couple (x, y)

def codage(x, y):

	n = x + y + 1           # Indice de la diagonale n
	z = n * (n + 1) / 2     # Nombre total de points
	return z - x

# Test sur quelques couples d'entiers :
print("codage(0, 0) --->\t" + str(int(codage(0, 0))))
print("codage(1, 0) --->\t" + str(int(codage(1, 0))))
print("codage(0, 1) --->\t" + str(int(codage(0, 1))))
print("codage(2, 0) --->\t" + str(int(codage(2, 0))))
print("codage(1, 1) --->\t" + str(int(codage(1, 1))))
print("codage(0, 2) --->\t" + str(int(codage(0, 2))))
print("codage(3, 0) --->\t" + str(int(codage(3, 0))))
print("codage(2, 1) --->\t" + str(int(codage(2, 1))))

#-------------------------------------------------------------------------------

# Construction de l'arbre (à base de listes imbriquées)

# On remplace les 'f' par les nombres de la suite. Puis, tant que l'arbre
# n'est pas binaire (s'il est de dimension > 2), on le parcourt et on examine
# les racines. Si celles-ci engendrent deux nombres ou une liste
# (racine qui a déjà subi une transformation) et un nombre, on remplace ces racines
# par la liste de leurs deux enfants. On efface (pop) ces derniers, puis on sort
# de la boucle (break) pour éviter les erreurs (dues au changement de la taille 
# de l'arbre), et la boucle recommence.

def buildArbre(schema, suite):

	print("\nConstruction de l'arbre...\n")
	for i in range(len(schema)):
		if schema[i] == 'f':
			schema[i] = suite.pop(0)
	print("Remplacement des 'f' par des nombres\t" + str(schema))
	while len(schema) > 2:
		for i in range(len(schema)):
			if schema[i] == 'R':
				if (type(schema[i + 1]) == int \
				or type(schema[i + 1]) == list) \
				and (type(schema[i + 2]) == int \
				or type(schema[i + 2]) == list):
					schema[i] = [schema[i + 1], schema[i + 2]]
					schema.pop(i + 1)
					schema.pop(i + 1)
					break
	print("Construction terminée ->\t\t" + str(schema))
	return schema

#----------------------------------------

# Codage d'un arbre de façon récursive (à terminer)

def codageRecursif(schema, suite):

	schema = buildArbre(schema, suite)
	print("\nCodage récursif de l'arbre...\n")
	return schema

schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
suite = [1, 2, 3, 4, 5]

print("\nSchéma de départ :\t" + str(schema))
print("Suite de départ :\t" + str(suite))
arbre1 = codageRecursif(schema, suite)
print("\nRÉSULTAT DU CODAGE RÉCURSIF (pas terminé):\t" + str(arbre1))

 

 

Résultat :

 
codage(0, 0) --->	1
codage(1, 0) --->	2
codage(0, 1) --->	3
codage(2, 0) --->	4
codage(1, 1) --->	5
codage(0, 2) --->	6
codage(3, 0) --->	7
codage(2, 1) --->	8

Schéma de départ :	['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
Suite de départ :	[1, 2, 3, 4, 5]

Construction de l'arbre...

Remplacement des 'f' par des nombres	['R', 'R', 1, 2, 'R', 'R', 3, 4, 5]
Construction terminée ->		[[[1, 2], [[3, 4], 5]]]

Codage récursif de l'arbre...


RÉSULTAT DU CODAGE RÉCURSIF (pas terminé):	[[[1, 2], [[3, 4], 5]]]
>>>

 

 

 

 

Noob

Noob

Posté
Posté

Oui c'est assez juste, maintenant pour faire ton truc récursif bien comme il faut il te faut 4 listes.

2 pour représenter les nouveaux schema et 2 autres pour représenter la liste de nombre séparée en deux.

Malky

Malky

Posté
Posté 

schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
suite = [1, 2, 3, 4, 5]
codage=lambda x, y: (x+y+1)*(x+y+2)/2-x-1
schema=list(map(lambda x: (x=='R') and 'R' or suite.pop(0), schema))
def R(liste):
    a, b, reste=liste[0], -1, liste[1:]
    if liste[0]=='R': (a, reste)=R(liste[1:])
    if reste:
        if reste[0]=='R': (b, reste)=R(reste[1:])
       else: b=reste[0]
       return codage(a, , reste[1:]
   else: return a
print(R(schema))

 

13 lignes en tout dont 10 pour le code hors initialisation des variables d'entrée et le print() de fin

 

Résultat:

python3 pipi.py 
257394.0

 

Qui est à priori la réponse exacte : dans ta fonction codage (0,0) donne 1, alors que d'après le dessin ça devrait être 0

 

C'est vraiment du code torché vite fait et je ne te conseillerais pas de rendre le truc tel quel mais ça peut te donner des pistes. A la limite ça peut faire sourire le prof de lui emmener cette version en plus de la tienne, juste pour les "10 lignes minimum"  :icon_wink:

 

Nirvana

Nirvana

Posté
Posté

 

schema = ['R', 'R', 'f', 'f', 'R', 'R', 'f', 'f', 'f']
suite = [1, 2, 3, 4, 5]
codage=lambda x, y: (x+y+1)*(x+y+2)/2-x-1
schema=list(map(lambda x: (x=='R') and 'R' or suite.pop(0), schema))
def R(liste):
    a, b, reste=liste[0], -1, liste[1:]
    if liste[0]=='R': (a, reste)=R(liste[1:])
    if reste:
        if reste[0]=='R': (b, reste)=R(reste[1:])
       else: b=reste[0]
       return codage(a, , reste[1:]
   else: return a
print(R(schema))

 

13 lignes en tout dont 10 pour le code hors initialisation des variables d'entrée et le print() de fin

 

Résultat:

python3 pipi.py 
257394.0

 

Qui est à priori la réponse exacte : dans ta fonction codage (0,0) donne 1, alors que d'après le dessin ça devrait être 0

 

C'est vraiment du code torché vite fait et je ne te conseillerais pas de rendre le truc tel quel mais ça peut te donner des pistes. A la limite ça peut faire sourire le prof de lui emmener cette version en plus de la tienne, juste pour les "10 lignes minimum"  :icon_wink:

 

 

Merci. Tu peux m'expliquer ce que ça fait, map ?

 

Sinon, pour (0, 0) = 1, c'est pas un problème. 

Créer un compte ou se connecter pour commenter

Vous devez être membre afin de pouvoir déposer un commentaire

Créer un compte

Créez un compte sur notre communauté. C’est facile !

Créer un nouveau compte

Se connecter

Vous avez déjà un compte ? Connectez-vous ici.

Connectez-vous maintenant
Aller sur la liste des sujets
×
×
  • Créer...