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

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




Δημιουργία νέου θέματος Απαντήστε στο θέμα  [ 1 Δημοσίευση ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Βοηθήστε τον ταχυδρόμο **
ΔημοσίευσηΔημοσιεύτηκε: Παρ 21 Μάιος 2004 01:59 pm 
Χωρίς σύνδεση

Εγγραφή: Πέμ 22 Απρ 2004 11:16 am
Δημοσιεύσεις: 60
Τοποθεσία: Θεσσαλονίκη
Το παρακάτω πρόβλημα αποτέλεί μια απλή εκδοχή του γνωστού προβλήματος με τον ταχυδρόμο.
Syntax: [ Download ] [ Hide ]
! =============================================================================================================================
! Ένας ταχυδρόμος πρέπει να ξεκινήσει από το χωριό 1 και να επισκεφτεί τα 4 γειτονικά χωριά (2,3,4,5) για να μοιράσει επιστολές
! και δέματα περνώντας μόνο μια φορά από κάθε χωριό. Κάθε χωρίο σύνδεέεται με οδικό δίκτυο με όλα τα υπολοιπα
! χωριά με μια μοναδική διαδομή. Έστω ότι η διάταξη των χωριών είναι όπως απεικονίζεται στο επόμενο σχήμα.
!                            __
!        __         __      |4 |
!       |3 |       |1 |
!
!        __             ___
!       |2 |           | 5 |
!
!
! Να γραφεί πρόγραμμα το οποίο:
! α) θα διαβάζει όλες τις αποστάσεις μεταξύ των χωριών Απ[i,j] και θα τις καταχωρεί σε ένα δισδιαστατο πίνακα,
! β) θα βρίσκει και θα εμφανίζει τις χιλιομετρικές αποστάσεις όλων των δυνατών διαδρομών που ξεκινούν
! από το χωριό 1 και περιλαμβάνουν  όλα τα υπόλοιπα χωριά (2,3,4,5),
! γ) θα βρίσκει και θα εμφανίζει τη συντομότερη διαδρομή,
!
! ΣΗΜΕΙΩΣΗ:   Θεωρήστε ότι καμία απόσταση μεταξύ δυο χωριών δεν είναι μεγαλύτερη των 100 Km
! και ότι είναι ακέραιοι αριθμοί (0<Απ[i,j]<100)
! =============================================================================================================================


ΠΡΟΓΡΑΜΜΑ Ταχυδρόμος
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ:i,j,k,n,διατάξη,Απ[5,5][24],x2,x3,x4,x5,min   ! Δ[24]: πλήθος πιθανών διαδρομών: 4!=1*2*3*4=24 διαδρομές
ΑΡΧΗ                                                       ! προκύπτει από το πλήθος διατάξεων των στοιχείων 2,3,4,5
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 5
    ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ 5
      ΑΝ i<j ΤΟΤΕ
        ΓΡΑΨΕ 'Δώσε απόσταση μεταξύ ',i,'ου και ',j,'ου χωριού'
        ΔΙΑΒΑΣΕ Απ[i,j]
      ΑΛΛΙΩΣ_ΑΝ i=j ΤΟΤΕ
        Απ[i,j] <-- 0
      ΑΛΛΙΩΣ
        Απ[i,j] <-- Απ[j,i]
      ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ


  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 5
    ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ 5
      ΓΡΑΨΕ_ Απ[i,j],' '
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΡΑΨΕ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  min <-- 400
  διατάξη <-- 0
  ΓΙΑ i ΑΠΟ 2 ΜΕΧΡΙ 5
    ΓΙΑ j ΑΠΟ 2 ΜΕΧΡΙ 5
      ΓΙΑ k ΑΠΟ 2 ΜΕΧΡΙ 5
        ΓΙΑ n ΑΠΟ 2 ΜΕΧΡΙ 5
          ΑΝ (i<>j) ΚΑΙ (i<>k) ΚΑΙ (i<>n) ΚΑΙ (j<>k) ΚΑΙ (j<>n) ΚΑΙ (k<>n) ΤΟΤΕ
            διατάξη <-- διατάξη+1
            Δ[διατάξη] <-- Απ[1,i]+Απ[i,j]+Απ[j,k]+Απ[k,n]
            ΓΡΑΨΕ  διατάξη,'η διαδρομή: 1 ',i,' ',j,' ',k,' ',n, ' με απόσταση: '[διατάξη], ' km'

            ΑΝ Δ[διατάξη]<min ΤΟΤΕ
              min <-- Δ[διατάξη]
              x2 <-- i
              x3 <-- j
              x4 <-- k
              x5 <-- n
            ΤΕΛΟΣ_ΑΝ
          ΤΕΛΟΣ_ΑΝ
        ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΡΑΨΕ 'Πλήθος πιθανών διαδρομών=',διατάξη
  ΓΡΑΨΕ 'Η διαδρομή με την ελάχιστη απόσταση είναι η: 1 ',x2,' ',x3,' ',x4,' ',x5, ' με συνολική απόσταση: ',min,' km'

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


 


Tο πλήθος των πιθανών διαδρομών θα άλλαζε αν ο ταχυδρόμος ήταν υποχρεωμένος να επιστρέφει στο τέλος της διαδρομής του στο χωρίο 1 ; :)

---- Ανάλογο Προβλημα 1 ------
Ένα πρακτορείο ταξιδιών διοργανώνει μία εκδρομή για το γύρο του κόσμου σε 80 ημέρες. Για να κάνει το σχεδιασμό του ταξιδιού χρειάζεται να επιλέξει κάποιες πόλεις και συγκεκριμένη διαδρομή. Να να καταγράψετε τα βασικά βήματα ενός αλγορίθμου που θα σχεδιάζει τη διαδρομή που θα πρέπει να ακολουθήσει ο ταξιδιώτης ξεκινώντας από μία πόλη και καταλήγοντας πάλι σε αυτήν αφού περάσει μία φορά από τις πόλεις που έχουν επιλεγεί. Είναι χρήσιμο στο σχεδιασμό της διαδρομής να παίρνει κανείς την απόφαση για τη μικρότερη δυνατή διαδρομή.

(Δραστηριότητα ΔΤ4, από το σχολικό ΤΕΤΡΑΔΙΟ του ΜΑΘΗΤΗ, σελιδα 40, κεφ. 4, Τεχνικές Σχεδίασης Αλγορίθμων)

------ Ανάλογο Προβλημα 2 ----------
Παράδειγμα από το σχολικό ΒΙΒΛΙΟ του ΜΑΘΗΤΗ, σελιδα 81, κεφ. 4, Τεχνικές Σχεδίασης Αλγορίθμων


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

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


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

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


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

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