Ενότητα 2 . Τεχνικές Σχεδίασης Αλγορίθμων

2.1 . Μέθοδος Διαίρει και Βασίλευε

Ο Φίλιππος ο 2ος ο Μακεδών Θεωρείται ο πρώτος που το είπε.

Παράδειγμα 1. Βρες το δαχτυλίδι.

Παράδειγμα 2. Το κάλπικο νόμισμα.

Δίνεται για επίλυση ένα στιγμιότυπο ενός προβλήματος. 1. Το στιγμιότυπο του προβλήματος υποδιαιρείται σε υποστιγμιότυπα του ίδιου προβλήματος. 3. Δίνεται ανεξάρτητη λύση σε κάθε ένα υποστιγμιότυπο. 4. Συνδυάζονται όλες οι μερικές λύσεις που βρέθηκαν για τα υποστιγμιότυπα, έτσι ώστε να δοθεί η συνολική λύση του προβλήματος.

Βήμα 1 : 64 - 64 νομίσματα Βήμα 2 : 32 - 32 νομίσματα

Βήμα 3 : 16 - 16 νομίσματα Βήμα 4 : 8 - 8 νομίσματα Βήμα 5 : 4 - 4 νομίσματα Βήμα 6 : 2 - 2 νομίσματα Βήμα 7 : 1 - 1 νομίσματα

7 Φορές

Προαιρετική απλή εξήγηση του αριθμού των προσπαθειών. Έστω έχουμε ν στοιχεία να διαιρέσουμε :

1η φορά το μήκος του μισού τμήματος θα είναι

2η φορά το μήκος του μισού τμήματος θα είναι

3η φορά το μήκος του μισού τμήματος θα είναι

𝜈 2 𝜈 4 𝜈 8

=

=

Έστω την κ φορά το μήκος του μισού τμήματος θα είναι

𝜈 22 𝜈 23 𝜈 και θα είναι ίσο με 1 𝜅 2

Άρα ν = 2κ άρα log2(v)=log22k άρα log2(v)=k log22 άρα log2(v)=k Συνεπώς για να φτάσω στο τμήμα με μήκος 1, δηλαδή μετά από κ υποδιαιρέσεις, θα χρειαστώ το πολύ Α_Μ( log2(v)+1 ) διαιρέσεις του αρχικού συνόλου. Το 1 αφορά την περίπτωση που ο λογάριθμος μου δώσει δεκαδικό αριθμό. Πχ 6,643856 ενώ οι υποδιαιρέσεις πρέπει να είναι ακέραιες δηλαδή 7.

Μετρείστε τον αριθμό των προσπαθειών, για να αποδείξετε ότι θα χρειαστείτε το πολύ

Ακέραιο_Μέρος ( log2(n)+1)) φορές για βρείτε τον αριθμό.