Entrainement algorithme et reflexion

Version imprimable

11/02/2012, 23h20
YoshioToutou

Entrainement algorithme et reflexion

Bonjour, je m'entraine en c++ en faisant des exercices que je trouve sur des archives de concours d'informatique,pour la plupart, ils demandent d'écrire des algo sur des énoncés plus ou moins étrange. Jusque là je n'ai pas eu trop de problème sur des exercices basiques tels que le chiffre de cesar ou d'autres exercices dans le genre, mais là je bloque depuis 3 jours, sans savoir si je vais dans la bonne voie ou pas, ce qui est assez frustrant, je dois l'avouer.
Dans l'exercice, il est demander de trouver le nombre de voyage minimal pour X personnes en respectant certaines conditions.
pour le moment mon code ce compose d'une boucle while, qui s'arrete lorsque toutes les personnes ont finies leur voyages à l'intérieur de laquelle se trouve une très grandr quantité de if, else if, else ce que je trouve particulièrement moche, et peut adapter (pas) à certaines situations données.

jJe ne souhaite evidement pas la réponse au problème posé mais des pistes pour continuer de rechercher des informations sur la facon de traiter ce sujet.

merci beaucoup.
en effet avec le lien c'est mieux, http://cil.cte.lu/chronologie_cil/ar...cil/2001/2.pdf exerice numero 2. Pour mon code je le poste demain, je ne l'ai pas sur en ce moment.
11/02/2012, 23h22
Trademark

Pour que l'on puisse t'aider au mieux, il nous faudrait l'énoncé (copier/coller ou lien) ainsi que ton code ;)
11/02/2012, 23h26
YoshioToutou

En effet j'avais oublié ce détail, post mis à jour.
merci
12/02/2012, 10h54
Trademark

À la lecture de l'énoncé, je dirais qu'un algorithme glouton est suffisant pour résoudre le problème. Un algorithme glouton est un algo qui choisit localement la meilleure solution.

Difficile d'en dire plus sans donner la réponse, en tout cas une boucle while convient parfaitement au algorithme glouton. Si j'étais toi je m'inspirerais assez bien de l'exemple 2...
Et ensuite il faut essayer de trouver l'algo qui choisit la meilleure solution lorsqu'ils ne sont plus que un petit nombre sur l'île (3 ou 4).

Pour tes if-else, ... Tu peux essayer de faire des fonctions pour factoriser ton code si il y a des bouts de code redondants.

Si tu veux t'entrainer à des problèmes algorithmiques, tu peux aller sur : http://algo.developpez.com

Voici un code qui fonctionne dans la plupart des cas que j'ai essayé, mais pourriez vous me dire si vous le trouvez correct.

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
 
#include <iostream>
#include <fstream>
 
using namespace std;
 
int main(int argc, char*argv[]){
        ifstream input("cannibales.in", ios::in);
        int tCan, tNCan, resultat(0);
        input >> tCan;
        input >> tNCan;
        while(tCan+tNCan){
                resultat++;
                if(tCan>=3){ // On enlève le maximum de canibales possibles
                        tCan-=2; // Deux sont sur le rivage de l'autre coté, un sur le bateau
                }else if(tCan == 1 && tNCan >= 3){ // Voyage à deux non canibales et 1 canibale
                        tNCan-=1; // Un arrive à destination, l'autre est sur le bateau
                        tCan =0; // On déponse le dernier canibale de l'autre coté
                }else if(tCan == 0 && tNCan == 2){ // Voyage à 2 non canibales, c'est le dernier voyage
                        tNCan = 0; // Celui qui est sur le bateau va chercher le dernier.
                }else if(tCan == 0 && tNCan > 3){ // On evacue le reste des non-canibales
                        tNCan-=2;
                }else if(tCan == 0 && tNCan ==3){ // Si il ne reste plus que 3 personnes, on fait un dernier aller
                        tNCan =0;
                }else if(tCan == 2 && tNCan == 1){ // Si il reste deux canibales et un non canibales, on doit le faire en deux étapes
                        tCan-=1;
                }else if(tCan == 1 && tNCan <=2 ){ // Si il reste 1 de chaque, dernier aller
                        tCan=0;
                        tNCan=0;
                }else if(tCan == 2 && tNCan >=3){ // Si il ne reste que 2 canibales, on les fait voyager
                        tCan = 0;
                }
        }
 
        cout << (resultat*2)-1 << endl; // On multiplie par deux car trajet = aller + retour et on enlève le dernier retour car il n'y en a pas
        return 0;
}

merci

12/02/2012, 17h50
Trademark

C'est pas très beau, par contre j'ai bien l'impression qu'il y a une solution qui ne nécessite même pas de boucle while (potentiellement un simple return (expression) ) ;) Réfléchis bien aux étapes nécessaires et n'essayent pas de tout faire en même temps.

PS : isole bien les cas où il reste n, 2, 1 et 0 cannibales et t'apparaitra peut-être une bien meilleure solution.
12/02/2012, 20h30
YoshioToutou

Si tu parles du cas ou il y a N d'une sorte et 0 de l'autre, alors oui, le retour est N-1, mais ca ne résous qu'une infime partie du problème (si c'est de ça dont tu parles).
Je continue de chercher.
12/02/2012, 20h31
Trademark

Non ce n'est pas ça.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
int getVoyages(int c, int nc)
{
   // Car où il faudra d'abord évacuer tous les C puis le dernier C reviendra pour chercher le seul NC.
   if (nc == 1 && c > 1) return 1 + getVoyages(c, 0);
 
   // Si nc == 0, cas simple.
   // Si nc == 2, ils font le premier voyage ensemble, un C revient.
   // Sinon, les cannibales partent ensemble tant que c > 2. Après ça, on a c <= 2 et nc >=3, on peut faire des groupes (1C + 2NC). Puis des groupes NC exclusivement.
   // De cette façon tous les radeaux partent avec trois personnes, et un seul revenant, sauf peut-être le dernier.
   // (c + nc) in {1,2,3} -> 1 ; (c + nc) in {4,5} -> 2 ; ...
   if (c + nc <= 1) return c + nc;
   return (c + nc) / 2;    
}

Plus simple qu'il n'y paraissait n'est-ce pas ? ;)
EDIT : Mauvaise lecture d'énoncé, correction du cas nc==1 après relecture.

14/02/2012, 22h03
YoshioToutou

Ok, je vais me penche sur le début de code que tu m'a passé, merci beaucoup, je vous tiens au courant.