Παρασκευή 5 Ιουλίου 2013

▪ 128 αντικείμενα

Ποιος είναι ο ελάχιστος αριθμός ζυγίσεων που απαιτούνται προκειμένου να διαπιστώσουμε, ποια είναι τα δύο βαρύτερα αντικείμενα από ένα πλήθος $128$ αντικειμένων; 
Αναρτήθηκε από στις 5.7.13
Ετικέτες

4 σχόλια:

  1. RIZOPOULOS GEORGIOS9 Ιουλίου 2013 στις 9:12 μ.μ.

    Ουσιαστικά η ερώτηση αντιστοιχεί στο σορτάρισμα 128 τυχαίων αντικειμένων. 128 αντικείμενα (βάρη, στην περίπτωσή μας) αντιστοιχούν σε 128! διαφορετικές μεταθέσεις. Η σύγκριση είναι δυαδικής φύσεως ,αρα το προβλημα αντιστοιχεί στην επίλυση ενός binary tree με 128! κλαδιά. ΑΔΥΝΑΤΟΝ να υπολογιστεί(ακόμη)!
    Το μόνο που μπορούμε να εκτιμήσουμε είναι το κάτω όριο (το ελάχιστο) αυτού του αριθμού.Ο συγκριτικός αλγόριθμος(αυτός που σορτάρει δηλαδή) πρέπει να συνάγει απο τις συγκρίσεις πληροφορία ώστε να καταλήξει στην σωστή (αύξουσα ή φθίνουσα) Μετάθεση (permutation). Έστω λοιπόν οτι ο αλγόριθμος τερματίζει μετά από x βήματα. Δεν μπορεί να έχει λύσειπερισσοτερew απο 2^x περιπτωσεις-συγκρίσεις γιατί κα΄θε συγκριση ειναι διακριτή και έχει 2 αποτελέσματα.
    Άρα ισχύει 2^x>=x! ή x>=log(2)του x!
    log(2)(128!)=5.040 και αυτό είναι το "κάτω όριο" στην πε΄ριπτωσή μας ,αλλά η ακριβής τιμή είναι μακριά...
    Παρεμπιπτόντως ακριβής λύση έχει βρεθεί μεχρι μόνο 15 αντικείμενα (log(2)(15!)=41. Eλάχιστες ζυγίσεις=42. Από το 16 όμως μέχρι το 128 ,υπάρχει ακόμη ψωμί! :-)

    ΑπάντησηΔιαγραφή
  2. RIZOPOULOS GEORGIOS10 Ιουλίου 2013 στις 3:29 μ.μ.

    ΔΙΟΡΘΩΣΗ: log2(128!)=717 το κατώτατο όριο ζυγίσεων

    ΑπάντησηΔιαγραφή
  3. ΕΥΘΥΜΗΣ ΑΛΕΞΙΟΥ10 Ιουλίου 2013 στις 7:14 μ.μ.

    Σωστό επίσης νομίζω ότι είναι, για τυπικό κυρίως λόγο, οι σχέσεις "2^x>=x! ή x>=log(2)του x!"
    να γραφούν 2^x>=Ν! ή x>=log(2)του Ν!, όπου, όπως αναφέρει ο κ. Ριζόπουλος, χ τα ελάχιστα βήματα και Ν ο αριθμός όλων των αντικειμένων προς κατάταξη, στην πολύ ενδιαφέρουσα ανάλυση για το κάτω όριο. Να προσθέσω ότι μπορούμε να δούμε και ένα πάνω όριο, μάλλον όχι το μικρότερο δυνατό, που είναι
    χ<<128*127/2 ή γενικά χ<< Ν*(Ν-1)/2. Αν υπάρχει, που θα υπάρχει, κάποιο μικρότερο πάνω όριο για το χ θα ήθελα να το πληροφορηθώ.

    ΑπάντησηΔιαγραφή
  4. ΕΥΘΥΜΗΣ ΑΛΕΞΙΟΥ28 Ιουλίου 2013 στις 9:20 π.μ.

    Το συγκεκριμένο πρόβλημα όμως δεν ζητάει την κατάταξη ΟΛΩΝ των 128 αντικειμένων αλλά την εύρεση των 2 ΒΑΡΥΤΕΡΩΝ από τα 128, που είναι σχετικά εύκολη υπόθεση!
    Η λύση του συγκεκριμένου προβλήματος και η γενίκευση του "Εύρεση των 2 βαρύτερων από 2^ν αντικείμενα στη διεύθυνση http://www.blogger.com/comment.g?blogID=4661842447490996112&postID=582533251115834464

    ΑπάντησηΔιαγραφή

Εγγραφή σε: Σχόλια ανάρτησης (Atom)