Μετατροπή από μία εντολή επανάληψης σε άλλη

[Σπύρος Δουκάκης]

Το ερώτημά σου έχει συζητηθεί και στο παρελθόν.

Αν θέλεις δες το https://alkisg.mysch.gr/steki/index.php?topic=1142.0

Στην αλγοριθμική προσέγγιση της μετατροπής από μία εντολή επανάληψης σε άλλη , για τη μετατροπή από
ΟΣΟ σε ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ υπάρχει η μεθοδολογία:
Αν συνθήκη τότε
  Αρχή_επανάληψης
         Εντολές
  Μέχρις_ότου όχι(συνθήκη)
Τέλος_αν

Θα μπορούσε ισοδύναμα να χρησιμοποιηθεί το:
Αρχή_επανάληψης
    Αν συνθήκη τότε
           Εντολές
    Τέλος_αν
Μέχρις_ότου όχι(συνθήκη)
ή είναι λάθος το ότι μπαίνει μια φορά στην αρχή_επανάληψης ακόμα και αν δεν εκτελεί κάτι;

[Σπύρος Δουκάκης]

Επανήλθε στο μυαλό μου σε κάποια φάση το θέμα της μετατροπής από την Όσο σε Για στην περίπτωση που ο συγκριτικός τελεστής είναι αυστηρά μικρότερος ή αυστηρά μεγαλύτερος και διαπίστωσα το εξής:

Σε περίπτωση αυστηρής ανισότητας (> ή <) όταν οι τ1, τ2 και β έχουν συγκεκριμένη αριθμητική τιμή, η τελική τιμή της εντολής Για, για την οποία προκύπτει ισοδύναμος αλγόριθμος, μπορεί να τεθεί απλά ως εξής:

Αν β >(<) 0 τότε τ2 = τ2 -(+) 10^-Ν

όπου η μεταβλητή Ν εκφράζει τη μεγαλύτερη θέση του τελευταίου μη μηδενικού ψηφίου μετά την υποδιαστολή, στις τιμές των τ1, τ2 και β. Είναι προφανές ότι το Ν ισούται με μηδέν αν όλοι οι αριθμοί είναι ακέραιοι.

Με άλλα λόγια δεν είναι απαραίτητος όλος αυτός ο διαχωρισμός σε περιπτώσεις (ακέραιων και πραγματικών ή προσθέτω ή αφαιρώ ένα ή 0,1 ή 0,01 ανάλογα με το αν... ), όπως έχει ειπωθεί. Όλη η ιστορία είναι μία γραμμή.

Αυτά βέβαια είναι εφαρμόσιμα στην περίπτωση που έχουν συγκεκριμένες αριθμητικές τιμές οι τ1, τ2 και β , διότι σε κάθε άλλη περίπτωση η μετατροπή δεν μπορεί να γίνει με τον τρόπο αυτό όπως αναδείχτηκε στην εργασία που βρίσκεται σε προηγούμενο μήνυμα.

Στην περίπτωση που οι τ1, τ2 και β δεν έχουν συγκεκριμένη αριθμητική τιμή τότε:

Βήμα 1:   Υπολογισμός των φορών που αλλάζει η μεταβλητή κατά το βήμα για να πλησιάσει ή να φτάσει την τελική τιμή, όχι όμως να την ξεπεράσει,
                στη γενική μορφή της εντολής Όσο...επανάλαβε: κ = Α_Μ((τ2 - τ1) / β)
Βήμα 2:   Εύρεση της τελευταίας τιμής που λαμβάνει πραγματικά η μεταβλητή της εντολής Όσο...επανάλαβε στη γενική της μορφή: τπ2 = τ1 + κ * β
Βήμα 3:   Εύρεση της πραγματικά τελικής τιμής αν στην περίπτωση της αυστηρής ανισότητας ισχύει τπ2 = τ2, από τον τύπο τπ2 = τ1 + κ * β - β

ή αλγοριθμικά

κ ← Α_Μ((τ2 - τ1) / β)
τπ2 ← τ1 + κ * β
Αν τπ2 = τ2 τότε τπ2 ← τπ2 - β

[gpapargi]

Είδα κι άλλες τέτοιες συζητήσεις πρόσφατα, αλλά δυστυχώς δεν είχα χρόνο να συμμετάσχω και με έχει απασχολήσει το θέμα.
Θέλω να κάνω μια διευκρινιστική ερώτηση για τη βάση της κουβέντας:

Στα πλαίσια της Γ λυκείου και των πανελληνίων εξετάσεων, τι ακριβώς ζητάμε όταν θέλουμε μετατροπή μια δομή επανάληψης σε μια άλλη;

1) Ζητάμε οι 2 κώδικες να έχουν την ίδια έξοδο για την ίδια είσοδο;
2) Ζητάμε οι 2 κώδικες να έχουν την ίδια έξοδο για την ίδια είσοδο και την ίδια πολυπλοκότητα;
3) Ζητάμε οι 2 κώδικες να κάνουν ακριβώς τα ίδια πράγματα με ακριβώς την ίδια σειρά;
4) Ζητάμε κάτι άλλο; Αν ναι, τι ακριβώς;

Προσωπικά πιστεύω ότι ζητάμε το 3, αλλά μπορούμε να το συζητήσουμε. Δεν έχω πρόβλημα ότι και να ζητάμε, αλλά θα πρέπει οπωσδήποτε να το ξεκαθαρίσουμε για να μπορούμε να αποφασίσουμε πότε μια λύση είναι σωστή και πότε όχι. Κατά τη γνώμη μου ότι και να αποφασίσουμε θα υπάρχουν συνέπειες που δε θα μας αρέσουν, αλλά είναι αναγκαίες γιατί θα προκύπτουν από τον ορισμό που δώσαμε. Για μένα το θέμα είναι να αποφασίσουμε σε τι ακριβώς θέλουμε να εξετάσουμε το μαθητή.

[Αθανάσιος Πέρδος]

1) Με βάση τους διαγωνισμούς πληροφορικής ισοδύναμα τμήματα αλγορίθμου είναι αυτά που για ίδια είσοδο δίνουν ίδια έξοδο. Βέβαια εκεί εξετάζεται και ο χρόνος εκτέλεσης κατί που στο πλαίσιο της ΑΕΠΠ δεν είναι εφικτό.
2) Η πολυπλοκότητα είναι εκτός ύλης άρα δεν μπορούμε να μίλάμε σε τέτοια βάση.
3) Είναι αδύνατον να γίνουν όλες οι μετατροπές και να εκτελούνται οι εντολές με την ίδια σειρά αφού είναι διαφορετικός ο τρόπος λειτουργίας τους.
Μάλλον αν κρίνουμε και από τα θέματα των πανελλαδικών, αυτό που ζητάμε είναι να υλοποιηθεί ένα τμήμα αλγορίθμου με κάποια άλλη εντολή επανάληψης, εφόσον αυτό είναι εφικτό, ώστε να προκύπτουν ίδια αποτελέσματα για ίδια δεδομένα.Καλό όμως είναι, μιας και τέτοιου είδους θέματα εξετάζονται συχνά πυκνά, να υπάρξει ένα διδακτικό συμβόλαιο το οποίο να ξεκαθαρίζει τι ακριβώς ζητάμε από τους μαθητές. Ή η εκφώνηση να είναι έτσι δομημένη που να μην αφήνει περίπτωση παρερμηνείας.
Νομίζω ότι μια διευκρύνηση από το Π.Ι. θα έλυνε το θέμα.
 

[gpapargi]

Για το 1 συμφωνώ κι εγώ. Να και ένα παράδειγμα:

Ας πούμε ότι η εκφώνηση δίνει τη σειριακή αναζήτηση με Όσο και ζητάει μετατροπή σε Μέχρις_ότου. Ο μαθητής γράφει τη δυαδική (αντί για τη σειριακή αναζήτηση) με μέχρις_ότου. Έχουμε ίδια έξοδο για την ίδια είσοδο. Αλλά είναι φανερό ότι ο μαθητής δεν ελέγχθηκε σε αυτό που θέλαμε. Άρα μια τέτοια προσέγγιση δε μας κάνει για το λύκειο. Φυσικά για τους διαγωνισμούς δεν υπάρχει πρόβλημα να πούμε: «αντί για τη σειριακή αναζήτηση έκανα ισοδύναμο αλγόριθμο που τρέχει πιο γρήγορα». Εκεί τους κάνει. Εμάς όμως δε μας κάνει.

Για το 2 επίσης συμφωνώ. Έχω κι εκεί ένα αντιπαράδειγμα που είχα αναφέρει και παλιότερα: Σε πίνακα 2 διαστάσεων να δώσεις μέσο όρο στήλης σαρώνοντας κατά στήλη (με όσο) και ο μαθητής να γυρίσει μέσο όρο στήλης σαρώνοντας κατά γραμμή (με μέχρις)ότου). Πάλι δεν έκανε αυτό που θέλουμε.

Το 3 θέλει κουβέντα. Σε κάποιες περιπτώσεις είναι δυνατόν να εκτελούνται τα ίδια βήματα και με την ίδια σειρά, όπως πχ κάθε μετατροπή μεταξύ Όσο και μέχρις_ότου. Σε τέτοιες περιπτώσεις ορίζεται η μετατροπή με αυτό τον τρόπο και τέτοιες μόνο ασκήσεις πρέπει να ζητάμε.

Πχ
Όσο συνθήκη επανάλαβε
  Ομάδα εντολών
Τέλος_επανάληψης

Αν συνθήκη τότε
  Αρχή_επανάληψης
    Ομάδα εντολών
  Μέχρις_ότου όχι (συνθήκη)
Τέλος_αν

Τα 2 παραπάνω τμήματα κάνουν ακριβώς τα ίδια βήματα με την ακριβώς ίδια σειρά (εννοείται ότι αν ελέγχεις μια συνθήκη ελέγχεις ταυτόχρονα και την άρνησή της, η πληροφορία είναι ίδια).

Δεν είναι ίδια η μετατροπή της Όσο με αλλαγή μετρητή στη μέση σε Για. Μπορείς να δώσεις ίδια έξοδο για ίδια είσοδο αλλά έχεις αλλοιώσει τη σειρά.

Πιστεύω ότι επειδή  δεν έχει αποσαφηνιστεί το θέμα, στις πανελλήνιες δεν έχει ξέρουν τι ακριβώς ζητάνε. Το θέμα προέκυψε ακριβώς επειδή στο παρελθόν έδωσαν λάθος λύση σε μια μετατροπή. Το ζητούμενο είναι τουλάχιστον εμείς στο forum να καταλήξουμε κάπου ως προς το τι έχει νόημα να ζητάμε. Πρέπει να καταλήξουμε σε ένα ορισμό και να τον ακολουθήσουμε.

[Αθανάσιος Πέρδος]

Αν όμως δοθεί το παρακάτω

χ<--3
όσο χ<=8 επανάλαβε
   Εμφάνισε χ
   χ <-- χ + 2
Τέλος_επανάληψης

και δοθεί ως μετατροπή

χ<--3
Αρχή_επανάληψης
Εμφάνισε χ
   χ <-- χ + 2
Μέχρις_ότου όχι(χ<=8)

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

Άρα μέσα στο πλαίσιο του μαθήματος όπως έχει οριστεί μέσα στο διδακτικό πακέτο και με βάση τις διευκρινήσεις του Π.Ι. εγώ θα πρότεινα να καταλήξουμε στην παραδοχή "ίδια είσοδος - ίδια έξοδος"

[gpapargi]

Αυτό ακριβώς είχα στο νου όταν έγραψα πιο πάνω "Κατά τη γνώμη μου ότι και να αποφασίσουμε θα υπάρχουν συνέπειες που δε θα μας αρέσουν, αλλά είναι αναγκαίες γιατί θα προκύπτουν από τον ορισμό που δώσαμε."

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

Το βασικό είναι να δοθεί ορισμός που ανταποκρίνεται σε αυτό που αισθανόμαστε ότι θέλουμε να εξετάσουμε που είναι ουσιαστικά το «να κάνεις τα ίδια με την άλλη εντολή». Το να βάλεις την παραπανίσια συνθήκη δεν του κάνει και κακό του μαθητή. Ίσα ίσα που θα καταλάβει και καλύτερα τη λειτουργία των εντολών. Το μόνο κακό είναι ότι έρχεται σε αντίθεση με πράγματα που θεωρούμε δεδομένα. Και τελικά ο κώδικας με την παραπανίσια εντολή είναι και πιο σωστός αφού αυτό ακριβώς γίνεται.  Δηλαδή αν θέλεις να κάνεις ακριβώς τα ίδια πράγματα, όντως η παραπανίσια εντολή δεν είναι παραπανίσια αλλά αναγκαία. Χωρίς βέβαια αυτό να σημαίνει ότι πρόκειται για σοβαρό σφάλμα.

Το πραγματικό πρόβλημα θα έρθει αν  ο μαθητής καταφέρει και κάνει με την ίδια εντολή άλλα πράγματα (όπως πχ δυαδική-σειριακή). Αυτό είναι το μειονέκτημα του "ίδια είσοδος- ίδια έξοδος"

[Αθανάσιος Πέρδος]

Το παράδειγμα που δίνεις είναι ιδιαίτερη περίπτωση και δεν ξέρω και τι ακριβώς θα εξετάζαμε αν δοθεί.
Έστω όμως ότι δίνονταν τέτοιο παράδειγμα. Μπορούμε να πάμε σε διατύπωση της μορφής  «να κάνεις τα ίδια με την άλλη εντολή» και συμπληρώνω εγώ "χωρίς όμως να αλλάξεις τη λογική του τμήματος αλγορίθμου μέσα στο σώμα της επανάληψης".
Εξάλλου σε ένα θέμα μετατροπής θα πρέπει να μας ενδιαφέρει πως συντάσεται η δομή επανάληψης και όχι τι κάνει ο αλγόριθμος που υλοποιείται με τη χρήση της επανάληψης.
Νομίζω ότι η κατάλληλη εκφώνηση μπορεί να ξεκαθαρίσει τι ακριβώς ζητάμε σε μία μετατροπή από μία εντολή επανάληψης σε μία άλλη.
Διαφορετικά και όπως έχουν δοθεί οι εκφωνήσεις μέχρι τώρα στις πανελλαδικές προτείνω "ίδια είσοδος - ίδια έξοδος".

Α και κάτι ακόμα που μου ξέφυγε πριν. Στην μετατροπή από όσο σε Για με εντολές μετά την αλλαγή της μεταβλητής κατά το βήμα, στην εργασία που παρουσιάσαμε στο συνέδριο της ΠΕΚΑΠ δεν αλλάζουμε την σειρά των εντολών. Απλά αλλάζουμε την τιμή της μεταβλητής κατά το βήμα όπου αυτή εμπλέκεται στις συγκεκριμένες εντολές. Απλά όπως έχει συζητηθεί και στο foroum, το πως δουλεύει η Για σε επίπεδο μεταγλωτιστή - διερμηνευτή, δεν είναι ξεκάθαρο από κανέναν.

[gpapargi]

Την εργασία την είδα (βέβαια όχι με πολλή λεπτομέρεια). Ξεκαθαρίζει ότι ασχολείται με το ίδια είσοδος-ίδια έξοδος, οπότε στο πλαίσιο αυτό δεν υπάρχει πρόβλημα.
Παρένθεση:
(Από ότι είδα ασχολείται και με περιπτώσεις μετατροπής που η Όσο με γνήσια ανισότητα γίνεται Για. Εδώ αλλάζει η συνθήκη δηλαδή αλλάζουν τα ακριβή βήματα. Η Όσο ελέγχει πχ αν χ<10 και η Για ελέγχει αν χ<=10. Επίσης υπάρχουν και περιπτώσεις που δε θυμάμαι αν αναφέρονται στην εργασία, αλλά υπάρχουν σε ασκήσεις που κυκλοφορούν και έχω λύσει τέτοιες που ο μετρητής της όσο αλλάζει στη μέση)

Ξαναλέω όμως ότι η εργασία κινείται στο πλαίσιο «ίδια είσοδος ίδια έξοδος» οπότε με αυτή την παραδοχή δεν υπάρχει κάποια διαφωνία.

Το παράδειγμα που ανέφερα είναι απλά μια ένδειξη του τι μπορεί να πάει στραβά με έναν ορισμό. Φοβάμαι πως η φράση «χωρίς όμως να αλλάξεις τη λογική του τμήματος αλγορίθμου μέσα στο σώμα της επανάληψης» δεν είναι απόλυτα σαφής και αυστηρή. Τι είναι ακριβώς η «λογική του αλγορίθμου»; Εγώ καταλαβαίνω τα ακριβή βήματα και τη σειρά κάτι απόλυτα σαφές (με τα όποια στραβά του), αλλά εσύ δεν εννοείς αυτό. Είναι η ίδια πολυπλοκότητα; Σίγουρα όχι.

Για να δεις με ένα παράδειγμα τι σου λέω φαντάσου πχ ότι δίνεται κώδικας που υπολογίζει το άθροισμα 100 όρων της ακολουθίας 1/ν γραμμένος σε όσο με το ν να ξεκινάει από 1 και να φτάνει στο 100. Στη μετατροπή σε μέχρις_ότου ο μαθητής γράφει την εντολή με το ν να ξεκινάει από το 100 και να φτάνει στο 1.

Σίγουρα η «λογική» δεν άλλαξε, αλλά πάλι ο μαθητής δεν έκανε αυτό που θέλουμε.

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

[Αθανάσιος Πέρδος]

Όσον αφορά την εργασία προτείνει τρόπο μετατροπής για όλες τις δυνατές περιπτώσεις αλλά δεν είναι αυτό τώρα το θέμα μας.
Η φράση "λογική του αλγορίθμου" ούτε εμένα μου αρέσει. Έχεις δίκαιο μάλλον μία αναφορά στα βήματα και τη σειρά τους θα ήταν καλύτερη διατύπωση.
Τελικά όμως καταλήγω σε  δύο πράγματα Ή μια διατύπωση της ακόλουθης μορφής "Να μετατραπεί το τμήμα αλγορίθμου ώστε αντί της εντολής Για να χρησιμοποιηθεί η εντολή Μέχρι_ότου." και από εκεί και πέρα αφού κάθε απάντηση επιστημονικά τεκμηριωμένη είναι αποδεκτή ας γράψει ο μαθητής όπως νομίζει τις υπόλοιπές εντολές αρκεί να δίνουν ο αρχικός αλγόριθμος και αυτός με την μετατροπή τα ίδια αποτελέσματα, ή αυτός που βάζει τα θέματα ας ξεκαθαρίσει με μία σαφέστατη διατύπωση τι ακριβώς θέλει να δεί κατά την μετατροπή.
Άρα μάλλον συμφωνούμε ότι μέσω της διατύπωσης μπορούμε να ορίσουμε ξεκάθαρα όπως λές, τι ακριβώς αξιολογούμε.