Αποστολέας Θέμα: επαναληψεις φυσαλιδα  (Αναγνώστηκε 3943 φορές)

kiro

  • Βετεράνος
  • ****
  • Μηνύματα: 52
  • Γράψτε το προσωπικό σας σλόγκαν!
επαναληψεις φυσαλιδα
« στις: 21 Φεβ 2006, 01:57:45 πμ »
Μια ακόμη ερώτηση στη φυσαλίδα...

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

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

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

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

kinik

  • Επισκέπτης
Απ: επαναληψεις φυσαλιδα
« Απάντηση #1 στις: 21 Φεβ 2006, 07:11:44 πμ »
Ας υποθέσουμε οτι έχουμε έναν πίνακα 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

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 708
Απ: επαναληψεις φυσαλιδα
« Απάντηση #2 στις: 21 Φεβ 2006, 10:00:02 πμ »
Η γνώμη μου είναι ότι πρέπει να παραμείνει ο μαθητής στα πλαίσια του αλγορίθμου που δίνει το βιβλίο και να μην πειραματίζεται με αλλαγές στις δομές επανάληψης.

Ποιος ο λόγος να αλλαχθούν οι τιμές των δομών επανάληψης;
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

kinik

  • Επισκέπτης
Απ: επαναληψεις φυσαλιδα
« Απάντηση #3 στις: 21 Φεβ 2006, 11:46:03 πμ »
Elenik γνώμη μου είναι ότι ο μαθητής θα πρέπει να καταλάβει τι κάνει ο κάθε αλγόριθμος. Για να το πετύχει αυτό οι πειραματισμοί που δημιουργούν απορίες κατά τη διάρκεια του μαθήματος είναι σωστοί και πρέπει να υπάρχουν.
Η συμβουλή που και εγώ δίνω στους μαθητές είναι να μην αλλάζουν τις επαναλήψεις αλλά κατά την διάρκεια του μαθήματος δίνω και διαφορετικές εκδοχές.

kiro

  • Βετεράνος
  • ****
  • Μηνύματα: 52
  • Γράψτε το προσωπικό σας σλόγκαν!
Απ: επαναληψεις φυσαλιδα
« Απάντηση #4 στις: 21 Φεβ 2006, 12:50:33 μμ »
Απλά με μπέρδεψε λίγο ένα βοήθημα…γενικά είμαι λίγο μπερδεμένη, πρώτη φορά το κάνω το μάθημα. Στο βοήθημα έλεγε ότι η εξωτερική επανάληψη μας δείχνει πόσες φορές θα εκτελεστεί η επανάληψη ποσά βήματα δηλ μέχρι να ταξινομηθεί ο πίνακας, στην περίπτωση των 5 θέσεων εκτελείται Ν-1 φορές δηλ 4. Όπως το καταλαβαίνω εγώ η Εξωτερική επανάληψη μας δείχνει μέχρι ποιο στοιχείο πρέπει να φτάσει η σάρωση του πίνακα κάθε φορά. Δηλ

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

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


coolio

  • Νέος
  • *
  • Μηνύματα: 2
Απ: επαναληψεις φυσαλιδα
« Απάντηση #5 στις: 22 Φεβ 2006, 06:59:33 μμ »
Kiro ως μαθητής θα σου δώσω απάντηση:
Οι συμαθητές μου καλα καλά δεν μπορούν να καταλάβουν πως προχωρά ο μετρητής και πώς γίνονται οι επαναλήψεις ! Λές να μπορούν να κάνουν και αλλαγές στον κώδικα;

EleniK

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 708
Απ: επαναληψεις φυσαλιδα
« Απάντηση #6 στις: 22 Φεβ 2006, 10:58:40 μμ »
Δεν ανάφερα ότι δεν θέλω τους προβληματισμούς των παιδιών, αλοίμονο! Ισα ίσα που τους ενθαρρύνω. Αυτό που δεν ενθαρρύνω είναι να πειραματίζονται όταν δεν κατανοούν καλά πώς δουλεύει μία μεθοδολογία. Πειραματισμοί μέσα στην ταξη ναι, όχι σε διαγωνίσματα και εξετάσεις.
Ελένη Κοκκίνου
Καθηγήτρια Πληροφορικής, ΠΕ19

kinik

  • Επισκέπτης
Απ: επαναληψεις φυσαλιδα
« Απάντηση #7 στις: 23 Φεβ 2006, 06:17:56 πμ »
Ούτε εγώ ανάφερα πειραματισμούς σε εξετάσεις αλλά σε συζήτηση με αφορμή την ερώτηση του kiro.

Vangelis

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 799
  • Για ακούτε και κανένα μεγαλύτερο!!!
Απ: επαναληψεις φυσαλιδα
« Απάντηση #8 στις: 23 Φεβ 2006, 09:51:34 πμ »
Η δική μου προσέγγιση συνάδελφοι είναι ΄"καταλαβαίνουμε τον αλγόριθμο και στη συνέχεια τον μαθαίνουμε απ' έξω και τον γράφουμε έτσι ακριβώς στις εξετάσεις για΄τι δεν ξέρετε ποιός θα διορθώσει το γραπτό σας".
Συνεπώς πρέπει να καταλάβουν καλά ότι η πρώτη επανάληψη χρησιμοποιείται για να καθορίζει τον αριθμο των επαναλήψεων (χρειαζόμαστε Ν-1 επαναλήψεις για Ν αριθμούς).  Συνεπώς είναι καλή άσκηση να δούν τι αλλάζει όταν βάλουμε Για Ι απο 1 μέχρι Ν-1.
Επίσης πρέπει να καταλάβουν ότι η δεύτερη επανάληψη είναι  αυτή που κάνει "τη δουλεία" των αντιμεταθέσεων.  Συνεπώς μπορεί να βάλουμε κάλιστα Για j από  Ν μέχρι 2  με _βήμα -1 και να γίνει μια χαρά η ταξινόμηση.  Εκεί πρέπει να καταλάβουν τι κερδίζουν βάζοντας αντί για 2 το Ι. 

Ενδιαφέρον έχει να προσπάθησουν να κάνουν την ταξινόμηση αρχίζοντας όχι απο το τέλος αλλά από την αρχή του πίνακα.  Επίσης να δούν τι αλλάζει αν αντί για Αν A[j-1] > A[j]  βάλουν  Αν Α[j] >A[j+1].

Τέλος πρέπει να δούν πως σταματάει ο αλγόριθμός όταν η ταξινόμηση έχει επιτευχθεί πριν απο Ν-1 επαναλήψεις.

Φιλικά
Βαγγέλης

kiro

  • Βετεράνος
  • ****
  • Μηνύματα: 52
  • Γράψτε το προσωπικό σας σλόγκαν!
Απ: επαναληψεις φυσαλιδα
« Απάντηση #9 στις: 24 Φεβ 2006, 12:30:38 μμ »
Αρχίζω να νιώθω τύψεις!! ούτε εγώ μίλησα για εξετάσεις...απλα μια δεύτερη γνώμη ζήτησα σε τυχόν απορία των παιδιών που πολλές φορές ρώτανε και τα πιο απίθανα!!

Ευχαριστώ :)

Ηλίας

  • Επισκέπτης
Απ: επαναληψεις φυσαλιδα
« Απάντηση #10 στις: 24 Φεβ 2006, 02:22:31 μμ »
Γεια χαρά σε όλους
πιστεύω και εγώ εν μέρη στο ας μεινουμε στο βιβλίο διότι το εξεταστικοκεντρικό σύστημα μας αναγκάζει, ΑΛΛΑ ας διευρύνουμε λίγο και τους ορίζοντες των παιδιών.
Ναι στις εξετάσεις καλύτερα ότι έχει το βιβλίο.
Στις ασκήσεις στην τάξη και στις προς μελέτη να παίζουμε με αλλαγές.
Άλλωστε (όπως ξαναέχω πει) η χρονιά είναι περίεργη.
Δεν αποκλείτε να δώσουν έτοιμο αλγόριθμο ταξινόμησης με
Για i απο 1 μέχρι Ν-1
  Για j από Ν μέχρι ι+1 ή Για j από Ν-1 μέχρι ι με_βήμα -1
   Αν Π[j]>Π[j-1] τότε  ή    Αν Π[j]>Π[j+1]


και πολλές άλλες προσεγγίσεις και να ζητήσουν π.χ. πίνακα μεταβλητων ........
Δεν μπορούμε να πούμε ότι είναι εκτός θέματος.
Νομίζω ότι υπάρχει χρόνος για δοκιμες.
Όπως π.χ. και στη σειριακή αναζήτηση μπορούν να γίνουν αλλαγές
Μέχρις_ότου .....

Καλό είναι να αποφθεχθούν στις εξετάσεις αλλά δυσκολεύμαι να βάλω σε καλούπια κάποιους καλούς και δημιουργικούς αν και δεν ξέρω αν κάνω καλά (κάτι που συνηθίζουμε σχεδόν όλοι.

Ηλίας