Discussion :

[Beginneritmaghcas]

Bonjour cher communauté je suis un nouveau débutant en programmation et je rencontre un problème je voudrais développer un programme qui a partir d'une liste de points donnés (un point est défini avec ses coordonnées) divisé cette ensemble de points en sous ensemble tel que la distance entre tout les points de cet sous ensemble est inférieur strictement à 20km le but est de savoir combien de sous ensemble on aura et que sont les points de chaque sous ensemble je me suis dit que cet algorithm marche :
Soit E = ensemble de points x tel que E={X1,X2,X3,......Xn}
Pour i allant de 0 à n on a
Fi = Xi
E= E - Fi
Pour j allant de 0 a n et i !=j on a


Si la distance entre Xi et Xi est inférieur à 20km alors Fi = {Xi,Xj}
E= E - Fi
On affiche F1,F2,F3,....Fn on arrête lorsque E est vide
Voilà l'idée pour lalgorithm je sais pas si ca va marcher mais le problème c'est que je n'arrive pas a le coder j'ai rencontré des problèmes avec les tableaux aussi avec la notion de point définie avec ses coordonnées aussi un problème de calcul de distance ainsi que le compteur ... je suis bloqué si vous pouvez m'aider ou m'éclairer je vous en remercie

[Sve@r]

Bonjour

Désolé de te décevoir mais c'est un problème d'un trop haut niveau pour un débutant.
Prenons un exemple simple, avec des points en 1D (c'est pareil qu'en 2D, c'est juste pour illustrer). Imaginons que tu aies A(5), B(12) et C(17). Toutes les distances font moins de 20km. Ton algo donnera alors ABC mais aussi ACB et aussi BCA et aussi BAC et aussi CBA et aussi CAB. C'est à dire pour 3 points 6 chemins.
Avec 4 points il te sortira 24 chemins (moins si certains font plus de 20km mais de toute façon tu devras quand-même calculer les 24 chemins pour les mesurer). Avec 5 points tu en auras 120. Et avec n points tu en auras n! (factorielle de n). Et plus encore si on y rajoute aussi les chemins n'incluant pas tous les points (ex AB, AC, BC).
Donc déjà il te faut

• générer les chemins (récursivité)
• stocker les chemins (allocation de mémoire)

Autant de notions qu'on n'a pas quand on débute. Sans compter les trucs annexes comme les structures (un point 2D c'est 2 coordonnées qu'on groupera dans une structure permettant de manipuler les deux coordonnées d'un coup), les pointeurs (parce que quand tu passeras ton tableau de chemins à la fonction fille tu lui passeras un simple pointeur).

Maintenant si tu veux quand-même te lancer, alors la base c'est la génération des chemins. Or générer chemins(ABC) c'est A+chemins(BC) puis B+chemins(AC) puis C+chemins(AB) et rebelote à partir de chemins(BC) => récursivité.

[dalfab]

Bonjour,

Ce que tu recherches est particulier.
- Est-ce un exercice?
- Est-ce une étape pour effectuer un programme?

Dans le premier cas c'est curieux car ça demande d'utiliser des concepts où le langage C n'est pas le mieux placé. Ça fait donc utiliser des choses compliquées pour un objectif qui semble simple. Ça serait donc contre pédagogique.
Dans le second cas, peut-être que ce que tu envisages n'est pas la bonne étape. On pourrait mieux t'aider avec une vision de l'objectif final.

On peut t'aider à obtenir ta liste d'ensembles. Pour une dizaine de points ça fera une énorme liste. Sais-tu combien de points il y aura? Sve@r t'a indiqué les concepts nécessaires pour cela. Dis nous en plus.

[Beginneritmaghcas]

Merci pour vos indications les gars l'objectif final est :
J'ai 10 equipes et 113 points sur la map Google et je voudrais de la façon la plus optimale que chaque équipe se charge d'un nombre de points de tels sorte que chaque équipe puisse se déplacer d'un point a un autre sans passé une éternité sur la route d'où la condition de 20km je sais si cest assez clair mais en tout cas merci pour votre aide

[dalfab]

Aïe.

Ton problème ressemble à celui du voyageur de commerce et en plus compliqué. Sa solution exacte pour plus de 18 points n'est pas calculable avec les moyens informatiques de la planète. Le nombre de routes à envisager serait de (18-1)!/2 soit 177843714048000.

Ce que tu peux, c'est faire un outil d'aide à la décision qui quantifierait des solutions que tu essaierais. En tout cas, énumérer l'ensemble est impossible.
D'autre part le C est le dernier des langages auquel je penserais pour faire ce genre d'outil.

[Sve@r]

Ton problème ressemble à celui du voyageur de commerce et en plus compliqué.

Et déjà que le voyageur de commerce est lui-même d'une complexité incalculable...

Sa solution exacte pour plus de 18 points n'est pas calculable avec les moyens informatiques de la planète. Le nombre de routes à envisager serait de (18-1)!/2 soit 177843714048000.

Ou, en termes plus compréhensibles, dans les 177 mille milliards. Il faut savoir qu'un ordinateur type PC peut calculer facilement (grosso-modo) jusqu'à 1 million. On peut le forcer à 10 millions et on attend un peu (dans les 10 minutes). Pour 100 millions l'attente commence à se compter en heures mais c'est pas encore démesuré (tu auras des temps style 5h). Mais pour 177 mille milliards là le temps d'attente devrait avoisiner le millier d'années. Et même si je me trompe d'un facteur 1000 à ton avantage dans mon évaluation, ça te ramène à un temps de calcul de 1 an.

[Mat.M]

Merci pour vos indications les gars l'objectif final est :
J'ai 10 equipes et 113 points sur la map Google et je voudrais de la façon la plus optimale que chaque équipe se charge d'un nombre de points de tels sorte que chaque équipe puisse se déplacer d'un point a un autre sans passé une éternité sur la route d'où la condition de 20km je sais si cest assez clair mais en tout cas merci pour votre aide

bonjour ça s'apparente à l'algorithme de Djikstra dans toute sa splendeur.
https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

D'une part la distance entre deux points comme chacun sait c'est

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
 
typedef struc sPoint
{ int x;
int y;
}
 
int CalcDistance(sPoint pt1, sPoint pt2)
{
	float delta_x;	
	float delta_y;
	float distance;
	int int_distance;
	delta_x=(float)abs(pt1.x-pt2.x );   
	delta_y=(float)abs(pt1.y-pt2.y );   
	delta_x=delta_x*delta_x;
	delta_y=delta_y*delta_y;
	distance=sqrt(delta_x+delta_y);
	int_distance=(int)distance;
	return int_distance;
 
}

ensuite il faut utiliser encore une fois des listes simplement ou doublemetn chaïnées et créer des "noeuds" entre chaque point, construire une liste de points.
Après il faut parcourir la liste , passer deux points en argument et comparer si la distance entre les deux est inférieure à 20 km

Code :

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

1
2
3
4
5
6
 
typedef struct node
{
float distance;
node *pNextNode;
}

Allez débrouillez vous avec ça , ça va vous permettre d'avancer je reviens en fin de journée et je ramasse les copies

[Sve@r]

D'une part la distance entre deux points comme chacun sait c'est

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
int CalcDistance(sPoint pt1, sPoint pt2) {
	float delta_x;	
	float delta_y;
	float distance;
	int int_distance;
	delta_x=(float)abs(pt1.x-pt2.x );   
	delta_y=(float)abs(pt1.y-pt2.y );   
	delta_x=delta_x*delta_x;
	delta_y=delta_y*delta_y;
	distance=sqrt(delta_x+delta_y);
	int_distance=(int)distance;
	return int_distance;
}

Beaucoup d'instructions et variables inutiles là dedans. Pourquoi utiliser un float pour stocker une soustraction de deux int ? Pourquoi passer par abs() alors que même si la soustraction est négative son carré sera quand-même positif ? Et vu qu'une distance est un truc à priori positif, autant utiliser un type adéquat pour le manipuler. Et quand on transmet des structures à des fonctions, vaut mieux passer par des pointeurs (juste une adresse de 4 octets à copier) que copier directement une structure pouvant contenir plusieurs centaines d'octets (même si ce n'est pas le cas ici, c'est une habitude à prendre).

Code :

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

1
2
3
4
5
unsigned int CalcDistance(const sPoint* const pt1, const sPoint* const pt2) {
	int delta_x=pt1->x - pt2->x;	
	int delta_y=pt1->y - pt2->y;
	return (unsigned int)sqrt(delta_x * delta_x + delta_y * delta_y);
}