Τώρα είναι Πέμ 28 Μαρ 2024 03:21 pm

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απαντήστε στο θέμα  [ 1 Δημοσίευση ] 
Συγγραφέας Μήνυμα
ΔημοσίευσηΔημοσιεύτηκε: Τρί 25 Μάιος 2004 10:16 am 
Χωρίς σύνδεση

Εγγραφή: Πέμ 22 Απρ 2004 11:16 am
Δημοσιεύσεις: 60
Τοποθεσία: Θεσσαλονίκη
Syntax: [ Download ] [ Hide ]
! ==========================================================================================================
! Ύλη Εξετάσεων
!
! Το βιβλίο κάποιου μαθήματος της Β Λυκείου έχει 10 κεφάλαια, αριθμημένα από το 11 έως το 20.
! Η ύλη του μαθήματος για τις εξετάσεις είναι 4 από τα 10 αυτά κεφάλαια.
! Ένας τρόπος για τον καθορισμό της ύλης είναι να γίνει σε δυο βήματα:
!  1ο ΒΗΜΑ: θα επιλέγεται ένα υποσύνολο S κεφαλαίων, με k (5<=k<=7)από αυτά τα 10 κεφάλαια.
!    Η επιλογή των κεφαλαίων στο πρώτο βήμα γίνεται με βάση το πόσο σημαντικό είναι το κάθε κεφάλαιο.
!    Ο καθηγητής που καθορίζει την ύλη του μαθήματος έχει δώσει σε κάθε κεφάλαιο, με βάση ορισμένα κριτήρια,
!    έναν συντελεστή βαρύτητας (30-60). Δηλαδή, δίνεται ένα σύνολο από δέκα ζευγάρια που αποτελούνται από
!    τον αριθμό του κεφαλαίου και τον αντίστοιχο συντελεστή βαρύτητάς του.
!  2ο ΒΗΜΑ: από το υποσύνολο S θα επιλέγονται τα 4 κεφάλαια που θα είναι η ύλη αυτού του μαθήματος.
!
! Ζητείται να γραφτεί πρόγραμμα, που θα διαβάζει το συντελεστή βαρύτητας για κάθε κεφάλαιο
! από το 11ο εως και το 20ο και στη συνέχεια θα διαβάζει τον αριθμό k. Θα καταγράφει τέλος όλους τους δυνατούς
! συνδυασμούς κεφαλαίων που μπορεί να χρησιμοποιήσει ο καθηγητής ώστε να καθορίσει την ύλη του μαθήματος,
! αλλά και πόσοι είναι αυτοί οι συνδυασμοί.
! Ζητούνται δηλ. όλοι οι δυνατοί συνδυασμοί των k στοιχείων (κεφαλαίων του βιβλίου) ανά 4. Οι συντελεστές
! βαρύτητας θεωρήστε ότι είναι τέτοιοι ώστε να είναι εφικτό να επιλέγονται k ακριβώς στοιχεία στο υποσύνολο S.
! ---- Παρατήρηση: -------
! Το σύνολο S, όπως και οι αριθμοί κεφαλαίων σε κάθε τετράδα, πρέπει να είναι ταξινομημένοι λεξικογραφικά,
! δηλ. πρώτα ο μικρότερος αριθμός, μετά ο αμέσως μεγαλύτερος κλπ.
! Οι διαφορετικές τετράδες πρέπει επίσης να είναι σε λεξικογραφική σειρά όπως φαίνεται στο παρακάτω παράδειγμα.
!
! ----- ΠΑΡΑΔΕΙΓΜΑ 1 -------------
! Δεδομένα Εισόδου:
! Αν το k διαβαστεί 5 (k=5) και οι συντελεστές βαρύτητας των 10 κεφαλαίων όπως παρακάτω:
!     ΚΕΦ[i]   Bαρύτητα[i]
!       11         48
!       12         46
!       13         47
!       14         35
!       15         47
!       16         34
!       17         33
!       18         49
!       19         36
!       20         34
!
! Δεδομένα Εξόδου:
! Τα 5 κεφάλαια είναι τα εξής:   11  12  13  15  18
!
!  Οι πιθανές τετράδες είναι 5 και είναι οι επόμενες
!  11  12  13  15
!  11  12  13  18
!  11  12  15  18
!  11  13  15  18
!  12  13  15  18
!
! ( Από τον 14ο Πανελλήνιο Διαγωνισμό Πληροφορικής, Φάση 1η )
! ( http://epy.compulink.gr/panellinios/ )
!
! ===============================================================================================================

ΠΡΟΓΡΑΜΜΑ Ύλη_Εξετάσεων
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: i,j,k,m,q,ΚΕΦ[10],ΒΑΡΥTHΤΑ[10],συνδ,temp,Ν
ΑΡΧΗ
  Ν <-- 10
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
      ΓΡΑΨΕ 'Δώσε συντελεστή βαρύτητας', i,'ου κεφαλαίου'
      ΔΙΑΒΑΣΕ  ΒΑΡΥTHΤΑ[i]
    ΜΕΧΡΙΣ_ΟΤΟΥ (ΒΑΡΥTHΤΑ[i]>=30) ΚΑΙ (ΒΑΡΥTHΤΑ[i]<=60)
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΡΑΨΕ 'Δώσε ακέραιο αριθμό k (5-7), (αριθμός κεφαλαίων υποσυνόλου S)'
    ΔΙΑΒΑΣΕ k
  ΜΕΧΡΙΣ_ΟΤΟΥ (k>=5) ΚΑΙ (k<=7)

  ΚΑΛΕΣΕ Εμφάνιση_Δεδομένων (ΚΕΦ,ΒΑΡΥTHΤΑ,Ν)

  ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ Ν
    ΓΙΑ j ΑΠΟ Ν ΜΕΧΡΙ i ΜΕ ΒΗΜΑ -1
      ΑΝ ΒΑΡΥTHΤΑ[j-1]<ΒΑΡΥTHΤΑ[j] ΤΟΤΕ    ! φθίνουσα ταξινόμηση  ΒΑΡΥTHΤΑ[1]>ΒΑΡΥTHΤΑ[2]>......>ΒΑΡΥTHΤΑ[Ν]
        temp <-- ΒΑΡΥTHΤΑ[j]
        ΒΑΡΥTHΤΑ[j] <-- ΒΑΡΥTHΤΑ[j-1]
        ΒΑΡΥTHΤΑ[j-1] <-- temp

        temp <-- ΚΕΦ[j]
        ΚΕΦ[j] <-- ΚΕΦ[j-1]
        ΚΕΦ[j-1] <-- temp
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ k
    ΓΙΑ j ΑΠΟ k ΜΕΧΡΙ i ΜΕ ΒΗΜΑ -1
      ΑΝ ΚΕΦ[j-1]>ΚΕΦ[j] ΤΟΤΕ    ! Λεξικογραφική αύξουσα ταξινόμηση  ΚΕΦ[1]<ΚΕΦ[2]<......<ΚΕΦ[k]
        temp <-- ΚΕΦ[j]          ! των k σημαντικότερων κεφαλαίων
        ΚΕΦ[j] <-- ΚΕΦ[j-1]
        ΚΕΦ[j-1] <-- temp
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ
  ΓΡΑΨΕ'-----------------------------------'
  ΓΡΑΨΕ'Τα ',k,' σημαντικότερα κεφάλαια είναι τα επόμενα'
  ΓΡΑΨΕ'-----------------------------------'
  ΚΑΛΕΣΕ Εμφάνιση_Δεδομένων (ΚΕΦ,ΒΑΡΥTHΤΑ,k)
  ΓΡΑΨΕ
  ΓΡΑΨΕ
  συνδ <-- Παραγοντικό(k) DIV (Παραγοντικό(4)*Παραγοντικό(k-4))
  ΓΡΑΨΕ 'Πιθανοί Συνδυασμοί: ',συνδ ,' (πιθανές τετράδες κεφαλαίων)'

!-----------------1ος τρόπος ----------------------------------

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ k                   ! εμφανίζουμε όλες τις πιθανές τετράδες κεφαλαίων
    ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ k                 ! για τις οποίες ισχύει ΚΕΦ[i]<ΚΕΦ[j]<ΚΕΦ[m]<ΚΕΦ[q]
      ΓΙΑ m ΑΠΟ 1 ΜΕΧΡΙ k               ! αλγόριθμος ο οποίος πραγματοποιεί αρκετές
        ΓΙΑ q ΑΠΟ 1 ΜΕΧΡΙ k             ! περιττές επαναλήψεις
          ΑΝ (i<j) ΚΑΙ (j<m) ΚΑΙ (m<q) ΤΟΤΕ
            ΓΡΑΨΕ ΚΕΦ[i],' ',ΚΕΦ[j],' ',ΚΕΦ[m],' ',ΚΕΦ[q]
          ΤΕΛΟΣ_ΑΝ
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!-------------------------------------------------------------


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


!------------------------------------------

ΣΥΝΑΡΤΗΣΗ Παραγοντικό(x): ΑΚΕΡΑΙΑ
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ:i,p,x
ΑΡΧΗ
  p <-- 1
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ x
    p <-- P*i
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  Παραγοντικό <-- p
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

!------------------------------------------

ΔΙΑΔΙΚΑΣΙΑ Εμφάνιση_Δεδομένων (ΚΦ,ΒΑΡ,lim)
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: i,ΚΦ[10],ΒΑΡ[10],lim
ΑΡΧΗ
  ΓΡΑΨΕ_ 'ΚΕΦΑΛΑΙΑ[i]: '
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ lim
    ΓΡΑΨΕ_ ΚΦ[i], '  '
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ
  ΓΡΑΨΕ
  ΓΡΑΨΕ_ 'ΒΑΡΥTHΤΑ[i]: '
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ lim
    ΓΡΑΨΕ_ ΒΑΡ[i], '  '
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

!-------------------------------------------
 

Ο επόμενος αλγόριθμος "γλιτώνει" μερικές επαναλήψεις, αλλά εξακολουθεί να εκτελεί και περιττές επαναλήψεις.

Syntax: [ Download ] [ Hide ]
!-----------------2ος τρόπος ----------------------------------

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ k-3
    ΓΙΑ j ΑΠΟ 2 ΜΕΧΡΙ k-2
      ΓΙΑ m ΑΠΟ 3 ΜΕΧΡΙ k-1
        ΓΙΑ q ΑΠΟ 4 ΜΕΧΡΙ k
          ΑΝ (i<j) ΚΑΙ (j<m) ΚΑΙ (m<q) ΤΟΤΕ
            ΓΡΑΨΕ ΚΕΦ[i],' ',ΚΕΦ[j],' ',ΚΕΦ[m],' ',ΚΕΦ[q]
          ΤΕΛΟΣ_ΑΝ
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!-------------------------------------------------------------
 

Ο επόμενος αλγόριθμος τέλος αποτελεί το βέλτιστος τρόπο επίλυσης, αφού εκτελεί μονο τις επαναλήψεις που χρειάζονται κάθε φορά. Παρατηρείστε ότι είναι απηλαγμένος από την εντολή ελέγχου "Αν" !!!
Syntax: [ Download ] [ Hide ]
!-----------------3ος τρόπος ----------------------------------

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ k-3
    ΓΙΑ j ΑΠΟ i+1 ΜΕΧΡΙ k-2
      ΓΙΑ m ΑΠΟ j+1 ΜΕΧΡΙ k-1
        ΓΙΑ q ΑΠΟ m+1 ΜΕΧΡΙ k
            ΓΡΑΨΕ ΚΕΦ[i],' ',ΚΕΦ[j],' ',ΚΕΦ[m],' ',ΚΕΦ[q]
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!-------------------------------------------------------------


 


Κορυφή
 Προφίλ  
Απάντηση με παράθεση  
Τελευταίες δημοσιεύσεις:  Ταξινόμηση ανά  
Δημιουργία νέου θέματος Απαντήστε στο θέμα  [ 1 Δημοσίευση ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μέλη σε σύνδεση

Μέλη σε αυτή την Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επισυνάπτετε αρχεία σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
cron
Προβολές: