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.

Une idée pour rendre mon programme plus rapide?

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 !

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

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

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 :

public class Main {
 
    public static void main(String[] args) {
        int entriesNb = Integer.parseInt(args[0]);
        int[] entries = new int[entriesNb + 1];
        for (int i = 1; i <= entriesNb; ++i) {
            entries[i] = Integer.parseInt(args[i]);
        }
 
        int i = 1;
        int j = entriesNb;
        int goal = 42000000;
        while (entries[i] + entries[j] != goal) {
            if (entries[i] + entries[j] > goal) {
                while (entries[i] + entries[--j] > goal);     // Tant qu'on dépasse, il faut diminuer le plus grand nombre
            } else if (entries[i] + entries[j] < goal) {
                while (entries[++i] + entries[j] < goal);     // Tant qu'on manque, il faut augmenter le plus petit nombre
            }
        }
        System.out.println(entries[i]);
        System.out.println(entries[j]);
    }
}

 
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 :

public class Main {
 
    public static void main(String[] args) {
        int entriesNb = Integer.parseInt(args[0]);
        int[] entries = new int[entriesNb + 1];
        for (int i = 1; i <= entriesNb; ++i) {
            entries[i] = Integer.parseInt(args[i]);
        }
 
        int i = 1;
        int j = entriesNb;
        int goal = 42000000;
        while ((entries[i] + entries[j] != goal) && (i < j)) {
            if (entries[i] + entries[j] > goal) {
                // Tant qu'on dépasse, il faut diminuer le plus grand nombre
                while ((entries[i] + entries[--j] > goal) && (i < j));
            } else if (entries[i] + entries[j] < goal) {
                // Tant qu'on manque, il faut augmenter le plus petit nombre
                while ((entries[++i] + entries[j] < goal) && (i < j));
            }
        }
        if ((i < j) && (entries[i] + entries[j] == goal)) {
            System.out.println(entries[i]);
            System.out.println(entries[j]);
        } else {
            System.out.println("Pas de solution pour une somme de "+ goal);
        }
    }
}

(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+,

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.

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+,

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

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
 

public class Main {
 
    public static void main(String[] args) {
        int entriesNb = Integer.parseInt(args[0]);
        int[] entries = new int[entriesNb + 1];
        for (int i = 1; i <= entriesNb; ++i) {
            entries[i] = Integer.parseInt(args[i]);
        }
 
        int i = 1;
        int j = entriesNb;
        int goal = 42000000;
        while (entries[i] + entries[j] != goal) {
            if (entries[i] + entries[j] > goal) {
                while (entries[i] + entries[--j] > goal);     // Tant qu'on dépasse, il faut diminuer le plus grand nombre
            } else if (entries[i] + entries[j] < goal) {
                while (entries[++i] + entries[j] < goal);     // Tant qu'on manque, il faut augmenter le plus petit nombre
            }
        }
        System.out.println(entries[i]);
        System.out.println(entries[j]);
    }
}

public class Main {
 
    public static void main(String[] args) {
        int entriesNb = Integer.parseInt(args[0]);
        int[] entries = new int[entriesNb + 1];
        for (int i = 1; i <= entriesNb; ++i) {
            entries[i] = Integer.parseInt(args[i]);
        }
 
        int i = 1;
        int j = entriesNb;
        int goal = 42000000;
        while ((entries[i] + entries[j] != goal) && (i < j)) {
            if (entries[i] + entries[j] > goal) {
                // Tant qu'on dépasse, il faut diminuer le plus grand nombre
                while ((entries[i] + entries[--j] > goal) && (i < j));
            } else if (entries[i] + entries[j] < goal) {
                // Tant qu'on manque, il faut augmenter le plus petit nombre
                while ((entries[++i] + entries[j] < goal) && (i < j));
            }
        }
        if ((i < j) && (entries[i] + entries[j] == goal)) {
            System.out.println(entries[i]);
            System.out.println(entries[j]);
        } else {
            System.out.println("Pas de solution pour une somme de "+ goal);
        }
    }
}

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

> 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

public class Main {
    static Scanner input = new Scanner(System.in);
 
    public static void main(String[] args) {
        int entriesNb = input.nextInt();
        int[] entries = new int[entriesNb + 1];
        for (int k = 1; k <= entriesNb; ++k) {
            entries[k] = input.nextInt();
        }

A+,
 
 
 

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.

public class Main {
    static Scanner input = new Scanner(System.in);
 
    public static void main(String[] args) {
        int entriesNb = input.nextInt();
        int[] entries = new int[entriesNb + 1];
        for (int k = 1; k <= entriesNb; ++k) {
            entries[k] = input.nextInt();
        }

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

Ç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+,

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

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 :

int i = 1;
int j = entriesNb;
int goal = 42000000;
int ei = entries[1];
int ej = entries[entriesNb];
while (ei + ej != goal) {
    if (ei + ej > goal)
        do ej = entries[--j]; while (ej > (goal - ei));
    else
        do ei = entries[++i]; while (ei < (goal - ej));
}

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+,