Η αναπαράσταση ενός σήματος στο πεδίο των συχνοτήτων αποτελεί το φάσμα του. Εξαιρετικά σημαντική είναι η παρατήρηση ότι τα τεχνητά σήματα (τα σήματα δηλαδή που παράγονται από τεχνητά κατασκευασμένα συστήματα), έχουν μια μοναδική χαρακτηριστική κατανομή φάσματος. Η κατανομή αυτή ονομάζεται και χαρακτηριστική τριπλέτα επειδή συμμετρικά και εκατέρωθεν μιας δεδομένης συχνότητας, (χαρακτηριστική συχνότητα), εμφανίζονται δύο σήματα ίδιας ισχύος, και μάλιστα μικρότερης από το 50% της ισχύος του σήματος που αντιστοιχεί στη χαρακτηριστική συχνότητα.

Το Πανεπιστήμιο του Berkeley (California U.S.A.) έχει αναπτύξει ένα διεθνές πρόγραμμα επεξεργασίας σημάτων από εθελοντές χρήστες του Διαδικτύου, που αποσκοπεί στην αναζήτηση εξωγήινης νοημοσύνης και βασίζεται στην ανάλυση των σημάτων που συλλέγονται από ραδιοτηλεσκόπια (http://setiahome.berkeley.edu) Το Berkeley συλλέγει τα σήματα από τα ραδιοτηλεσκόπια και, αφού κάνει μια αρχική επεξεργασία, τα διανέμει στους συμμετέχοντες στο πρόγραμμα για να τα επεξεργαστούν. Αυτό που σας ζητείται σε αυτό το πρόβλημα είναι μία πολύ απλοποιημένη εκδοχή της επεξεργασίας που οι συμμετέχοντες καλούνται να κάνουν.

Σχήμα 1. Μετασχηματισμός σήματος από το πεδίο του χρόνου στο πεδίο των συχνοτήτων.

Πρόβλημα:

Να αναπτύξετε ένα πρόγραμμα σε Γλώσσα το οποίο θα διαβάζει τις τιμές στο πεδίο των συχνοτήτων που αντιστοιχούν σε ένα μετασχηματισμένο σήμα και θα τις καταχωρεί σε έναν Πίνακα 100 θέσεων. Στη συνέχεια θα αναγνωρίζει και θα εμφανίζει το πλήθος και τη θέση των χαρακτηριστικών συχνοτήτων μέσα στις αναγνωριζόμενες τριπλέτες. (πλήθος είναι και το 0)

Σημείωση:

Μία τριπλέτα σε ένα σήμα είναι μία τριάδα τιμών του σήματος με τις εξής ιδιότητες: (α) οι δύο ακραίες τιμές ισαπέχουν από τη μεσαία τιμή, και (β) οι δύο ακραίες τιμές είναι ίσες μεταξύ τους και μικρότερες του μισού της μεσαίας τιμής. Για παράδειγμα, η τριάδα τιμών που φαίνονται με έντονα γράμματα παρακάτω, είναι τριπλέτα:

Η μεσαία τιμή μίας τριπλέτας μας δίνει τη χαρακτηριστική συχνότητα, η οποία ισούται με τη θέση της μεσαίας τιμής στο σήμα. Στο παραπάνω παράδειγμα, η χαρακτηριστική συχνότητα είναι 6 (γιατί η μεσαία τιμή 5, είναι ο έκτος αριθμός που εμφανίζεται στο σήμα). ΕΠΥ, 25ος Π.Δ.Π. (2013) Α’ Φάση.

Παράδειγμα 1 (Ν=9)
Είσοδος: 4 1 2 1 3 5 3 1 4 Έξοδος: 2 (τριπλέτες), θέσεις: 5 6

Παράδειγμα 2 (Ν=20)
Είσοδος: 1 2 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2  Έξοδος: 1 (τριπλέτες), θέσεις: 3

Παράδειγμα 3 (Ν=25)
Είσοδος: 4 4 5 5 5 6 6 6 6 7 7 7 6 6 6 6 5 5 5 4 4 3 2 1 0 Έξοδος: 0 (τριπλέτες), θέσεις: 

Παράδειγμα 4 (Ν=12)
Είσοδος: 1 2 2 5 3 2 1 6 1 2 1 4 Έξοδος: 3 (τριπλέτες), θέσεις: 4 5 8
1 2 2 5 3 2 1 6 1 2 1 4
1 2 2 5 3 2 1 6 1 2 1 4
1 2 2 5 3 2 1 6 1 2 1 4
1 2 2 5 3 2 1 6 1 2 1 4

ΛΥΣΗ

! *Δημιουργείται πολυπλοκότητα αν θέλω να αποφύγω να εμφανιστούν ξανά 
! οι ίδιες θέσεις (χαρ. συχνότητες). βλ. Παράδειγμα 4
! Προτείνεται η επίλυση χωρίς αυτό τον περιορισμό
! Επίσης, προτείνεται να προστεθεί στις εισόδους ο αριθμός των τιμών Ν
ΠΡΟΓΡΑΜΜΑ ΑΣΚ11_ΠΑΡ_Β_ΠΙΝ_BERKELEY_ΣΥΧΝΟΤΗΤΕΣ
ΣΤΑΘΕΡΕΣ
  Ν=12
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: f[Ν], i,j,k,symmetriko_j, pos[Ν-2], count

ΑΡΧΗ

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΔΙΑΒΑΣΕ f[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


  ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ Ν-2   ! πιθανώς βρίσκονται από τη θέση 2 μέχρι και την Ν-1
    pos[j] <-- 0          ! συνεπώς το μέγιστο πλήθος τους είναι Ν-2
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  count <-- 0
  k <-- 2     ! Αφήνω τo pos[1] κενό, γιατί χρησιμοποιώ το pos[k-1], για k=1

  ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν-1

    j <-- i-1
    symmetriko_j <-- i+1
    ΟΣΟ j>=1 και symmetriko_j <=Ν ΕΠΑΝΑΛΑΒΕ                                  

      ΑΝ f[j]=f[symmetriko_j] ΤΟΤΕ    ! 1o κριτήριο            

        ΑΝ f[j]< f[i]/2 ΤΟΤΕ          ! 2ο κριτήριο            
          ΑΝ pos[k-1] <> i ΤΟΤΕ       ! πρόκειται για διαφορετική χαρ. συχνότητα* 
            pos[k] <-- i
            k <-- k + 1
            count <-- count + 1
          ΤΕΛΟΣ_ΑΝ              
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΑΝ

      j <-- j - 1
      symmetriko_j <-- symmetriko_j + 1

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

  ΓΡΑΨΕ 'Πλήθος χαρακτηριστικών συχνοτήτων', count
  ΑΝ count>0 ΤΟΤΕ
    ΓΡΑΨΕ 'χαρακτηριστική συχνότητα/ες (θέση/εις εμφάνισης στο σήμα)'
    ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ k-1
      ΓΡΑΨΕ pos[i]
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΑΝ

ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ