Discussion :

[russs]

salut à tous, e suis nouveau ici et c'est mon 1er post
bon, pour etre bref, notre prof d'algo nous a posé la question suivante:
c'est l'histoire d'un agriculteur qui a 24 000 dattes qu'il veut vendre dans le marché du village voisin, distant de 6000 mètres , il a un chameau avec les caractéristiques suivantes : il ne peut transporter que 6000 dattes à la fois et il mange 1 dattes/mètre
la question est : écrire un algo qui permet de calculer combien de dattes notre agriculteur peut vendre dans le village SACHANT QUE LA ROUTE QU'IL EMPREINTE NE COMPREND PAS DE VOLEURS (c à d si jamais on oublie ou on laisse qq chose sur la route on la retrouve meme après 100 ans) (j'ai écrit la derniere remarque en majiscule car il a insisté la dessus)
moi j'ai rien compris, déja si le chameau transporte les 6000 dattes, une fois arrivé au village, il n'aura plus quoi manger (pour retourner) il va mourir de faim
bon si qqn voit une solution qu'il me la file
et merci

[thewho]

Bonjour,

Première règle pour un programmeur (et bien d'autres, d'ailleurs) :

T H I N K !

[Vinchou]

Pour éviter que son chameau ne meure de fin, l'agriculteur doit faire des étapes dans son voyage, où il pourra déposer ses dates. Ensuite à toi de voir ce qui se passe en fonction des étapes et des dattes déposées à chaque étape...

[Jean-Marc.Bourguet]

moi j'ai rien compris, déja si le chameau transporte les 6000 dattes, une fois arrivé au village, il n'aura plus quoi manger (pour retourner) il va mourir de faim

Il faut faire des dépots en chemin. Exemple: il part avec 6000 dates, avance de 1500 m, fait un dépot de 3000 dates et revient. Il peut faire ça trois fois et au quatrième voyage il lui reste 3000x3 dates + 4500 (il n'a pas à prévoir pour le retour) soit 13500 dates et a avancé de 1500m. Il te reste à organiser les voyages et les dépots pour arriver au village avec le plus de dates possibles.

[2Eurocents]

Le chameau peut-il avancer sans manger de dattes (cas du retour) ? En d'autre termes, est-ce que le chameau ne mange des dates que quand il est chargé ?

Tu as déduit que non (il allait mourir de faim), alors que rien ne le précise dans l'énoncé.

Lever cette ambiguïté peut changer énormément la solution.

[Nemerle]

Avant l'explication, la solution:

Tu avances en 4 étapes:

858 mètres
1199 mètres
2000 mètres
1943 mètres


et là , tu es au village avec 4056 dattes

[Graffito]

Bonjour,

Tu avances en 4 étapes:
858 mètres
1199 mètres
2000 mètres
1943 mètres

Ca correspond à la solution que j'avais trouvée intuitivement, c'est à dire

• étape 1 avec 4 allers à 6000 (et 3 retours) telle que le résultat donne 18000 dates / Longueur étape =6000/(3+4) /
• étape 2 avec 3 allers à 6000 (et 2 retours) telle que le résultat donne 12000 dates / Longueur étape =6000/(2+3) /
• étape 3 avec 2 allers à 6000 (et 1 retour) telle que le résultat donne 6000 dates / Longueur étape=6000/(2+1) /
• étape 4 avec 1 aller simple / nombre de dates = 6000-Longueur restante /

Mais, je n'arrive pas à démontrer qu'il s'agit de la meilleure solution ...

[Nemerle]

Cherche les invariants du problèmes (contenus dans ton textes ) qui permettent de minimiser la consommation d'eulh chameau

[russs]

Le chameau peut-il avancer sans manger de dattes (cas du retour) ? En d'autre termes, est-ce que le chameau ne mange des dates que quand il est chargé ?

Tu as déduit que non (il allait mourir de faim), alors que rien ne le précise dans l'énoncé.

Lever cette ambiguïté peut changer énormément la solution.

c vrai j'ai pas précisé mais le chameau mange toujours (chargé ou non)
bon le prof a donné la solution aujourd'hui mais elle me semblait parachutée
Nemerle tu nous file la tienne?