Αρχική ΑΕΠΠ - Δομές Δεδομένων Λειτουργικά Συστήματα Δίκτυα Υπολογιστών ΙΙ Βάσεις Δεδομένων Παιδαγωγικά - Διδακτική

Βασικές Έννοιες

Μεταβλητή - Έκφραση Δομή Ακολουθίας Δομή Επιλογής Δομή Επανάληψης

Αναπαράσταση Αλγορίθμων

Διάγραμμα Ροής

Πίνακας Τιμών

Πίνακες

Μονοδιάστατοι Δισδιάστατοι Πολυδιάστατοι Αναζήτηση Ταξινόμηση Στοίβα Ουρά

Υποπρογράμματα

Συναρτήσεις Διαδικασίες Σχετικά με τις παράμετρους

Δυναμικές Δομές

Λίστες Δέντρα Γράφοι

 Ιστορικό Πρόσφατες αλλαγές Εκτύπωση Αναζήτηση

Στις ασκήσεις ο αναγνώστης καλείται να αναπτύξει πρόγραμμα για την επίλυση της άσκησης. Είναι φυσικά ελεύθερος να αναπτύξει αλγόριθμο αν αυτό το επιθυμεί. Επειδή το πρόγραμμα είναι η τελική ζητούμενη μορφή αυτή θα δίνουμε εδώ ως απάντηση.

Εύρεση πλήθους ελαχίστων/μεγίστων στοιχείων

Να γραφεί πρόγραμμα το οποίο θα βρίσκει το ελάχιστο στοιχείο ενός δεδομένου πίνακα και το πλήθος των στοιχείων που ισούνται με το ελάχιστο.
Η άσκηση μπορεί να γίνει και για το μέγιστο με την ίδια ακριβώς λογική.

  1. ΠΡΟΓΡΑΜΜΑ ΠΛΗΘΟΣ_ΕΛΑΧΙΣΤΩΝ
  2. ΜΕΤΑΒΛΗΤΕΣ
  3.   ΑΚΕΡΑΙΕΣ: Τ[10], Ι, ΜΙΝ, Σ
  4. ΑΡΧΗ
  5.   ΜΙΝ <- Τ[1]
  6.   Σ <- 1
  7.   ΓΙΑ Ι ΑΠΟ 2 ΜΕΧΡΙ 10
  8.     ΑΝ Τ[Ι] < ΜΙΝ ΤΟΤΕ
  9.       ΜΙΝ <- Τ[Ι]
  10.       Σ <- 1
  11.     ΑΛΛΙΩΣ_ΑΝ Τ[Ι] = ΜΙΝ ΤΟΤΕ
  12.       Σ <- Σ + 1
  13.     ΤΕΛΟΣ_ΑΝ
  14.     ΓΡΑΨΕ 'ΤΟ ΕΛΑΧΙΣΤΟ ΕΙΝΑΙ: ', ΜΙΝ
  15.     ΓΡΑΨΕ 'ΕΜΦΑΝΙΖΕΤΑΙ ', Σ, ' ΦΟΡΕΣ'
  16.   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  17. ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Στη γραμμή 5 θεωρούμε ότι το ελάχιστο είναι το πρώτο στοιχείο του πίνακα. Αφού λοιπόν έχουμε έχουμε ένα ελάχιστο, τότε το σύνολο των ελαχίστων μέχρι τώρα είναι 1 (γραμμή 6).

Όλα τα υπόλοιπα στοιχεία του πίνακα ελέγχονται με το ελάχιστο. Αν βρεθεί ένα νέο ελάχιστο (γραμμή 8), τότε κρατάμε το νέο ελάχιστο (γραμμή 9) και το σύνολο των ελαχίστων γίνεται πάλι 1 (γραμμή 10). Αν όμως βρεθεί ένα στοιχείο ίσο με το ελάχιστο (γραμμή 11), τότε αυξάνουμε το σύνολο των ελαχίστων που έχουμε βρει (γραμμή 12).

Εύρεση δύο ελαχίστων/μεγίστων

Να γραφεί πρόγραμμα το οποίο σε μονοδιάστατο πίνακα μεγέθους Ν να βρίσκει τα δύο μεγαλύτερα στοιχεία. Να μη γίνει καμία αλλαγή στα στοιχεία του πίνακα όπως αντιμετάθεση και να μη χρησιμοποιηθεί άλλος πίνακας ως βοηθητικός.

Συγχώνευση με Δυαδική Αναζήτηση

Δώστε ένα πρόγραμμα για την ακόλουθη μέθοδο συγχώνευσης των πινάκων Α και Β στον πίνακα Γ. Εκτελείται δυαδική αναζήτηση του στοιχείου Β[1] στον πίνακα Α. Έστω ότι είναι μεταξύ του Α[i] και A[i+1]. Μεταφέρονται τότε τα στοιχεία Α[1]..Α[i] στον πίνακα Γ και μετά το στοιχείο Β[1]. Στη συνέχεια εκτελείται νέα δυαδική αναζήτηση του στοιχείου Β[2] στον υποπίνακα Α[i+1] μέχρι τέλους και επαναλαμβάνονται τα προηγούμενα. Η διαδικασία γίνεται για όλα τα στοιχεία του Β. Η μέθοδος αυτή εφαρμόζεται όταν ο πίνακας Β είναι μικρός σε σχέση με τον Α.

Ταξινόμηση με Δυαδική Παρεμβολή

Στον αλγόριθμο ταξινόμησης με ευθεία παρεμβολή η ακολουθία προορισμού Α[1..i-1] για το i-οστό στοιχείο του πίνακα Α, είναι ταξινομημένη. Μπορεί, λοιπόν, να χρησιμοποιηθεί η μέθοδος της δυαδικής αναζήτησης για την εύρεση της θέση του στοιχείου στην ακολουθία προορισμού. Να υλοποιήσετε τον αυτό τον αλγόριθμο (ο οποίος ονομάζεται δυαδική παρεμβολή).

Παιχνίδι

Δύο παίκτες παίζουν το εξής περίεργο παιχνίδι: Ο ένας δίνει 80 φορές τα γράμματα Α και Φ, τα οποία αποθηκεύονται σε έναν πίνακα 80 στηλών (ένα γράμμα σε κάθε στήλη), τελείως τυχαία. Ο άλλος διαλέγει πέντε στήλες από τις 80 τυχαία (έστω Σ1, Σ2, Σ3, Σ4, και Σ5 αυτές) και κερδίζει αν πετύχει (α) τουλάχιστον 4 Φ σε οποιαδήποτε σειρά, (β) τουλάχιστον 3 Φ στη σειρά, (γ) Φ στην Σ1 (πρώτη στήλη που διάλεξε), την Σ3 και την Σ5, (δ) κανένα Φ. Αν δίνεται η γραμμή του παιχνιδιού (με τα Α και Φ στις 80 στήλες) και οι στήλες Σ που επέλεξε ο δεύτερος παίχτης, να βρεθεί ποιος από τους δύο κέρδισε.

Αιμοδότες

Συχνά για μια εγχείρηση χρειάζεται να βρεθεί γρήγορα ένας αιμοδότης. Αν υπάρχει ένας κατάλογος αιμοδοτών, γράψτε ένα πρόγραμμα το οποίο με δεδομένο την ομάδα του αίματος που χρειάζεται να βρίσκει τους κατάλληλους αιμοδότες και να τους κατατάσσει σε σειρά προτίμησης (π.χ. πρώτος αυτός που έχει τον περισσότερο καιρό να δώσει αίμα).

Ύποπτοι

Για το δράστη μιας ληστείας δόθηκαν από αυτόπτες μάρτυρες τα εξής χαρακτηριστικά: Ηλικία 30-35 ετών, ύψος 1.70-1.80, βάρος περίπου 80 κιλά, μαλλιά μαύρα, μάτια καστανά, πρόσωπο οβάλ, μύτη σπασμένη (σαν παλαιστή), μικρό μούσι. Γράψτε ένα πρόγραμμα που από τα αρχεία σεσημασμένων κακοποιών της αστυνομίας θα βρίσκει τους πιθανούς υπόπτους και θα τυπώνει τις διαφορές τους (για στοιχεία που δεν παρατηρήθηκαν από τους μάρτυρες).

Interpole

Στα αρχεία της Ιντερπόλ υπάρχουν στοιχεία για παραβάτες του νόμου που δρουν σε ευρωπαϊκή ή παγκόσμια κλίμακα. Γράψτε ένα πρόγραμμα που να ελέγχει αν ορισμένα στοιχεία που δόθηκαν από αυτόπτες μάρτυρες σε μια ληστεία (π.χ. ύψος, βάρος, τρόπος κίνησης, ομιλία του ληστή, κτλ.) αντιστοιχούν σε σεσημασμένους κακοποιούς και να τυπώνει έναν κατάλογο τους.

Ασθενείς

Γράψτε ένα πρόγραμμα στο οποίο να δίνονται 100 κοινές ασθένειες με 10 συμπτώματα η καθεμιά και μετά να ερωτάται ο ΗΥ να βρει την ή τις ασθένειες που παρουσιάζουν 6 συμπτώματα που παρατηρήσατε στον εαυτό σας. Το πρόγραμμα πρέπει να είναι τέτοιο ώστε να δίνει τα συμπτώματα που δεν παρατηρήσατε για κάθε πιθανή ασθένεια σας, υποδεικνύοντας έτσι τι πρέπει να παρατηρήσετε για να βρείτε τι ακριβώς έχετε.

Συγχώνευση με τη Βοήθεια Δυαδικής Αναζήτησης

Δώστε ένα πρόγραμμα για την ακόλουθη μέθοδο συγχώνευσης των πινάκων Α και Β στον πίνακα Γ. Εκτελείται δυαδική αναζήτηση του στοιχείου Β[1] στον πίνακα Α. Έστω ότι είναι μεταξύ του Α[i] και A[i+1]. Μεταφέρονται τότε τα στοιχεία Α[1]..Α[i] στον πίνακα Γ και μετά το στοιχείο Β[1]. Στη συνέχεια εκτελείται νέα δυαδική αναζήτηση του στοιχείου Β[2] στον υποπίνακα Α[i+1] μέχρι τέλους και επαναλαμβάνονται τα προηγούμενα. Η διαδικασία γίνεται για όλα τα στοιχεία του Β. Η μέθοδος αυτή εφαρμόζεται όταν ο πίνακας Β είναι μικρός σε σχέση με τον Α.

Αναζήτηση με Μπαλαντέρ

Δυαδική Αναζήτηση - Εύρεση Όλων των Αναζητούμενων Στοιχείων

Να γραφεί πρόγραμμα το οποίο για έναν δεδομένο μονοδιάστατο πίνακα Α να φτιάχνει έναν δεύτερο μονοδιάστατο πίνακα Β ίδιου μεγέθους στον οποίο θα ταξινομεί τα στοιχεία του Α χρησιμοποιώντας τη θέση στην οποία αυτά εμφανίζονται έτσι ώστε για κάθε i στο διάστημα [1, n-1] ισχύει Α[Β[i]]<A[B[i+1]]. Παράδειγμα:

Θέση12345678
Α1789547611632631
Β51783642

Τελευταία ενημέρωση: 23-05-2008 (13:05)

Copyright 2008 - Άρης Φεργάδης