Skip to content
The Chat Archive
qwen3-235b-a22b-no-thinking· Alibaba (Qwen) LMArena Human Preference 140K

Θεωρήστε έναν ταξινομημένο πίνακα [1..n], σε αύξουσα σειρά, με n διακριτούς ακέραιους…

  1. User

    Θεωρήστε έναν ταξινομημένο πίνακα [1..n], σε αύξουσα σειρά, με n διακριτούς ακέραιους αριθμούς. Έστω ότι γνωρίζουμε εκ των προτέρων ότι ο πίνακας περιέχει αριθμούς από το 1 ως το n + 1, επομένως, αφού είναι όλοι διακριτοί μεταξύ τους, λείπει ακριβώς ένας από τους παραπάνω αριθμούς στα περιεχόμενα του πίνακα. Για παράδειγμα, ο Α θα μπορούσε να είναι στην εξής μορφή:A = [1, 2, 4, 5] όπου λείπει το 3 ή A = [2, 3, 4, 5, 6], όπου λείπει το

    1. Ο σκοπός της άσκησης είναι να σχεδιάσετε έναν αλγόριθμο Διαίρει και Βασίλευε που βρίσκει ποιος αριθμός λείπει και τον επιστρέφει, σε όσο το δυνατόν καλύτερο χρόνο.

    (i) (6 μονάδες) Περιγράψτε με λόγια την ιδέα του αλγορίθμου σας και συγκεκριμένα το πώς θα εφαρμόσετε την τεχνική Διαίρει και Βασίλευε για να λύσετε το πρόβλημα. Μπορείτε να υποθέσετε για απλότητα ότι το n είναι δύναμη του 2. (ii) (16 μονάδες) Περιγράψτε τον αλγόριθμο σας με ψευδοκώδικα. (iii) (10 μονάδες) Aναλύστε την πολυπλοκότητα του αλγορίθμου σας.

  2. Assistant

    Θα λύσουμε το πρόβλημα χρησιμοποιώντας την τεχνική Διαίρει και Βασίλευε, εκμεταλλευόμενοι το γεγονός ότι ο πίνακας είναι ταξινομημένος και ότι από τους αριθμούς 1 έως n+1 λείπει μόνο ένας.


    (i) Ιδέα του αλγορίθμου

    Η βασική παρατήρηση είναι η εξής:

    Αν ο πίνακας δεν έλειπε κανένας αριθμός, τότε για κάθε θέση i (με βάση 1), θα είχαμε A[i] == i.
    Εφόσον λείπει ένας αριθμός, υπάρχει κάποιο σημείο όπου A[i] > i. Το πρώτο τέτοιο σημείο μας δείχνει τον αριθμό που λείπει.

    Για να το βρούμε αποδοτικά, χρησιμοποιούμε δυαδική αναζήτηση (binary search), που είναι μια μορφή Διαίρει και Βασίλευε. Η διαδικασία είναι η εξής:

    • Αρχίζουμε από το μέσο του πίνακα.
    • Αν A[mid] == mid + 1, τότε το λείπον στοιχείο είναι στο δεξί μισό.
    • Αν A[mid] > mid + 1, τότε το λείπον στοιχείο είναι στο αριστερό μισό ή είναι το mid + 1.
    • Συνεχίζουμε αναδρομικά μέχρι να βρούμε τη θέση όπου το στοιχείο λείπει.

    Έτσι, αντί να εξετάσουμε όλα τα στοιχεία (γραμμική πολυπλοκότητα), εργαζόμαστε σε λογαριθμικό χρόνο.


    (ii) Ψευδοκώδικας

    function missingNumber(A[1..n])
        low = 1
        high = n
    
        while low <= high do
            mid = floor((low + high) / 2)
    
            if A[mid] == mid + 1 then
                // Το λείπον στοιχείο είναι στα δεξιά
                low = mid + 1
            else
                // Το λείπον στοιχείο είναι στα αριστερά ή είναι mid + 1
                high = mid - 1
    
        return low + 1
    

    Παρατήρηση: Ο πίνακας είναι 1-based για να είναι ευκολότερη η αντιστοίχιση με τη θεωρία. Αν ο πίνακας είναι 0-based, τότε στην αρχή το low = 0, high = n - 1 και η σύγκριση γίνεται με A[mid] == mid + 1.


    (iii) Ανάλυση Πολυπλοκότητας

    Χρονική πολυπλοκότητα:

    Κάθε φορά διαιρούμε τον πίνακα στη μέση και εξετάζουμε μόνο το ένα κομμάτι. Έτσι, η πολυπλοκότητα είναι:

    T(n)=T(n/2)+O(1)T(n) = T(n/2) + O(1)

    Αυτή η αναδρομική σχέση λύνεται σε:

    T(n)=O(log⁡n)T(n) = O(\log n)

    Χώρος:

    Ο αλγόριθμος είναι επιτόπου (in-place) και δεν χρησιμοποιεί επιπλέον χώρο, εκτός από λίγες μεταβλητές. Άρα:

    S(n)=O(1)S(n) = O(1)

    Παράδειγμα Λειτουργίας

    Έστω A = [1, 2, 4, 5] (n=4). Θέλουμε να βρούμε ποιος αριθμός λείπει από τους 1 έως 5.

    • mid = 2 → A[2] = 2 → σωστός αριθμός, συνεχίζουμε στα δεξιά.
    • mid = 3 → A[3] = 4, ενώ περιμέναμε 3+1=4 → άρα εξακολουθεί να είναι σωστός, πάμε δεξιά.
    • low = 4, high = 4 → mid = 4 → A[4] = 5, περιμέναμε 4+1=5 → OK, πάμε δεξιά.
    • low = 5 > high → τερματίζουμε, λείπει το low + 1 = 5 + 1 = 3.

    Άρα επιστρέφουμε 3.


    Συμπεράσματα

    • Ο αλγόριθμος βρίσκει τον λείποντα αριθμό σε O(log n) χρόνο.
    • Είναι αποδοτικός και χρησιμοποιεί σταθερό χώρο.
    • Είναι βασισμένος στην τεχνική Διαίρει και Βασίλευε (divide and conquer), με τη μορφή της δυαδικής αναζήτησης.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.