Γενικό Λύκειο > Ταξινόμηση

επαναληψεις φυσαλιδα

(1/3) > >>

kiro:
Μια ακόμη ερώτηση στη φυσαλίδα...

Στην πρώτη επανάληψη => Για i από 2 μέχρι Ν

Θα μπορούσαμε να πάρουμε.... Για i από 1 μέχρι Ν-1?

Ενώ στη δεύτερη επανάληψη να πάρουμε αντί για Για j από Ν μέχρι i με_βημα -1....Για j από Ν μέχρι 2 με_βημα -1?

Τα δυο i είναι σχετικά (δηλ. η τιμή του ενός εξαρτάται από το άλλο ή απλά στην πρώτη επανάληψη περνούμε μέχρι από 2 μέχρι Ν επειδή απλά οι επαναλήψεις που εκτελούνται μέχρι να ταξινομηθεί ο πίνακας είναι μια λιγότερες από τον αριθμό στοιχείων ενώ στη δεύτερη επανάληψη το από Ν μέχρι I, το i δηλ,  δε σχετίζεται με την πρώτη απλά το βάζουμε μέχρι i αντί να βάλουμε μέχρι 2 επειδή απλά δεν μπορεί να πάρει την τιμή 1. Στην περίπτωση δηλ που βάζαμε Για ι από 1 μέχρι Ν-1 θα βάζαμε αντί για i 2 στη δεύτερη. Ελπίζω να μην τα είπα πολύ μπερδεμένα!!!

kinik:
Ας υποθέσουμε οτι έχουμε έναν πίνακα 5 θέσεων ο οποίος  πρέπει να ταξινομηθεί με χρήση του αλγορίθμου ταξίνομησης φυσσαλίδας. Ο αλγόριθμος ταξινόμησης φυσσαλίδας κάνει διαδοχικά περάσματα (προσπελάσεις στον πίνακα). Σε κάθε προσπέλαση ξεκινάει από το τέλος και συγκρίνει τα στοιχεία του πίνακα ανά δύο.
Το πρώτο πέρασμα θα  είναι:
Για i από 5 μέχρι 2 με_βήμα -1
       Αν Α[i-1]>A τότε
            ...
        Τέλος_αν
Τέλος_επανάληψης
Το i σταματάει στο 2 προκειμένου να ελεγχθεί Αν Α[1]>Α[2]
Μετά την εκτέλεση του παρπάνω τμήματος στη 1η θέση θα έρθει το μικρότερο στοιχείο του  πίνακα , όμως ο πίνακας δεν θα είναι ταξινομημένος. Πρέπει να γίνει 2ο πέρασμα.Στο 2ο πέρασμα δε χρειάζεται να συγκριθεί ξανά το 1ο στοιχείο γιατί είναι ήδη ταξινομημένο. Συνεπώς θα σταματήσω για i=3 ώστε να ελεγχθεί Αν Α[2]>Α[3]
Για i απο 5 μέχρι 3 με_βήμα -1
    ....
Τέλος_επανάληψης
Έχει ταξινομηθεί και το δεύτερο στοιχείο του πίνακα και συνεπώς στο 3ο πέρασμα θα σταματήσω για i=4 ώστε να  ελεγχθεί Αν Α[3]>Α[4].
Για i απο 5 μέχρι 4 με_βήμα -1
     ....
Τέλος_επανάληψης
Τελευταίο πέρασμα:
Για i απο 5 μέχρι 5 με_βήμα -1
     ....
Τέλος_επανάληψης
Άρα πρέπει 4 φορές να εκτελεστεί η Για η οποία κάνει συγκρίσεις και η οποία τη πρώτη φορά σταματάει στο 2 (συγκρίνει και το 1), τη δεύτερη στο 3 (συγκρίνει και το 2), τη τρίτη στο 4(συγκρίνει και 3), τη τέταρτη στο 5 (συγκίνει και το 5). Συνεπώς βάζω το j να παίρνει τιμές από 2 μέχρι 5.
Για j από 2 μέχρι 5
   Για i από 5 μέχρι j με_βήμα -1
      ...
   Τέλος_επανάληψης
Τέλος_επανάληψης
Παρατηρήσεις:
1. Η εσωτερική επανάληψη αν ήταν Για i από 5 μέχρι 2 θα σήμαινε ότι σε κάθε πέρασμα συγκρίνονται όλα τα στοιχεία του πίνακα ανεξάρτητα του αν έχουν ή όχι ταξινομηθεί σε προηγούμενα περάσματα. Απλά θα γίνονται σε κάποια περάσματα περιττές συγκρίσεις (συγκρίσεις ταξινομημένων στοιχείων).
2. Αν στην εξωτερική επανάληψη έβαζα Για j από 1 μέχρι Ν-1
τότε μπορούσα να πω το εξής:
Για j από 1 μέχρι Ν-1
  Για i από Ν-1 μέχρι j με_βήμα -1
         Αν Α>A[i+1] τότε
            ...
    ...
....
ή
Για j απο 1 μέχρι Ν-1
    Για i από Ν μέχρι j+1 με_βήμα -1
          Αν Α[i-1]>A τότε
            ...
      ...
...
Με βάση τη πρώτη παρατήση μπορώ να βάλω μέχρι 2 στην εσωτερική επανάληψη (2η περίπτωση - μέχρι 1 στη πρώτη περίπτωση) απλά γίνοντια περιττές συγκρίσεις σε επόμενα περάσματα. Δεν θεωρώ ότι θα έπρεπε να βαθμολογηθεί με λιγότερα μόρια ο μαθητής που θα το έκανε. Αυτό όμως δεν έχει σχέση με την εξωτερική επανάληψη αλλά με τη λειτουργία του αλγορίθμου.

EleniK:
Η γνώμη μου είναι ότι πρέπει να παραμείνει ο μαθητής στα πλαίσια του αλγορίθμου που δίνει το βιβλίο και να μην πειραματίζεται με αλλαγές στις δομές επανάληψης.

Ποιος ο λόγος να αλλαχθούν οι τιμές των δομών επανάληψης;

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

kiro:
Απλά με μπέρδεψε λίγο ένα βοήθημα…γενικά είμαι λίγο μπερδεμένη, πρώτη φορά το κάνω το μάθημα. Στο βοήθημα έλεγε ότι η εξωτερική επανάληψη μας δείχνει πόσες φορές θα εκτελεστεί η επανάληψη ποσά βήματα δηλ μέχρι να ταξινομηθεί ο πίνακας, στην περίπτωση των 5 θέσεων εκτελείται Ν-1 φορές δηλ 4. Όπως το καταλαβαίνω εγώ η Εξωτερική επανάληψη μας δείχνει μέχρι ποιο στοιχείο πρέπει να φτάσει η σάρωση του πίνακα κάθε φορά. Δηλ

Για i από 2 μέχρι Ν
   Για j από Ν μέχρι i

Όταν τι ι είναι 2 θα φτάσει να συγκρίνει μέχρι και το πρώτο όταν είναι 3 μέχρι και το δεύτερο κ.ο.κ κάθε φορά δηλ λειτουργεί σαν δείκτης για το μέχρι που θα συγκρίνει η εσωτερική επανάληψη. Κάθε φορά η δεύτερη επανάληψη θα φτάνει μέχρι εκεί που η πρώτη έχει ορίσει. Έτσι δεν είναι?

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση