Discussion :

[honolyani]

Bonsoir les amis. J'ai besoin d'aide!

Je voudrais écrire un programme en C ou C++ qui va choisir entre 10 nombres par exemple,
ou plus et qui pourra distrubuer 3 ou 4 nombres entre 2 personnes sans pour autant
repeter un nombre déjà donné; à la fin il va décompter les nombres déjà donnés et
afficher le reste.

Exemple: On a 10 nombres de 1 à 10 et deux pseudo-personnes A et B.
Je voudrais que le programme puisse donner à A et à B 3 nombres entre 1 et 10 sans repéter
un nombre donné.
Comme ceci:
A(1, 5, 2) ; B(3, 7, 9) et Reste: 4, 6, 8, 10. Voilà ce que je voudrais obtenir!

Et non ceci: A(1, 2, 5); B(3, 2, 4) ou A(1, 5, 2); B(3, 3, 10)
Reste: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

Je n'arrive pas à trouver l'algo.
Pouvez-vous m'aider, s'il vous plait.

Voilà mon adresse mail:honolyani@gmail.com

[vikki]

Hello,
Déjà il te faut trancher entre C et C++, l'implémentation risquant d'être totalement différente
Étant sur le forum C++, on va plutôt réfléchir à des solutions C++ si ca te va . A mon avis, une solution simple consiste à stocker tous les nombres pouvant être distribués dans un conteneur quelconque (comme une std::list contenant par exemple tous les nombres de 1 à 10). Pour distribuer une valeur à A ou B, tu pioche (aléatoirement ou non) une valeur dans le conteneur, la distribue à la personne concernée et supprime l'élément ainsi choisi du conteneur. De cette manière, tu es sûr d'éviter les doublons et le conteneur ne contient que les éléments restant.

[honolyani]

D'accord, mais comment m'y prendre? je connais pas les conteneurs!!!

[JolyLoic]

Un truc genre :

Code :

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

1
2
3
4
5
6
7
8
9
#include <vector>
#include <algorithm>
 
std::vector<int> lesNombres;
for (int i=1 ; i!=11 ; ++i)
{
   lesNombres.push_back(i);
}
random_shuffle(lesNombre.begin(), lesNombres.end());

Puis tu associes lesNombres d'indice 0 à 2 à A, d'indices 3 à 5 à B, le reste étant non utilisé.

[JolyLoic]

Pour distribuer une valeur à A ou B, tu pioche (aléatoirement ou non) une valeur dans le conteneur, la distribue à la personne concernée et supprime l'élément ainsi choisi du conteneur. De cette manière, tu es sûr d'éviter les doublons et le conteneur ne contient que les éléments restant.

Cette manière est fonctionnelle, et pour 10 valeurs, aucun soucis. Mais il est bon de savoir qu'elle n'est pas très bonne en terme de performances si on désire l'étendre à plus de valeurs (O(n²), alors que ma proposition est en O(n)).

[vikki]

Je ne connaissais pas la fonction random_shuffle. Effectivement, c'est bien mieux comme ca

[Emmanuel Deloget]

L'exercice est similaire à une distribution de cartes.

1/ initialiser une file avec l'ensemble des nombres. L'idée d'utiliser une file va paraître plus simple à la fin. max_num est le plus grand nombre souhaité.

Code :

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

1
2
3
 
std::vector<int> numbers;
for (int i=1; i<=max_num; ++) numbers.push_back(i);

2/ effectuer un nombre quelconque de permutations entre deux éléments pris au hasard dans ce tableau. perm_num > 2 * max_num devrait donner un résultat cohérent.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
// initialiser rand() 
srand(time(NULL));
int perm_num = max_num * 2;
for (int p=0; p<perm_num; ++p)
{
  // je défini la fonction random_number plus loin, pas d'inquiétude
  std::size_t a = (std::size_t)random_number(0, max_num);
  std::size_t b = (std::size_t)random_number(0, max_num);
  std::swap(numbers[a], numbers[b]);
}

3/ Le tableau est censé être complètement détrié à ce moment. Du coup, l'élément 0 a une probabilité assez faible d'être 0. On peut considérer qu'il s'agit d'un vecteur de nombres uniques ordonnés au hasard. Donc pour distribuer, je peux tout simplement prendre le dernier élément, le donenr à A, prendre l'avant dernier, le donner à B, etc.

Code :

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

1
2
3
4
5
6
 
for (int i=0; i<3; ++i)
{
  give(A, numbers.back()); numbers.pop_back();
  give(B, numbers.back()); numbers.pop_back();
}

Là, on voit le pourquoi d'une file : a chaque fois qu'on donne un élément, on l'enlève de la liste. Puisque c'est le dernier éléments à chaque fois, ça veut juste dire qu'on le dépile.

La liste des nombres restants :

Code :

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

1
2
3
4
5
6
7
8
 
  // pour la trier avant de l'afficher
  // std::sort(numbers.begin(), numbers.end());
  for (std::size_t i=0; i<numbers.size(); ++i)
  {
    std::cout << numbers[i] << " ";
  }
  std::cout << std::endl;

La fonction random_number() :

Code :

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

1
2
3
4
5
 
int random_number(int mini, int maxi)
{
  return int(float(rand()) / (float(RAND_MAX) + 1.0) / float(maxi - mini)) + mini;
}

[honolyani]

Salut les amis.
@JolyLoic Je ne comprenais pas ton raisonnement j'ai du le lire et relire plusieurs fois
avant de comprendre, enfin je crois. En fait voilà ce que tu veux dire:
Je défini les nombres dans la variable lesNombres, j'utilise la fonction random_shuffle pour
le mélange et après, j'attribue à A les 3 premières valeurs générées ensuite les 3 suivantes
à B ?

@Emmanuel Deloget. Merci pour tes sources. Je me pose une question: Au cas ou
je voudrais donner 3 nombres directement à un A ou/et B, comment m'y prendre dans ce cas ?
Et la fonction give, tu ne l'as pas implementé ?

@TOUS! Merci les gars. En moins d'une semaine vous m'avez fait énormément avancer en C++,
dire que je ne comprenais rien aux Template, vector et Compagnies deux jours auparavant(c'est
vrai que j'ai encore besoin de lecture et de pratique, mais j'ai avancé grace à vous).
Merci encore. Vous etes les meilleurs et surtout changés pas!