Ερώτημα πάνω στο θέμα 1.Γ.1 Διαγωνίσματος 06-07 Δ.επανάληψης

[mbathas]

Συνάδελφοι καλημέρα,
Σας παραθέτω ένα θέμα από διαγώνισμα του στεκιού για συζήτηση:

Δίνεται το ακόλουθο τμήμα αλγορίθμου κωδικοποιημένο σε ψευδογλώσσα:

Διαβασε κ
ι ← 1
Αρχή_επανάληψης
  Εμφάνισε ι
  ι  ← ι+1
Μέχρις_ότου ι>κ

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

Προφανώς για να μετατρέψουμε την αρχή_επανάληψης σε Για..από...μέχρι θα χρησιμοποιήσουμε σαν σκαλοπάτι την όσο...επανάλαβε.
Η πρώτη σκέψη θα ήταν:
Διάβασε κ
i<-1
Όσο i<=κ επανάλαβε
   Εμφάνισε i
   i<-i+1
Τελος_επανάληψης
¨Ομως πρέπει να προσέξουμε την περίπτωση όπου το κ<1 γιατί εκεί θέλουμε να εμφανιστεί η αρχική τιμή του i που είναι το 1.

Έτσι μαθητής μου έδωσε τη λύση:

Διάβασε κ
i<-1
Εμφάνισε i
Όσο i<=κ επανάλαβε
   Εμφάνισε i
   i<-i+1
Τελος_επανάληψης
... στην οποία όμως για κ>=1 η αρχική τιμή του I που είναι 1 εμφανίζεται 2 φορές...

Έτσι μπορούμε να οδηγηθούμε στην εξής λύση:

Διάβασε κ
i<-1
Αν κ<1 τότε Εμφάνισε i
Όσο i<=κ επανάλαβε
   Εμφάνισε i
   i<-i+1
Τελος_επανάληψης

και άρα στην:
Διάβασε κ
Αν κ<1 τότε εμφάνισε i
Για i από 1 μέχρι κ
   Εμφάνισε i
Τέλος_επανάληψης

Περιμένω τις απόψεις σας πάνω στη λύση του μαθητή (θα κόβατε κάτι για μια επιπλέον εμφάνιση?) και στη λύση που παραθέτω.

[gpapargi]

Προφανώς είναι λάθος το να εκτυπωθεί κάτι διαφορετικό.

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

Ας δούμε λίγο το ποια είναι ακριβώς τα βήματα που κάνει ο παραπάνω κώδικας.

Διαβάζω κ
Θέτω ι ίσο με 1
***************
Εμφανίζω ι
Αυξάνω ι κατά 1
Ελέγχω αν ι>κ
****************
Εμφανίζω ι
Αυξάνω ι κατά 1
Ελέγχω αν ι>κ
****************
Εμφανίζω ι
Αυξάνω ι κατά 1
Ελέγχω αν ι>κ

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

Ξαναγράφω τώρα ακριβώς τα ίδια βήματα αλλάζοντας μόνο το γκρουπάρισμα έτσι ώστε να αρχίζω με έλεγχο. Ο σκοπός είναι σχεδόν προφανής: Να κάνω αντιστοίχιση των βημάτων με την Όσο που ξεκινάει από συνθήκη. Έχω λοιπόν:

Διαβάζω κ
Θέτω ι ίσο με 1
Εμφανίζω ι
Αυξάνω ι κατά 1
***************
Ελέγχω αν ι>κ
Εμφανίζω ι
Αυξάνω ι κατά 1
****************
Ελέγχω αν ι>κ
Εμφανίζω ι
Αυξάνω ι κατά 1
****************
Ελέγχω αν ι>κ

Προσοχή ότι κανένα βήμα δεν έχει αλλάξει παρά μόνο το γκουπάρισμα.
Τώρα η μετατροπή σε Όσο είναι προφανής:
Διάβασε κ
ι<-1
Εμφάνισε ι
ι<-ι+1
Όσο ι<=κ επανάλαβε
  Εμφάνισε ι
  ι<-ι+1
Τέλος_επανάληψης

Αυτή είναι η ακριβής μεταφορά δηλαδή αυτή που κάνει ακριβώς τα ίδια πράγματα με ακριβώς την ίδια σειρά.

Βέβαια μπορεί κάποιος να πει απλά "βγάζουμε μια φορά τις εντός βρόχου εντολές απέξω". Εγώ όμως επιμένω στην απόδειξη για να καταλάβουν τι γίνεται ακριβώς. Ομοίως αποδεικνύεται και η μετατροπή από Όσο σε Μέχρις_ότου. (Καταλήγει σε μια Αν έξω από τη μέχρις_ότου. )

Τώρα αν θέλουμε απλώς την ίδια έξοδο μπορούμε να κάνουμε:
Διάβασε κ
Εμφάνισε «1»
Για ι από 2 μέχρι κ
  Εμφάνισε ι
Τέλος_επανάληψης

[mbathas]

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

Από κει και πέρα τη λύση που παραθέτω θα τη θεωρούσες λανθασμένη ?

Διάβασε κ
i<-1
Αν κ<1 τότε Εμφάνισε i
Όσο i<=κ επανάλαβε
   Εμφάνισε i
   i<-i+1
Τελος_επανάληψης

[gpapargi]

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

Επίσης εδώ  τίθεται ένα σοβαρό θέμα: το κατά πόσο 2 κώδικες είναι ισοδύναμοι.
Αν απλώς δίνουν ίδια έξοδο για ίδια είσοδο είναι ισοδύναμοι;

Εγώ λέω όχι. Για μένα καταρχήν πρέπει να μιλάμε για ισοδυναμία και μετατροπή  κωδικοποιήσεων και όχι αλγορίθμων. Και για να είναι 2 κώδικες ισοδύναμοι πρέπει να κάνουν ακριβώς τα ίδια πράγματα με ακριβώς την ίδια σειρά. Οτιδήποτε άλλο μπορεί να οδηγήσει σε ασυνέπειες. Η ίδια έξοδος για ίδια είσοδο δε μου αρκεί για ορισμό ισοδυναμίας κωδικοποιήσεων. Σκέψου πχ ότι ο δοσμένος κώδικας κάνει σειριακή αναζήτηση με «όσο» και ο νέος κάνει δυαδική αναζήτηση με «μέχρις_ότου». Ίδια έξοδο έχουμε.
Κάναμε καμιά ισοδύναμη μετατροπή από όσο σε μέχρις_ότου; Όχι. Έχουμε αλλάξει αυτό που κάνει ο κώδικας και δε μιλάμε για μετατροπή από Όσο σε μέχρις_ότου. Για να μιλάμε για κάτι τέτοιο πρέπει οι κώδικες να κάνουν το ίδιο πράγμα.

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

[Νίκος Αδαμόπουλος]

Από κει και πέρα τη λύση που παραθέτω θα τη θεωρούσες λανθασμένη ?

Διάβασε κ
i<-1
Αν κ<1 τότε Εμφάνισε i
Όσο i<=κ επανάλαβε
   Εμφάνισε i
   i<-i+1
Τελος_επανάληψης

(συμπληρώνω: αφού δίνει την ίδια έξοδο, όπως ζητάει και η άσκηση τότε είναι σωστό - όμως δεν είναι με Για...από...μέχρι - βλέπε επόμενα μηνύματα του andrea_p)

Με την ευκαιρία δες τε το "αντίθετο" Θέμα 1.Δ των Επαναληπτικών του 2006 (αν και εκεί μιλάει για ισοδυναμία...)

http://dide.ilei.sch.gr/keplinet/education/docs/them_plir_c_kat_hmer_epan_060706.pdf

[andreas_p]

Διάβασε κ
Αν κ<1 τότε Εμφάνισε 1
Για i από 1 μέχρι κ
   Εμφάνισε i
Τέλος_επανάληψης

[andreas_p]

ή καλύτερα για να διασφαλίσουμε την εκχώρηση του 1 στο  i  (που πάντα συμβαίνει)

Διάβασε κ
Αν κ<1 τότε
   i <-1
   Εμφάνισε i
Τέλος_αν
Για i από 1 μέχρι κ
   Εμφάνισε i
Τέλος_επανάληψης

[Νίκος Αδαμόπουλος]

ή καλύτερα για να διασφαλίσουμε την εκχώρηση του 1 στο  i  (που πάντα συμβαίνει)

Και με τον 1ο τρόπο σου δεν θα εκχωρηθεί στο i το 1; Αν και σιγά σιγά το σπρώχνουμε προς τις γνωστές γκρίζες ζώνες... 

[andreas_p]

ok. Αρκεί ο 1ος τρόπος.

[gpapargi]

Προφανώς η ερώτηση ζητάει με Για και η απάντηση του Μιχάλη είναι με Όσο. Ωστόσο καταλαβαινόμαστε. Απαντάω σε αυτό που θέλει να πει και όχι σε αυτό που είπε. Εννοείται ότι η Όσο που παρουσίασε γίνεται Για με τελειώς τετριμένο τρόπο.

Θα επαναλάβω όμως ότι το να φτιάχνεις λύσεις που ελέγχονται με trial and error δεν είναι ασφαλές. Προτιμώ λύσεις που είναι δυνατόν η ορθότητά τους να αποδειχτεί. Υπάρχει και το πλεονέκτημα ρτων ακριβώς ίδιων βημάτων και μετην ίδια σειρά που οδηγεί στην βαθύτερη κατανόηση των εντολών επανάληψης και στο πως 2 διαφορετικές απο αυτές είναι δυνατόν να οδηγούν σε απολύτως πανομοιότυπα βήματα. Ίδια βήματα-ίδιος αλγόριθμος-διαφορετική κωδικοποίση σε ψευδογλώσσα. Αυτό είναι και το νόημα αυτών των ασκήσεων. Αυτό θέλει να ελέγξει ο θεματοδότης.

[mbathas]

Προφανώς η ερώτηση ζητάει με Για και η απάντηση του Μιχάλη είναι με Όσο. Ωστόσο καταλαβαινόμαστε. Απαντάω σε αυτό που θέλει να πει και όχι σε αυτό που είπε. Εννοείται ότι η Όσο που παρουσίασε γίνεται Για με τελειώς τετριμένο τρόπο.

Θα επαναλάβω όμως ότι το να φτιάχνεις λύσεις που ελέγχονται με trial and error δεν είναι ασφαλές. Προτιμώ λύσεις που είναι δυνατόν η ορθότητά τους να αποδειχτεί. Υπάρχει και το πλεονέκτημα ρτων ακριβώς ίδιων βημάτων και μετην ίδια σειρά που οδηγεί στην βαθύτερη κατανόηση των εντολών επανάληψης και στο πως 2 διαφορετικές απο αυτές είναι δυνατόν να οδηγούν σε απολύτως πανομοιότυπα βήματα. Ίδια βήματα-ίδιος αλγόριθμος-διαφορετική κωδικοποίση σε ψευδογλώσσα. Αυτό είναι και το νόημα αυτών των ασκήσεων. Αυτό θέλει να ελέγξει ο θεματοδότης.

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

[mbathas]

Άρα λοιπόν αν θέλουμε να καταλήξουμε σε μια ΄"τυποποίηση", μπορούμε να πούμε να πούμε ότι:
1) από μέχρις ότου... σε όσο...
Βγάζω το μπλοκ εντολών που είναι εντός της επανάληψης, αυτούσιο να εκτελεστεί μία φορά πριν την επανάληψη
2) από όσο.. σε μέχρις ότου...
βάζω τη μέχρις ότου μέσα σε μια δομή απλής επιλογής για να ελεγχθεί την πρώτη φορά αν θα γίνει η επανάληψη

και νομίζω είμαστε οκ,έτσι δεν είναι?

[Νίκος Αδαμόπουλος]

Προφανώς η ερώτηση ζητάει με Για και η απάντηση του Μιχάλη είναι με Όσο. Ωστόσο καταλαβαινόμαστε. Απαντάω σε αυτό που θέλει να πει και όχι σε αυτό που είπε. Εννοείται ότι η Όσο που παρουσίασε γίνεται Για με τελειώς τετριμένο τρόπο.

Οκ. Δεν υπήρχε διαφωνία πάνω σε αυτό...

[Νίκος Αδαμόπουλος]

Άρα λοιπόν αν θέλουμε να καταλήξουμε σε μια ΄"τυποποίηση", μπορούμε να πούμε να πούμε ότι:
1) από μέχρις ότου... σε όσο...
Βγάζω το μπλοκ εντολών που είναι εντός της επανάληψης, αυτούσιο να εκτελεστεί μία φορά πριν την επανάληψη
2) από όσο.. σε μέχρις ότου...
βάζω τη μέχρις ότου μέσα σε μια δομή απλής επιλογής για να ελεγχθεί την πρώτη φορά αν θα γίνει η επανάληψη

και νομίζω είμαστε οκ,έτσι δεν είναι?

Εγώ πιστεύω ότι καλές είναι οι τυποποιήσεις, αλλά και ότι η κάθε άσκηση αποτελεί ξεχωριστή περίπτωση. Για τη συγκεκριμένη άσκηση, ναι, αυτή η τυποποίηση είναι εντάξει, αλλά ας μην τη γενικεύσουμε...

Π.χ. στην:

i<-1
Όσο i<=100 επανάλαβε
   Εμφάνισε i
   i<-i+1
Τελος_επανάληψης

... είναι σίγουρο ότι έχουμε 100 επαναλήψεις. Το ίδιο και στην:

i ← 1
Αρχή_επανάληψης
  Εμφάνισε ι
  i ← i+1
Μέχρις_ότου i>100

... αλλά και στην:

Για i από 1 μέχρι 100
   Εμφάνισε i
Τέλος_επανάληψης


Γιατί λοιπόν να βγάλεις το μπλοκ εντολών αυτούσιο να εκτελεστεί μία φορά πριν την επανάληψη (στην Όσο), ή να το βάλεις μέσα σε μια δομή απλής επιλογής για να ελεγχθεί την πρώτη φορά αν θα γίνει η επανάληψη (στην Μέχρις_ότου);...