Algo de recherche de solutions

Résolu
ctoutkc Messages postés 2 Date d'inscription vendredi 27 août 2004 Statut Membre Dernière intervention 22 février 2006 - 21 févr. 2006 à 14:54
ctoutkc Messages postés 2 Date d'inscription vendredi 27 août 2004 Statut Membre Dernière intervention 22 février 2006 - 22 févr. 2006 à 09:08
Bonjour,

J'ai un petit probleme a vous soumetre.



Si on considere 5 tableaux de variables (structures) chacun de ces tableaux contient n éléments.

je voudrais calculer toutes les solutions possibles en parcourant chaque tableau et chaque variables.

petit exemple:

Tableau1 Sol1-1 Sol1-2 Sol1-3

Tableau2 Sol2-1 Sol2-2

Tableau3 Sol3-1 Sol3-2 Sol3-3 Sol3-4

Tableau4 Sol4-1 Sol4-2 Sol4-3

Tableau5 Sol5-1 Sol5-2



La premiere solution globale serait:

Sol1-1,Sol2-1,Sol3-1,Sol4-1,Sol5-1

La deuxieme

Sol1-1,Sol2-1,Sol3-1,Sol4-1,Sol5-2

La troisieme
Sol1-1,Sol2-1,Sol3-1,Sol4-2,Sol5-1

etc...



La difficulte est que:

- le nb de tableaux est variable ainsi que le nb de solutions par tableau.

- une solution globale doit imperativement passer par tout les tableaux.

Quelqu'un purrait il m'aider a trouver l'algo qui va bien ?



Merci d'avance


CtoutKC

4 réponses

cs_AlexN Messages postés 694 Date d'inscription lundi 5 décembre 2005 Statut Membre Dernière intervention 8 janvier 2014 18
21 févr. 2006 à 18:06
Salut,



// CountTab.cpp : Defines the entry point for the console application.

//



#include "stdafx.h"

#include <stdlib.h>

#include <string.h>

#include <time.h>



// Changer ici le nombre de tableaux a traiter

// (Doit être connu à la compilation)

#define MAXTAB 3

#define TAILLE 7

#define MAXRAND 5



typedef struct {

int Dim; // Taille du tableau

char **Tab; // Tableau de chaines ("Sol1-1", "Sol1-2"..)

} _Tabs, *_pTabs;



typedef int SubTab[MAXTAB];



// Et hop !

void AfficherSol (int IdxTab, _pTabs Tabs, SubTab Index, int Niveau) {



int IdxEle;



if ( IdxTab == MAXTAB ) {

for ( int Idx = 0; Idx < MAXTAB; Idx++ )

printf ("%s ", Tabs[Idx].Tab[Index[Idx]]);

puts("");

return;

}

for (IdxEle = 0 ; IdxEle < (*(Tabs+IdxTab)).Dim ; IdxEle++ ) {

Index[Niveau] = IdxEle;

AfficherSol (IdxTab+1, Tabs, Index, Niveau+1);

}

}



int main(int argc, char* argv[]) {



_Tabs Tabs[MAXTAB];

int IdxTab, IdxEle;

char Element[TAILLE];

SubTab Index;



// Création des tableaux

srand((unsigned)time( NULL ));

for ( IdxTab = 0; IdxTab < MAXTAB; IdxTab++ ) {

Tabs[IdxTab].Dim = rand()%MAXRAND + 1;

Tabs[IdxTab].Tab = (char **) malloc (sizeof(char *)*Tabs[IdxTab].Dim);

for ( IdxEle = 0; IdxEle < Tabs[IdxTab].Dim; IdxEle++ ) {

Tabs[IdxTab].Tab[IdxEle] = (char *) malloc (sizeof(char)*TAILLE);

sprintf (Element, "Sol%1d-%1d", IdxTab+1, IdxEle+1);

strcpy (Tabs[IdxTab].Tab[IdxEle], Element);

}

}

// Affichage des tableaux

for ( IdxTab = 0; IdxTab < MAXTAB; IdxTab++ ) {

printf ("Tableau numero %d : ", IdxTab+1);

for ( IdxEle = 0; IdxEle < Tabs[IdxTab].Dim; IdxEle++)

printf ("%s ", Tabs[IdxTab].Tab[IdxEle]);

puts("");

}

puts("");

// Affichage de la solution

AfficherSol(0, (_pTabs) &Tabs, Index, 0);

return 0;

}






Si c'est ca alors t'auras p'têt une bonne note !
3
zaibacker Messages postés 98 Date d'inscription vendredi 17 février 2006 Statut Membre Dernière intervention 24 janvier 2018
21 févr. 2006 à 17:16
Je ne vois pas trop ce que tu cherches malgré tes efforts pour l'expliquer en tout cas tu es d'accord que si la taille est variable il faut utilisé un tableau dynamique. Une sorte de tableau de tableaux puisque tu ne connais pas le nombre de tableaux.

typedef struct _tableaux
{
int a; ........
}Tableaux;


Tableaux **tab;
*tab=(Tableaux**)malloc(nombre_tableaux*sizeof(Tableaux*));
for(i=0;i<nombre_tableaux;i++)
{
tab[i]=(Tableaux*)malloc(n*sizeof(Tableaux));
}

Enfin bon,d'après ce que jai compris je commencerais par faire quelque chose de ce style la.
0
MisterDa2 Messages postés 13 Date d'inscription samedi 28 janvier 2006 Statut Membre Dernière intervention 28 février 2006
21 févr. 2006 à 19:35
Ton problème me fait penser à un problème d'affectation comme on peut voir en recherche op. As tu jeté un coup d'oeil du cotès des graph et notemment de l'algorithme hongrois ?

En espérant t'avoir aidé...

da
0
ctoutkc Messages postés 2 Date d'inscription vendredi 27 août 2004 Statut Membre Dernière intervention 22 février 2006
22 févr. 2006 à 09:08
Merci à tous pour vos contributions.

La solution postée par AlexN me convient tout a fait.
Il faut juste que je la traduise en C++ pure.

Encore merci.

CtoutKC
0
Rejoignez-nous