Algo de recherche de solutions [Résolu]

Signaler
Messages postés
2
Date d'inscription
vendredi 27 août 2004
Statut
Membre
Dernière intervention
22 février 2006
-
ctoutkc
Messages postés
2
Date d'inscription
vendredi 27 août 2004
Statut
Membre
Dernière intervention
22 février 2006
-
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

Messages postés
694
Date d'inscription
lundi 5 décembre 2005
Statut
Membre
Dernière intervention
8 janvier 2014
7
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 !
Messages postés
98
Date d'inscription
vendredi 17 février 2006
Statut
Membre
Dernière intervention
24 janvier 2018

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.
Messages postés
13
Date d'inscription
samedi 28 janvier 2006
Statut
Membre
Dernière intervention
28 février 2006

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
Messages postés
2
Date d'inscription
vendredi 27 août 2004
Statut
Membre
Dernière intervention
22 février 2006

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