Pour les passionnés d'algorithmie ! - Page 1

Matez le sujet des demi-finales de Nantes de Prologin 2002 :



Amusez-vous bien

PS : perso, j'ai pas trouvé la 5° et j'ai eu des idées pour la 6° mais pas eu le temps de les écrires.

oua

Ouai je vous serais reconnaissant de rester sérieux, si vous voulez délirer sur la y'a une section pour dans le forum.

Ce que je voudrais c'est qu'on réfléchisse ensemble, qu'on propose nos idées, etc sur le sujet, surtout sur les questions 5 et 6 : les plus dures.

dsl, g pas put resister
non, ca a l'air sympa, j'y serai bien allé si je connaissais mieux les languages proposés
bah sinon, la question 1 à 51 pts, ca va
la 2, t'utilise une matrice,non

ouaaa!

question 1 (51 points):

- Sec (sans eau, sans glaçons)

Question 2 (2 points):

ba... la réaction immédiate serait de dire un tableau...
mais je c pas... avec le ricard sec, on est vite , v dormir...

Pour les noms de récipients, j'ai proposé :
typedef enum {VASE, GAMELLE, DE, SOUCOUPE, BAC, etc...} TNoms;

Pour la structure des récipients :

typedef struct {
                 short capacite; // la capicité maximale de liquide que le récipient peut acceuillir
                 short libre;    // quand on remplit le récipient, le volume restant change...
               } TRecip;

TRecip Recips[NB_RECIPIENTS];    // Voilà la liste dont les éléments sont accessibles directement avec les noms des récipients (puisque de type enum) :)

Pour les transvasements :

typedef struct {
                 TNoms source; // le récipient qu'on veut vider
                 TNoms dest;   // là où il doit être vidé
               } TTransv;

C'était franchement pas le plus difficile Par contre les questions 5 et 6...

[edit]Edité par Thibaut le 27-01-2002 à 11:59:07[/edit]

ué, bon, tu peux traduire ça en asm stp?
c koi tt ces trucs bordéliques là??
c des tableaux?

Laisse tomber pour faire ça en ASM, ça serait illisible. Apprend le C ou le Pascal, on peut rien pour toi.

A midi on a discuté de l'épreuve (évident), et en fait les organisateurs nous ont expliqué qu'il fallait faire un algo récursif ET dynamique pour résoudre ces questions...
Bref peu de monde avait deviné celà, donc on a tous buté au même endroit
[edit]Edité par Thibaut le 27-01-2002 à 11:58:00[/edit]

bah, le + mieu ça aurait été d'utiliser des arbres

bsp rulezz

Les kestions 5 et 6 c'est du backtraking ... un peu le meme genre d'algo que pour la resolution du probleme des 8 reines sur un echiquiers !
C'est le genre de fonction qui doit pas prendre plus de 10 lignes de codes tres simple en C

v essayer pour voir :]

tibo>a bon...

Le backtracking c'est mauvais comparé à un algorithme probabiliste... Pour le probleme des 8 reines, si tu fais des placements succéssifs au hasard tu as plus de chance de trouver une bonne réponse plus rapidement. (avec le backtracking tu es sur de trouver une bonne réponse, mais en plus longtemps)

Nitro > la question que l'on pose c de trouver TOUS les volumes possibles et non pas de trouver UN volume POSSIBLE le plus rapidement
Donc t'as pas le choix : backtraking ...

Oui t'as raison
Je donnais juste un élargissement d'idées pour ouvrir l'esprit à ceux que ça interesse ...

moi g fini

c quoi le backtraking ?

tu construis une solution etape par etape ... et lorsque tu es bloké tu reviens un coup en arriere et tu changes le precedent coup qui t'avais bloké et qui t'avais fait revenir en arriere.

Si le fait de revenir en arriere ne te debloke pas alors tu reviens encore une fois en arriere ... etc

Tu vas donc parcourir l'ensemble des solutions possibles.
Lorsque tu es bloké des la premiere etape c que tu es petit a petit remonté en arriere d'un coup jusk'a arrivé a ta premiere etape et bien ton algo est fini !

Bon ca a l'air compliqué comme ca mais en fait c un algo recursif ... et la recursivite fait tout le travail ... y a preske rien a faire

Un petit exemple pour illustrer tout ca
Le probleme des 8 reines et tres bien pour servir d'exemple !

Donc tu as ton echikier et tes 8 reines a placer !
Premiere chose comme les reines peuvent capturer toutes pieces se trouvant sur la meme ligne horizontale k'elles ... il est evident qu'on ne vas en fait placer qu'une reine par ligne !

Le but c donc de mettre la premiere reine sur la premiere case de l'echiquier !
Ensuite ... et bien on passe a la deuxieme ligne pour placer la deuxieme reine ... on place cette reine sur la premiere case de la deuxieme ligne !
La on se trouve dans un etat blokant : la premiere reine peut capturer la seconde !
Alors on revient en arriere : on enleve la seconde reine et on la fait avancer d'une case !
Encore un etat blokant !
On revient en arriere et on fait avancer la seconde reine d'une autre case ... cette fois c bon

On passe a la troisieme reine et on commence par la placer sur la premiere case de la 3eme ligne ...etc ...

dans ce probleme on va revenir en arriere et faire avancer la reine lorsque la place k'elle occupe peut-etre prise par une precedente reine!
Lorsqu'une reine arrive au bout de la ligne (a force de les faire avancer d'une case ca va vite arriver) et bien on ejecte la reine et on repasse a l'etape precedente ... c'est a dire qu'on avance d'une case la reine d'avant (on backtracke)

l'algo se termine loske la premiere reine arrive en bout de ligne et que l'on aimerait la faire avancer d'une case ... mais comme elle est en bout de ligne on ne peut pas

et ici y a le code que j'avais fais qui utilise ce principe : post.php?id=1,2935,0

Et le mien en itératif (pas très efficace franchement ).

Alors Bill Bob ta fonction ?

UÉ et ta fonction alors....10 lignes c'est quand même short...

un parcours infixé ce serait pas mieux qu'un algo récursif?

lol sBibi, et un parcours infixe récursif pourquoi pas ?

arf, je voulais dire un parcours infixe NON recursif

Dans ce cas on dit "itératif"

ba g pa dit, puiske ct précisé "pas mieux qu'un algo récursif" dc ça impliquait ke ct PAS récursif

(ué, bon, itératif...)

kikoo ca bosse dur ici ?

ben non ... on dirait que ca glandouille plutot