Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Α17.12 · Εύρεση μηδενός σε πίνακα

Εξέταση Σεπτεμβρίου 2024, Θέμα 3 · Δυσκολία ★★☆ · programming · Κεφάλαια: 17, 15

Εύρεση Μηδενός σε Πίνακα [15 Μονάδες]

Γράψτε μία συνάρτηση find_zero η οποία λαμβάνει ως όρισμα έναν πίνακα από τιμές double ταξινομημένες σε αύξουσα σειρά και επιστρέφει την θέση (index) όπου υπάρχει το 0 ή -1 αν δεν το βρει. Η συνάρτηση μπορεί να έχει οποιαδήποτε διεπαφή (ορίσματα / τύπο επιστροφής) επιθυμείτε. Για παράδειγμα αν δοθεί ο πίνακας {-8.1, -2.3, 0.0, 1.9} θέλουμε να επιστραφεί η τιμή 2. Αντίστοιχα, αν δοθεί ο πίνακας {1.0} θέλουμε να επιστραφεί -1. Τι χρονική και χωρική πολυπλοκότητα έχει ο αλγόριθμός σας (5/15 της βαθμολογίας);

Υπόδειξη

Ο πίνακας είναι ταξινομημένος, άρα μια σειριακή αναζήτηση αφήνει βαθμούς στο τραπέζι: σκεφτείτε ποιος αλγόριθμος εκμεταλλεύεται τη διάταξη για λογαριθμικό χρόνο. Αφού ο πίνακας δεν «ξέρει» το μέγεθός του, η διεπαφή πρέπει να περνά και το πλήθος των στοιχείων. Ελέγξτε τις ακραίες περιπτώσεις: πίνακας ενός στοιχείου, μηδέν στην πρώτη ή στην τελευταία θέση, όλα θετικά ή όλα αρνητικά.

Αριθμός στον οδηγό: Α17.12 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: exam-2024-sep-q3 · Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2024-sep-q3.html · Markdown (GitHub)