A voir également:
- Déterminer des fréquences de chaque chaines->une liste de liste
- Liste déroulante excel - Guide
- Liste déroulante en cascade - Guide
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Liste de diffusion whatsapp - Guide
- Liste site streaming illégal - Accueil - Services en ligne
2 réponses
KX
Messages postés
16755
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 février 2025
3 020
23 mai 2014 à 00:07
23 mai 2014 à 00:07
Bonsoir,
Je ne suis pas sûr d'avoir bien compris le problème.
Tu as une
Exemple :
En terme d'algorithme je verrais bien un parcours d'arbre. Mon exemple pourrait se représenter comme ceci :
Ton problème revient alors à calculer le nombre de feuilles du sous arbre dont la racine est déterminée par le chemin déjà parcouru de la liste.
Exemple, la liste [1] conduit à la racine 1, donc au sous-arbre {1, 2, 3, 4, 5, 6} qui contient 3 feuilles {3, 4, 6}.
Pour tout avoir, il faut récursivement construire au fur et à mesure la liste chemin de la racine, et faire la somme des résultats obtenus pour chaque sous arbre.
Exemple : f([1]) = f([1,2]) + f([1,5]) = f([1,2,3]) + f([1,2,4]) + f([1,5,6]) = 3
Remarque : en faisant ce parcours on n'a pas seulement trouvé [1], mais aussi calculé et trouvé le résultat de [1,2], [1,5], [1,2,3], [1,2,4] et [1,5,6] qu'il faut aussi enregistrer pour ne pas avoir à refaire les calculs.
Au final la complexité de l'algorithme devrait être plutôt sympathique, même si je ne me risquerais pas à la formaliser par une heure aussi tardive ^^
Je ne suis pas sûr d'avoir bien compris le problème.
Tu as une
List<List<E>> aet tu veux obtenir une
List<Node<List<E>,Integer>> btelle que pour
Node(list,n)dans
b on ait toujours n qui soit égal au nombre de fois où les éléments de a commencent par list. C'est bien ça ?
Exemple :
a = [[1, 2, 3], [1, 2, 4], [1, 5, 6], [7, 8, 9]]
b = [([1], 3), ([7], 1), ([1, 2], 2), ([1, 5], 1), ([7, 8], 1), ([1, 2, 3], 1), ([1, 2, 4], 1), ([1, 5, 6], 1), ([7, 8, 9], 1)]
En terme d'algorithme je verrais bien un parcours d'arbre. Mon exemple pourrait se représenter comme ceci :
/ \
1 7
/ \ \
2 5 8
/ \ \ \
3 4 6 9
Ton problème revient alors à calculer le nombre de feuilles du sous arbre dont la racine est déterminée par le chemin déjà parcouru de la liste.
Exemple, la liste [1] conduit à la racine 1, donc au sous-arbre {1, 2, 3, 4, 5, 6} qui contient 3 feuilles {3, 4, 6}.
Pour tout avoir, il faut récursivement construire au fur et à mesure la liste chemin de la racine, et faire la somme des résultats obtenus pour chaque sous arbre.
Exemple : f([1]) = f([1,2]) + f([1,5]) = f([1,2,3]) + f([1,2,4]) + f([1,5,6]) = 3
Remarque : en faisant ce parcours on n'a pas seulement trouvé [1], mais aussi calculé et trouvé le résultat de [1,2], [1,5], [1,2,3], [1,2,4] et [1,5,6] qu'il faut aussi enregistrer pour ne pas avoir à refaire les calculs.
Au final la complexité de l'algorithme devrait être plutôt sympathique, même si je ne me risquerais pas à la formaliser par une heure aussi tardive ^^
Bonjour,
Oui c'est un peu ça, j'ai résolu mon problème, notamment j'ai arrivé de faire le comptage des nombres.
Il me reste de faire un arbre qui me parait n-aire( c'est un peu près comme votre arbre) ça c'est autre problème hahahaha
Pour :
"Au final la complexité de l'algorithme devrait être plutôt sympathique, même si je ne me risquerais pas à la formaliser par une heure aussi tardive ^^"
Oui, ça fait 2 semaines je bosse dessus. c'est ne pas évident, je dois gérer aussi le temps de réponse de programme de calcul plus les tests de débogage.
Oui c'est un peu ça, j'ai résolu mon problème, notamment j'ai arrivé de faire le comptage des nombres.
Il me reste de faire un arbre qui me parait n-aire( c'est un peu près comme votre arbre) ça c'est autre problème hahahaha
Pour :
"Au final la complexité de l'algorithme devrait être plutôt sympathique, même si je ne me risquerais pas à la formaliser par une heure aussi tardive ^^"
Oui, ça fait 2 semaines je bosse dessus. c'est ne pas évident, je dois gérer aussi le temps de réponse de programme de calcul plus les tests de débogage.
KX
Messages postés
16755
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
12 février 2025
3 020
24 mai 2014 à 14:32
24 mai 2014 à 14:32
Non ce n'est pas un arbre n-aire, car tu n'as apriori aucune limite "n" connue.
Toi ce que tu as c'est un arbre quelconque, mais la structure n'est pas très compliquée.
Toi ce que tu as c'est un arbre quelconque, mais la structure n'est pas très compliquée.
public class Tree<E> { private E node; private List<Tree<E>> children; }