Αλγόριθμοι Προβλήματα

[strat92man]

Καλησπέρα,

 

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

 

Γιατί το θέλω;

Μαθαίνω στο Πανεπιστήμιο να λύνω προβλήματα με αλγόριθμους, είτε αναζήτησης,ταξινόμησης,αλγόριθμοι γραφημάτων ΑΠΒ-ΑΠΠ σχετικά με δέντρα AVl,B,RB και κτλ Dijkstra,Prim,Krustal κτλ κτλ κτλ Furier Κτλ κτλ ....

οκ λύνω στο χαρτί τις ασκήσεις γράφω 10 χαίρομαι αλλά νιώθω ότι δεν έχω μάθει τίποτα πάνω στο computer πως χρησιμοποιούνται σε αληθινά μεγάλα προβλήματα..ΟΛΑ τα βιβλία αλγορίθμων (που έχω δει) σου έχουν κώδικα 10-15 γραμμές τον αλγόριθμο που προσωπικά δεν με βοηθάει να καταλάβω την ουσία απλά πως δουλεύει ο αλγόριθμος τι κάνει..

 

ε..?

 

θενκσ

[harry_fyt]

Θυμάμαι όταν διάβασα κι εγώ αλγορίθμους είχα παρόμοιο θέμα. Αυτό που με βοήθησε να καταλάβω την ουσία και το πως δουλεύουν ήταν το YouTube. Κάνε μια αναζήτηση κ θα εκπλαγεις.

[migf1]

Καλησπέρα,

 

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

 

Γιατί το θέλω;

Μαθαίνω στο Πανεπιστήμιο να λύνω προβλήματα με αλγόριθμους, είτε αναζήτησης,ταξινόμησης,αλγόριθμοι γραφημάτων ΑΠΒ-ΑΠΠ σχετικά με δέντρα AVl,B,RB και κτλ Dijkstra,Prim,Krustal κτλ κτλ κτλ Furier Κτλ κτλ ....

οκ λύνω στο χαρτί τις ασκήσεις γράφω 10 χαίρομαι αλλά νιώθω ότι δεν έχω μάθει τίποτα πάνω στο computer πως χρησιμοποιούνται σε αληθινά μεγάλα προβλήματα..ΟΛΑ τα βιβλία αλγορίθμων (που έχω δει) σου έχουν κώδικα 10-15 γραμμές τον αλγόριθμο που προσωπικά δεν με βοηθάει να καταλάβω την ουσία απλά πως δουλεύει ο αλγόριθμος τι κάνει..

 

ε..?

 

θενκσ

Τα βιβλία αλγορίθμων προϋποθέτουν να γνωρίζεις ήδη κάποια γλώσσα προγραμματισμού, παρόλο που τα περισσότερα από αυτά δεν εστιάζουν σε καμία γλώσσα. Θα πρέπει πρώτα να μάθεις μια γλώσσα προγραμματισμού με άλλο βιβλίο γραμμένο για αυτό τον σκοπό, και κατόπιν να επιστρέψεις στους αλγόριθμους για να τους υλοποιήσεις με τη γλώσσα που έμαθες.

[strat92man]

@migf1 !! Ξέρω προγραμματισμό αρκετά καλό!!!!!!

 

? πως σου ήρθε αυτό !?!? :-D

[migf1]

@migf1 !! Ξέρω προγραμματισμό αρκετά καλό!!!!!!

 

? πως σου ήρθε αυτό !?!? :-D

 

Και μένα μου έκανε εντύπωση να μαθαίνετε djikstra χωρίς να ξέρετε μια γλώσσα, αλλά είπα μήπως είναι κάνα εξωτικό μάθημα σε κάποιον θεωρητικό κλάδο.

 

Οπότε, εφόσον ξέρεις προγραμματισμό και μάλιστα αρκετά καλό, που είναι το πρόβλημα;

[nilosgr]

Ελπιζω να μην με κυνηγαει ο καθηγητης μου...

 

Εισαγωγή

Μετά από την όγδοη φορά που χάθηκε ανάμεσα στους ουρανοξύστες προσπαθώντας να βρει πού

γινόταν μια ληστεία, ο Spiderman αποφάσισε πως ήταν καιρός να προσαρμόσει ένα GPS στη στολή

του. Δυστυχώς όμως το GPS δε μπορούσε να του πει με αξιοπιστία αν υπάρχει τρόπος να πάει από ένα

σημείο σε ένα άλλο "πηδώντας" από ουρανοξύστη σε ουρανοξύστη, κι αν ναι, ποια είναι η πιο

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

εφαρμογής. Ο νικητής του διαγωνισμού θα έχει την τιμή να γίνει ο προσωπικός προγραμματιστής του

Spiderman με τη δυνατότητα να προσληφθεί και από άλλους ιπτάμενους υπερήρωες (Superman, κτλ.)

 

Περιγραφή πρώτου σταδίου

Σε μια πόλη υπάρχουν Ν ουρανοξύστες. Δεδομένων δύο ουρανοξυστών θέλουμε να γνωρίζουμε αν

υπάρχει τρόπος να ταξιδέψει ο Spiderman από τον ένα στον άλλο. Πρέπει να λάβουμε υπόψη ότι δεν

είναι πάντα δυνατό γι΄αυτόν να "πηδήσει" άμεσα από ένα ουρανοξύστη σε κάποιο άλλο.

Δεδομένα

Υπάρχουν Ν ουρανοξύστες και θεωρούμε πως είναι αριθμημένοι από 0 έως και το Ν-1.

Οι πληροφορίες σχετικά με τη δυνατότητα σύνδεσης δύο ουρανοξυστών με ιστό αράχνης δίνονται με

τη μορφή ενός ΝxN πίνακα, όπου η θέση (i, j) περιέχει 1 αν ο Spiderman μπορεί να ταξιδέψει άμεσα

από τον i στον j.

Τα δεδομένα του προγράμματος δίνονται σε ένα αρχείο με την εξής μορφή:

• Στην πρώτη γραμμή του αρχείου δίνεται το πλήθος των ουρανοξυστών, Ν.

• Στις επόμενες Ν γραμμές δίνονται τα στοιχεία του πίνακα (Ν ακέραιοι ανά γραμμή, με κενό

ανάμεσα σε κάθε δύο διαδοχικούς ακεραίους).

• Στιν επόμενη γραμμή δίνονται δύο ακέραιοι χωρισμένοι με κενό, όπου ο πρώτος είναι ο αύξων

αριθμός του ουρανοξύστη από όπου ξεκινά ο Spiderman και ο δεύτερος είναι ο αύξων αριθμός

του ουρανοξύστη-προορισμού.

Το όνομα του αρχείου δίνεται ως όρισμα του προγράμματος στη γραμμή εντολής.

Η ανάγνωση και επαλήθευση όλων των δεδομένων πρέπει να γίνεται μέσα σε μία συνάρτηση η οποία

παίρνει ως παραμέτρους : το δείκτη σε FILE για το αρχείο εισόδου, τη διεύθυνση της μεταβλητής στην

οποία θα αποθηκευτεί το πλήθος των ουρανοξυστών, τη διεύθυνση της μεταβλητής στην οποία θα

αποθηκευτεί η αφετηρία και τη διεύθυνση της μεταβλητής στην οποία θα αποθηκευτεί ο προορισμός.

Η συνάρτηση πρέπει να επιστρέφει ένα δυναμικά δεσμευμένο διδιάστατο πίνακα (με άλλα λόγια, ο

πίνακας είναι τύπου int **) που περιέχει τις πληροφορίες για τις συνδέσεις ανάμεσα στους

ουρανοξύστες. Είναι απαραίτητο ο πίνακας να είναι δυναμικά δεσμευμένος γιατί δε γνωρίζουμε εκ

των προτέρων πόσοι είναι οι ουρανοξύστες.

Εύρεση διαδρομής

Η ανίχνευση του αν υπάρχει ή όχι διαδρομή ανάμεσα στην αφετηρία και τον προορισμό θα πρέπει να

γίνεται μέσω μιας αναδρομικής συνάρτησης. Σκεφτείτε πως αν γνωρίζουμε ότι από τον ουρανοξύστη

που βρίσκεται κάποια χρονική στιγμή ο Spiderman μπορεί να πάει άμεσα σε συγκεκριμένους άλλους,

τότε αρκεί να λύσουμε το πρόβλημα αναδρομικά, θεωρώντας αυτούς τους γειτονικούς ουρανοξύστες

ως αφετηρία.

Επίσης, φροντίστε να μην επισκέπτεστε ουρανοξύστες που έχουν ήδη εξεταστεί.

Αρκεί να βρεθεί αν υπάρχει ή όχι διαδρομή - δε χρειάζεται να βρείτε ποια είναι αυτή.

 

Ανίχνευση λαθών και μηνύματα

Το πρόγραμμά σας δεν πρέπει ποτέ να τερματίζει πρόωρα (με άλλα λόγια μη χρησιμοποιήσετε exit).

Κάθε φορά που ανιχνεύεται κάποιο λάθος πρέπει να εκτυπώνεται ένα κατάλληλο μήνυμα και η

συνάρτηση να επιστρέφει κατάλληλη τιμή. Τα μηνύματα που πρέπει να εκτυπώνονται σε κάθε

περίπτωση λάθους είναι:

• Αν δεν έχει προσδιοριστεί το αρχείο στη γραμμή εντολής:

◦ Speficy input file

• Αν υπάρχει πρόβλημα στην ανάγνωση του αρχείου:

◦ Could not open "F" for reading (όπου F το όνομα του αρχείου)

• Αν το πλήθος των ουρανοξυστών δεν είναι θετικός αριθμός:

◦ Number of buildings should be positive

• Αν η αφετηρία ή ο προορισμός δεν είναι εντός του δυνατού πλήθους ουρανοξυστών

◦ Building out of range

• Αποτυχία δέσμευσης μνήμης:

◦ Error in memory allocation

Αν το πρόγραμμα βρει ότι υπάρχει διαδρομή ανάμεσα στην αφετηρία και τον προορισμό, τότε

εκτυπώνει στην οθόνη τη λέξη YES, διαφορετικά εκτυπώνει στην οθόνη τη λέξη NO.

Στο τέλος εκτυπώνεται μια κενή γραμμή.