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
- Gertrude a préparé la liste des affaires à prendre pour l'excursion. juliette a modifié cette liste en utilisant le mode suivi des modifications proposé par le traitement de texte. - Guide
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Liste de diffusion whatsapp - Guide
2 réponses
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
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
bon ait toujours
nqui soit égal au nombre de fois où les éléments de
acommencent 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
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
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;
}