Μετατροπή Μέχρις_ότου σε Για (θέμα εξετάσεων)

[andreas_p]

Για Α=4 και Μ=6 βγάζει ένα 8 παραπάνω. Έχει αρχίσει και έχει πλάκα αυτό το θεματάκι.

Γιώργο, καλημέρα.

Ρίξε  μια 2η ματιά   για  Α=4  και Μ=6.

Μέχρις_ότου  ->  6  και 8
Για               ->  6 και 8

Μήπως τελικά ... δεν 'μπάζει' άλλο ;;;;

Ανδρέας

[gpapargi]

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

Κάνω λοιπόν την απόπειρα

Ο αρχικός κώδικας είναι:

Χ ← Α
Αρχή_επανάληψης
     Χ ← Χ + 2
     Εκτύπωσε το Χ
Μέχρις_ότου Χ >= Μ

Αυτό ισοδύναμα μετατρέπεται σε:

Χ ← Α
Χ ← Χ + 2
Εκτύπωσε το Χ
Όσο Χ<Μ επανάλαβε
    Χ ← Χ + 2
    Εκτύπωσε το Χ
Τέλος_επανάληψης

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

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

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

Άρα «ισοδύναμα» έχω (τα εισαγωγικά έχουν νόημα γιατί στην πραγματικότητα έχω κλέψει):
Χ ← Α
Χ ← Χ + 2
Εκτύπωσε το Χ
Όσο Χ<Μ επανάλαβε
    Εκτύπωσε το Χ+2
    Χ ← Χ + 2
Τέλος_επανάληψης

Τώρα το μόνο που με ενοχλεί είναι ο τελεστής <. Θα ήθελα να τον κάνω <= για ομαλή μετάβαση σε Για.

Η σκέψη είναι να γράψω το Χ<Μ σαν (Χ<Μ ή Χ=Μ) και Χ<>Μ
Αυτά όντως είναι ισοδύναμα αφού
(Χ<Μ ή Χ=Μ) και Χ<>Μ ~                      ! (με επιμερισμό του και ως προς το ή)
(Χ<Μ και Χ<>Μ) ή (Χ=Μ και Χ<>Μ) ~ ! (σύζευξη αντιθέτων)
(Χ<Μ και Χ<>Μ) ή  Ψευδής ~                 ! (κάτι ή ψευδής μας κάνει το κάτι)
Χ<Μ και Χ<>Μ  ~                                    ! (η πρώτη συνθήκη περιέχει τη δεύτερη)
Χ<Μ
ʼρα η παραπάνω σχέση γίνεται:

Χ ← Α
Χ ← Χ + 2
Εκτύπωσε το Χ
Όσο (Χ<Μ ή Χ=Μ) και Χ<>Μ επανάλαβε
    Εκτύπωσε το Χ+2
    Χ ← Χ + 2
Τέλος_επανάληψης

Αυτό γράφεται ισοδύναμα
Χ ← Α
Χ ← Χ + 2
Εκτύπωσε το Χ
Όσο (Χ<=Μ) και Χ<>Μ επανάλαβε
    Εκτύπωσε το Χ+2
    Χ ← Χ + 2
Τέλος_επανάληψης

Όπου απλά έγραψα το (Χ<Μ ή Χ=Μ) σαν Χ<=Μ (για να εμφανιστεί ο τελεστής που θέλω για ομαλή μετάβαση σε Για.

Ο έλεγχος της Όσο σημαίνει
Αν  (Χ<=Μ) και Χ<>Μ τότε
…

Το οποίο μπορεί να γραφτεί ισοδύναμα
Αν Χ<=Μ τότε
    Αν Χ<>Μ τότε
       …

Όπου απλά άλλαξε τη σύνθετη συνθήκη με εμφώλευση.
Έτσι προκύπτει:

Χ ← Α
Χ ← Χ + 2
Εκτύπωσε το Χ
Όσο (Χ<=Μ) επανάλαβε
   Αν Χ<> Μ τότε
      Εκτύπωσε το Χ+2
      Χ ← Χ + 2
    Τέλος_αν
Τέλος_επανάληψης

Εδώ υπάρχει ένα λεπτό σημείο: Η εντολή «Εκτύπωσε το Χ» πρέπει να εκτελείται μόνο όταν το Χ είναι μικρότερο του Μ (ο ρόλος του Αν είναι να μην εκτελεστεί η εντολή εμφάνισης όταν Χ=Μ). Αλλά η Χ<-Χ+2 πρέπει να εκτελείται κάθε φορά που μπαίνουμε στην Όσο έτσι ώστε να φύγουμε από το Χ=Μ και να τερματίσει ο βρόχος. Έτσι ο προηγούμενος κώδικας γίνεται:
Χ ← Α
Χ ← Χ + 2
Εκτύπωσε το Χ
Όσο (Χ<=Μ) επανάλαβε
   Αν Χ<> Μ τότε
      Εκτύπωσε το Χ+2
    Τέλος_αν
    Χ ← Χ + 2
Τέλος_επανάληψης

Οι 2 τελευταίοι ψευδοκώδικες είναι ίδιοι με μια μόνο διαφορά: Στην περίπτωση που το Χ γίνει Μ ο πρώτος δεν εκτελεί καμία εντολή ενώ ο δεύτερος εκτελεί μόνο τη δεύτερη. Έτσι το Χ αυξάνεται και τερματίζει ο βρόχος.

Τώρα είμαστε έτοιμη για μετάβαση σε Για. 
Χ ← Α
Χ ← Χ + 2
Εκτύπωσε το Χ
Για Χ από Α+2 μέχρι Μ με_βήμα 2
   Αν Χ<> Μ τότε
      Εκτύπωσε το Χ+2
    Τέλος_αν
Τέλος_επανάληψης