IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

 C++ Discussion :

Entrainement algorithme et reflexion


Sujet :

C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Inscrit en
    Janvier 2011
    Messages
    34
    Détails du profil
    Informations forums :
    Inscription : Janvier 2011
    Messages : 34
    Par défaut 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.

  2. #2
    Membre Expert Avatar de Trademark
    Profil pro
    Inscrit en
    Février 2009
    Messages
    762
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2009
    Messages : 762
    Par défaut
    Pour que l'on puisse t'aider au mieux, il nous faudrait l'énoncé (copier/coller ou lien) ainsi que ton code

  3. #3
    Membre averti
    Inscrit en
    Janvier 2011
    Messages
    34
    Détails du profil
    Informations forums :
    Inscription : Janvier 2011
    Messages : 34
    Par défaut
    En effet j'avais oublié ce détail, post mis à jour.
    merci

  4. #4
    Membre Expert Avatar de Trademark
    Profil pro
    Inscrit en
    Février 2009
    Messages
    762
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2009
    Messages : 762
    Par défaut
    À 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

  5. #5
    Membre averti
    Inscrit en
    Janvier 2011
    Messages
    34
    Détails du profil
    Informations forums :
    Inscription : Janvier 2011
    Messages : 34
    Par défaut
    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

  6. #6
    Membre Expert Avatar de Trademark
    Profil pro
    Inscrit en
    Février 2009
    Messages
    762
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2009
    Messages : 762
    Par défaut
    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.

Discussions similaires

  1. Formalisation graphique des algorithmes
    Par David R. dans le forum Algorithmes et structures de données
    Réponses: 14
    Dernier message: 08/12/2012, 10h21
  2. Algorithme de randomisation ... ( Hasard ...? )
    Par Anonymous dans le forum Assembleur
    Réponses: 8
    Dernier message: 06/09/2002, 14h25
  3. recherches des cours ou des explications sur les algorithmes
    Par Marcus2211 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 19/05/2002, 22h18
  4. Recherche de documentation complète en algorithmes
    Par Anonymous dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 29/03/2002, 12h09
  5. Algorithme génétique
    Par Stephane.P_(dis Postef) dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 15/03/2002, 17h14

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo