Προς το περιεχόμενο

ΔΙΚΤΥΑ KAI ΠΡΟΓΡΑΜΑΤΙΣΜΟΣ ΜΕ C

turbo_amd

Από τον turbo_amd
στο Προγραμματισμός

Προτεινόμενες αναρτήσεις

turbo_amd Proficient

turbo_amd

Δημοσ.
Δημοσ.

Παιδιά έχω μια εργασία στα δίκτυα και θέλω τη βοήθεια σας σε γλώσσα C. Το πρόβλημα έχει ως εξής:

 

  • Να δημιουργηθεί ένα δίκτυο Ν κόμβων με τυχαία διάταξη στο επίπεδο (είσοδος Ν κόμβοι).
  • Καθορίζεται παράμετρος r τέτοια ώστε αν η ευκλείδια απόσταση 2 κόμβων είναι μικρότερη ή ίση με r, τότε ανάμεσα στους εν λόγω κόμβους να υπάρξει ζεύξη βάρους ίσου με την ευκλείδια απόσταση.
  • Το πρόγραμμα θα πρέπει να βρίσκει την ελάχιστη τιμή του r, συμβολιζόμενη με rc για την οποία το δίκτυο να είναι συνεκτικό (όταν υπάρχει μονοπάτι ανάμεσα σε κάθε ζεύγος κόμβων)
  • Το πρόγραμμα θα πρέπει να μπορεί να υπολογίζει τη διάμετρο D του δικτύου (μήκος του μεγαλύτερου ελάχιστου μονοπατιού για όλα τα ζεύγη κόμβων του δικτύου). Όταν το δίκτυο δεν είναι συνεκτικό τότε ωσ διάμετρο θα ορίζεται η μεγαλύτερη διάμετρος των υποδικτύων που αποτελούν το δίκτυο.

 

Ελπίζω να μην σας κούρασα. Οτιδήποτε βοήθεια (κώδικας) ή προτάσεις είναι αποδεκτές

bokarinho Proficient

bokarinho

Δημοσ.
Δημοσ.

Ας ξεκινήσουμε σταδιακά, ο παρακάτω κώδικας δημιουργεί ένα σύνολο από τυχαίους Ν κόμβους τους οποίους του θεωρώ σαν σημεία στο επίπεδο. Οι κόμβοι αυτοί είναι τυχαίοι και οφείλουν να είναι μοναδικά σημεία, για αυτό και θα πρέπει να μην δημιουργηθούν 2 ή και παραπάνω ίδιοι κόμβοι. Οι κόμβοι αυτοί αφού δημιουργηθούν αποθηκεύονται σε ένα πίνακα και με την συνάρτηση που ακολουθεί υπολογίζουμε την Ευκλείδια απόσταση ανάμεσα σε 2 κόμβους. Ελπίζω να σε βοηθάω μέχρι στιγμής, βρωμάει η άσκηση για γράφους αλλά ας δούμε τι θα κάνουμε. Περιμένω σχόλια σου.

 

>
//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

/* Global Structure for Our Nodes. Each Node is a simple Point. */

typedef struct _Point{
float CordX;
float CordY;
}Point;
//---------------------------------------------------------------------------

/* Functions */

Point *CreateNodes(const int N, int Lower, int Upper)
{
if(N)
{
	/* Get memory for the whole Nodes. */
	Point *Nodes = calloc(N, sizeof(Point));
	if(!Nodes)
	{
		fprintf(stderr,"CreateNodes(): Memory Fault.\n");
		return NULL;
	}
	else
	{
		int i, j, Width = Upper - Lower;
		float randomX = 0, randomY = 0;
		srand(time(NULL));
		for(i = 0; i < N; i++)
		{
			while(1)
			{
				randomX = ((double)rand() / (double)RAND_MAX)*Width + Lower;
				randomY = ((double)rand() / (double)RAND_MAX)*Width + Lower;
		  //		printf("%f %f\n", randomX, randomY);
				for(j = 0; j < i && Nodes[j].CordX != randomX && Nodes[j].CordY != randomY; j++);
				if(j == i)
				{
					Nodes[i].CordX = randomX;
					Nodes[i].CordY = randomY;
					break;
				}
			}
		}
		/* Return the Nodes */
		return i == N ? Nodes : NULL;
	}
}
else
{
	fprintf(stderr, "CreateNodes(): Invalid N Parameter.\n");
	return NULL;
}
}
/* Print the Nodes. */
void PrintNodes(const Point *p, int N)
{
int i;
printf("Our Nodes:\n");
for(i = 0; i < N; i++)
	printf("Node[%d]: CorX = %.3f, CorY = %.3f\n", i, p[i].CordX, p[i].CordY);
}
void FreeNodes(Point *p)
{
free(p);
}

float EukleidianDistance(Point *p1, Point *p2)
{
return sqrt(pow(fabs((*p2).CordY - (*p1).CordY),2) + (fabs((*p2).CordX - (*p1).CordX),2));
}
int main(int argc, char* argv[])
{
Point *Nodes = CreateNodes(10, 2,5);
PrintNodes(Nodes, 10);
printf("Distance between Node[0] and Node[1] is: %.3f\n", EukleidianDistance(&Nodes[0], &Nodes[1]));
FreeNodes(Nodes);
printf("Hit enter to end....");
getchar();
return 0;
}
//---------------------------------------------------------------------------

 

Τυπωμένα αποτελέσματα:

 

Our Nodes:

Node[0]: CorX = 3.334, CorY = 3.336

Node[1]: CorX = 2.597, CorY = 3.262

Node[2]: CorX = 3.195, CorY = 2.204

Node[3]: CorX = 4.784, CorY = 2.988

Node[4]: CorX = 3.573, CorY = 4.170

Node[5]: CorX = 3.358, CorY = 4.888

Node[6]: CorX = 2.497, CorY = 4.128

Node[7]: CorX = 3.793, CorY = 3.385

Node[8]: CorX = 3.662, CorY = 4.731

Node[9]: CorX = 3.679, CorY = 2.686

Distance between Node[0] and Node[1] is: 1.416

Hit enter to end....

 

Το πρόγραμμα έχει ξεκινήσει να υλοποιείται σε TurboC++ Compiler της Borland σε περιβάλλον Windows XP Pro SP2 En.

toshibam8 Proficient

toshibam8

Δημοσ.
Δημοσ.

Ευχαριστώ bokarinho για τα πρώτα σχόλια σου και με βρίσκεις απόλυτα σύμφωνο.Αυτό που με προβληματίζει όμως είναι ο τρόπος που το πρόγραμμα θα πρέπει να μπορεί να υπολογίζει όλα τα μονοπάτια για όλα τα ζεύγη των κόμβων και στη συνέχεια να επιλέγει τη διάμετρο D του δικτύου (μήκος του μεγαλύτερου ελάχιστου μονοπατιού για όλα τα ζεύγη κόμβων του δικτύου). (παρατήρηση :Όταν το δίκτυο δεν είναι συνεκτικό τότε ως διάμετρο θα ορίζεται η μεγαλύτερη διάμετρος των υποδικτύων που αποτελούν το δίκτυο.)

Περιμένω με χαρα να ακούσω την άποψη σου.Αν σε βολεύει να συμπληρώσεις τον κώδικα θα με διευκόλυνες αφάνταστα γιατί τον βρήκα πολύ ωραία δομημένο (εγώ είμαι κάπως αρχάριος!)

warchief Proficient

warchief

Δημοσ.
Δημοσ.

@bokarinho: Πραγματικά καταλαβαίνω όλη σου την καλή διάθεση, αλλα πραγματικά πιστεύεις πως βοηθάς τον χρήστη toshibam8 απλά σερβίροντας του την λύση στο πιάτο (ή τουλάχιστον μεγάλο μέρος της);

bokarinho Proficient

bokarinho

Δημοσ.
Δημοσ.

Στην νέα έκδοση που ακολουθεί προστέθικε ο υπολογισμός από ένα συγκεκριμένο κόμβο των αποστάσεων σε σχέση με όλους τους υπόλοιπους και με βάση το κριτήριο της ζεύξης αν υπάρχει η ελάχιστη απόσταση r. Τώρα δεν μπορώ να καταλάβω το τι ακριβώς το τι θέλει η άσκηση σου και το πως σας έχει υποδείξει ο καθηγητής ή δεν ξέρω ποιος να συνεχίσετε, μήπως θα πρέπει να με βοηθήσεις με ακριβέστερες πληροφορίες, πχ αν είναι να υλοποιήσουμε γράφους να το ξέρουμε για να μπούμε σε μία λογική να δημιουργήσουμε λίστες που θα δημιουργήσουν τους γράφους κτλ.

 

>
//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

/* Global Structure for Our Nodes. Each Node is a simple Point. */

typedef struct _Point{
float CordX;
float CordY;
/* Node ID */
int Identity;
}Point;
//---------------------------------------------------------------------------

/* Functions */

Point *CreateNodes(const int N, int Lower, int Upper)
{
if(N)
{
	/* Get memory for the whole Nodes. */
	Point *Nodes = calloc(N, sizeof(Point));
	if(!Nodes)
	{
		fprintf(stderr,"CreateNodes(): Memory Fault.\n");
		return NULL;
	}
	else
	{
		int i, j, Width = Upper - Lower;
		float randomX = 0, randomY = 0;
		srand(time(NULL));
		for(i = 0; i < N; i++)
		{
			while(1)
			{
				randomX = ((double)rand() / (double)RAND_MAX)*Width + Lower;
				randomY = ((double)rand() / (double)RAND_MAX)*Width + Lower;
		  //		printf("%f %f\n", randomX, randomY);
				for(j = 0; j < i && Nodes[j].CordX != randomX && Nodes[j].CordY != randomY; j++);
				if(j == i)
				{
					Nodes[i].CordX = randomX;
					Nodes[i].CordY = randomY;
					/* Initialise Identity of Each Node, will be like a name. */
					Nodes[i].Identity = i;
					break;
				}
			}
		}
		/* Return the Nodes */
		return i == N ? Nodes : NULL;
	}
}
else
{
	fprintf(stderr, "CreateNodes(): Invalid N Parameter.\n");
	return NULL;
}
}
/* Print the Nodes. */
void PrintNodes(const Point *p, int N)
{
int i;
printf("Our Nodes:\n");
for(i = 0; i < N; i++)
	printf("Node[%d]: CorX = %.3f, CorY = %.3f\n", p[i].Identity, p[i].CordX, p[i].CordY);
}
void FreeNodes(Point *p)
{
free(p);
}

float EukleidianDistance(Point *p1, Point *p2)
{
return sqrt(pow(fabs((*p2).CordY - (*p1).CordY),2) + (fabs((*p2).CordX - (*p1).CordX),2));
}
/* Calculate all the  distances from node with nodeId, save those that are lower to r .*/
float *CalculateDistancesFromNode(Point *Nodes, const int N, int NodeId, const float r, int *Connections)
{
/* Declare Variables. */
int i, j = 0;
float *Dist = calloc(1, sizeof(float));
float distance = 0.0;
if(NodeId < 0)
	NodeId = -NodeId;
if(NodeId > N)
	return NULL;
if(!Dist)
	return NULL;
/* Calculate and save it. */
for(i = 0; i < N; i++)
{
	if(i == NodeId)
		continue;
	else
	{
		if((distance = EukleidianDistance(&Nodes[NodeId], &Nodes[i])) <= r && Dist)
		{
			Dist[j++] = distance;
			Dist = realloc(Dist, (j+1) * sizeof(float));
		}
	}
}
/* Return the Distance Array. */
*Connections = j;
return i == N ? Dist : NULL;

}
int main(int argc, char* argv[])
{
int i = 0;
int countConnections = 0;
float *DistFrom3dNode = NULL;
Point *Nodes = CreateNodes(10, 2,5);
PrintNodes(Nodes, 10);
/* Calculate  the distances for a node, eg with Node #3 */
DistFrom3dNode = CalculateDistancesFromNode(Nodes, 10, 3, 1.6, &countConnections);
for(i = 0; i < countConnections; i++)
	printf("Distance from 3d node to others with rmin = 1.6: %.3f\n", DistFrom3dNode[i]);
/* Free memory before exit. */
free(DistFrom3dNode);
FreeNodes(Nodes);
printf("Hit enter to end....");
getchar();
return 0;
}
//---------------------------------------------------------------------------

 

Τυπωμένα αποτελέσματα:

 

Our Nodes:

Node[0]: CorX = 2.956, CorY = 3.729

Node[1]: CorX = 3.839, CorY = 4.086

Node[2]: CorX = 4.653, CorY = 4.913

Node[3]: CorX = 3.614, CorY = 3.875

Node[4]: CorX = 3.319, CorY = 4.638

Node[5]: CorX = 4.532, CorY = 3.466

Node[6]: CorX = 4.520, CorY = 2.285

Node[7]: CorX = 2.909, CorY = 2.028

Node[8]: CorX = 3.453, CorY = 3.679

Node[9]: CorX = 4.626, CorY = 4.317

Distance from 3d node to others with rmin = 1.6: 1.422

Distance from 3d node to others with rmin = 1.6: 1.430

Distance from 3d node to others with rmin = 1.6: 1.472

Distance from 3d node to others with rmin = 1.6: 1.428

Distance from 3d node to others with rmin = 1.6: 1.482

Hit enter to end....

 

Bokarinho!!

bokarinho Proficient

bokarinho

Δημοσ.
Δημοσ.
@bokarinho: Πραγματικά καταλαβαίνω όλη σου την καλή διάθεση, αλλα πραγματικά πιστεύεις πως βοηθάς τον χρήστη toshibam8 απλά σερβίροντας του την λύση στο πιάτο (ή τουλάχιστον μεγάλο μέρος της);

 

Σωστά μιλάς, δεν έχω σκοπό να του λύσω όλη την άσκηση, ίσως όμως λύνοτας ένα μέρος της:

1. Να καταφέρει να την συνεχίσει - τροποποιήσει - ολοκληρώσει.

2. Να μάθει κάτι εφόσον παραδέχεται ότι είναι αρχάριος πάνω σε C.

 

Πάντως δεν έχω σκοπό να κάνω όλη την άσκηση, δεν το επιδιώκω και δεν έχω και το χρόνο.

turbo_amd Proficient

turbo_amd

Δημοσ.
  • Μέλος
Δημοσ.

Επειδή η εργασία είναι εξ απόστασης από το λίγο που μίλισα με τον καθηγητή κατάλαβα ότι είναι να υλοποιήσουμε γράφους δηλαδή να δημιουργήσουμε λίστες που θα δημιουργήσουν τους γράφους.Αυτό είναι το πρώτο κομμάτι της εργασίας και απλά ήθελα μια βοήθεια για να μπω λίγο στο σκεπτικό του προγραματισμού.Δεν έχω σκοπό να σας πρήξω για να μου κάνετε ολόκληρη την άσκηση.Όποιος έχει την καλή διάθεση και το χρόνο να με βοηθήσει με τον κώδικα είναι ευπρόσδεκτος.Ουτως η άλλως ο δικός μου κώδικας θα είναι πιο απλοποιημένος!!

bokarinho Proficient

bokarinho

Δημοσ.
Δημοσ.
Επειδή η εργασία είναι εξ απόστασης από το λίγο που μίλισα με τον καθηγητή κατάλαβα ότι είναι να υλοποιήσουμε γράφους δηλαδή να δημιουργήσουμε λίστες που θα δημιουργήσουν τους γράφους.Αυτό είναι το πρώτο κομμάτι της εργασίας και απλά ήθελα μια βοήθεια για να μπω λίγο στο σκεπτικό του προγραματισμού.Δεν έχω σκοπό να σας πρήξω για να μου κάνετε ολόκληρη την άσκηση.Όποιος έχει την καλή διάθεση και το χρόνο να με βοηθήσει με τον κώδικα είναι ευπρόσδεκτος.Ουτως η άλλως ο δικός μου κώδικας θα είναι πιο απλοποιημένος!!

 

Το περίμενα, δύσκολα τα πράγματα για να δωθεί λύση στην άσκηση σου θα πρέπει να υλοποιηθεί η μονά συνδεδεμένη λίστα για να υλοποιήσεις αργότερα τον Γράφο σου, για να υλοποιήσεις αργότερα και μία dfs ή bfs ή ότι χρειάζεται. Οι ασκήσεις αυτές δεν είναι απλές ασκήσεις σε λίγο κώδικα για να σου δώσει κάποιος ένα tip ή να σου γράψει λίγο κώδικα, λυπάμαι αλλά δεν έχω τον τόσο χρόνο να σε βοηθήσω, θεωρητικά μπορώ να σου πω ότι θέλεις αλλά πρακτικά όπως και στον Huffman είναι λίγο δύσκολο να κάνω κάτι για όλη την εργασία.

toshibam8 Proficient

toshibam8

Δημοσ.
Δημοσ.

Μπορείς να μου εξηγήσεις κάποια πράγματα έστω θεωρητικά για να καταλάβω πως πρέπει να το υλοποιήσω?Δηλαδή το σκεπτικό πως θα επιλύσω τη βέλτιστη διαδομή.

Επίσης αν γνωρίζεις κάποιο καλό βιβλίο που θα μπορούσα να διαβάσω κάποια πράγματα ευχαρίστως.

Αρχειοθετημένο

Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.

Προς την λίστα θεμάτων
  • Δημιουργία νέου...