Θέμα Δ, 2010, Επαναληπτικές, Ημερήσια

Ερευνητές που ασχολούνται με μοντέλα προσομοίωσης εξάπλωσης επιδημιών χρησιμοποιούν για τις μελέτες τους ένα αριθμητικό πίνακα Μ[5000]. Κάθε κελί του πίνακα αυτού αντιπροσωπεύει ένα άτομο σε μια περιοχή 5.000 κατοίκων στην οποία υπάρχουν εστίες μιας συγκεκριμένης μολυσματικής ασθένειας (επιδημίας). Από σύμβαση η τιμή μηδέν 0 σε ένα κελί αντιπροσωπεύει ένα υγιές άτομο, ενώ η τιμή -1 αντιπροσωπεύει ένα άτομο που έχει τη συγκεκριμένη ασθένεια (μολυσμένο άτομο). Κάθε άτομο έρχεται σε επαφή με τα γειτονικά του και η ασθένεια μπορεί να μεταδοθεί από τον ένα στον άλλο. (Γειτονικά χαρακτηρίζονται δύο άτομα, όταν τα κελιά του πίνακα που τα αντιπροσωπεύουν έχουν μια κοινή πλευρά).

Θεωρήστε ότι δίνεται ο πίνακας Μ που περιέχει ήδη έναν αριθμό  μολυσμένων  ατόμων.  Να  υλοποιήσετε  αλγόριθμο  ο οποίος:

Δ1. Υπολογίζει   και   εμφανίζει   με   κατάλληλο   μήνυμα   τον συνολικό αριθμό των μολυσμένων ατόμων που υπάρχουν στο σύνολο του πληθυσμού.

Μονάδες 4

Δ2. Αποθηκεύει σε κάθε κελί του πίνακα Μ που αντιπροσωπεύει ένα υγιές άτομο έναν αριθμό ο οποίος δείχνει με πόσα μολυσμένα άτομα γειτονεύει το υγιές.

Μονάδες 8

Δ3. Βρίσκει αν υπάρχει έστω και μία «σημαντική» εστία μόλυνσης. Αν υπάρχει, εμφανίζει το μήνυμα «Υπάρχει σημαντική εστία μόλυνσης» μαζί με τη θέση του πρώτου κελιού της εστίας. Αν δεν υπάρχει, εμφανίζει το μήνυμα «∆εν υπάρχει σημαντική εστία μόλυνσης». (Μια εστία μόλυνσης χαρακτηρίζεται σημαντική, όταν δύο ή περισσότερα μολυσμένα άτομα βρίσκονται σε συνεχόμενα γειτονικά κελιά).

Μονάδες 8

Τα θέματα σε pdf, 2010, Επαναληπτικές, Ημερήσια

ΛΥΣΗ

ΘΕΜΑ_Δ_2010_ΕΠΑΝ_ΗΜΕΡ [demo_δεδομένα_πληθυσμός_50]

ΠΡΟΓΡΑΜΜΑ  θΕΜΑ_Δ_2010_ΕΠΑΝ_ΗΜΕΡ
ΣΤΑΘΕΡΕΣ
  ΠΛΗΘΥΣΜΟΣ=50  ! Για τα demo Δεδομένα, 500000 για την άσκηση
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Μ[ΠΛΗΘΥΣΜΟΣ], i, μολυσμένοι, πλήθος, θέση
  ΛΟΓΙΚΕΣ: βρέθηκε
ΑΡΧΗ
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ ΠΛΗΘΥΣΜΟΣ
    ΔΙΑΒΑΣΕ Μ[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  Μολυσμένοι <-- 0
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ ΠΛΗΘΥΣΜΟΣ
    ΑΝ Μ[i] = -1 ΤΟΤΕ
      Μολυσμένοι <-- Μολυσμένοι + 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ 'Πλήθος μολυσμένων ατόμων :', Μολυσμένοι

! ΓΙΑ το πρώτο κελί που γειτονεύει μόνο δεξιά
  ΑΝ  Μ[1] = 0 ΤΟΤΕ
    ΑΝ Μ[2] = -1 ΤΟΤΕ
      Μ[1] <-- 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΑΝ

  ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ ΠΛΗΘΥΣΜΟΣ-1
    ΑΝ Μ[i] = 0 ΤΟΤΕ
      ΑΝ Μ[i-1] = -1 ΤΟΤΕ
        Μ[i] <-- Μ[i]+1
      ΤΕΛΟΣ_ΑΝ
      ΑΝ Μ[i+1] = -1 ΤΟΤΕ
        Μ[i] <-- Μ[i]+1
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ

  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

 ! ΓΙΑ το τελευταίο κελί που γειτονεύει μόνο αριστερά
  ΑΝ Μ[ΠΛΗΘΥΣΜΟΣ] = 0 ΤΟΤΕ
    ΑΝ Μ[ΠΛΗΘΥΣΜΟΣ-1] = -1 ΤΟΤΕ
      Μ[ΠΛΗΘΥΣΜΟΣ] <-- 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΑΝ

  πλήθος <-- 0
  βρέθηκε <-- ΨΕΥΔΗΣ
  i <-- 1
  ΟΣΟ (i <= ΠΛΗΘΥΣΜΟΣ) ΚΑΙ (βρέθηκε = Ψευδής) ΕΠΑΝΑΛΑΒΕ
    ΑΝ Μ[i] = -1 ΤΟΤΕ
      πλήθος <-- πλήθος + 1
    ΑΛΛΙΩΣ
      πλήθος <-- 0
    ΤΕΛΟΣ_ΑΝ

    ΑΝ πλήθος = 2 ΤΟΤΕ
      βρέθηκε <-- Αληθής
      θέση <-- i-1
    ΤΕΛΟΣ_ΑΝ
    i <-- i + 1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΑΝ βρέθηκε = Αληθής ΤΟΤΕ
    ΓΡΑΨΕ  'Υπάρχει σημΑΝτική εστία μόλυνσης', θέση
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Δεν υπάρχει σημΑΝτική εστία μόλυνσης'
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ