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

Algorithmes et structures de données Discussion :

Les défis des golgoths


Sujet :

Algorithmes et structures de données

  1. #1
    Membre expert
    Avatar de Golgotha
    Homme Profil pro
    Full-stack Web Developer
    Inscrit en
    août 2007
    Messages
    1 381
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Full-stack Web Developer
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2007
    Messages : 1 381
    Points : 3 513
    Points
    3 513
    Billets dans le blog
    1
    Par défaut Les défis des golgoths
    Bonjour !

    Je vous propose chaque semaine, de participer à un petit défi algorithmique.

    J'ouvre donc ce thread pour vous permettre à tous le monde de proposer sa solution, et surtout de discuter sur la façon de faire de chacun, les meilleurs pratiques, etc..

    Chaque semaine aussi (je l'espère), un gagnant sera élu, et son code source sera publié sur mon blog, comme étant la meilleure résolution du défi.

    J'espère que vous serez nombreux chaque semaine à participer, ça sera l'occasion de tester vos connaissances, et de les améliorer si besoin. Les défis que je propose, sont facilement abordables par tous, pour que le plus grand nombre de personne puissent participer, je suis aussi ouvert a toute proposition de défis, n'hésitez donc pas à m'écrire !

    Bonne chance à tous !

    Défis Terminé :

    Les 100.000 boites
    Participants :
    - GhoStRideROriGinS (python)
    - fearyourself (C)
    - mabu (C/C++)
    - Sylvain Togni (C++)
    - pseudocode (java)
    - st20085 (java)
    - Waldar (SQL)


    Le courrier est trop long !
    Participants :
    - pseudocode (java) : Longueur trouvé : 89188
    - les Golgoths (VB.NET) : Longueur trouvé : 90334
    - Sylvain Togni (C++) : Longueur trouvé : 89188


    Défi en cours : Pas de triche
    Participants :
    - philben (nc)

    Prochains défi : Lundi 12 avril

    le blog : http://blog.developpez.com/cs-blog/p...oths/#more8756

    ps : Merci de faire en sorte d'avoir toujours le temps d'exécution dans votre programme.
    Consultant et développeur full-stack spécialiste du Web
    faq jQuery - règles du forum - faqs web

  2. #2
    Nouveau membre du Club
    Profil pro
    Inscrit en
    septembre 2009
    Messages
    41
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2009
    Messages : 41
    Points : 30
    Points
    30
    Par défaut
    Voici ma réponse pour le défi Les 10.000 boites:

    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
    file = open('box.txt', 'r')
    txt = file.read()
    file.close()
     
    txt = txt.split(';')
    del(txt[-1])
     
    list = {}
    for x in txt:
        dim = x.split(',')
        size = int(dim[0]) * int(dim[1]) * int(dim[2])
        list[str(size)] = x
     
    temp = []
    for x in list:
        temp.append(x)
     
    temp.sort()
     
    box = ''
    for x in temp:
        box = box + list[x] + ';'
     
    file = open('box.txt', 'w')
    file.write(box)
    file.close()
     
    raw_input('La boite la plus grande est de: ' + list[temp[-1]])

  3. #3
    Expert éminent sénior

    Avatar de fearyourself
    Homme Profil pro
    Ingénieur Informaticien Senior
    Inscrit en
    décembre 2005
    Messages
    5 121
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur Informaticien Senior
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2005
    Messages : 5 121
    Points : 11 857
    Points
    11 857
    Par défaut
    Bon je suppose que c'est un problème d'algorithmie donc la solution en C est peu intéressante mais là voici :-)

    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
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
     
    #include <stdio.h>
    #include <assert.h>
    #include <stdlib.h>
     
    #define MAX 100000
     
    //Structure de base : largeur,longueur,hauteur et dimension
    //On garde la dimension car cela accelere le tri
    typedef struct sBoites 
    {
        int largeur;
        int longueur;
        int hauteur;
        int dimension;
    }SBoite;
     
    //Lecture du fichier... Fonction basique...
    SBoite *
    lireFichier (FILE *f, int *nombre)
    {
        int cnt = 0;
        //Pour cet exercice on va tricher et allouer directement MAX,
        //normalement on ferait un système d'agrandissement du tableau...
        SBoite *res = malloc (sizeof (*res) * MAX);
        assert (res);
     
        while (1)
        {
            int largeur, longueur, hauteur;
            int r = fscanf (f, "%d,%d,%d;", &longueur, &largeur, &hauteur);
     
            if (r != 3)
                break;
     
            res[cnt].largeur = largeur;
            res[cnt].longueur = longueur;
            res[cnt].hauteur = hauteur;
     
            //Calcul de la dimension
            res[cnt].dimension = largeur * longueur * hauteur;
            cnt++;
     
            //Paranoia
            assert (cnt <= MAX);
        }
     
        *nombre = cnt;
        return res;
    }
     
    //Ce tri mettra le plus grand en position 0
    int 
    comparBoites (const void *pva, const void *pvb)
    {
        const SBoite *pba = pva;
        const SBoite *pbb = pvb;
     
        int dima = pba->dimension;
        int dimb = pbb->dimension;
     
        return dimb - dima;
    }
     
    //Tri utilisant qsort de la libc
    void
    triBoites (SBoite *boites, int nombre)
    {
        qsort (boites, nombre, sizeof (*boites), comparBoites);
    }
     
    //Affichage
    void
    afficheBoite (SBoite *b)
    {
        fprintf (stderr, "Boite plus grande %d,%d,%d\n", b->longueur,b->largeur,b->hauteur);
    }
     
    //Liberation du tableau
    void
    libereBoites (SBoite *boites)
    {
        free (boites), boites = NULL;
    }
     
    //Ecriture
    void
    ecrireFichier (FILE *f, SBoite *boites, int nombre)
    {
        int i;
        if (nombre > 0)
        {
            for (i=0; i < nombre - 1; i++)
            {
                fprintf (f, "%d,%d,%d;", boites[i].longueur, boites[i].largeur, boites[i].hauteur);
            }
            //Last one
            fprintf (f, "%d,%d,%d", boites[i].longueur, boites[i].largeur, boites[i].hauteur);
        }
    }
     
    int 
    main (void)
    {
        const char *fname = "box.txt",
                   *foutname = "box_output.txt";
        FILE *f = fopen (fname, "r");
        SBoite *boites;
        int nombre = 0;
     
        if (f == NULL)
        {
            fprintf (stderr, "Fichier %s n'a pas ete ouvert", fname);
            return EXIT_FAILURE;
        }
     
        boites = lireFichier (f, &nombre);
     
        //On trie
        triBoites (boites, nombre);
     
        //On affiche le plus grand
        afficheBoite (boites);
     
        //On ferme
        fclose (f), f = NULL;
     
        //On ouvre pour ecrire
        f = fopen (foutname, "w");
        if (f == NULL)
        {
            fprintf (stderr, "Fichier %s n'a pas ete ouvert", foutname);
            return EXIT_FAILURE;
        }
     
        //Ecrire fichier
        ecrireFichier (f, boites, nombre);
     
        //On ferme
        fclose (f), f = NULL;
     
        //On libere la memoire
        libereBoites (boites), boites = NULL;
     
        return EXIT_SUCCESS;
    }
    J'ai :
    Boite plus grande 997,979,997

    real 0m0.150s
    user 0m0.140s
    sys 0m0.008s

  4. #4
    Membre expert
    Avatar de Golgotha
    Homme Profil pro
    Full-stack Web Developer
    Inscrit en
    août 2007
    Messages
    1 381
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Full-stack Web Developer
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2007
    Messages : 1 381
    Points : 3 513
    Points
    3 513
    Billets dans le blog
    1
    Par défaut
    Merci, ça serais bien de voir quelqu'un faire un algo de trie "a la main"
    Consultant et développeur full-stack spécialiste du Web
    faq jQuery - règles du forum - faqs web

  5. #5
    Expert confirmé

    Inscrit en
    août 2006
    Messages
    3 865
    Détails du profil
    Informations forums :
    Inscription : août 2006
    Messages : 3 865
    Points : 5 469
    Points
    5 469
    Par défaut
    Goe,
    Citation Envoyé par Golgotha Voir le message
    ps : Merci de faire en sorte d'avoir toujours le temps d'exécution dans votre programme.
    Alors ce n'est pas vraiment une question d'algorithme, mais d'implémentation (même si l'algorithme compte pour la vitesse, bien entendu).
    "Mon pied droit est jaloux de mon pied gauche.
    Quand l'un avance, l'autre veut le dépasser.
    Et moi, comme un imbécile, je marche !"
    [Raymond Devos]

  6. #6
    Membre expert
    Avatar de Golgotha
    Homme Profil pro
    Full-stack Web Developer
    Inscrit en
    août 2007
    Messages
    1 381
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Full-stack Web Developer
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2007
    Messages : 1 381
    Points : 3 513
    Points
    3 513
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par droggo Voir le message
    Goe,

    Alors ce n'est pas vraiment une question d'algorithme, mais d'implémentation (même si l'algorithme compte pour la vitesse, bien entendu).
    Ce n'est qu'a titre informatif, le but est de faire voir des solutions différente et de les confronter.
    Consultant et développeur full-stack spécialiste du Web
    faq jQuery - règles du forum - faqs web

  7. #7
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    septembre 2003
    Messages
    4 930
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2003
    Messages : 4 930
    Points : 6 377
    Points
    6 377
    Par défaut
    J'ai sans doute sauté une info, mais comment définis-tu l'ordre sur les boîtes, par le volume, la somme des dimensions ?
    Y a-t-il des maxima pour les dimensions ?
    (je n'ai pas lu les solutions proposées).
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  8. #8
    Invité(e)
    Invité(e)
    Par défaut
    Bonjour

    Après le C, voici le C/C++.

    Pourquoi C/C++ plutôt que C ou C++ (sans faire de troll) :

    C : réponse déjà donnée par fearyourself (je vois mal comment faire mieux);
    C++ : trop lent avec mes compétences (STL seule).

    Le temps n'aurait pas été une contrainte, je serai resté au C++ pur.

    Donc C/C++ : les accès aux fichiers et les formatages de chaines restent en C quand les opérations sont nombreuses.

    Code c++ : 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
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    // pour perror et FILE
    #include <cstdio>
    // pour cout
    #include <iostream>
    // pour stringstream et string
    #include <sstream>
    // je vous laisse deviner
    #include <vector>
    // pour sort
    #include <algorithm>
     
    // structure qui contiendra la description d'une boite 
    struct box {
        int m_x;
        int m_y;
        int m_z;
        int m_size;
     
        box(int x, int y, int z):m_x(x), m_y(y), m_z(z) {
            m_size = m_x * m_y * m_z;
        } 
     
        // pour le tri
        bool operator <(const box & op) const {
            return m_size < op.m_size;
        } 
     
        // pour qu'une boite s'identifie (méthode lente : utilise stringstream)
        std::string tell() const {
            std::stringstream ss;
            ss << m_x << "," << m_y << "," << m_z << ";";
            return ss.str();
        }
        // pour qu'une boite s'identifie
        // (méthode rapide : utilise sprintf sur un buffer déjà pret)
        void tell(char *buf) const {
            sprintf(buf, "%d,%d,%d;", m_x, m_y, m_z);
        }
    };
     
    int main(int argc, char *argv[])
    {
        if (argc != 3) {
            std::cout << "usage: " << *argv << " in.txt out.txt" << std::endl;
        } else {
            std::vector < box > boxes;
     
            FILE *fin = NULL, *fout = NULL;
     
            do {
                // ouverture du fichier source
                fin = fopen(argv[1], "r");
                if (NULL == fin) {
                    perror(argv[1]);
                    break;
                }
     
                // ouverture du fichier destination
                fout = fopen(argv[2], "w");
                if (NULL == fout) {
                    perror(argv[2]);
                    break;
                }
     
                {
                    // lecture du fichier
                    int x, y, z;
                    while (3 == fscanf(fin, "%d,%d,%d;", &x, &y, &z)) {
                        boxes.push_back(box(x, y, z));
                    }
                }
     
                // tri de la liste
                std::sort(boxes.begin(), boxes.end());
     
                // affichage de la plus grande boite
                std::cout << "largest box is " << boxes.back().tell() << std::endl;
     
                {
                    // on prend la taille de la plus grand boite pour déterminer la taille
                    // nécessaire au stockage de la description de chaque boite.
                    // A noter : cette approche est fausse : ici la plus grande boite
                    // est 997x979x997. s'il existe une boite comme 
                    //     10000x10000x1, 
                    // on va avoir un beau dépassement mémoire.
                    size_t str_size = boxes.back().tell().length() + 1;
                    // buffer pour stocker le description des boites
                    char *buf = new char[str_size];
                    // stockage de la liste triée dans un autre fichier
                    std::vector < box >::iterator it;
                    for (it = boxes.begin(); it != boxes.end(); ++it) {
                        it->tell(buf);
                        fprintf(fout, buf);
                    //fprintf(fout, it->tell().c_str());
                    }
                    delete [] buf;
                }
     
            } while (0);
            // fermeture des fichiers
            if (NULL != fin) {
                fclose(fin);
            }
            if (NULL != fout) {
                fclose(fout);
            }
        }
        return 0;
    }

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    $ g++ -O3 -Wall -Wextra test.cc -o test && time ./test.exe box.txt sorted.txt
    largest box is 997,979,997;
     
    real    0m0.450s
    user    0m0.358s
    sys     0m0.062s
    Dernière modification par Invité(e) ; 25/03/2010 à 18h53. Motif: Description d'un bug latent

  9. #9
    Membre expert
    Avatar de Golgotha
    Homme Profil pro
    Full-stack Web Developer
    Inscrit en
    août 2007
    Messages
    1 381
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Full-stack Web Developer
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2007
    Messages : 1 381
    Points : 3 513
    Points
    3 513
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Trap D Voir le message
    J'ai sans doute sauté une info, mais comment définis-tu l'ordre sur les boîtes, par le volume, la somme des dimensions ?
    Y a-t-il des maxima pour les dimensions ?
    (je n'ai pas lu les solutions proposées).
    Oui, c'est bien le volume de la boite qui compte.
    Consultant et développeur full-stack spécialiste du Web
    faq jQuery - règles du forum - faqs web

  10. #10
    Membre éclairé

    Profil pro
    Inscrit en
    septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2006
    Messages : 717
    Points : 858
    Points
    858
    Par défaut
    Citation Envoyé par mabu
    Donc C/C++ : les accès aux fichiers et les formatages de chaines restent en C quand les opérations sont nombreuses.
    Bof, voici une version 100% C++, elle semble au contraire plus rapide !

    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
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    #include <fstream>
    #include <vector>
    #include <iterator>
    #include <algorithm>
    #include <iostream>
     
    struct Box
    {
      int x;
      int y;
      int z;
    };
     
    std::istream& operator>>(std::istream& src, Box& b)
    {
      char c1, c2, c3;
      return src >> b.x >> c1 >> b.y >> c2 >> b.z >> c3;
      if (c1 != ',' || c2 != ',' || c3 != ';')
        src.setstate(std::ios::failbit);
    }
     
    std::ostream& operator<<(std::ostream& dst, Box const& b)
    {
      return dst << b.x << ',' << b.y << ',' << b.z << ';';
    }
     
    bool operator<(Box const& b1, Box const& b2)
    {
      return b1.x*b1.y*b1.z < b2.x*b2.y*b2.z;
    }
     
    int main(int argc, char* argv[])
    {
      // Usage
      if (argc != 3)
      {
        std::cerr << "Usage: " << argv[0] << " in.txt out.txt" << '\n';
        return EXIT_FAILURE;
      }
     
      // Lecture des boites
      std::ifstream src(argv[1]);
      std::vector<Box> boxes((std::istream_iterator<Box>(src)), std::istream_iterator<Box>());
      if (!src.eof())
      {
        std::cerr << "Erreur de lecture !\n";
        return EXIT_FAILURE;
      }
     
      // Tri des boites
      std::sort(boxes.begin(), boxes.end());
     
      // Affichage de la plus grande boite
      std::cout << "La plus grande boite est " << boxes.back() << '\n';
     
      // Sauvegarde des boites triées
      std::ofstream dst(argv[2]);
      std::copy(boxes.begin(), boxes.end(), std::ostream_iterator<Box>(dst));
      if (!dst)
      {
        std::cerr << "Erreur d'écriture !\n";
        return EXIT_FAILURE;
      }
    }
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    $ g++ -O3 -Wall -Wextra test.cpp -o test && time ./test.exe box.txt sorted.txt
    La plus grande boite est 997,979,997;
     
    real    0m0.172s
    user    0m0.171s
    sys     0m0.031s

  11. #11
    Invité(e)
    Invité(e)
    Par défaut
    Citation Envoyé par Sylvain Togni Voir le message
    Bof, voici une version 100% C++, elle semble au contraire plus rapide !
    Attention, je n'ai pas accusé la STL, mais mes compétences.

  12. #12
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 062
    Points : 15 892
    Points
    15 892
    Par défaut
    Tout pareil que les autres, mais avec ce langage affreusement lent qu'est Java ()

    Code java : 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
    38
    39
    40
    41
    42
    43
    44
    45
    import java.io.FileReader;
    import java.io.FileWriter;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
     
    public class Test {
     
    	static class Box {
    		int x,y,z,volume;
    		public Box(int x, int y, int z) {
    			this.x=x; this.y=y; this.z=z;
    			this.volume=x*y*z;
    		}
    		public String toString() {
    			return this.x+","+this.y+","+this.z;
    		}
    	}
     
    	public static void main(String[] args) throws Exception {
    		ArrayList<Box> list = new ArrayList<Box>();
     
    		// read file and insert into list
    		FileReader reader = new FileReader("box.txt");
    		while(reader.ready()) {
    			int x=0,y=0,z=0,d;
    			while((d=reader.read())!=',') x=10*x+(d-'0');
    			while((d=reader.read())!=',') y=10*y+(d-'0');
    			while((d=reader.read())!=';') z=10*z+(d-'0');
    			list.add(new Box(x, y, z));
    		}
    		reader.close();
     
    		// sort the list
    		Collections.sort(list, new Comparator<Box>() {
    			public int compare(Box b1, Box b2) { return b1.volume-b2.volume; }
    		});
     
    		// write the sorted list to file
    		FileWriter writer = new FileWriter("sorted.txt");
    		for(Box box:list)
    			writer.append(box.toString()).append(';');
    		writer.close();
    	}
    }

    Durée : environ 300ms sur mon PC
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  13. #13
    Membre habitué

    Profil pro
    Inscrit en
    juin 2006
    Messages
    106
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juin 2006
    Messages : 106
    Points : 182
    Points
    182
    Par défaut
    Une version améliorée du code de Pseudocode

    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
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
     
    import java.io.*;
    import java.util.*;
     
    public class BoxTest
    {
      static class Box implements Comparable<Box>
      {
        int x, y, z, volume;
     
        public Box(int x, int y, int z)
        {
          this.x = x;
          this.y = y;
          this.z = z;
          this.volume = x * y * z;
        }
     
        public String toString() {
          return this.x+","+this.y+","+this.z;
        }
     
     
        public void writeToBuffer(StringBuffer buffer)
        {
          buffer.append(x).append(',').append(y).append(',').append(z);
        }
     
        /*
         * @see java.lang.Comparable#compareTo(java.lang.Object)
         */
        @Override
        public int compareTo(Box box)
        {
          int result = volume-box.volume;
          if (result == 0)
            result = hashCode()-box.hashCode(); // tempo
          return result;
        }
      }
     
      public static void main(String[] args) throws Exception
      {
        //long time = System.currentTimeMillis();
        TreeSet<Box> list = new TreeSet<Box>();
     
        // read file and insert into set
        Reader reader = new BufferedReader(new FileReader("d:/box.txt"));
        while(reader.ready())
        {
          int x = 0, y = 0, z = 0, d;
          while((d = reader.read()) != ',')
            x = 10 * x + (d - '0');
          while((d = reader.read()) != ',')
            y = 10 * y + (d - '0');
          while((d = reader.read()) != ';')
            z = 10 * z + (d - '0');
          list.add(new Box(x, y, z));
        }
        reader.close();
        //System.out.println("TIME=" + (System.currentTimeMillis() - time));
     
        // write the sorted list to file
        StringBuffer buffer = new StringBuffer(1200000);
        for(Box box : list)
        {
          box.writeToBuffer(buffer);
          buffer.append(';');
        }
        Writer writer = new BufferedWriter(new FileWriter("d:/sorted.txt"));
        writer.write(buffer.toString());
        writer.close();
        //System.out.println("TIME=" + (System.currentTimeMillis() - time));
        System.out.println("La plus grande boite est "+list.last());
      }
    }

  14. #14
    Modérateur
    Avatar de Waldar
    Homme Profil pro
    Consultant Teradata
    Inscrit en
    septembre 2008
    Messages
    8 240
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Consultant Teradata
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2008
    Messages : 8 240
    Points : 17 205
    Points
    17 205
    Par défaut
    En SQL (Oracle 11g utilisée ici) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    With SR AS
    (
      select x, y, z
        from box
    order by x*y*z desc
    )
    select x,y,z
      from SR
     where rownum = 1;
    Temps : environ 220 ms en lecture directe du fichier,
    150 ms si chargement préalable dans une table.

    Déclarations préalables :
    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
    -- Déclaration du répertoire
    CREATE OR REPLACE DIRECTORY BOX AS 'E:\BOX\';
     
    -- Table externe (lecture directe du fichier)
    CREATE TABLE box
    (
        x  NUMBER(3),
        y  NUMBER(3),
        z  NUMBER(3)
    )
    ORGANIZATION EXTERNAL
    (
      TYPE oracle_loader
      DEFAULT DIRECTORY BOX
        ACCESS PARAMETERS
        (
        RECORDS DELIMITED BY ';'
        BADFILE 'bad_%a_%p.bad'
        LOGFILE 'log_%a_%p.log'
        FIELDS TERMINATED BY ','
        MISSING FIELD VALUES ARE NULL
        REJECT ROWS WITH ALL NULL FIELDS
        (x, y, z)
        )
        LOCATION ('box.txt')
    )
    NOPARALLEL
    NOMONITORING;
     
    -- Table classique (import du fichier dans le SGBD)
    CREATE TABLE box2
    AS
    SELECT * FROM box;

  15. #15
    Membre expert
    Avatar de Golgotha
    Homme Profil pro
    Full-stack Web Developer
    Inscrit en
    août 2007
    Messages
    1 381
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Full-stack Web Developer
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2007
    Messages : 1 381
    Points : 3 513
    Points
    3 513
    Billets dans le blog
    1
    Par défaut
    Un grand MERCI aux participants de cette première mise en bouche, on à même du SQL ! c'est génial.

    Je pense que je vais clore cette introduction, et lancer un vrai défis dès ce soir, digne de vous mettre un peux plus à l'épreuve (enfin je l'espère).

    Merci encore à tous les participants.
    Consultant et développeur full-stack spécialiste du Web
    faq jQuery - règles du forum - faqs web

  16. #16
    Membre expert
    Avatar de Golgotha
    Homme Profil pro
    Full-stack Web Developer
    Inscrit en
    août 2007
    Messages
    1 381
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Full-stack Web Developer
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2007
    Messages : 1 381
    Points : 3 513
    Points
    3 513
    Billets dans le blog
    1
    Par défaut
    Bonsoir,

    Je vous informe que le Second défis des Golgoths, est officiellement lancé :

    http://blog.developpez.com/cs-blog/

    Défi en cours : Le courrier est trop long !

    Bonne chance à tous !
    Consultant et développeur full-stack spécialiste du Web
    faq jQuery - règles du forum - faqs web

  17. #17
    Membre régulier Avatar de Bucketpc
    Inscrit en
    août 2008
    Messages
    98
    Détails du profil
    Informations personnelles :
    Âge : 34

    Informations forums :
    Inscription : août 2008
    Messages : 98
    Points : 118
    Points
    118
    Par défaut heuristiques
    Bonjour,

    Il y a 30 points de passage, alors il y a 29! (FACT(29)) de solutions possibles. C'est un problème NP-complet, ce qui n'est pas possible a tester avec un pc (peut être l'exécution va prendre 20ans ). Ce problème est similaire au problème du voyageur de commerce.

    Pour le résoudre, il est nécessaire d'utiliser une méthode d'optimisation heuristique (non-exacte), telle que les algorithmes génétique, la recherche dispersée, etc.
    Les méthodes heuristiques donnent des solutions optimales dans un temps admissible. Mais rien ne garantit qu'il n'existe pas de meilleurs solutions qu'elles.

    Pour l'exécution j'ai pas le courage pour saisir les 30 points, ainsi de calculer la distance entre chaque paire , et attendre le résultat. Sauf que je vois qu'il ne coutera rien d'expliquer comment ça se passe.

    1. au début, il faut définir une population initiale de solutions (fixées aléatoirement, où en utilisant des heuristiques).
    2. évaluer chaque solution présente dans la population, en s'appuyant sur des critères biens définis (ici la distance du parcours).
    3. En s'appuyant sur l'évaluation, Sélectionner des solutions qui vont êtres combinées pour la création des nouvelles solutions. Ceci, en utilisant des méthodes de reproduction (croisement, mutation).
    4. insérer les nouveaux individus (généralement ceux ayant une qualité meilleurs) dans une nouvelle population. Bien sûr, suivant des règles.
    5. répéter les étapes 2, 3, 4, 5 jusqu'à la convergence vers une solution satisfaisante.

    A+

  18. #18
    Membre expert
    Avatar de Golgotha
    Homme Profil pro
    Full-stack Web Developer
    Inscrit en
    août 2007
    Messages
    1 381
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Full-stack Web Developer
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : août 2007
    Messages : 1 381
    Points : 3 513
    Points
    3 513
    Billets dans le blog
    1
    Par défaut
    Merci Bucketpc,

    C'est effectivement un problème np-complet, impossible à résoudre en parcourant l'arbre des possibilités, il faut donc mettre au point un algorithme un peux plus subtile, comme vous le dite, les algorithmes génétique est une des voie qui peux donner une solution.

    Je proposerais moi même un solution, dans quelques jours.
    Consultant et développeur full-stack spécialiste du Web
    faq jQuery - règles du forum - faqs web

  19. #19
    Membre régulier Avatar de Bucketpc
    Inscrit en
    août 2008
    Messages
    98
    Détails du profil
    Informations personnelles :
    Âge : 34

    Informations forums :
    Inscription : août 2008
    Messages : 98
    Points : 118
    Points
    118
    Par défaut
    Je rajoute, les coordonnés des villes sont en fonction de X, Y, et Z (repère 3D). Donc, le calcul de la distance entre deux villes se fait en utilisant une formule comme celle d'Euclide.
    Distance (P1, P2) = racine( [(X1-Y1)^2] + [(X2-Y2)^2] + [(X3-Y3)^2]) // (X-Y)^au carrée

  20. #20
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 062
    Points : 15 892
    Points
    15 892
    Par défaut
    Citation Envoyé par Bucketpc Voir le message
    Pour le résoudre, il est nécessaire d'utiliser une méthode d'optimisation heuristique (non-exacte), telle que les algorithmes génétique, la recherche dispersée, etc.
    j'ai codé un petit algo génétique a la va vite. Ca converge vers une solution en moins d'une minute. Je trouve un circuit fermé de longueur 89188. Mais je ne sais pas si c'est l'optimum.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. LES TECHNIQUES DES SGBDR / MySQL rapide ???
    Par SQLpro dans le forum Langage SQL
    Réponses: 1
    Dernier message: 12/09/2003, 12h16
  2. specifier les chemins des .class
    Par draken dans le forum Eclipse Java
    Réponses: 2
    Dernier message: 29/07/2003, 10h35
  3. Récuperer les icons des JDialog
    Par Pro_Fete dans le forum Agents de placement/Fenêtres
    Réponses: 2
    Dernier message: 17/04/2003, 14h00
  4. Réponses: 2
    Dernier message: 22/07/2002, 19h02

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