Algorithmique
Résolu
chouchou1978
Messages postés
4
Date d'inscription
vendredi 6 janvier 2006
Statut
Membre
Dernière intervention
8 janvier 2006
-
6 janv. 2006 à 12:27
Pamaury Messages postés 341 Date d'inscription jeudi 3 avril 2003 Statut Membre Dernière intervention 17 juin 2008 - 8 janv. 2006 à 16:33
Pamaury Messages postés 341 Date d'inscription jeudi 3 avril 2003 Statut Membre Dernière intervention 17 juin 2008 - 8 janv. 2006 à 16:33
8 réponses
Pamaury
Messages postés
341
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
17 juin 2008
3
6 janv. 2006 à 20:08
6 janv. 2006 à 20:08
Si j'ai bien comrpis ce que tu veux dire(pseudo C):
typedef struct Tab1D
{
Array array;
};
Array<Tab1D> Array2D;
void EnumAllPos(int row,Array& cur_list)
{
if(row==Array2D.size())
return Print(cur_list);
int last_index=cur_list.push();
for(int i=0;i ): Void
if row == array.size then
ret Print(list)
foreach value V of array[row]
list[row]=V
call EnumAllPos(row+1 , list )
end
ret
end
Et l'appel initial:
list: Array
list.size = array.size
call EnumAllPos( 0, list )
J'espère que c'est bien ce que tu veux faire
en fait il suffit pour chaque ligne de réappeler la fonction pour la ligne suivante en lui passant une liste des entier de la liste en cours et en la mettant en cours selon la valeur de la ligne
A m a u r y
typedef struct Tab1D
{
Array array;
};
Array<Tab1D> Array2D;
void EnumAllPos(int row,Array& cur_list)
{
if(row==Array2D.size())
return Print(cur_list);
int last_index=cur_list.push();
for(int i=0;i ): Void
if row == array.size then
ret Print(list)
foreach value V of array[row]
list[row]=V
call EnumAllPos(row+1 , list )
end
ret
end
Et l'appel initial:
list: Array
list.size = array.size
call EnumAllPos( 0, list )
J'espère que c'est bien ce que tu veux faire
en fait il suffit pour chaque ligne de réappeler la fonction pour la ligne suivante en lui passant une liste des entier de la liste en cours et en la mettant en cours selon la valeur de la ligne
A m a u r y
ketchupy45
Messages postés
101
Date d'inscription
dimanche 1 mai 2005
Statut
Membre
Dernière intervention
13 décembre 2007
1
6 janv. 2006 à 15:22
6 janv. 2006 à 15:22
C'est quoi le rapport entre l'entrée et la sortie??
Explique un peu plus en détails j'ai pas compris ce que tu veux
Explique un peu plus en détails j'ai pas compris ce que tu veux
chouchou1978
Messages postés
4
Date d'inscription
vendredi 6 janvier 2006
Statut
Membre
Dernière intervention
8 janvier 2006
7 janv. 2006 à 13:05
7 janv. 2006 à 13:05
Salut et merci
En fait, je vais essayer d'etre plus cair en decrivant ma structure de
donnees. J'ai une classe PILE <T> qui est derivee de std::vector
<T>. Donc, du C++ ...
Mon tableau est en fait une PILE < PILE >. J'ai donc
la methode size() pour connaitre le nombre de lignes, et pour chaque
ligne, le nombre de colonnes. J'empile avec l'operateur "<<". Par
exemple :
PILE < PILE > app;
app << NULL; // je cree une nouvelle ligne
app(ind) << k; // j'ajoute la valeur k a la ligne ind (a la fin)
En sortie, je voudrais avoir une PILE < PILE > qui
donne toutes les solutions possibles d'enumerations comme donne dans
l'exemple du 1er message. Il est evidemment possible de connaitre le
nombre de possibilites a l'avance
J'avoue que je ne comprens pas tres bien le code que tu m'as donne,
alors, si tu pouvais me le reexpliquer, ca m'arrangerait bien.
Merci encore
En fait, je vais essayer d'etre plus cair en decrivant ma structure de
donnees. J'ai une classe PILE <T> qui est derivee de std::vector
<T>. Donc, du C++ ...
Mon tableau est en fait une PILE < PILE >. J'ai donc
la methode size() pour connaitre le nombre de lignes, et pour chaque
ligne, le nombre de colonnes. J'empile avec l'operateur "<<". Par
exemple :
PILE < PILE > app;
app << NULL; // je cree une nouvelle ligne
app(ind) << k; // j'ajoute la valeur k a la ligne ind (a la fin)
En sortie, je voudrais avoir une PILE < PILE > qui
donne toutes les solutions possibles d'enumerations comme donne dans
l'exemple du 1er message. Il est evidemment possible de connaitre le
nombre de possibilites a l'avance
J'avoue que je ne comprens pas tres bien le code que tu m'as donne,
alors, si tu pouvais me le reexpliquer, ca m'arrangerait bien.
Merci encore
MrdJack
Messages postés
146
Date d'inscription
jeudi 22 avril 2004
Statut
Membre
Dernière intervention
8 mars 2008
2
7 janv. 2006 à 16:34
7 janv. 2006 à 16:34
"Il est evidemment possible de connaitre le nombre de possibilites a l'avance"
--> si tu multiplies le nombre de colonne de chaques ligne de la liste, tu as ton nombre de combinaison.
2 6
5
4 8
1
-->> 2 * 1 * 2 * 1 = 4 possibilités
2541
2581
6541
6581
voila pour le ptit detail sanqs importance...
--> si tu multiplies le nombre de colonne de chaques ligne de la liste, tu as ton nombre de combinaison.
2 6
5
4 8
1
-->> 2 * 1 * 2 * 1 = 4 possibilités
2541
2581
6541
6581
voila pour le ptit detail sanqs importance...
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
chouchou1978
Messages postés
4
Date d'inscription
vendredi 6 janvier 2006
Statut
Membre
Dernière intervention
8 janvier 2006
7 janv. 2006 à 17:03
7 janv. 2006 à 17:03
Oui, sans detailler, la methode, c'est ce que je disais ...
Pamaury
Messages postés
341
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
17 juin 2008
3
8 janv. 2006 à 13:50
8 janv. 2006 à 13:50
Bon je vais essayer de détailler l'algo(qui est pourtant clair je trouve):
Théorie:
A chaque ligne, il a N éléments .
Pour énumérer chaque possibilité, il faut que chaque un élément de chaque ligne apparaisse donc on en choisit un parmis les N possible .
comme on veut énumérer TOUTES les possibilité il faut choisir tour à tour chaqcun des N élément de réappeler l'algorithme à la ligne d'en dessous .
Exemple:
1 2
4 5
6
7 8
liste L={}
->Première ligne: 2 éléments
On choisit 1: L={1}
->Deuxième ligne: 2éléments
On choisit 4: L={1,4}
->Trosième ligne: 1 élément
On choisit 6: L={1,4,6}
->Quatrième ligne: 2 éléments
On choisit 7:L={1,4,6,7} PREMIRE POSSIBILITE
On chosit 8: L={1,4,6,8} DEUXIEME POSSIBILITE
On chosit 5: L={1,5}
->Trosième ligne: 1 élément
On choisit 6: L={1,5,6}
->Quatrième ligne: 2 éléments
On choisit 7:L={1,5,6,7} TROISIEME POSSIBILITE
On chosit 8: L={1,5,6,8} QUATRIEME POSSIBILITE
On choisit 2: L={2}
->Deuxième ligne: 2éléments
On choisit 4: L={2,4}
->Trosième ligne: 1 élément
On choisit 6: L={2,4,6}
->Quatrième ligne: 2 éléments
On choisit 7:L={2,4,6,7} SINQUIEME POSSIBILITE
On chosit 8: L={2,4,6,8} SIXIEME POSSIBILITE
On chosit 5: L={2,5}
->Trosième ligne: 1 élément
On choisit 6: L={2,5,6}
->Quatrième ligne: 2 éléments
On choisit 7:L={2,5,6,7} SEPTIEME POSSIBILITE
On chosit 8: L={2,5,6,8} HUITIEME POSSIBILITE
Et comme l'a dit MrdJack: 2*2*1*2=8 possibilité
J'epsère que c'est clair comme çà
A m a u r y
Théorie:
A chaque ligne, il a N éléments .
Pour énumérer chaque possibilité, il faut que chaque un élément de chaque ligne apparaisse donc on en choisit un parmis les N possible .
comme on veut énumérer TOUTES les possibilité il faut choisir tour à tour chaqcun des N élément de réappeler l'algorithme à la ligne d'en dessous .
Exemple:
1 2
4 5
6
7 8
liste L={}
->Première ligne: 2 éléments
On choisit 1: L={1}
->Deuxième ligne: 2éléments
On choisit 4: L={1,4}
->Trosième ligne: 1 élément
On choisit 6: L={1,4,6}
->Quatrième ligne: 2 éléments
On choisit 7:L={1,4,6,7} PREMIRE POSSIBILITE
On chosit 8: L={1,4,6,8} DEUXIEME POSSIBILITE
On chosit 5: L={1,5}
->Trosième ligne: 1 élément
On choisit 6: L={1,5,6}
->Quatrième ligne: 2 éléments
On choisit 7:L={1,5,6,7} TROISIEME POSSIBILITE
On chosit 8: L={1,5,6,8} QUATRIEME POSSIBILITE
On choisit 2: L={2}
->Deuxième ligne: 2éléments
On choisit 4: L={2,4}
->Trosième ligne: 1 élément
On choisit 6: L={2,4,6}
->Quatrième ligne: 2 éléments
On choisit 7:L={2,4,6,7} SINQUIEME POSSIBILITE
On chosit 8: L={2,4,6,8} SIXIEME POSSIBILITE
On chosit 5: L={2,5}
->Trosième ligne: 1 élément
On choisit 6: L={2,5,6}
->Quatrième ligne: 2 éléments
On choisit 7:L={2,5,6,7} SEPTIEME POSSIBILITE
On chosit 8: L={2,5,6,8} HUITIEME POSSIBILITE
Et comme l'a dit MrdJack: 2*2*1*2=8 possibilité
J'epsère que c'est clair comme çà
A m a u r y
chouchou1978
Messages postés
4
Date d'inscription
vendredi 6 janvier 2006
Statut
Membre
Dernière intervention
8 janvier 2006
8 janv. 2006 à 16:24
8 janv. 2006 à 16:24
OK, merci. En fait, l'algo que tu m'avais donne precedemment etait tres
clair. Juste une erreur d'implementation ... Corrige, avec ma structure
de donnees decrites ci-dessus, ca donne ca :
bool EnumAllPos(int raw, const PILE < PILE >
&app, PILE &pile, PILE < PILE >
&result)
{
if( raw == app.size() )
{
result << pile;
return true;
}
int i;
for(i=0;i > app;
app << NULL;
app(0) << 1;
app << NULL;
app(1) << 5;
app(1) << 8;
app << NULL;
app(2) << 12;
app(2) << 1276;
app(2) << 3;
app(2) << 98;
app << NULL;
app(3) << 15;
app(3) << 22;
int i, tot = 1;
PILE pi;
pi.reserve(4);
for (i=0;i > res;
res.reserve(tot);
EnumAllPos(0,app,pi,res);
for (i=0;i<res.size();i++)
SORTIEMESSAGE("res("<
"<<res(i)<<std::endl);
}
Merci pour ton aide ...
clair. Juste une erreur d'implementation ... Corrige, avec ma structure
de donnees decrites ci-dessus, ca donne ca :
bool EnumAllPos(int raw, const PILE < PILE >
&app, PILE &pile, PILE < PILE >
&result)
{
if( raw == app.size() )
{
result << pile;
return true;
}
int i;
for(i=0;i > app;
app << NULL;
app(0) << 1;
app << NULL;
app(1) << 5;
app(1) << 8;
app << NULL;
app(2) << 12;
app(2) << 1276;
app(2) << 3;
app(2) << 98;
app << NULL;
app(3) << 15;
app(3) << 22;
int i, tot = 1;
PILE pi;
pi.reserve(4);
for (i=0;i > res;
res.reserve(tot);
EnumAllPos(0,app,pi,res);
for (i=0;i<res.size();i++)
SORTIEMESSAGE("res("<
"<<res(i)<<std::endl);
}
Merci pour ton aide ...
Pamaury
Messages postés
341
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
17 juin 2008
3
8 janv. 2006 à 16:33
8 janv. 2006 à 16:33
ligne en anglais c'est pas "row" ?
A m a u r y
A m a u r y