[Concours de programmation] Première épreuve.
3 participants
Page 1 sur 1
[Concours de programmation] Première épreuve.
Le problème:
Le but du problème est de calculer tous les nombres premiers compris strictement entre deux bornes.
Rappel: un nombre premier est un nombre qui est divisible par exactement deux naturels distincts (1 et lui-même).
Rappel: les premiers nombres premiers sont 2,3,5,7,11,13,17,19,23,29,31,...
Attention: 1 n'est pas un nombre premier !
Exemple: si les bornes sont 5 et 20, le programme doit retourner 7,11,13,17,19.
Entrée (input):
Un fichier texte contenant deux nombres naturels dans l'ordre croissant, séparés par un espace. Il n'y a pas de limite de taille sur ces nombres.
Exemple 1: 0 100
Exemple 2: 2000 30000
Exemple 3: 987654321012345678901234567890 987654321012345678902345678900
Sortie (output):
Un fichier texte contenant le nombre de nombres premiers trouvés suivit de la liste de ces nombres.
Exemple: Pour un fichier d'entrée "5 32" il faut un fichier de sortie "8 7 11 13 17 19 23 29 31"
Objectif:
Rapidité d'exécution !
Langages autorisés:
C/C++
Java
Python
Pascal
Dead Line:
Le code source du programme doit être remis à Julien ou moi-même pour le 20 avril au plus tard.
Le but du problème est de calculer tous les nombres premiers compris strictement entre deux bornes.
Rappel: un nombre premier est un nombre qui est divisible par exactement deux naturels distincts (1 et lui-même).
Rappel: les premiers nombres premiers sont 2,3,5,7,11,13,17,19,23,29,31,...
Attention: 1 n'est pas un nombre premier !
Exemple: si les bornes sont 5 et 20, le programme doit retourner 7,11,13,17,19.
Entrée (input):
Un fichier texte contenant deux nombres naturels dans l'ordre croissant, séparés par un espace. Il n'y a pas de limite de taille sur ces nombres.
Exemple 1: 0 100
Exemple 2: 2000 30000
Exemple 3: 987654321012345678901234567890 987654321012345678902345678900
Sortie (output):
Un fichier texte contenant le nombre de nombres premiers trouvés suivit de la liste de ces nombres.
Exemple: Pour un fichier d'entrée "5 32" il faut un fichier de sortie "8 7 11 13 17 19 23 29 31"
Objectif:
Rapidité d'exécution !
Langages autorisés:
C/C++
Java
Python
Pascal
Dead Line:
Le code source du programme doit être remis à Julien ou moi-même pour le 20 avril au plus tard.
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8280
Date d'inscription : 16/01/2006
Re: [Concours de programmation] Première épreuve.
On a le droit de combiner les langages ? (Je n'ai pas d'exemple mais pourquoi pas...) Et pourquoi restreindre les langages ?
Sinon, pas de recommandations sur la mesure du temps d'exécution ?
J'espère que j'aurais le temps de m'y mettre parce que ça peut être intéressant mais j'ai tellement de projets en cours qu'il faudrait que j'en finisse un peu avant de commencer d'autres choses...
Sinon, pas de recommandations sur la mesure du temps d'exécution ?
J'espère que j'aurais le temps de m'y mettre parce que ça peut être intéressant mais j'ai tellement de projets en cours qu'il faudrait que j'en finisse un peu avant de commencer d'autres choses...
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22514
Date d'inscription : 10/03/2005
Re: [Concours de programmation] Première épreuve.
Julien a écrit:Et pourquoi restreindre les langages ?
Peut être parce que les language comme mathématica sont trop specialisé en matiére
et aussi peut être parce que ce concours et un deal entre ces languages(les plus célébre)
porteuris- Membre
- Nombre de messages : 224
Age : 31
Localisation : BETHUNE
Profession / Etudes : Lycéen 1°S -si
Points : 6386
Date d'inscription : 19/03/2009
Re: [Concours de programmation] Première épreuve.
Et aussi parce que pour tester un code matlab ou mathématica, la rapidité dépendra de la version. Et les version récentes ne sont pas gratuites !
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8280
Date d'inscription : 16/01/2006
Re: [Concours de programmation] Première épreuve.
Pour ce qui est de la gestion du temps, je propose le schéma suivant:
Début du timer
Chargement des données
Calculs
Ecriture des résultats.
Fin du timer
Les input-output étant des opérations lentes dépendant principalement de la configuration de la machine, je pense qu'il ne sont pas importants.
Début du timer
Chargement des données
Calculs
Ecriture des résultats.
Fin du timer
Les input-output étant des opérations lentes dépendant principalement de la configuration de la machine, je pense qu'il ne sont pas importants.
Dernière édition par Duche le Jeu 26 Mar 2009 - 13:14, édité 1 fois
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8280
Date d'inscription : 16/01/2006
Re: [Concours de programmation] Première épreuve.
OK, donc tu veux calculer que le temps de calcul. Ca marche.
Sinon, j'ai fait une première version en C avec la méthode du crible d'Erathostène. Inutile de dire que c'est la méthode la moins performante ! ^^
Pour trouver les nombres premiers entre n'importe quelle borne inférieure à 40 000 et 40 000, ça prend déjà plus de 6 secondes chez moi...
49 secondes pour les nombres premiers inférieurs à 100 000. :p
Tout ça pour dire que si tu veux porteuris, tu peux déjà faire cette méthode. Elle est simple à mettre en oeuvre.
Après, faut chercher les algorithmes pour améliorer.
Sinon, j'ai fait une première version en C avec la méthode du crible d'Erathostène. Inutile de dire que c'est la méthode la moins performante ! ^^
Pour trouver les nombres premiers entre n'importe quelle borne inférieure à 40 000 et 40 000, ça prend déjà plus de 6 secondes chez moi...
49 secondes pour les nombres premiers inférieurs à 100 000. :p
Tout ça pour dire que si tu veux porteuris, tu peux déjà faire cette méthode. Elle est simple à mettre en oeuvre.
Après, faut chercher les algorithmes pour améliorer.
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22514
Date d'inscription : 10/03/2005
Re: [Concours de programmation] Première épreuve.
Juste une précision : en rajoutant la bonne ligne qu'il faut, je passe de 49 secondes à moins d'une demi-seconde...Julien a écrit:
49 secondes pour les nombres premiers inférieurs à 100 000. :p
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22514
Date d'inscription : 10/03/2005
Re: [Concours de programmation] Première épreuve.
En fait, ca peut restreindre les possibilités... Donc c'est pas génial.
Début du timer avant la lecture du fichier, fin du timer après l'écriture du fichier.
Début du timer avant la lecture du fichier, fin du timer après l'écriture du fichier.
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8280
Date d'inscription : 16/01/2006
Re: [Concours de programmation] Première épreuve.
Bon ben alors dans ce cas je ferai avec la commande time. Ca m'arrange !
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22514
Date d'inscription : 10/03/2005
Re: [Concours de programmation] Première épreuve.
Petite adaptation en fonction des problèmes que l'on peut rencontrer.
- Les valeurs du fichier final peuvent être séparées par plus d'un espace si nécessaire (sinon ça risque d'exploser la ram sur les petites config (et même sur les grosses)).
- Je pense que pour ne pas pénaliser les config lentes, il serait pas mal de faire le calcul de la durée de l'algo en supprimant l'écriture dans le fichier. Cette écriture n'est là que pour vérifier qu'il n'y a pas de triche/erreurs de toutes façons. (en la mettant en commentaire pour le test de temps). D'autant plus que ça change beaucoup de chose, ce qui rend difficilement visibles les petites optimisations de l'algo en lui-même. (j'ai un différence d'un facteur 10 chez moi).
- Les valeurs du fichier final peuvent être séparées par plus d'un espace si nécessaire (sinon ça risque d'exploser la ram sur les petites config (et même sur les grosses)).
- Je pense que pour ne pas pénaliser les config lentes, il serait pas mal de faire le calcul de la durée de l'algo en supprimant l'écriture dans le fichier. Cette écriture n'est là que pour vérifier qu'il n'y a pas de triche/erreurs de toutes façons. (en la mettant en commentaire pour le test de temps). D'autant plus que ça change beaucoup de chose, ce qui rend difficilement visibles les petites optimisations de l'algo en lui-même. (j'ai un différence d'un facteur 10 chez moi).
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8280
Date d'inscription : 16/01/2006
Re: [Concours de programmation] Première épreuve.
C'est quoi l'avantage de mettre plusieurs espaces ?Duche a écrit:- Les valeurs du fichier final peuvent être séparées par plus d'un espace si nécessaire (sinon ça risque d'exploser la ram sur les petites config (et même sur les grosses)).
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22514
Date d'inscription : 10/03/2005
Re: [Concours de programmation] Première épreuve.
De ne pas devoir tout stocker en mémoire ram.
Puisque la première valeur du fichier doit être le nombre de nombres premiers trouvés.
Il suffit de laisser un peu de place (pas trop, pas trop peu, à vous de choisir les critères) et puis l'écrire après.
Puisque la première valeur du fichier doit être le nombre de nombres premiers trouvés.
Il suffit de laisser un peu de place (pas trop, pas trop peu, à vous de choisir les critères) et puis l'écrire après.
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8280
Date d'inscription : 16/01/2006
Re: [Concours de programmation] Première épreuve.
Ok... je n'ai pas eu de problème encore. C'est en affichant combien de nombres que ça te demande trop de ressources ? Et t'as combien de RAM ?
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22514
Date d'inscription : 10/03/2005
Re: [Concours de programmation] Première épreuve.
J'ai 1Go de RAM.
En fait comme il faut fournir le nombre de valeurs trouvées avant ces valeurs, il faut stocker les valeurs trouvées en RAM ou faire un transfert de fichier (lourd).
En fait comme il faut fournir le nombre de valeurs trouvées avant ces valeurs, il faut stocker les valeurs trouvées en RAM ou faire un transfert de fichier (lourd).
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8280
Date d'inscription : 16/01/2006
Re: [Concours de programmation] Première épreuve.
Pour le moment, j'ai mis au point un algo qui gère bien les nombres jusqu'à 100 chiffres (en base 10). Bien évidemment, le calcul sur des nombres aussi grands est infaisable pour des petits ordinateurs comme les notres...
Voila pour le moment les chiffres que j'ai (l'ordi tournait avec beaucoup d'applications, mais je ne pense pas que le laisser avec seulement le programme pourrait changer beaucoup de choses...)
1 10000 -> Duree de la recherche : 0.113260 sec.
1 40000 -> Duree de la recherche : 0.754984 sec.
1 100000 -> Duree de la recherche : 2.551853 sec.
1 200000 -> Duree de la recherche : 6.689810 sec.
1 300000 -> Duree de la recherche : 11.660389 sec.
1 400000 -> Duree de la recherche : 17.435228 sec.
1 500000 -> Duree de la recherche : 24.039731 sec.
1 1000000 -> Duree de la recherche : 63.384426 sec.
1 10000000 -> Duree de la recherche : 1787.598792 sec.
1000000000000000 1000000000010000 -> Duree de la recherche : 17993.159675 sec.
Etant donné que certains types (du moins en C++) peuvent gérer les nombres jusqu'à 2^64, je me demande s'il ne serait pas judicieux d'abandonner l'idée de la taille illimitée.
Cela dit, il est intéressant de développer les opérations de bases pour des grands nombres, mais ça reste assez indépendant...
Je propose de tester également l'algo avec des types allant jusque 2^64. (2^32 est quand meme un peu faible)
Edit:
J'ai implémenté le même algo pour la recherche des nombres premiers, mais avec le type entier de 64 bits.
La différence est éloquente
1 10000 -> Duree de la recherche : 0.002130 sec.
1 40000 -> Duree de la recherche : 0.011390 sec.
1 100000 -> Duree de la recherche : 0.022692 sec.
1 200000 -> Duree de la recherche : 0.064430 sec.
1 300000 -> Duree de la recherche : 0.099417 sec.
1 400000 -> Duree de la recherche : 0.132191 sec.
1 500000 -> Duree de la recherche : 0.170892 sec.
1 1000000 -> Duree de la recherche : 0.426916 sec.
1 10000000 -> Duree de la recherche : 9.467974 sec.
1000000000000000 1000000000010000 -> Duree de la recherche : 53.533033 sec.
Edit edit: Je me suis amusé avec quelques nombres encore plus grands, mais je ne peux pas aller plus haut avec ce type:
10000000000000000 10000000000000100 -> Duree de la recherche : 2.507479 sec.
100000000000000000 100000000000000100 -> Duree de la recherche : 12.448282 sec.
1000000000000000000 1000000000000000100 -> Duree de la recherche : 22.885113 sec.
10000000000000000000 10000000000000000100 -> Duree de la recherche : 114.811577 sec.
Voila pour le moment les chiffres que j'ai (l'ordi tournait avec beaucoup d'applications, mais je ne pense pas que le laisser avec seulement le programme pourrait changer beaucoup de choses...)
1 10000 -> Duree de la recherche : 0.113260 sec.
1 40000 -> Duree de la recherche : 0.754984 sec.
1 100000 -> Duree de la recherche : 2.551853 sec.
1 200000 -> Duree de la recherche : 6.689810 sec.
1 300000 -> Duree de la recherche : 11.660389 sec.
1 400000 -> Duree de la recherche : 17.435228 sec.
1 500000 -> Duree de la recherche : 24.039731 sec.
1 1000000 -> Duree de la recherche : 63.384426 sec.
1 10000000 -> Duree de la recherche : 1787.598792 sec.
1000000000000000 1000000000010000 -> Duree de la recherche : 17993.159675 sec.
Etant donné que certains types (du moins en C++) peuvent gérer les nombres jusqu'à 2^64, je me demande s'il ne serait pas judicieux d'abandonner l'idée de la taille illimitée.
Cela dit, il est intéressant de développer les opérations de bases pour des grands nombres, mais ça reste assez indépendant...
Je propose de tester également l'algo avec des types allant jusque 2^64. (2^32 est quand meme un peu faible)
Edit:
J'ai implémenté le même algo pour la recherche des nombres premiers, mais avec le type entier de 64 bits.
La différence est éloquente
1 10000 -> Duree de la recherche : 0.002130 sec.
1 40000 -> Duree de la recherche : 0.011390 sec.
1 100000 -> Duree de la recherche : 0.022692 sec.
1 200000 -> Duree de la recherche : 0.064430 sec.
1 300000 -> Duree de la recherche : 0.099417 sec.
1 400000 -> Duree de la recherche : 0.132191 sec.
1 500000 -> Duree de la recherche : 0.170892 sec.
1 1000000 -> Duree de la recherche : 0.426916 sec.
1 10000000 -> Duree de la recherche : 9.467974 sec.
1000000000000000 1000000000010000 -> Duree de la recherche : 53.533033 sec.
Edit edit: Je me suis amusé avec quelques nombres encore plus grands, mais je ne peux pas aller plus haut avec ce type:
10000000000000000 10000000000000100 -> Duree de la recherche : 2.507479 sec.
100000000000000000 100000000000000100 -> Duree de la recherche : 12.448282 sec.
1000000000000000000 1000000000000000100 -> Duree de la recherche : 22.885113 sec.
10000000000000000000 10000000000000000100 -> Duree de la recherche : 114.811577 sec.
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8280
Date d'inscription : 16/01/2006
Re: [Concours de programmation] Première épreuve.
Juste une question : quand tu mets une borne inférieure égale à 1000000 par exemple, c'est juste que t'affiches les résultats juste à partir de ce nombre et que ton algo fait tout le travail pour les nombres inférieurs ou pas ?
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22514
Date d'inscription : 10/03/2005
Re: [Concours de programmation] Première épreuve.
Non non, l'algo commence à la borne inférieure.
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8280
Date d'inscription : 16/01/2006
Re: [Concours de programmation] Première épreuve.
OK, j'ai plus qu'à trouver comment faire alors. ^^
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22514
Date d'inscription : 10/03/2005
Re: [Concours de programmation] Première épreuve.
Tu utilisais les nombres premiers précédemment trouvés pour tester la primalité ?
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8280
Date d'inscription : 16/01/2006
Re: [Concours de programmation] Première épreuve.
Oui, je fais avec la méthode du crible d'Eratosthène pour le moment.
Julien- Administrateur
- Nombre de messages : 12291
Age : 37
Localisation : Clermont-Ferrand
Profession / Etudes : Ingénieur
Points : 22514
Date d'inscription : 10/03/2005
Re: [Concours de programmation] Première épreuve.
Ok, moi je fais avec un test de primalité.
Duche- Modérateur
- Nombre de messages : 2210
Age : 39
Localisation : Louvain-la-Neuve (Belgique)
Profession / Etudes : Développeur en optimisation
Points : 8280
Date d'inscription : 16/01/2006
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
|
|
Jeu 2 Juil 2015 - 15:16 par louaraychi
» Devoir maison sur équilibre et réaction chimique
Dim 1 Fév 2015 - 17:19 par sararose
» Ma présentation
Sam 25 Oct 2014 - 23:29 par Rith
» projet scientique sur la LUMIERE
Ven 26 Sep 2014 - 20:33 par benjamin-010
» La trajectoire de la Terre
Mar 5 Aoû 2014 - 22:19 par Alban
» Equilibrer une réaction redox
Dim 8 Juin 2014 - 21:18 par Courtney ♥
» les effets sur les lignes de transport de l’électricité
Ven 30 Mai 2014 - 17:14 par leila14
» lignes de transport de l'électricité
Ven 30 Mai 2014 - 17:07 par leila14
» Gravitation
Ven 16 Mai 2014 - 20:16 par fatimaa
» Maquette suspension de moto 2D
Jeu 17 Avr 2014 - 17:20 par Sti2d