[Δομημένος Προγρ.] Εργασια C

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Admins]

Για αλλαγή του public name σας, επικοινωνήστε με έναν από τους Admins.

[AckermanMik]

Άσκηση C

       Σε ένα γράφημα που αποτελείται από Ν κορυφές, οι κορυφές του αριθμούνται από το 0 έως το Ν-1. Οι κορυφές του γραφήματος συνδέονται με ακμές κάθε μια από τις οποίες έχει ένα ορισμένο βάρος. Για το γράφημα αυτό ζητείται, εκκινώντας από μια δεδομένη κορυφή, να βρεθεί ένα μονο-πάτι που να περνά, τουλάχιστον μια φορά, από κάθε κορυφή του και να έχει το ελάχιστο κόστος. Ως κόστος για το μονοπάτι θεωρείται το άθροισμα των βαρών των ακμών από τις οποίες αυτό θα περάσει.
       Ένας αλγόριθμος που θα μπορούσε να δώσει μία καλή λύση (όχι τη βέλτιστη) ξεκινά από την κορυφή εκκίνησης επιλέγοντας ως επόμενη κορυφή αυτή με την οποία συνδέεται με την ακμή που έχει το μικρότερο βάρος. Στη συνέχεια διαγράφει την ακμή και επαναλαμβάνει την ίδια διαδικασία από την νέα κορυφή. Η διαδικασία σταματά αν το μονοπάτι περάσει από όλες τις κορυφές ή αν δι-απιστωθεί ότι ο αλγόριθμος δεν μπορεί να συνεχίσει επειδή όλες οι ακμές που συνδέουν την κορυ-φή στην οποία έχει φτάσει το μονοπάτι έχουν διαγραφεί.  
       Να γραφεί το πρόγραμμα που να υλοποιεί τον πιο πάνω αλγόριθμο. Στο πρόγραμμα να οριστεί ο πίνακας, δύο διαστάσεων, adj με Ν γραμμές και Ν στήλες. Ως τιμή για το στοιχείο adj[j] του πίνακα και για i=0,…,N-1 και j=0,…,N-1, να δοθεί η τιμή 1 αν υπάρχει ακμή που να συνδέει την κορυφή i με την κορυφή j διαφορετικά ως τιμή για το adj[j] να δοθεί το 0. Στο πρόγραμμα να οριστεί ακόμη και ο πίνακας, δύο διαστάσεων, weight με Ν γραμμές και Ν στήλες. Ως τιμή για το στοιχείο weight [j] του πίνακα και για i=0,…,N-1 και j=0,…,N-1, να δοθεί το βάρος της ακμής που συνδέει την κορυφή i με την κορυφή j στην περίπτωση που υπάρχει ακμή που να συνδέει τις δυο κορυφές.
       Το πρόγραμμα να διαβάζει τα απαραίτητα στοιχεία και να σχηματίζει τους πίνακες adj και weight. Στη συνέχεια να διαβάζει τον αριθμό της κορυφής εκκίνησης και εφαρμόζοντας των αλγό-ριθμο, να βρίσκει και να τυπώνει το μονοπάτι και το αντίστοιχο βάρος.
Βοηθητικές παρατηρήσεις  
     Για τη διαγραφή μιας ακμής από το γράφημα να δίνεται η τιμή 0 στο αντίστοιχο στοιχείο του πίνακα adj.

Για την εργασία και αντίστοιχο παράδειγμα:
http://alexander.ee.auth.gr:8083/eTHMMY/cms.downloadFile.data.do?method=jsplist&PRMID=264

[vasilis1005]

Άσκηση C

       Σε ένα γράφημα που αποτελείται από Ν κορυφές, οι κορυφές του αριθμούνται από το 0 έως το Ν-1. Οι κορυφές του γραφήματος συνδέονται με ακμές κάθε μια από τις οποίες έχει ένα ορισμένο βάρος. Για το γράφημα αυτό ζητείται, εκκινώντας από μια δεδομένη κορυφή, να βρεθεί ένα μονο-πάτι που να περνά, τουλάχιστον μια φορά, από κάθε κορυφή του και να έχει το ελάχιστο κόστος. Ως κόστος για το μονοπάτι θεωρείται το άθροισμα των βαρών των ακμών από τις οποίες αυτό θα περάσει.
       Ένας αλγόριθμος που θα μπορούσε να δώσει μία καλή λύση (όχι τη βέλτιστη) ξεκινά από την κορυφή εκκίνησης επιλέγοντας ως επόμενη κορυφή αυτή με την οποία συνδέεται με την ακμή που έχει το μικρότερο βάρος. Στη συνέχεια διαγράφει την ακμή και επαναλαμβάνει την ίδια διαδικασία από την νέα κορυφή. Η διαδικασία σταματά αν το μονοπάτι περάσει από όλες τις κορυφές ή αν δι-απιστωθεί ότι ο αλγόριθμος δεν μπορεί να συνεχίσει επειδή όλες οι ακμές που συνδέουν την κορυ-φή στην οποία έχει φτάσει το μονοπάτι έχουν διαγραφεί.  
       Να γραφεί το πρόγραμμα που να υλοποιεί τον πιο πάνω αλγόριθμο. Στο πρόγραμμα να οριστεί ο πίνακας, δύο διαστάσεων, adj με Ν γραμμές και Ν στήλες. Ως τιμή για το στοιχείο adj[j] του πίνακα και για i=0,…,N-1 και j=0,…,N-1, να δοθεί η τιμή 1 αν υπάρχει ακμή που να συνδέει την κορυφή i με την κορυφή j διαφορετικά ως τιμή για το adj[j] να δοθεί το 0. Στο πρόγραμμα να οριστεί ακόμη και ο πίνακας, δύο διαστάσεων, weight με Ν γραμμές και Ν στήλες. Ως τιμή για το στοιχείο weight [j] του πίνακα και για i=0,…,N-1 και j=0,…,N-1, να δοθεί το βάρος της ακμής που συνδέει την κορυφή i με την κορυφή j στην περίπτωση που υπάρχει ακμή που να συνδέει τις δυο κορυφές.
       Το πρόγραμμα να διαβάζει τα απαραίτητα στοιχεία και να σχηματίζει τους πίνακες adj και weight. Στη συνέχεια να διαβάζει τον αριθμό της κορυφής εκκίνησης και εφαρμόζοντας των αλγό-ριθμο, να βρίσκει και να τυπώνει το μονοπάτι και το αντίστοιχο βάρος.
Βοηθητικές παρατηρήσεις  
     Για τη διαγραφή μιας ακμής από το γράφημα να δίνεται η τιμή 0 στο αντίστοιχο στοιχείο του πίνακα adj.

Για την εργασία και αντίστοιχο παράδειγμα:
http://alexander.ee.auth.gr:8083/eTHMMY/cms.downloadFile.data.do?method=jsplist&PRMID=264

το παραδειγμα που εχει με τι browser μπορουμε να το δουμε;

[PureForm]

http://alexander.ee.auth.gr:8083/eTHMMY/archive%5C102%5CdownloadFile%5C1831%5CAskisiC.doc

με λιγα λογια κατεβασε την ασκηση απο το υλικο μαθηματοσ και δεσ το απο εκει

[Μουργόλυκος]

Με explorer διαβάζεται απευθείας πάντως. Αλλά θα μου πεις γιατί να έχεις explorer στο pc σου?

[Mvp Morgul]

Έχω κολλήσει στο πόσο n να έχω όταν γίνεται ο έλεγχος και να σταματάει . Και τι παράγοντα να βάλω για να τερματίζει αν περάσει από όλες τις κορυφές.

[Μουργόλυκος]

Έχω κολλήσει στο πόσο n να έχω όταν γίνεται ο έλεγχος και να σταματάει . Και τι παράγοντα να βάλω για να τερματίζει αν περάσει από όλες τις κορυφές.

Εγώ έχω βάλει while (Π<Ν && Sum!=0)

Π: Πλήθος διαφορετικών κορυφών που έχω περάσει.
Ν: Πλήθος κορυφών
Sum: Το άθροισμα των στοιχείων της γραμμής του adj στην οποία βρισκόμαστε, δηλαδή το πόσες ακμές έχει ακόμα η κορυφή στην οποία είμαστε.

[airguitar]

Ξέρει κανεις πως βάζουμε δυνάμεις στη c χρησιμοποιώ τo pow αλλά με βγάζει (illegal use of floating point ) Μπορει να βοηθήσει κανεί;???  

Greeklish PsPs

[George_RT]

xerei kaneis pws vazoume dunameis sthn c xrisimopoiw to pow alla me bgazei (illegal use of floating point ) mporei na bohthisei kaneis ??? 

Με την συνάρτηση pow δεν μπορείς να χρησιμοποιήσεις μεταβλητές float κτλ αλλά μόνο int .
Δοκίμασε με την συνάρτηση fmod πάλι με το function <math.h>.


(Μην γράφεις greeklish)

[airguitar]

Nα σαι καλά και αυτή είναι η τελευταία φορά που γράφω με greeklish  

Greeklish PsPs

[airguitar]

H fmod είναι για το υπόλοιπο όμως >>?????

Greeklish PsPs

[AckermanMik]

h fmod einai gia to upoloipo omws >>?????

Σε παρακαλώ πολύ μη γράφεις greeklish.
Ευχαριστώ.

[George_RT]

Ναι έχεις δίκιο μπερδεύτηκα λίγο με της συναρτήσεις .

Δοκίμασα με το pow και κάνει πράξεις και με την κινητή υποδιαστολή χωρίς πρόβλημα .Μήπως έχεις κάπου άλλου πρόβλημα ; δοκίμασε επίσης αντί για float double

[Mvp Morgul]

Έχω κολλήσει στο πόσο n να έχω όταν γίνεται ο έλεγχος και να σταματάει . Και τι παράγοντα να βάλω για να τερματίζει αν περάσει από όλες τις κορυφές.

Εγώ έχω βάλει while (Π<Ν && Sum!=0)

Π: Πλήθος διαφορετικών κορυφών που έχω περάσει.
Ν: Πλήθος κορυφών
Sum: Το άθροισμα των στοιχείων της γραμμής του adj στην οποία βρισκόμαστε, δηλαδή το πόσες ακμές έχει ακόμα η κορυφή στην οποία είμαστε.

Βασικά αυτό που δεν μπορώ να κάνω είναι να μετράει σε πόσες διαφορετικές κορυφές έχει πάει για να σταματήσει . αυτο που έχεις σαν Π εσύ δηλαδή πως το όρισες;

[vasilis1005]

αφου περασει απο μια ακμη μετα πως μπορω να την διαγραψω γιατι παει και ξαναπερναει;

(χρησιμοποιησα μονο for και if μεχρι τωρα)

[Μουργόλυκος]

αφου περασει απο μια ακμη μετα πως μπορω να την διαγραψω γιατι παει και ξαναπερναει;

(χρησιμοποιησα μονο for και if μεχρι τωρα)

Βάζεις σε αυτόν το adj για εκείνη την ακμή που χρησιμοποίησες το 0 και βάζεις μια if που λες:

Code:

if(adj[i][j]=1)