Comment trouver le deuxième nombre minimum sans utiliser de tableaux ou de boucles ?

Question

J'ai essayé d'écrire un programme qui reçoit de l'utilisateur 5 entiers et d'imprimer le deuxième nombre minimum.
Voici un échantillon de ce que j'ai essayé :

#include <iostream>
using namespace std;
int main () {
int a,b,c,d,e;
cin>>a>>b>>c>>d>>e;
if (a>b && a<c && a<d && a<e)
    cout<<a<<endl;
if (b>a && b<c && b<d && b<e)
    cout<<b<<endl;
if (c>a && c<b && c<d && c<e)
    cout<<c<<endl;
if (d>a && d<b && d<c && d<e)
    cout <<d<<endl;
if (e>a && e<b && e<c && e<d)
cout <<e<<endl;
return 0;

}

Quand j'entre 1 2 3 4 5 il imprime le deuxième minimum, mais quand je saisis
5 4 3 2 1 Rien ne s'imprime à l'écran. Qu'est-ce qui ne va pas dans ce cas ? Existe-t-il une autre façon d'écrire mon programme ?

Answer 1

Le problème de votre logique est que vous ne vous imposez pas d'imprimer un seul élément, et au moins un élément. En utilisant la partie "else" de la syntaxe if/else, vous vous assurez qu'une seule branche peut être atteinte. Vous pouvez ensuite poursuivre avec un simple else à la fin, puisque vous savez que toutes les autres conditions sont fausses.

Une fois que vous avez fait cela, vous verrez que vous imprimez la dernière valeur, (1) plutôt que la valeur attendue (4). C'est parce que votre logique concernant la façon de trouver la deuxième valeur la plus basse est fausse. b>a est faux pour le cas 5,4...

Note : Tout ingénieur employé, jamais, ferait de ceci une boucle dans un std::vector / std::array, et je vous suggère de diriger votre professeur vers ce post parce qu'encourager les boucles est une bonne chose plutôt qu'une mauvaise.

Quelque chose comme

vector<int> data;
for (int i=0; i<5; ++i) {
    int t;
    cin >> t;
    data.push_back(t);
}
std::nth_element(data.begin(), data.begin()+1, data.end(), std::greater<int>());
cout << data[1];

Answer 2

Il existe 120 permutations possibles sur 5 éléments. Votre code doit produire le nombre correct pour chacune d'entre elles. Un code infaillible utiliserait donc 120 répétitions d'un contrôle, comme le suivant :

if (a > b && b > c && c > d && d > e) // the order is a>b>c>d>e
    cout << d;
else if (a > b && b > c && c > e && e > d) // the order is a>b>c>e>d
    cout << e;
...
else if (e > d && d > c && c > a && e > b) // the order is e>d>c>a>b
    cout << a;
else // the order is e>d>c>b>a
    cout << b;

Ce code est très long, inefficace et délicat. Si vous faites une faute de frappe dans une seule variable, il produira une mauvaise réponse dans certains cas rares. De plus, il ne gère pas la possibilité que certaines entrées soient égales.

---

Si le nombre d'entrées d'un algorithme de tri est une petite constante connue, vous pouvez utiliser une approche appelée réseaux de triage . Il s'agit d'un problème informatique bien défini, dont les solutions optimales sont bien connues pour un petit nombre d'entrées, et 5 est certainement un petit nombre. Un réseau de tri optimal pour 5 entrées contient 9 comparateurs, et est décrit par exemple dans le document suivant aquí .

Puisque vous n'avez pas besoin de trier les nombres, mais seulement de connaître la deuxième plus petite entrée, vous pouvez réduire encore la taille du réseau, à 7 comparateurs.

Le réseau de tri complet (sans la réduction de 9 à 7) a été traduit en C++ :

if (b < c)
    swap(b, c);
if (d < e)
    swap(d, e);
if (b < d)
    swap(b, d);
if (a < c)
    swap(a, c);
if (c < e)
    swap(c, e);
if (a < d)
    swap(a, d);
if (a < b)
    swap(a, b);
if (c < d)
    swap(c, d);
if (b < c)
    swap(b, c);
// now the order is a ≥ b ≥ c ≥ d ≥ e
cout << d;

Ce code est également obscur - il n'est pas du tout évident de savoir comment et pourquoi il fonctionne - mais au moins il est petit et, dans un sens, optimal. De plus, il est clair qu'il imprime toujours quelque chose (il résout donc le problème initial) et prend en charge le cas des entrées partiellement égales.

Si vous utilisez un tel code dans un projet plus important, vous devez documenter l'endroit où vous l'avez pris et le tester. Heureusement, il existe exactement 120 possibilités différentes (ou 32, si vous utilisez l'option principe zéro-un ), il existe donc un moyen de prouver que ce code n'a pas de bogues.

Answer 3

Cela devrait fonctionner pour vous. (Notez que ce n'est peut-être pas la meilleure approche et que vous pouvez la minimiser avec une fonction pour calculer min et secondMin au lieu de l'affreux copier-coller de la logique, mais cela vous aidera à démarrer :

#include <iostream>
using namespace std;
int main () {
int a,b,c,d,e;
int min, secondMin;

cin>>a>>b;

min = a < b ? a : b;
secondMin = a < b ? b : a;

cin>>c;

if (c < min)
{
    secondMin = min;
    min = c;
}
else if (c < secondMin)
{
    secondMin = c;
}

cin>>d;

if (d < min)
{
    secondMin = min;
    min = d;
}
else if (c < secondMin)
{
    secondMin = d;
}

cin>>e;

if (e < min)
{
    secondMin = min;
    min = e;
}
else if (e < secondMin)
{
    secondMin = e;
}

cout << "min = " << min << ", secondMin = " << secondMin << endl;

return 0;

}

Si vous avez des questions, n'hésitez pas à les poser dans les commentaires.

Answer 4

#include <set>

std::set<int> values = { a, b, c, d, e }; // not an array.
int second_min = *std::next(values.begin(), 1); // not a loop

Answer 5

Qu'en est-il d'un récursif y plus générique approche ? Pas de tableaux , pas de boucles et ne se limite pas à 5 entiers.

La fonction suivante get_2nd_min() garde la trace des deux plus petits entiers lus à partir de std::cin un total de count temps :

#include <climits>
#include <cstddef>
#include <iostream>

int get_2nd_min(size_t count, int min = INT_MAX, int second_min = INT_MAX)
{
   if (!count)
      return second_min; // end of recursion

   // read next value from cin
   int value;
   std::cin >> value;

   // Does second_min need to be updated?
   if (value < second_min) {

     // Does min also need to be updated?
     if (value < min) {
        // new min found
        second_min = min; // move the so far min to second_min
        min = value; // update the new min
     } else {
        // value is lower than second_min but higher than min
        second_min = value; // new second_min found, update it
     }
   }
   // perform recursion
   return get_2nd_min(count - 1, min, second_min);
}

---

Pour lire 5 nombres entiers et obtenir le deuxième plus petit :

int second_min = get_2nd_min(5);