freestuff.gr αρχική σελίδα
 FAQFAQ    ΑναζήτησηΑναζήτηση   Λίστα ΜελώνΛίστα Μελών   Ομάδες ΜελώνΟμάδες Μελών   <b>Εγγραφή Μέλους</b>Εγγραφή Μέλους 
 ΠροφίλΠροφίλ   Επιλογές μέλους Επιλογές   Τα bookmarks μου Τα bookmarks μου   Προσωπικά μηνύματαΠροσωπικά μηνύματα 
  διαφήμιση  

Καλώς ήρθατε στο forum μας! Για να συμμετάσχετε στις συζητήσεις θα πρέπει να είσαστε μέλος. Γίνετε μέλος τώρα!.

Γράφημα


 Forum index » Δημιουργία Web Sites, Γραφικών & Προγραμματισμός » Γλώσσες Προγραμματισμού » C, C++
Moderators:  Super-Moderators, WebDev Moderators
Εισαγωγή νέου Θέματος   Απάντηση στο Θέμα Σελίδα 1 από 1 [3 Μηνύματα]       Mark the topic unread :: Προηγούμενο θέμα :: Επόμενο θέμα
ΑποστολέαςΜήνυμα
ethnikos


Μέλος από: 03 Μαρ 2006
Μηνύματα: 39

View users profile
ΜήνυμαΣτις: 03 Μαρ 2006 16:59    Θέμα: Γράφημα Απάντηση με παράθεση  Mark this post and the followings unread

askisi se c
κώδικας:
http://rapidshare.de/files/14586710/___________4.doc.html
ethnikos


Μέλος από: 03 Μαρ 2006
Μηνύματα: 39

View users profile
ΜήνυμαΣτις: 04 Μαρ 2006 10:52    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

AFTI EINAI I ASKISI XORIS TIS 2 EIKONES....GIA NA TIN DEITE OLI KATEVASTE TO ARXEIO DOC
----------------------------------
Ένα από τα πιο θεμελιώδη μαθηματικά αντικείμενα, με πλήθος εφαρμογών στην Επιστήμη των Υπολογιστών, είναι το Γράφημα. ¨Ένα γράφημα αποτελείται από έναν αριθμό αντικειμένων, τις κορυφές, και έναν αριθμό συνδέσεων μεταξύ ζευγών των αντικειμένων αυτών, τις ακμές. Ένα παράδειγμα γραφήματος είναι το ακόλουθο:

Το γράφημα αυτό θα μπορούσε να αναπαριστά, για παράδειγμα, 5 πόλεις και τους εθνικούς δρόμους που τις συνδέουν, εάν υπάρχουν (η πόλη 2, που δεν φαίνεται να συνδέεται με τις άλλες, μπορεί να βρίσκεται, π.χ. σε κάποιο νησί).
Ένα γράφημα έχει μία πολύ κομψή και εύχρηστη αναπαράσταση με ένα διδιάστατο (2D) πίνακα, που ονομάζεται πίνακας γειτνίασης, στον οποίο η θέση (i,j) περιέχει 0 εάν δεν υπάρχει σύνδεση μεταξύ των κορυφών i και j ενώ εάν υπάρχει σύνδεση, η θέση (i,j) περιέχει 1. Στο παράδειγμα μας, το γράφημα μπορεί να αναπαρασταθεί με έναν 5 Χ 5 πίνακα ως εξής:

Κοιτώντας, για παράδειγμα, την πρώτη γραμμή βλέπουμε ότι η κορυφή 1 συνδέεται με τις κορυφές 4 και 5. Λέμε τότε, ότι ο βαθμός (degree) της είναι ίσος με 2, καθώς συνδέεται με 2 κορυφές. Κοιτώντας τη δεύτερη γραμμή, βλέπουμε ότι η κορυφή 2 δεν συνδέεται με καμία από τις υπόλοιπες κορυφές, πρόκειται δηλαδή για απομονωμένη κορυφή (κορυφή βαθμού 0). Παρατηρήστε ότι ο πίνακας είναι συμμετρικός, δηλαδή εάν υπάρχει 1 (0) στη θέση (i,j) τότε υπάρχει 1 (0) και στη θέση (j,i) (οι συνδέσεις, δηλαδή, είναι αμφίδρομες).
ΣΚΟΠΟΣ
Α) Σχεδιάστε και υλοποιήστε πρόγραμμα σε γλώσσα προγραμματισμού C με τις εξής προδιαγραφές:
1. Να ορίζει ένα διδιάστατο(2D) πίνακα γειτνίασης με NODES στήλες και NODES γραμμές, στον οποίο θα αναπαριστά ένα γράφημα NODES κορυφών (το NODES θα ορίζεται στην αρχή ως σταθερά). Στο παράδειγμα μας πιο πάνω, θα είχαμε πίνακα NODES X NODES= 5 Χ 5.
2. Να ορίζει ένα μονοδιάστατο(1D) πίνακας διάστασης NODES που θα καλείται degrees(βαθμοί). Πάλι στο παράδειγμα μας, ο πίνακας αυτός θα είχε διάσταση NODES=5.
3. Να περιέχει μία συνάρτηση που θα διαβάζει, ένα-ένα, από το πληκτρολόγιο τα στοιχεία του πίνακα γειτνίασης (0 και 1). Θα περιέχει, επίσης, μία συνάρτηση που θα τυπώνει τον πίνακα γειτνίασης στην οθόνη, γραμμή-γραμμή. Στο παράδειγμα μας, θα πρέπει να τυπωθούν NODES=5 γραμμές, κάθε μία από τις οποίες θα περιέχει 5 σύμβολα, 0 ή 1 (χωρισμένα με κενό ή τον χαρακτήρα «,» για παράδειγμα).
4. Να περιέχει μία συνάρτηση που θα υπολογίζει και θα τυπώνει στην οθόνη τους βαθμούς των NODES κορυφών, αποθηκεύοντας τους ταυτόχρονα στον πίνακα degrees. Θα περιέχει, επίσης, δύο άλλες συναρτήσεις που θα επιστρέφουν τους αριθμούς των κορυφών (μπορεί αυτές οι κορυφές να συμπίπτουν σε κάποιους τύπους γραφημάτων!) με το μέγιστο και ελάχιστο βαθμό αντίστοιχα μαζί με το βαθμό τους.
5. Να περιέχει μία συνάρτηση που θα βρίσκει τις απομονωμένες κορυφές του γραφήματος.
Β) Η μεταβατική κλειστότητα (transitive closure) ενός γραφήματος είναι ένας πίνακας R με περιεχόμενα 0 και 1 τέτοιος ώστε R[i,j]=1 μόνον εάν υπάρχει κάποιο μονοπάτι (σύνδεση) μεταξύ των κορυφών i και j του γραφήματος. Σε διαφορετική περίπτωση, R[i,j]=0. Ένας αλγόριθμος για τον υπολογιστή της μεταβατικής κλειστότητας είναι και ο αλγόριθμος Floyd-Warshall:
Είσοδος: Ο πίνακας γειτνίασης Α ενός γραφήματος n κορυφών.
Έξοδος: Ο πίνακας R της μεταβατικής κλειστότητας του γραφήματος.
/* Η αρίθμηση των κορυφών είναι 1,Κ , n. */
R<- A/* Πρώτα αντιγράφουμε τον πίνακα Α στον πίνακα R. */
ΓΙΑ k=1 ΕΩΣ n ΕΠΑΝΕΛΑΒΕ
ΓΙΑ i=1 ΕΩΣ n ΕΠΑΝΕΛΑΒΕ
ΓΙΑ j=1 ΕΩΣ n ΕΠΑΝΕΛΑΒΕ
ΕΑΝ R[i,k]=1 ΚΑΙ R[k,j]=1 ΤΟΤΕ R[i.j]<-1
Υλοποιήστε τον πιο πάνω αλγόριθμο με μία συνάρτηση που δέχεται ως είσοδο δύο πίνακες, Α (πίνακας γειτνίασης) και R (όπου θα επιστρέφεται η έξοδος). Μετά την εκτέλεση της συνάρτησης, ο πίνακας R θα πρέπει να περιέχει τη μεταβατική κλειστότητα του γραφήματος με πίνακα γειτνίασης Α. Δώστε, επίσης, και μία εκτίμηση της πολυπλοκότητας του αλγόριθμου σας ως συνάρτηση του αριθμού των κορυφών του γραφήματος.
Για να ελέγξετε τις απαντήσεις σας στο Α και στο Β πιο πάνω, χρησιμοποιήστε ως είσοδο το γράφημα-παράδειγμα που δίνεται στην εκφώνηση της υποεργασίας.
ethnikos


Μέλος από: 03 Μαρ 2006
Μηνύματα: 39

View users profile
ΜήνυμαΣτις: 05 Μαρ 2006 11:13    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

Opios den borei olokliri tin askisi as lisi mono ena meros tis....please einai poli simandiko
Εμφάνιση Μηνυμάτων:   
Εισαγωγή νέου Θέματος   Απάντηση στο Θέμα Σελίδα 1 από 1 [3 Μηνύματα] Mark the topic unread :: Προηγούμενο θέμα :: Επόμενο θέμα
 Forum index » Δημιουργία Web Sites, Γραφικών & Προγραμματισμός » Γλώσσες Προγραμματισμού » C, C++
Τώρα είναι 21 Ιαν 2017 12:43 | All times are UTC + 2


Email This Page to Someone! add to Favorites

     Powered by p h p B B © 2001,2005 p h p B B Group
Για άμεση επικοινωνία με τον διαχειριστή του freestuff.gr στο email: freestuff.gr(παπάκι)gmail.com


Copyright © 1999-2013 Freestuff.gr All Rights Reserved  
Version Aegean, designed by N. Tsaganos