Discussion :

[cyberkamikaz]

Salut,
(J'ai ajoute encore des explications et des exemples dans un post en dessous)
Dans une chaîne de ballons, on a deux types de ballons : les rouges et les noirs. Les ballons ont une propriété : si il y a trois ballons de la même couleur, l'une à côté de l'autre,les trois exploses . On a une autre chaîne de ballons (qui n'explosent pas ici) d'où l'on prend à chaque fois un ballon de la gauche et on le met dans la première liste n'importe où.

Par exemple, on à la chaîne initiale : « RRNNRRNRNR » et la deuxième chaîne d'où on va prendre un ballon, un à la fois, et le mettre dans la chaîne initiale : RNR.

On prend le premier R et on va le mettre là : RRNNRRRMRNR.
Comme vous le voyez, ces ballons vont exploser (souligné) : « RRNNRRRNRNR »

… et on ne restera qu'avec RNRNR et la liste d'où on prend à chaque fois un ballon : « NR ». On répete la procédure : on va prendre « NR » et le mettre à une position dans la chaîne initiale « RNNRNR ». Rien ne va exploser car on n'a pas trois couleurs identiques côte à côte. Au dernier pas, on va prendre le dernier qui reste R et le mettre dans la chaîne initiale : « RNNRNR ». Et, encore une fois rien ne va exploser.

Dans un fichier, on a les deux chaînes de caractères : la chaîne initiale et la chaîne d'où on prend un ballon. Et on doit calculer le numéro minimum des ballons pris de la deuxième chaîne pour arriver à vider la chaîne initiale.

Comment faire pour calculer ce nombre minimum cite en dessus ?

Je ne sais pas comment faire mais je crois que c'est avec du backtracking ,J'aimerais bien une autre solution si c'est possible plus optimisé (Memoire et Temps) .


Merci d'avance.


Ps:
Meme le backtracking je ne m'y connais pas (j'ai seulement entendu en quoi il conste).

[250rgv]

Donc, tu voudrais que nous fassions tes devoirs ?

[cyberkamikaz]

J'aimerais seulement que vous me metiez sur route.

[250rgv]

Et bien tu peut déjà commencer par :
* faire un algo "naif" sans optimisation, elle viendra en son temps.
* chercher ce qu'est le backtraking par ex. ici.
* rechercher ce que sont les méta-heuristiques comme les fourmis, les algo. génétiques, le recuit simulé, le hill-climbing (me souvient plus du nom "français") et d'autres.
* etc...

[cyberkamikaz]

Merci pour ton aide.
Je vais voir tous ce que tu m'a donne.

[cyberkamikaz]

La seule chose qui me passe par la tete est de utiliser le backtracking + des conditions pour reduire les solutions partielle mais je crois pas que ca marche prenons la conditions de ajouter le ballon a cote de 2 autres ballons de la meme couleure qui existe dans la chaine initiale.
Je crois pas que ca marche parceque on peux poser le ballons dans d'autres lieux et pui il y'auras plusieres reductions (explosions).