Java tableau [Résolu]
tt -
20 oct. 2015 à 17:13 - Dernière réponse :
Whismeril
Contributeur Dernière intervention
21 novembre 2018
- 27 oct. 2015 à 16:18
- Messages postés
- 12272
- Date d'inscription
- mardi 11 mars 2003
- Statut
9 réponses
- Messages postés
- 15830
- Date d'inscription
- samedi 31 mai 2008
- Statut
Bonjour,
Je n'ai pas testé, mais en lisant le code (bien que ce soit illisible sans les balises de code voir ici) je dirais :
1) la méthode union n'existe pas dans le main, c'est uni
2) tu ne devrais pas faire de add dans le deuxième cas puisqu'il n'y a pas égalité
Je n'ai pas testé, mais en lisant le code (bien que ce soit illisible sans les balises de code voir ici) je dirais :
1) la méthode union n'existe pas dans le main, c'est uni
2) tu ne devrais pas faire de add dans le deuxième cas puisqu'il n'y a pas égalité
l'union de deux tableaux dans le tableauD renvoit normalement les valeurs distinctes des deux tableaux.
le pseudo code consiste t il bien à:
- regarder si les valeurs des deux tableaux est identiques et de les ajouter dans le tableauD
-ajouter les valeurs non contenu dans les deux tableaux dans le tableauD
le pseudo code consiste t il bien à:
- regarder si les valeurs des deux tableaux est identiques et de les ajouter dans le tableauD
-ajouter les valeurs non contenu dans les deux tableaux dans le tableauD
- Messages postés
- 15830
- Date d'inscription
- samedi 31 mai 2008
- Statut
"l'union de deux tableaux dans le tableauD renvoit normalement les valeurs distinctes des deux tableaux."
Bah non... l'union renvoie tout ce qui est dans au moins l'un des deux.
https://fr.wikipedia.org/wiki/Union_(mathématiques)
Bah non... l'union renvoie tout ce qui est dans au moins l'un des deux.
https://fr.wikipedia.org/wiki/Union_(mathématiques)
- Messages postés
- 15830
- Date d'inscription
- samedi 31 mai 2008
- Statut
L'exemple est bon.
Quelques cas de tests :
Quelques cas de tests :
union([1,2,3],[4,5,6])=[1,2,3,4,5,6] union([1,2,3],[1,2,3])=[1,2,3] union([1,3,5],[2,4,6])=[1,2,3,4,5,6] union([1,2,4,5],[2,3,5,6])=[1,2,3,4,5,6] union([1,1,2,2],[2,2,3,3])=[1,2,3]
- Messages postés
- 5293
- Date d'inscription
- dimanche 4 mai 2003
- Statut
Salut,
Si tu cherches à obtenir ce que KX te propose tu peux le faire assez simplement avec un Set et les méthodes dispo dans les classes Collections et Arrays
ex:
Si tu cherches à obtenir ce que KX te propose tu peux le faire assez simplement avec un Set et les méthodes dispo dans les classes Collections et Arrays
ex:
public static void main(String[] args) {
print(union(new Integer [] { 1,2,3 }, new Integer [] { 4,5,6 }));
print(union(new Integer [] { 1,2,3 }, new Integer [] { 1,2,3 }));
print(union(new Integer [] { 1,3,5 }, new Integer [] { 2,4,6 }));
print(union(new Integer [] { 1,2,4,5 }, new Integer [] { 2,3,5,6 }));
print(union(new Integer [] { 1,1,2,2 }, new Integer [] { 2,2,3,3 }));
}
public static List<Integer> union(Integer [] a, Integer [] b) {
Set<Integer> c = new TreeSet<Integer>();
c.addAll(Arrays.asList(a));
c.addAll(Arrays.asList(b));
List<Integer> d = Arrays.asList(c.toArray(new Integer[] { }));
Collections.sort(d);
return d;
}
public static void print(List<Integer> list) {
StringBuilder sb = new StringBuilder();
sb.append("[");
for(int i = 0; i < list.size(); ++i) {
sb.append(list.get(i));
if(i < list.size() - 1) sb.append(",");
}
sb.append("]");
System.err.println(sb.toString());
}
- Messages postés
- 15830
- Date d'inscription
- samedi 31 mai 2008
- Statut
Personnellement je ne vois pas 36 cas.
À tout moment dans l'exécution de ton programme, tu ne considères que 3 valeurs : le premier élément du tableauA, le deuxième élément du tableauB et le dernier élément du tableauD.
On considère la plus petite valeur entre A et B, si elle est différente de D on la rajoute, et dans tout les cas on passe au suivant...
À tout moment dans l'exécution de ton programme, tu ne considères que 3 valeurs : le premier élément du tableauA, le deuxième élément du tableauB et le dernier élément du tableauD.
On considère la plus petite valeur entre A et B, si elle est différente de D on la rajoute, et dans tout les cas on passe au suivant...
- Messages postés
- 15830
- Date d'inscription
- samedi 31 mai 2008
- Statut
Prenons par exemple ce cas de test :
Entre A et B, le plus petit c'est 1, qui n'est pas la valeur de D.
Donc on l'ajoute et on passe au suivant.
Entre A et B, le plus petit c'est 2, qui n'est pas la valeur de D.
Donc on l'ajoute et on passe au suivant.
Entre A et B, le plus petit c'est 2, qui est la valeur de D.
Donc on ne l'ajoute pas et on passe au suivant.
Entre A et B, le plus petit c'est 3, qui n'est pas la valeur de D.
Donc on l'ajoute et on passe au suivant.
etc.
union([1,2,4,5],[2,3,5,6])=[1,2,3,4,5,6]
tA = [1,2,4,5] → A=1 tB = [2,3,5,6] → B=2 tD = [] → D=
Entre A et B, le plus petit c'est 1, qui n'est pas la valeur de D.
Donc on l'ajoute et on passe au suivant.
tA = [/,2,4,5] → A=2 tB = [2,3,5,6] → B=2 tD = [1] → D=1
Entre A et B, le plus petit c'est 2, qui n'est pas la valeur de D.
Donc on l'ajoute et on passe au suivant.
tA = [/,/,4,5] → A=4 tB = [2,3,5,6] → B=2 tD = [1,2] → D=2
Entre A et B, le plus petit c'est 2, qui est la valeur de D.
Donc on ne l'ajoute pas et on passe au suivant.
tA = [/,/,4,5] → A=4 tB = [/,3,5,6] → B=3 tD = [1,2] → D=2
Entre A et B, le plus petit c'est 3, qui n'est pas la valeur de D.
Donc on l'ajoute et on passe au suivant.
tA = [/,/,4,5] → A=4 tB = [/,/,5,6] → B=5 tD = [1,2,3] → D=3
etc.
- Messages postés
- 15830
- Date d'inscription
- samedi 31 mai 2008
- Statut
Réponse courte : il faut trier tes tableaux avant de les fusionner.
Réponse longue : il y a plusieurs approches, mais on choisira généralement ce qui coûte le moins cher en terme de performance.
Il y a au moins deux cas possibles :
1) Tu tries d'abords les deux tableaux (en enlevant les doublons au passage), puis tu les fusionnes.
2) Tu concatènes les deux tableaux puis tu les tries (pour enlever les doublons).
En informatique on utilise la notion de complexité, c'est à dire une fonction qui relie la "taille" de la donnée à traiter, avec le nombre d'opérations nécessaires pour la traiter.
Dans ton cas :
f(n) serait le nombre d'opérations pour trier un tableau de taille n
g(n1,n2) pour fusionner deux tableaux triés de taille n1 et n2
h(n1,n2) pour concaténer deux tableaux quelconques
Donc avec mes deux cas on aurait :
1) f(n1)+f(n2)+g(n1,n2)
2) h(n1,n2)+f(n1+n2)
Remarque : avec un peu de chance le tri de t1 et t2 enlève des doublons donc en pratique on aura g(m1,m2) avec m1<=n1, m2<=n2, mais en théorie on considère le pire cas possible donc g(n1,n2).
Si on fait un petit calcul rapide, g(n1,n2)=n1+n2 avec l'algorithme que je t'ai donné. Et h(n1,n2)=n1+n2 aussi. Donc ça simplifie :
1) f(n1)+f(n2)+n1+n2
2) n1+n2+f(n1+n2)
Le choix repose donc (comme souvent) à comparer les algorithmes de tri.
Soit on a f(n1)+f(n2) < f(n1+n2) et il faut d'abord trier avant de fusionner.
Soit f(n1+n2) < f(n1)+f(n2), mais c'est théoriquement impossible.
Du coup, il est plus efficace de trier d'abord les tableaux avant de les fusionner.
Remarque : l'un des algorithmes de tri les plus performants est le tri par fusion, qui consiste à découper un grand tableau en petits tableaux pour les trier sur des petites tailles avant de les fusionner pour obtenir le tri du grand tableau.
Réponse longue : il y a plusieurs approches, mais on choisira généralement ce qui coûte le moins cher en terme de performance.
Il y a au moins deux cas possibles :
1) Tu tries d'abords les deux tableaux (en enlevant les doublons au passage), puis tu les fusionnes.
2) Tu concatènes les deux tableaux puis tu les tries (pour enlever les doublons).
En informatique on utilise la notion de complexité, c'est à dire une fonction qui relie la "taille" de la donnée à traiter, avec le nombre d'opérations nécessaires pour la traiter.
Dans ton cas :
f(n) serait le nombre d'opérations pour trier un tableau de taille n
g(n1,n2) pour fusionner deux tableaux triés de taille n1 et n2
h(n1,n2) pour concaténer deux tableaux quelconques
Donc avec mes deux cas on aurait :
1) f(n1)+f(n2)+g(n1,n2)
2) h(n1,n2)+f(n1+n2)
Remarque : avec un peu de chance le tri de t1 et t2 enlève des doublons donc en pratique on aura g(m1,m2) avec m1<=n1, m2<=n2, mais en théorie on considère le pire cas possible donc g(n1,n2).
Si on fait un petit calcul rapide, g(n1,n2)=n1+n2 avec l'algorithme que je t'ai donné. Et h(n1,n2)=n1+n2 aussi. Donc ça simplifie :
1) f(n1)+f(n2)+n1+n2
2) n1+n2+f(n1+n2)
Le choix repose donc (comme souvent) à comparer les algorithmes de tri.
Soit on a f(n1)+f(n2) < f(n1+n2) et il faut d'abord trier avant de fusionner.
Soit f(n1+n2) < f(n1)+f(n2), mais c'est théoriquement impossible.
Du coup, il est plus efficace de trier d'abord les tableaux avant de les fusionner.
Remarque : l'un des algorithmes de tri les plus performants est le tri par fusion, qui consiste à découper un grand tableau en petits tableaux pour les trier sur des petites tailles avant de les fusionner pour obtenir le tri du grand tableau.
si le tableau n'est pas trié
peux t on appeler une méthode qui recherche un element dans un tableau?
comme ceci:
public static void unionnt(int[] TableauA, int rang,int[] TableauB, List<Integer> TableauU) {
if(recherche_non_trie(TableauA,1,0)== false ){
TableauU.add(TableauB[rang]);
unionnt(TableauA,rang+1,TableauB,TableauU);}
}
public static List<Integer> unionnt(int[] TableauA, int[] TableauB) {
List<Integer> TableauU = new ArrayList<Integer>();
unionnt(TableauA,0, TableauB,TableauU);
return TableauU;}
public static boolean recherche_non_trie(int Tableau_nonTrie[],int x,int rang){
if(rang>=Tableau_nonTrie.length) return false;
else if(Tableau_nonTrie[rang]==x) return true;
else return recherche_non_trie(Tableau_nonTrie,x,rang+1);
}
Pourquoi je n'ai rien en retour?
peux t on appeler une méthode qui recherche un element dans un tableau?
comme ceci:
public static void unionnt(int[] TableauA, int rang,int[] TableauB, List<Integer> TableauU) {
if(recherche_non_trie(TableauA,1,0)== false ){
TableauU.add(TableauB[rang]);
unionnt(TableauA,rang+1,TableauB,TableauU);}
}
public static List<Integer> unionnt(int[] TableauA, int[] TableauB) {
List<Integer> TableauU = new ArrayList<Integer>();
unionnt(TableauA,0, TableauB,TableauU);
return TableauU;}
public static boolean recherche_non_trie(int Tableau_nonTrie[],int x,int rang){
if(rang>=Tableau_nonTrie.length) return false;
else if(Tableau_nonTrie[rang]==x) return true;
else return recherche_non_trie(Tableau_nonTrie,x,rang+1);
}
Pourquoi je n'ai rien en retour?
j'ai modifié le programme il me manquait des conditions.
public static void unionnt(int[] TableauA, int rang,int[] TableauB, List<Integer> TableauU) {
if(rang>=TableauA.length || rang>=TableauB.length) return;
if(recherche_non_trie(TableauA,1,0)== false ){
TableauU.add(TableauB[rang]);}
else {
TableauU.add(TableauA[rang]);
unionnt(TableauA,rang+1,TableauB,TableauU);}
}
il me retourne seulement 1,2,3,4
si:
int[] TableauA = {1,2,3,4};
int[] TableauB = {2,3,4,7};
Est ce que quelqu'un comprend pourquoi?
public static void unionnt(int[] TableauA, int rang,int[] TableauB, List<Integer> TableauU) {
if(rang>=TableauA.length || rang>=TableauB.length) return;
if(recherche_non_trie(TableauA,1,0)== false ){
TableauU.add(TableauB[rang]);}
else {
TableauU.add(TableauA[rang]);
unionnt(TableauA,rang+1,TableauB,TableauU);}
}
il me retourne seulement 1,2,3,4
si:
int[] TableauA = {1,2,3,4};
int[] TableauB = {2,3,4,7};
Est ce que quelqu'un comprend pourquoi?
- Messages postés
- 12272
- Date d'inscription
- mardi 11 mars 2003
- Statut
Bonjour ton premier message a été corrigé par NHenry, KX dans sa première réponse t'a signalé que sans la coloration ton code est illisible.
Dans les 2 cas, ils t'ont mis un lien vers la procédure à appliquer.
Dans chacune de ses réponses, KX l'a utilisée, mais toi non...
Plus c'est difficile à lire et moins tu as de chance que quelqu'un le fasse.
D'autre part, il ne faut pas oublier que ce site est animé par des bénévoles et que nous avons d'autres occupations que d'y répondre.
Dans les 2 cas, ils t'ont mis un lien vers la procédure à appliquer.
Dans chacune de ses réponses, KX l'a utilisée, mais toi non...
Plus c'est difficile à lire et moins tu as de chance que quelqu'un le fasse.
D'autre part, il ne faut pas oublier que ce site est animé par des bénévoles et que nous avons d'autres occupations que d'y répondre.
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.