Former le plus grand nombre possible avec 4 chiffres

Version imprimable

22/11/2023, 14h57
JPB-BFI

Former le plus grand nombre possible avec 4 chiffres

Bonjour,
Je sèche sur un petit problème…Je reçois un nombre de 4 chiffres, par exemple 7835 et je voudrais en faire, avec ces 4 chiffres, le plus grand nombre, soit 8753. Auriez-vous l'amabilité de m'aiguiller ?

Merci et bonne journée

Il y a 1 difficulté :weird::weird: ?

Code:

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
#include <iostream>
 
#include <cstdlib>
 
 
int main()
{
    size_t n = 7835;
    char tab[4];
 
//  Extract digits
    tab[0] =  (n / 1000);
    tab[1] = ((n /  100) - (tab[0] *  10));
    tab[2] = ((n /   10) - (tab[0] * 100) - (tab[1] * 10));
    tab[3] = (n - (tab[0] * 1000) - (tab[1] * 100) - (tab[2] * 10));
 
//  bubble sort, descending order
    for(size_t i=3, j, tmp; i > 0; --i) {
        for(j=0; j < i; ++j) {
            if (tab[j+1] > tab[j]) {
                tmp      = tab[j+1];
                tab[j+1] = tab[j];
                tab[j]   = tmp;
            }
        }
    }
 
//  Calculate maximum
    n = ((tab[0] * 1000) + (tab[1] * 100) + (tab[2] * 10) + tab[3]);
 
//  Display maximum
    std::cout << n << std::endl;
 
 
    return EXIT_SUCCESS;
}

22/11/2023, 15h28
Stellar7

Bonjour,

En approche basique (vision algo), je dirai :
- considérer que ton nombre est une liste de chiffres,
- trier les chiffres par ordre décroissant.

Pour cela, en version code :
- vérifier que c'est bien un nombre entier,
- le transformer en ce qui t'arranges : une liste ? un tableau ? une chaîne de caractères ? bref ce qui te simplifiera la vie pour le traitement,
- trier…
- retransformer en nombre entier.

Ton choix de structure de données pour le traitement dépend de ce que tu connais du C++, de ce qui existe déjà comme fonctions dans le langage (pour transformer, traiter, etc), etc. Pour les détails techniques du C++, ce n'est pas moi qui te répondrai.

Bonne continuation !
22/11/2023, 15h37
Bousk
Si le chiffre vient dans un int, tu le découpes, tries et recolles les morceaux.
Si c'est une string, tu peux directement la trier.
Depuis un int, tu pourrais aussi le mettre dans une string pour la trier.
Ceci se fait en... 1 ligne ?
std::sort
Code:

1 2 3 size_t n = 7835; std::string str = std::to_string(n); std::sort(str.begin(), str.end(), [](char a, char b) { return a > b; });
22/11/2023, 15h47
JPB-BFI

Merci à tous!

Bonjour,

Si on vise plus la performance que la concision, il est possible d'éviter le tri (bon pour 4 malheureux chiffres ce n'est pas très intéressant).

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdlib>
int main() {
   size_t   n     = 7835;
   uint8_t  v[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
 
   while(n != 0) {                               // extract digits
      int u = n;
      n /= 10;
      v[u-10*n]++;                               // v[5]=1, v[3]=1, v[8]=1, v[7]=1
      }
   for(int i = 9; i >= 0; --i) {
      while(v[i]) { n = 10*n + i; v[i]--; }      // n=0+8=8, n=80+7=87, n=870+3=873, n=8730+5=8735
   }
   std::cout << n << std::endl;                  // display maximum
 
   return EXIT_SUCCESS;
}

En fait cela s'apparente quand même au tri du facteur en base 10. Nous sommes quasiment en O(nb chiffres). En espérant n'avoir pas laissé trop de scories :oops:.

Salutations

23/11/2023, 00h56
foetus

:mrgreen: @Guesset voulait parler du bucket sort ou bin sort (<- lien wikipédia en anglais) qui est la base d'autres algos : histogram sort, postman's sort, radix sort, ...
23/11/2023, 10h09
JPB-BFI

Merci et cordiaux messages