Εργαστήριο Τεχνολογίας Λογισμικού
+1 vote
472 views

Γεια σας,
Έχει ειπωθεί στο μάθημα ότι για την 2η άσκηση του 1ου εργαστηριου θα χρειαστούμε union find δομή δεδομένων. Βρήκα την disjoint_set του πακέτου BOOST αλλά τίποτα άλλο ούτε στην STL. 1ον υπάρχει κάποια άλλη λύση εκτός από το BOOST (και φυσικά να το υλοποιήσουμε εκ του μηδενός)? 2ον Πώς θα χρησιμοποιήσουμε το BOOST και θα υπάρχει κάποιο θέμα με τον Grader? 3ον Το BOOST γράφει ότι το disjoint_set είναι παλιός κώδικας αλλά δεν φαίνεται να υπάρχει κάπου στην τελευταία του έκδοση? Μήπως υπάρχει με άλλο όνομα? Πρέπει να κατεβάσω την παλιά έκδοση?
https://www.boost.org/doc/libs/1_54_0/libs/disjoint_sets/disjoint_sets.html

in algorithms by (730 points) | 472 views

2 Answers

+3 votes
Best answer

Να το υλοποιήσετε εκ του μηδενός. Είναι 10 γραμμές κώδικα, και δεν απαιτεί τη χρήση καμίας βιβλιοθήκης. Ο χρόνος που καταναλώνουμε εδώ για το θέμα είναι πολύ μικρότερος από τον χρόνο που χρειάζεται να τον υλοποιήσετε (μόνοι σας), ώστε να καταλάβετε και την union-find (που είναι μέρος της ύλης).

by (2.5k points)
selected by
0

Φυσικά, η ερώτηση αφορά για να καταλάβουμε γενικότερα πότε πρέπει κάτι να το κάνουμε μόνοι μας και πότε όχι. Ευχαριστώ πολύ για την απάντηση!

+3 votes
  • Δεν υπάρχει κάποια άλλη γνωστή βιβλιοθήκη εκτός του BOOST (δεν το έχω χρησιμοποιήσει και ποτέ)

  • Το boost πρέπει να το εγκαταστήσεις στο μηχάνημά σου και έπειτα να κάνεις #include τα headers του -- όσον αφορά την εγκατάστασή του ψάξε στο διαδίκτυο. Ο grader νομίζω 99% δεν έχει αυτή τη βιβλιοθήκη

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

by (3.0k points)
edited by
+2

Μπορείς να ρίξεις μια ματιά σε αυτό:

GitHub - rakeshgk/Union-Find

0

Ευχαριστώ πολύ για την γρήγορη απάντηση. Βρήκα και εγώ πολλές έτοιμες υλοποιήσεις στο ίντερνετ, οι περισσότερες χρησιμοποιούν την έτοιμη map της STL. Όμως μπερδεύτηκα λιγάκι επειδή ο κύριος Φωτάκης είχε πει ξεκάθαρα στο μάθημα να μην χρησιμοποιήσουμε κώδικα έτοιμο από άλλους, αλλά να χρησιμοποιήσουμε ελεύθερα βιβλιοθήκες. Εννοεί με αυτό ότι επιτρέπεται να πάρουμε έτοιμη τη δομή δεδομένων, αλλά όχι να βρούμε κάποιο κομμάτι κώδικα του κυρίως αλγορίθμου; (μάλιστα αναφέρθηκε και ότι θα κάνει χρήση αυτόματου anti-plagiarism εργαλείου)

0

καλό είναι να μην κάνεις copy paste :P μπορείς να βρείς κάτι και να το έχεις ως αναφορά αλλά ως εκεί

301 questions

289 answers

288 comments

909 users