Petit defi algorithmique

Version imprimable

06/03/2009, 22h24
akrakrapovic

Petit defi algorithmique

Bonjour,
soit V mon nombre de voiture et G mon nombre de garage. Je voudrais connaitre toutes les combinaisons possibles.
Exemple
les voitures V1, V2, V3, V4
Les garages G1, G2, G3

les resultats:
G1: V1, V2
G2: V3
G3: V4

G1: V4
G2:V1,V2
G3:V3

...

Voila ca fait une semaine et je n'arrive pas à trouver l'algo qui va bien !
Si y en a qui veulent s'y casser les dents !
06/03/2009, 22h57
direct

Bon j'ai trouvé une belle solution pour ce défi mais je ne sais pas que c'est optimal ou pas.
On tient tout d'abord ma solution et on discutera plus tard.
L'idée dit :
soit deux tableau qui contient les noms des voitures et les garages d'une façon général.
Voitue[N]
Garage[M]
Il suffit de faire deux petit boucle avec un test.

pour i=1 à N faire
pour j=1 à M faire
si i != j alors //Si i différent de j
écrire (Voiture[i], Garage[j])
fin si
FP
FP
06/03/2009, 23h50
Zavonen

Une fois de plus il s'agit de dénombrer un ensemble d'applications (chaque voiture va dans un garage et un seul).
L'ensemble des applications de V1,V2,V3,V4 dans G1,G2,G3.
Voir mon cours maths-> bases->applications
07/03/2009, 03h38
ToTo13

Bonsoir,

et si tu faisais une recherche dans le forum sur tout ce qui est : "trouver toutes les combinaisons", "trouver les combinaisons", etc.
:recherch:
C'est un sujet qui a déjà été traité plusieurs fois.
07/03/2009, 18h55
FR119492

Salut!

Citation:

soit V mon nombre de voiture et G mon nombre de garage

Comme tu n'as pas mis de s à la fin des mots "voiture" et "garage", on a obligatoirement V=1 et G=1. Le problème est donc trivial.
Jean-Marc Blanc
08/03/2009, 16h07
henderson

Salut !

C'est un simple problème de compteur à (V) étages où chacun d'eux compte jusqu'à (G) !
On a (V) digits en base (G).
Le nombre de combinaisons possibles est égal à (G) puissance (V) (aux exceptions près).

Si ça se pense comme une imbrication de (V) boucles comptant jusqu'à (G), ça se modélise très simplement à l'aide de la récursivité (pour lister, par exemple, toutes les combinaisons) !

A plus !
09/03/2009, 09h16
akrakrapovic

Citation:

Envoyé par FR119492

Salut!

Comme tu n'as pas mis de s à la fin des mots "voiture" et "garage", on a obligatoirement V=1 et G=1. Le problème est donc trivial.
Jean-Marc Blanc

Super ca c'est du message avec un intérêt certain.
J'ai cherché avec les pistes que tout le monde a donné mais je n'ai rien trouvé.

Donc je vais continuer à investiguer je posterai une réponse si je trouve qq chose.
Pour info j'ai quand même posé la question à deux mathématiciens reconnus qui sont restés sans réponse. Donc les réponses du genre cherche c'est trop facile je veux bien mais ça ne fais pas avancer les choses. Données vos reponses si c'est si simple !

Citation:

Envoyé par akrakrapovic

Pour info j'ai quand même posé la question à deux mathématiciens reconnus qui sont restés sans réponse.

Entre le titre et cette remarque, j'ai l'impression que tu taquines notre égo pour avoir ta réponse. :D

Citation:

Donc les réponses du genre cherche c'est trop facile je veux bien mais ça ne fais pas avancer les choses. Données vos reponses si c'est si simple !

On a déjà donné la réponse plusieurs fois. Si tu cherches sur le forum il y a même des exemples de code. Il suffit de compter en de 0 à G^V en base G.

Dans ton exemple, on a V=4 et G=3 --> il faut compter de 0 a 81 en base 3.

0000, 0001, 0002, 0010, 0011, 0012, 0020, ... , 2220, 2221, 2222

Chaque digit de l'écriture en base 3 te dis dans quelle garage va la voiture:
0=Garage 1, 1=Garage 2, 2=Garage 3

0012 --> V1 et V2 dans Garage 1, V3 dans Garage 2 et V4 dans Garage 3

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
0000 --> G1={ V1 V2 V3 V4 } G2={ } G3={ } 
0001 --> G1={ V1 V2 V3 } G2={ V4 } G3={ } 
0002 --> G1={ V1 V2 V3 } G2={ } G3={ V4 } 
0010 --> G1={ V1 V2 V4 } G2={ V3 } G3={ } 
0011 --> G1={ V1 V2 } G2={ V3 V4 } G3={ } 
0012 --> G1={ V1 V2 } G2={ V3 } G3={ V4 } 
0020 --> G1={ V1 V2 V4 } G2={ } G3={ V3 } 
0021 --> G1={ V1 V2 } G2={ V4 } G3={ V3 } 
0022 --> G1={ V1 V2 } G2={ } G3={ V3 V4 } 
0100 --> G1={ V1 V3 V4 } G2={ V2 } G3={ } 
0101 --> G1={ V1 V3 } G2={ V2 V4 } G3={ } 
0102 --> G1={ V1 V3 } G2={ V2 } G3={ V4 } 
0110 --> G1={ V1 V4 } G2={ V2 V3 } G3={ } 
0111 --> G1={ V1 } G2={ V2 V3 V4 } G3={ } 
0112 --> G1={ V1 } G2={ V2 V3 } G3={ V4 } 
0120 --> G1={ V1 V4 } G2={ V2 } G3={ V3 } 
0121 --> G1={ V1 } G2={ V2 V4 } G3={ V3 } 
0122 --> G1={ V1 } G2={ V2 } G3={ V3 V4 } 
0200 --> G1={ V1 V3 V4 } G2={ } G3={ V2 } 
0201 --> G1={ V1 V3 } G2={ V4 } G3={ V2 } 
0202 --> G1={ V1 V3 } G2={ } G3={ V2 V4 } 
0210 --> G1={ V1 V4 } G2={ V3 } G3={ V2 } 
0211 --> G1={ V1 } G2={ V3 V4 } G3={ V2 } 
0212 --> G1={ V1 } G2={ V3 } G3={ V2 V4 } 
0220 --> G1={ V1 V4 } G2={ } G3={ V2 V3 } 
0221 --> G1={ V1 } G2={ V4 } G3={ V2 V3 } 
0222 --> G1={ V1 } G2={ } G3={ V2 V3 V4 } 
1000 --> G1={ V2 V3 V4 } G2={ V1 } G3={ } 
1001 --> G1={ V2 V3 } G2={ V1 V4 } G3={ } 
1002 --> G1={ V2 V3 } G2={ V1 } G3={ V4 } 
1010 --> G1={ V2 V4 } G2={ V1 V3 } G3={ } 
1011 --> G1={ V2 } G2={ V1 V3 V4 } G3={ } 
1012 --> G1={ V2 } G2={ V1 V3 } G3={ V4 } 
1020 --> G1={ V2 V4 } G2={ V1 } G3={ V3 } 
1021 --> G1={ V2 } G2={ V1 V4 } G3={ V3 } 
1022 --> G1={ V2 } G2={ V1 } G3={ V3 V4 } 
1100 --> G1={ V3 V4 } G2={ V1 V2 } G3={ } 
1101 --> G1={ V3 } G2={ V1 V2 V4 } G3={ } 
1102 --> G1={ V3 } G2={ V1 V2 } G3={ V4 } 
1110 --> G1={ V4 } G2={ V1 V2 V3 } G3={ } 
1111 --> G1={ } G2={ V1 V2 V3 V4 } G3={ } 
1112 --> G1={ } G2={ V1 V2 V3 } G3={ V4 } 
1120 --> G1={ V4 } G2={ V1 V2 } G3={ V3 } 
1121 --> G1={ } G2={ V1 V2 V4 } G3={ V3 } 
1122 --> G1={ } G2={ V1 V2 } G3={ V3 V4 } 
1200 --> G1={ V3 V4 } G2={ V1 } G3={ V2 } 
1201 --> G1={ V3 } G2={ V1 V4 } G3={ V2 } 
1202 --> G1={ V3 } G2={ V1 } G3={ V2 V4 } 
1210 --> G1={ V4 } G2={ V1 V3 } G3={ V2 } 
1211 --> G1={ } G2={ V1 V3 V4 } G3={ V2 } 
1212 --> G1={ } G2={ V1 V3 } G3={ V2 V4 } 
1220 --> G1={ V4 } G2={ V1 } G3={ V2 V3 } 
1221 --> G1={ } G2={ V1 V4 } G3={ V2 V3 } 
1222 --> G1={ } G2={ V1 } G3={ V2 V3 V4 } 
2000 --> G1={ V2 V3 V4 } G2={ } G3={ V1 } 
2001 --> G1={ V2 V3 } G2={ V4 } G3={ V1 } 
2002 --> G1={ V2 V3 } G2={ } G3={ V1 V4 } 
2010 --> G1={ V2 V4 } G2={ V3 } G3={ V1 } 
2011 --> G1={ V2 } G2={ V3 V4 } G3={ V1 } 
2012 --> G1={ V2 } G2={ V3 } G3={ V1 V4 } 
2020 --> G1={ V2 V4 } G2={ } G3={ V1 V3 } 
2021 --> G1={ V2 } G2={ V4 } G3={ V1 V3 } 
2022 --> G1={ V2 } G2={ } G3={ V1 V3 V4 } 
2100 --> G1={ V3 V4 } G2={ V2 } G3={ V1 } 
2101 --> G1={ V3 } G2={ V2 V4 } G3={ V1 } 
2102 --> G1={ V3 } G2={ V2 } G3={ V1 V4 } 
2110 --> G1={ V4 } G2={ V2 V3 } G3={ V1 } 
2111 --> G1={ } G2={ V2 V3 V4 } G3={ V1 } 
2112 --> G1={ } G2={ V2 V3 } G3={ V1 V4 } 
2120 --> G1={ V4 } G2={ V2 } G3={ V1 V3 } 
2121 --> G1={ } G2={ V2 V4 } G3={ V1 V3 } 
2122 --> G1={ } G2={ V2 } G3={ V1 V3 V4 } 
2200 --> G1={ V3 V4 } G2={ } G3={ V1 V2 } 
2201 --> G1={ V3 } G2={ V4 } G3={ V1 V2 } 
2202 --> G1={ V3 } G2={ } G3={ V1 V2 V4 } 
2210 --> G1={ V4 } G2={ V3 } G3={ V1 V2 } 
2211 --> G1={ } G2={ V3 V4 } G3={ V1 V2 } 
2212 --> G1={ } G2={ V3 } G3={ V1 V2 V4 } 
2220 --> G1={ V4 } G2={ } G3={ V1 V2 V3 } 
2221 --> G1={ } G2={ V4 } G3={ V1 V2 V3 } 
2222 --> G1={ } G2={ } G3={ V1 V2 V3 V4 }

09/03/2009, 19h17
henderson

Salut !

Ceci dit, le principe c'est une chose ...

J'ai trouvé plus amusant d'objétser (C++) un véhicule sachant sortir d'un garage pour entrer dans un autre et le cas échéant faire signe à un autre véhicule de faire la même chose !

En travaillant avec des listes, un garage donne directement ses véhicules !
C'est sûr que c'est plus long à coder qu'en C ... (en somme, juste pour le fun !) mais, ça fait une solution de plus !

A plus !
10/03/2009, 07h25
akrakrapovic

Super effectivement j'ai fais un bon en avant.
Mais ce n'est quand même tout à fais complet car il faut une hypothèse de départ V>G (plus de voitures que de garages pour que cela fonctionne).

Si on V<=G je pense à ajouter des voitures fictives pour garder le même algo.

PAs si simple quand même pour que ca marche dans tous les cas.

Je fais des tests pour voir le comportement lors de l'augmentation des garages et des voitures et je vous tiens au informe.

A+
10/03/2009, 16h11
souviron34

Citation:

Envoyé par akrakrapovic

Si on V<=G je pense à ajouter des voitures fictives pour garder le même algo.

Non, le problème ne se pose que si V < G

Mais là, à ce compte-là il suffit de prendre le problème dans l'autre sens (et comme c'est des combinaisons, c'est équivalent :P)
11/03/2009, 20h42
akrakrapovic

Bon c'est nikel, j'ai fait pleins de tests et ça marche. Merci beaucoup. Je ne sais pas comment on marque "resolu" dans le titre mais encore un gros merci pour la réponse.
A+:king:
30/03/2009, 15h30
compdev

ProLog

Bonjour,

il me paraît que l'algorithme que tu cherches peut être codé en PROLOG, langage de programmation utilisé en intelligence artificielle. D'ailleurs ProLog et ses similaires ont été inventés pour soulever ce types de problèmes et pour résoudre le problème de la complexité des algorithmes. Ces derniers peuvent se résoudre sans utilisation de structures ordinaires telles les boucles par exemple.

Les instructions seront du type:

Affecter_garage(V[i], G[j]):- (le ":-" veut dire "si")
A_L_Exterieur(V[i]) AND Place_Disponible(G[j]);
A_L_Exterieur(V[i]) := False;
Place_disponible(G[j]) := Place_disponible(G[j]) - Place0;
etc etc

Mais il faut procéder à l'initialisation de certaines variables comme Place_Disponible(G) et définir la place tenue pour chaque voiture (Place0).
Ceci rentre bien entendu dans la programmation en logique (ProLog) et utilise ce qu'on appelle le calcul des prédicats connu chez les logiciens.

Salutations