Discussion :

[YoshioToutou]

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.

[Trademark]

Pour que l'on puisse t'aider au mieux, il nous faudrait l'énoncé (copier/coller ou lien) ainsi que ton code

[YoshioToutou]

En effet j'avais oublié ce détail, post mis à jour.
merci

[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

[YoshioToutou]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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.