Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Aide | Shop Recherche
1388 connectés 

  FORUM HardWare.fr
  Programmation
  Java

  Concours de programmation

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Concours de programmation

n°2343462
Nat1329
Posté le 20-12-2019 à 14:16:37  profilanswer
 

Bonjour,

 

j'ai résolu un exercice sur un site de programmation et concours dont l'énoncé est la suivant.

 

Énoncé:

 

On vous donne une liste de nombres tous différents. Ces nombres vous sont donnés du plus petit au plus grand.

 

Écrivez un programme qui trouve et affiche deux nombres distincts parmi cette liste, dont la somme vaut 42 000 000. On vous garantit que ces deux nombres existent

 

Dans cet exercice, votre programme doit être rapide pour valider tous les tests. En particulier, si vous énumérez toutes les possibilités de deux nombres, vous ne pourrez obtenir que la moitié des points disponibles pour ce sujet.

 

Entrée
La première ligne de l'entrée contient un entier nbNombres, le nombre d'éléments de la liste, entre 1 et 20 000.

 

Les nbNombres lignes suivantes contiennent chacune un élément de la liste, un nombre entier entre 0 et 42 000 000. Les nombres sont donnés du plus petit au plus grand.

 

Sortie
Vous devez afficher deux nombres différents, chacun sur une ligne : les deux éléments de la liste à additionner pour obtenir 42 000 000, en commençant par le plus petit.

 

Exemples
Voici un exemple d'entrée.

 

6
271
4321
8754
999999
41995679
41998154

 

La sortie attendue est la suivante.

 

4321
41995679

 


Voici mon programme qui fonctionne parfaitement et passe 8 tests sur 10 (car en fait il est lent!) l'objectif est de résoudre l'exercice avec un algo optimisé et rapide à l'exécution sans tester toutes les combinaisons possible ce que mon programme fait hélas.

 
Code :
  1. class Main { 
  2.    static Scanner input = new Scanner(System.in);
  3.    public static void main(String[] args) {
  4.     int nbNombres = input.nextInt();
  5.     int[] liste = new int[100];
  6.     int somme = 0;
  7.     boolean trouve = false;
  8.     int valPetit = 0;
  9.     int valGrand = 0;
  10.     int cPair = 0;
  11.     int cImpair = 0;
  12.     for(int i = 0; i < nbNombres; i++){
  13.       liste[i] = input.nextInt();
  14.     }
  15.     for(int i = 0; i < nbNombres; i++){
  16.       for(int j = i + 1; j < nbNombres; j++){
  17.         if((liste[i] % 2 != 0 && liste[j] % 2 != 0) || (liste[i] % 2 == 0 && liste[j] % 2 == 0) ){
  18.            somme = liste[i] + liste[j];
  19.            if(somme != 42000000){
  20.               somme = 0;
  21.            }else{
  22.               valPetit = liste[i];
  23.               valGrand = liste[j];
  24.               trouve = true;
  25.               break;
  26.               }
  27.            }
  28.         }
  29.      }
  30.     if(trouve){
  31.       System.out.println(valPetit);
  32.       System.out.println(valGrand);
  33.     }
  34.    }
  35.    
  36.    }
 

Une idée pour rendre mon programme plus rapide?

 


Message édité par Nat1329 le 20-12-2019 à 14:18:04
mood
Publicité
Posté le 20-12-2019 à 14:16:37  profilanswer
 

n°2343469
mechkurt
Posté le 20-12-2019 à 14:55:47  profilanswer
 

Je ne suis pas un spécialiste en algorithmie, loin s'en faut, mais déjà si tu supprimes le j déjà effectué à la fin de la boucle i, tu affines ta recherche au fur et a mesure.
 
Je sais pas si je suis clair mais quand tu a fait (avec les chiffres de ton exemple) toutes les tentatives avec 271, il faut le supprimer des choix possible dans ta 2eme boucle for (si 271 et 4321 ne vont pas ensemble, 4321 et 271 n'iront pas mieux).
 
Après c'est de la logique de base, y'a surement des manières de procédé (je le dit au hasard, encore une fois c'est pas mon domaine), ou en alternant +petit et +grand chiffre, ou en partant du milieu vers les extrémités, ce genre de chose, je penses que le fait qu'on connaisse la somme et un indice sur l'algo à utiliser...
 
https://www.google.com/search?q=alg [...] +une+somme
 
Bon courage à toi !


Message édité par mechkurt le 20-12-2019 à 14:56:25

---------------
D3
n°2343471
mechkurt
Posté le 20-12-2019 à 14:59:55  profilanswer
 

Oh mon dieu, que je suis bête, pourquoi faire une seule liste, faits en 2 ce sera dejà 2 fois plus efficace !
 
...besoin de vacances moi. ^^


---------------
D3
n°2343476
rufo
Pas me confondre avec Lycos!
Posté le 20-12-2019 à 16:12:55  profilanswer
 

Tu peux tenter un algorithme LPT ;) Vu que c'est une somme que de 2 nombres, c'est très facile à optimiser. Tu prend le premier plus grand nb, on va l'appeler GNB1. Tu fais 42000000 - GNB1 = Reste1
Tu cherches dans la liste si un nb correspond exactement à Reste1. Si c'est pas le cas, tu prends le 2ème plus grand nombre GNB2 et tu recommence : 42000000 - GNB2 = Reste2
...


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Cantine Calandreta : http://sourceforge.net/projects/canteen-calandreta
n°2343490
gilou
Modérateur
Modzilla
Posté le 21-12-2019 à 01:53:35  profilanswer
 

Perso, en supposant les données passées au programme en argument (l'énoncé n'est pas clair, mais c'est facile a adapter avec un scanner si donné dans un fichier ou tapé interactivement) j'aurais fait ainsi :

Code :
  1. public class Main {
  2.  
  3.    public static void main(String[] args) {
  4.        int entriesNb = Integer.parseInt(args[0]);
  5.        int[] entries = new int[entriesNb + 1];
  6.        for (int i = 1; i <= entriesNb; ++i) {
  7.            entries[i] = Integer.parseInt(args[i]);
  8.        }
  9.  
  10.        int i = 1;
  11.        int j = entriesNb;
  12.        int goal = 42000000;
  13.        while (entries[i] + entries[j] != goal) {
  14.            if (entries[i] + entries[j] > goal) {
  15.                while (entries[i] + entries[--j] > goal);     // Tant qu'on dépasse, il faut diminuer le plus grand nombre
  16.            } else if (entries[i] + entries[j] < goal) {
  17.                while (entries[++i] + entries[j] < goal);     // Tant qu'on manque, il faut augmenter le plus petit nombre
  18.            }
  19.        }
  20.        System.out.println(entries[i]);
  21.        System.out.println(entries[j]);
  22.    }
  23. }


 
Après, si on veut un code robuste qui supporte des données sans solution (on est en dehors de l'énoncé, et plus près de la vraie vie) on peut faire :

Code :
  1. public class Main {
  2.  
  3.    public static void main(String[] args) {
  4.        int entriesNb = Integer.parseInt(args[0]);
  5.        int[] entries = new int[entriesNb + 1];
  6.        for (int i = 1; i <= entriesNb; ++i) {
  7.            entries[i] = Integer.parseInt(args[i]);
  8.        }
  9.  
  10.        int i = 1;
  11.        int j = entriesNb;
  12.        int goal = 42000000;
  13.        while ((entries[i] + entries[j] != goal) && (i < j)) {
  14.            if (entries[i] + entries[j] > goal) {
  15.                // Tant qu'on dépasse, il faut diminuer le plus grand nombre
  16.                while ((entries[i] + entries[--j] > goal) && (i < j));
  17.            } else if (entries[i] + entries[j] < goal) {
  18.                // Tant qu'on manque, il faut augmenter le plus petit nombre
  19.                while ((entries[++i] + entries[j] < goal) && (i < j));
  20.            }
  21.        }
  22.        if ((i < j) && (entries[i] + entries[j] == goal)) {
  23.            System.out.println(entries[i]);
  24.            System.out.println(entries[j]);
  25.        } else {
  26.            System.out.println("Pas de solution pour une somme de "+ goal);
  27.        }
  28.    }
  29. }


(Dans la vraie vie, les données seront en vrac, il faudra d'abord les trier, et il y a Arrays.sort pour cela)
 
A+,

Message cité 1 fois
Message édité par gilou le 21-12-2019 à 10:48:52

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --    In umbra igitur pugnabimus. --
n°2343493
rufo
Pas me confondre avec Lycos!
Posté le 21-12-2019 à 09:08:05  profilanswer
 

Gilou, l'énoncé indique que les données sont déjà triées dans l'ordre croissant, ce qui fait gagner du temps d'exécution.
Du coup, ton algo ressemble pas mal un mon algo LPT je trouve vu que tu pars des 2 extrémités du tableau.


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Cantine Calandreta : http://sourceforge.net/projects/canteen-calandreta
n°2343497
gilou
Modérateur
Modzilla
Posté le 21-12-2019 à 10:44:56  profilanswer
 

Oui, je l'avais précisé : on est en dehors de l'énoncé
Pour l'algo, ça y a y ressemblerait si tu précisais dans ton texte que quand tu cherches dans la liste si un nb correspond exactement à Reste2, tu peux partir de la position précédente.
A+,


Message édité par gilou le 21-12-2019 à 10:46:27

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --    In umbra igitur pugnabimus. --
n°2343498
Nat1329
Posté le 21-12-2019 à 11:33:26  profilanswer
 

tres bien, merci je vais essayer les solutions que vous proposez voir ce que ca donne et vous tenir au courant!

n°2343499
Nat1329
Posté le 21-12-2019 à 12:02:25  profilanswer
 

Bonjour,
 
Tes algos ne sont pas bon du tout en performance et en vitesse d'exécution.
 
j'ai testé tes deux codes mais aucun ne fonctionne sur le site, il passe 0 test sur 10 et le programme est super lent.(Accès mémoire invalide).
 
Je les ai ensuite testé sur Eclipse et il se trouve qu'il compile deux fois plus lentement que le mien. Je pense que la technique de cette algo est a revoir.
 
Je teste d'autres solutions en ce moment
 

gilou a écrit :

Perso, en supposant les données passées au programme en argument (l'énoncé n'est pas clair, mais c'est facile a adapter avec un scanner si donné dans un fichier ou tapé interactivement) j'aurais fait ainsi :

Code :
  1. public class Main {
  2.  
  3.    public static void main(String[] args) {
  4.        int entriesNb = Integer.parseInt(args[0]);
  5.        int[] entries = new int[entriesNb + 1];
  6.        for (int i = 1; i <= entriesNb; ++i) {
  7.            entries[i] = Integer.parseInt(args[i]);
  8.        }
  9.  
  10.        int i = 1;
  11.        int j = entriesNb;
  12.        int goal = 42000000;
  13.        while (entries[i] + entries[j] != goal) {
  14.            if (entries[i] + entries[j] > goal) {
  15.                while (entries[i] + entries[--j] > goal);     // Tant qu'on dépasse, il faut diminuer le plus grand nombre
  16.            } else if (entries[i] + entries[j] < goal) {
  17.                while (entries[++i] + entries[j] < goal);     // Tant qu'on manque, il faut augmenter le plus petit nombre
  18.            }
  19.        }
  20.        System.out.println(entries[i]);
  21.        System.out.println(entries[j]);
  22.    }
  23. }


 
Après, si on veut un code robuste qui supporte des données sans solution (on est en dehors de l'énoncé, et plus près de la vraie vie) on peut faire :

Code :
  1. public class Main {
  2.  
  3.    public static void main(String[] args) {
  4.        int entriesNb = Integer.parseInt(args[0]);
  5.        int[] entries = new int[entriesNb + 1];
  6.        for (int i = 1; i <= entriesNb; ++i) {
  7.            entries[i] = Integer.parseInt(args[i]);
  8.        }
  9.  
  10.        int i = 1;
  11.        int j = entriesNb;
  12.        int goal = 42000000;
  13.        while ((entries[i] + entries[j] != goal) && (i < j)) {
  14.            if (entries[i] + entries[j] > goal) {
  15.                // Tant qu'on dépasse, il faut diminuer le plus grand nombre
  16.                while ((entries[i] + entries[--j] > goal) && (i < j));
  17.            } else if (entries[i] + entries[j] < goal) {
  18.                // Tant qu'on manque, il faut augmenter le plus petit nombre
  19.                while ((entries[++i] + entries[j] < goal) && (i < j));
  20.            }
  21.        }
  22.        if ((i < j) && (entries[i] + entries[j] == goal)) {
  23.            System.out.println(entries[i]);
  24.            System.out.println(entries[j]);
  25.        } else {
  26.            System.out.println("Pas de solution pour une somme de "+ goal);
  27.        }
  28.    }
  29. }


(Dans la vraie vie, les données seront en vrac, il faudra d'abord les trier, et il y a Arrays.sort pour cela)
 
A+,


n°2343505
Lt Ripley
Mais ?!!
Posté le 21-12-2019 à 18:00:03  profilanswer
 

Salut
 
C'est sur codingame ?  Tu peux mettre un lien vers le truc ?


---------------
Viens programmer | Mon topal de vente
mood
Publicité
Posté le 21-12-2019 à 18:00:03  profilanswer
 

n°2343506
gilou
Modérateur
Modzilla
Posté le 21-12-2019 à 19:42:44  profilanswer
 

> Tes algos ne sont pas bon du tout en performance et en vitesse d'exécution.
> j'ai testé tes deux codes mais aucun ne fonctionne sur le site, il passe 0 test sur 10 et le programme est super lent.(Accès mémoire invalide).  
Arf! Ils vont deux fois plus vite que les tiens (et sur un échantillon aussi faible, 6 nb, on voit pas les problèmes du tien, mais il suffirait qu'on passe a un échantillonnage de 20 ou 30 nombres et la, ça va être bien pire, vu que mon algo est linéaire en nb d'échantillons)
Il compile et marche parfaitement sous IntelliJ, qui me signalerait un accès mémoire invalide....
 
Comme je t'ai dit, j'ai passé les données via la ligne de commande, c'est peut être cela que ton site ne sait pas gérer (ou que tu n'as pas configuré) et cela expliquerait le message d'erreur reçu.
Si tu tapes les nombres au fur et a mesure de l’exécution du programme, pourquoi pas, mais c'est pas terrible.
il suffit de remplacer le début par

Code :
  1. public class Main {
  2.    static Scanner input = new Scanner(System.in);
  3.  
  4.    public static void main(String[] args) {
  5.        int entriesNb = input.nextInt();
  6.        int[] entries = new int[entriesNb + 1];
  7.        for (int k = 1; k <= entriesNb; ++k) {
  8.            entries[k] = input.nextInt();
  9.        }


A+,
 
 
 


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --    In umbra igitur pugnabimus. --
n°2343511
Nat1329
Posté le 21-12-2019 à 21:24:49  profilanswer
 

Salut.

 

Tu peux tenter d'essayer et faire des modifs sur l'exercice qui se trouve au lien suivant https://concours.algorea.org/conten [...] 95141437/.

 

Le.probleme est qu'il faut valider les 5 exercices derriere pour avoir acces a cet exo qui se nomme somme a 42.000.000.

 

Franchement  les exos précédents sont facilement faisable a part lexo du bloc de quatre qui finalement n'est pas si compliqué mais demande un peu plus de reflexion

 

donc si quelqu'un trouve la motivation d'arriver a lexo de 42.000.000 et de proposer une solution qui marche sur le site cest le bienvenue.

 

Message cité 1 fois
Message édité par Nat1329 le 21-12-2019 à 21:32:13
n°2343512
Nat1329
Posté le 21-12-2019 à 21:26:55  profilanswer
 

gilou a écrit :

> Tes algos ne sont pas bon du tout en performance et en vitesse d'exécution.
> j'ai testé tes deux codes mais aucun ne fonctionne sur le site, il passe 0 test sur 10 et le programme est super lent.(Accès mémoire invalide).  
Arf! Ils vont deux fois plus vite que les tiens (et sur un échantillon aussi faible, 6 nb, on voit pas les problèmes du tien, mais il suffirait qu'on passe a un échantillonnage de 20 ou 30 nombres et la, ça va être bien pire, vu que mon algo est linéaire en nb d'échantillons)
Il compile et marche parfaitement sous IntelliJ, qui me signalerait un accès mémoire invalide....
 
Comme je t'ai dit, j'ai passé les données via la ligne de commande, c'est peut être cela que ton site ne sait pas gérer (ou que tu n'as pas configuré) et cela expliquerait le message d'erreur reçu.
Si tu tapes les nombres au fur et a mesure de l’exécution du programme, pourquoi pas, mais c'est pas terrible.
il suffit de remplacer le début par

Code :
  1. public class Main {
  2.    static Scanner input = new Scanner(System.in);
  3.  
  4.    public static void main(String[] args) {
  5.        int entriesNb = input.nextInt();
  6.        int[] entries = new int[entriesNb + 1];
  7.        for (int k = 1; k <= entriesNb; ++k) {
  8.            entries[k] = input.nextInt();
  9.        }


A+,
 
 
 


 
 
Effectivement le.mien serait tres lent avec de nombreuses valeurs voila pourquoi je veux le corriger

n°2343516
gilou
Modérateur
Modzilla
Posté le 21-12-2019 à 22:33:39  profilanswer
 

Nat1329 a écrit :

Salut.
 
Tu peux tenter d'essayer et faire des modifs sur l'exercice qui se trouve au lien suivant https://concours.algorea.org/conten [...] 95141437/.  
 
Le.probleme est qu'il faut valider les 5 exercices derriere pour avoir acces a cet exo qui se nomme somme a 42.000.000.
 
Franchement  les exos précédents sont facilement faisable a part lexo du bloc de quatre qui finalement n'est pas si compliqué mais demande un peu plus de reflexion
 
donc si quelqu'un trouve la motivation d'arriver a lexo de 42.000.000 et de proposer une solution qui marche sur le site cest le bienvenue.
 

Ça serait dans mes langages principaux ces temps ci, (xslt et xquery) je dirais pas non, mais sinon, non, j'ai autre chose à faire de 3h.
 
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --    In umbra igitur pugnabimus. --
n°2343517
faston
Posté le 21-12-2019 à 22:53:04  profilanswer
 

Bonsoir, en deux seconde, je ferais une sorte de recherche dicotomique donc on devrait trouver "/2" quelque par.

n°2343519
gilou
Modérateur
Modzilla
Posté le 22-12-2019 à 00:05:43  profilanswer
 

A partir du moment ou tes données sont triées, il est difficile de faire mieux que l'algo que j'ai donné. Si elles ne sont pas triées, il faut les trier, ce qui est couteux, et il y a plus efficace avec un HashSet.
 
Mais bon, on peut gratter encore un peu sur l'algo que j'ai donné en minimisant les accès au tableau en cachant les valeurs :

Code :
  1. int i = 1;
  2. int j = entriesNb;
  3. int goal = 42000000;
  4. int ei = entries[1];
  5. int ej = entries[entriesNb];
  6. while (ei + ej != goal) {
  7.    if (ei + ej > goal)
  8.        do ej = entries[--j]; while (ej > (goal - ei));
  9.    else
  10.        do ei = entries[++i]; while (ei < (goal - ej));
  11. }


Si on sait qu'on a de gros ensembles de nombres, on peut améliorer l'algo en cherchant le i (resp j) a partir duquel la valeur testée dans le do...while s'inverse par dichotomie.
A+,


Message édité par gilou le 22-12-2019 à 10:25:00

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --    In umbra igitur pugnabimus. --

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Java

  Concours de programmation

 

Sujets relatifs
[divers] conseil langage programmationProgrammation récursive ou itérative
Concours de programmation Code of Duty 2 J -Concours de programmation : Prologin 2007
[Concours de programmation]L'ultime jeuConcours de programmation : Prologin 2006 (derniers jours)
Concours de programmation : rundergroundconcours/defi programmation
Le concours de programmation ICFP 2004 a commencéConcours programmation
Plus de sujets relatifs à : Concours de programmation


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite) / Groupe LDLC / Shop HFR