Nirvana

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]]] >>>

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 !

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

"On peut aussi ajouter le cyber-libertarien, geek et adepte de science-fiction." Moi qui pensais être spécial.

Dans les bons il y a quand même Ubisoft Montpellier, Arkane Studios et Quantic Dream.

"Covers of the third edition of Volume 1 quote Bill Gates as saying, “If you think you're a really good programmer… read (Knuth's) Art of Computer Programming… You should definitely send me a résumé if you can read the whole thing." http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming#Critical_response

Atari, c'est cette boîte française qui s'appelait Infogrames et qui n'a rien à voir avec ces vieilles consoles ?

Critique par un des membres de la team fail0verflow (qui a réussi à hacker des consoles de jeux dont la Playstation 3) : https://twitter.com/marcan42

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 >>>

Arielle Dombasle ?

Spécial h16 : http://lci.tf1.fr/france/societe/une-soiree-pro-mariage-pour-tous-organisee-par-pierre-berge-7785643.html

Merci d'avoir précisé, vu que je n'ai pas compris le quart de ce qu'il a écrit.

Critiques de la sécurité de MEGA : http://bluetouff.com/2013/01/19/le-mega-retour-de-kim-dot-com/ http://reflets.info/le-retour-du-mega-merdier-de-kim/

Au fait, je viens de recevoir ma note pour le projet de Java dont j'avais parlé plus tôt : Merci pour votre aide, c'est aussi grâce à vous.

Pourquoi j'avais deviné qu'il s'agissait d'une famille africaine avant même de cliquer sur le lien ?

En ce moment il est occupé avec son film, son blog politique, son jeu de rôle papier, et les projets de sa femme française -> http://ancestralcult.com

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).

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 ?

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. 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.

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...

J'ai demandé à une lesbienne ce qu'elle pensait de cet argument, et elle m'a répondu "Tu peux pas avoir un pays qui fait tout juste pour une majorité - Et les Noirs ? Et les Juifs ? Et les handicapés ?- Et (sic) que c'est une tradition ? N'importe quoi, c'était aussi une tradition d'avoir des esclaves" Qu'est-ce que je devrais lui répondre ?

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 : 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 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) Et, en utilisant le codage vu ci-dessus, je dois remplacer les racines par le codage de leurs feuilles, comme ceci : 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 ?