Discussion :

[jeje87a]

Bonsoir a tous,

Petit nouveau sur ce forum je viens vous demander votre aide pour un mélange d'algo et de C++.
Comment ferriez vous pour résoudre le probleme suivant:
Trouver tous les nombres de 16 chiffres, qui ne commencent pas par 0, et dont aucun chiffre ne se répete plus de 3 fois.

Je n arrive pas a trouver de méthode "efficace".
Ma premiere idée, qui marche avec de "petits nombres" était de découper le nombre chiffre par chiffre puis de vérifier les conditions en utilisant un vecteur compteur. Ca marche trés bien jusqu'á 6 ou 7 nombres.
16 boucles imbriquées pour calculer chiffres par chiffre et vérifier les conditions, ca sera trop lent et donc pas efficace.

La solution est donc de ne trouver que les "bonnes valeurs" et ensuite de les compter.
On m'a conseille l'utilisation d'arbre n-aire mais n'ayant jamais utilisé d'arbre j'ai un peu du mal. D'aprés vous cette solution serait elle plus rapide?

Si vous avez des idées novatrices ou si vous pouvez m'aiguillez concernant la solution par arbre, vous etes les bienvenue

ps: la solution est bornéé par en dessus et en dessous par 999888777666 5554 et 1000112223334445.

[Twindruff]

Salut jeje87a,

La solution est donc de ne trouver que les "bonnes valeurs" et ensuite de les compter.

Oui c'est ça qu'il faut faire, il faut que tu génères tes nombres chiffre par chiffre et donc il faut que tu sache à tout moment à quels chiffres tu as encore droit.
Tu peux par exemple avoir un tableau de 10 entiers correspondant au nombre de fois que tu peux encore utiliser 0, 1, ..., 9.
Ensuite tu dois avoir une boucle qui construit tes nombres chiffre par chiffre et s'il te reste des 0 tu peux générer ton nombre actuel avec un zéro à la fin, si tu as des 1 avec un 1 à la fin, et ainsi de suite.

Et est-ce que tu dois seulement trouver le nombre de nombres qui vérifient ta propriété, ou tous les sortir ?

[jeje87a]

Bonjour

Merci de ta réponse.
Je dois juste trouver les nombres vérifiant la propriété mais je pense que le faire en "comptant" toutes les bonnes possibilités c est assez logique.

Je pense qu il y a une méthode purement mathematiques pour trouver juste le résultat mais pas évident a mon sens.

J'ai essayé de faire un programme avec un tableau comme tu l as expliqué mais mon programme "vérifie" grace au tableau si le nombre est bon ou non.
Si tu as une idée de code elle est la bienvenue.

Merci

[Dreambeliever]

Tout d'abord, un tableau de 16 char pour représenter ton nombre à 16 chiffres

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

char nombre[] = {1,0,0,0,1,1,2,2,2,3,3,3,4,4,4,5}; // le nombre de départ

Ensuite un tableau de 10 char pour représenter les chiffres utilisés

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

char chiffres[] = {3,3,3,3,3,1,0,0,0,0};

(il y a trois 0, trois 1, ...)

Ensuite, pour parcourir les solutions, rien de plus simple que d'incrémenter ton nombre!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
//code très naif, ne pas utiliser
void incrementer(char *nombre, char *chiffres, size_t pos)
{
    nombre[pos]++; //augmente le chiffre, par exemple de 7 à 8...
}

Mais après tu dois vérifier que si ton chiffre passe de 9 à 10, tu le fais passer de 9 à 0, et augmenter celui de la dizaine supérieure:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
//code très naif, ne pas utiliser
void incrementer(char *nombre, char *chiffres, size_t pos)
{
    if (++nombre[pos] == 10) //s'il y a une retenue
    {
         nombre[pos] = 0;
         incrementer(nombre, chiffres, pos-1); // on augmente la dizaine supérieure
    }
}

Mais après, tu dois vérifier certaines conditions avec chiffres (que nombre[pos] n'ait pas sa case dans chiffres à 3, ...), tu dois tenir à jour un compteur, et une fois que tu auras fini, tu pourras même peut-être trouver des simplifications qui vont augmenter la vitesse de l'algorithme.

Peut être que ce serait bien de commencer avec moins de chiffres que 16.

Bonne chance!

[Tomaka17]

On m'a conseille l'utilisation d'arbre n-aire mais n'ayant jamais utilisé d'arbre j'ai un peu du mal. D'aprés vous cette solution serait elle plus rapide?

C'est quelqu'un qui sait comment faire qui t'a conseillé ça, ou juste par intuition ?
Parce que je vois pas en quoi un arbre aiderait à ce problème


Mon idée à moi serait d'utiliser la récursivité :
On créé une fonction "creerListeNombresAvecNChiffres(int n, std::vector& aModifier, int& maxChiffres[10])"

Les paramètres sont :
- nombre de chiffres dans le nombre
- une référence vers une liste où stocker le résultat
- le nombre maximal de chiffres de chaque

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void creerListeNombresAvecNChiffres(int n, std::vector<int>& aModifier, int& maxChiffres[10]) {
 if (n == 1) {    // fin de la récursivité
  // on veut des nombres à 1 chiffre
  // on retourne donc comme résultat tous les chiffres dont la valeur dans maxChiffres n'est pas à 0
  for (int i = 0; i < 10; i++)
   if (maxChiffres[i] > 0) aModifier.push_back(i);
  return;
 }
 
 // petit opérateur ternaire pour éviter les nombres à 16 chiffres qui commencent par 0
 for (int i = (n == 16 ? 1 : 0); i < 10; i++) {
  if (maxChiffres[i] == 0) continue;  // on ne peut plus rajouter ce chiffre là
  maxChiffres[i]--;    // on fait comme si on l'avait utilisé pour l'appel récursif
 
  // et l'appel récursif
  std::vector<int> resultatsInferieur;
  creerListeNombresAvecNChiffres(n - 1, resultatsInferieur, maxChiffres);
  for (std::vector<int>::iterator j = resultatsInferieur.begin(); j != resultatsInferieur.end(); j++)
   aModifier.push_back(i * 10 * n + *j);
 
  maxChiffres[i]++;
 }
}

La récursivité commencerait donc avec :
creerListeNombresAvecNChiffres(16, resultats, maxChiffresInit);

Avec "resultats" un std::vector vide où mettre les résultats, et "maxChiffresInit" un tableau de 10 int avec chacun comme valeur 3

C'est pondu en 5mn chrono donc je garantis pas sans bug, et je ne sais pas si c'est plus rapide ou pas qu'une autre méthode (à voir en détails)

[jeje87a]

Merci pour vos 2 réponses, je vais les regarder en detail et je vous demanderai plus de conseils ou des precisions par la suite.

Pour l arbre n-aire, l'idée venait du fait que l'on aurait pu essayer de mettre 10 racines(de 0 a 10) puis chaque branche descendante en fonction de la valeur de l etage precedent.
Le nombres de feuilles au final donne le nombre de possibilités, le soucis c est que cela donnerai un arbre "immense" et pas tres facile a coder (je n'y suis pas parvenu).

[Sylvain Togni]

ps: la solution est bornéé par en dessus et en dessous par 999888777666 5554 et 1000112223334445.

Ce qui exclu toute méthode basée sur le comptage une à une des solutions (à moins de posséder un supercalculateur et plusieurs années devant soi).

Les mathématiques sont donc tes amies.

[jeje87a]

J ai trouvé la solution grace au C(n,P) et permutation.

Resolu

Merci a vous