Discussion :

[LiquidHuk]

Bonjour,

On m'a récemment proposé cet énoncé et comme je ne suis pas parvenu à une solution maline au problème, je suis à la recherche d'un nom à mettre sur celui-ci afin d'en apprendre plus sur les différentes solutions.

A partir d'un tableau de N valeurs (1 < N < 32), découper le tableau en trois groupes vérifiant la condition suivante : Les sommes des valeurs de chaque groupes doivent être égales.
Retourner une chaîne de caractère de taille N qui pour chaque valeur du tableau fait correspondre un groupe donné par les lettres "R", "G" ou "B". Si le tableau ne possède pas de solution, retourner "impossible".

Exemple : [1, 5, 6, 3, 7, 1, 2, 8, 3]
Une solution possible : "RRRGGBGBB"
R : 1+5+6 = 12
G : 3 + 7 + 2 = 12
B : 1 + 8 + 3 = 12

[yahiko]

Je ne sais pas si ce problème a un nom, mais cela ressemble plus à un problème mathématique de de l'algorithmique pure.

Néanmoins, voici une piste de résolution :

Puisque nous avons 3 groupes (R, G et B), la somme S des N valeurs doit être divisible par 3.

Chaque groupe doit donc avoir un total égal à s = S / 3.

Le job consiste donc à trouver l'ensemble des groupes de nombres dont la somme est égale à s.
Si N n'est pas trop grand, un algorithme naïf devrait être acceptable.

[tbc92]

Bonjour,

L'objectif de cet exercice, c'est quoi ?
C'est de parcourir toutes les combinaisons possibles,autrement dit, parcourir toutes les branches d'un arbre.
Dans l'exemple avec [1, 5, 6, 3, 7, 1, 2, 8, 3], on associe 1 avec 5 , puis 1 avec 5 et avec 6,1 avec 5 avec 3 ... etc, jusqu'à trouver une solution au problème.
Parcourir toutes les branches d'un arbre, il y a un algorithme incontournable pour cela, c'est l'algorithme A*.

Après, si on veut optimiser le truc, on va ordonner les nombres du plus grand au plus petit, parce que c'est comme ça qu'on va éliminer au plus vite les combinaisons qui mènent à des impasses.

Et c'est clairement un exercice d'algorithmique, et non de maths.

[yahiko]

En effet, ça peut se résoudre avec du A*, l'auteur du post sera donc content d'avoir la réponse.

[LiquidHuk]

A* se base sur le coût de passage d'un nœud à un autre pour effectuer les calculs jusqu'à l'arrivée (dans le cas de recherche de chemin).
Je ne vois pas bien le rapport entre les deux tbc92 ?

[tbc92]

L'algorithme A* commence par une première chose :
J'ai un point de départ (un noeud).
A partir de n'importe quel noeud, je sais comment trouver ses voisins immédiats. : 2 noeuds voisins sont reliés par un ARC
Je cherche un chemin pour aller de mon noeud de départ au noeud d'arrivée.
Et l'algorithme A* aide à explorer tous les chemins possibles, rebrousser chemin quand on est dans une impasse ... C'est cela l'objectif n°1 de l'algo A*.
Dans sa version plus élaborée, il va optimiser. Il va mettre de coté les chemins qui semblent peu prometteurs, et il va chercher le chemin le plus court.


Ici, c'est quoi notre exercice.
On a 4 boites : Une boite P=Pioche, une boite R=Rouge, une boite G (G=Green = Verte) et une Boite B=Bleue.
Le noeud de départ : tous les pions sont dans la boite P
Le noeud d'arrivée ? En fait, il y a plein de situations d'arrivées possibles, ce sont toutes les situations où la pioche est vide, et les 3 boites ont des montants égaux.

Les mouvements possibles : Un mouvement, c'est déplacer un pion d'une boite à une autre.
On peut même limiter les mouvements en disant que les pions sont ordonnés dans chaque boite ( un peu comme des cartes posées en tas), et les mouvements autorisés, c'est : prendre la carte qui est en haut d'une pile, et la poser en haut d'une autre pile. Ca limite énormément le nombre de doublons dans les hypothèses à explorer.

Ca y est , on a défini nos NOEUDS, nos ARCS ... On peut appliquer le fameux Algo.