Μετατροπή δομών επανάληψης

[eleni_p]

Καλησπέρα,

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

Από Αρχή_επανάληψης σε  Όσο (για γνωστό αριθμό επαναλήψεων – αρχικοποίηση με μετρητή).

μτ<-ατ
Αρχή_επανάληψης
Εντολές_1
μτ<-μτ+τιμή
Εντολές_2
Μέχρις_ότου <μτ τελεστής ττιμή>

μτ<-ατ
Εντολές_1
μτ<-μτ+τιμή
Εντολές_2
Όσο ΟΧΙ <μτ τελεστής ττιμή> επανάλαβε
Εντολές_1
μτ<-μτ+τιμή
Εντολές_2
Τέλος_επανάληψης

Από Όσο σε  Αρχή_επανάληψης (για γνωστό αριθμό επαναλήψεων – αρχικοποίηση με μετρητή).

μτ<-ατ
Όσο <μτ τελεστής ττιμή> επανάλαβε
Εντολές_1
μτ<-μτ+τιμή
Εντολές_2
Τέλος_επανάληψης

μτ<-ατ
Αρχή_επανάληψης
Αν <μτ τελεστής ττιμή>
Εντολές_1
μτ<-μτ+τιμή
Εντολές_2
Τέλος_αν
Μέχρις_ότου ΟΧΙ<μτ τελεστής ττιμή>

Ευχαριστώ,
Ελένη

[alkisg]

Στο τελευταίο, εγώ την Αν θα την έβγαζα απ' έξω, για να μην επιβαρύνεται η επανάληψη:

Κώδικας: Ψευδογλώσσα

μτ<-ατ
Αν <μτ τελεστής ττιμή> τότε
  Αρχή_επανάληψης
    Εντολές_1
    μτ<-μτ+τιμή
    Εντολές_2
  Μέχρις_ότου ΟΧΙ<μτ τελεστής ττιμή>
Τέλος_αν

Κατά τα άλλα καλό μου φαίνεται.

[P.Tsiotakis]

μπράβο Ελένη

μένουν 2 κατηορίες:
1. για <-> όσο
2. για <-> μέχρις_ότου

[alkisg]

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

Κώδικας: Ψευδογλώσσα

Εντολές_1
Όσο Συνθήκη_1 επανάλαβε
  Εντολές_2
Τέλος_επανάληψης

[gpapargi]

Χμμμμμ το θέμα αυτό με είχε απασχολήσει πολύ στο παρελθόν. Είχα αναπτύξει μια μέθοδο που παρέχει απόδειξη για όλες τις πιθανές μετατροπές (και όχι απλή μετατροπή). Η ίδια μέθοδος φωτογραφίζει αν μια άσκηση λύνεται καλύτερα με Όσο ή με Μέχρις_ότου και με αυτή κάνω την επιλογή.
Αν θυμάμαι καλά (δεν είμαι σίγουρος που είχα καταλήξει τότε) νομίζω ότι η Όσο με τελεστή < ή > και η μέχρις_ότου με τελεστή =< ή >= δεν μετατρέπεται πάντα σε Για ενώ τα άλλα γίνονται (ακόμα και η μεχρις_ότου με μετρητή στη μέση σε Για) . Εννοείται πως μιλάμε για Όσο και Μέχρις_ότου με συνθήκη πάνω στο μετρητή.
Είναι μια συζήτηση που πρέπει να την κάνουμε κάποια στιγμή για να δούμε και τι ακριβώς εννούμε όταν ζητάμε ισοδύναμο αλγόριθμο. 

Θέλω να βρω λίγο χρόνο να τα γράψω γιατί είναι αρκετά.   

[alkisg]

Ας ορίσουμε πρώτα τη ΓΙΑ και μετά πάμε και σε ισοδυναμίες! 

Π.χ.

Κώδικας: ΓΛΩΣΣΑ

ΓΙΑ α ΑΠΟ 1 ΜΕΧΡΙ α+1
  ΓΡΑΨΕ α
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Σταματάει αυτό ποτέ στη ΓΛΩΣΣΑ; Γιατί σε Pascal και Basic σταματάει μια χαρά, τα άκρα και το βήμα αποτιμούνται μόνο μία φορά... Κι αν πούμε ότι όντως συμβαίνει αυτό και στη ΓΛΩΣΣΑ, τότε καλύτερα να ξεχάσουμε τις μετατροπές από ΓΙΑ σε ΟΣΟ ή ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ, είναι υπερβολικά εξεζητημένες.

https://alkisg.mysch.gr/steki/index.php?topic=1118.msg7185#msg7185

[evry]

   
   Με τις ισοδυναμίες συμφωνώ και εγώ ότι υπάρχουν μερικά  μικροπροβληματάκια στον ορισμό. Ωστόσο στις γλώσσες C, C++, Java όπου η ΓΙΑ έχει τη μορφή

    for (i=1; i<=10; i=i+1)  { ...... }

έχουμε πλήρη ισοδυναμία μεταξύ ΓΙΑ και ΟΣΟ, δεν είναι αυτός ο τρόπος καλύτερος; δηλαδή δεν θα μπορούσαμε να είχαμε στη ΓΛΩΣΣΑ κάτι στο στυλ;

    ΕΠΑΝΑΛΑΒΕ ΓΙΑ (i=1; i<=10; i=i+1)  { ...... }

Ας ορίσουμε πρώτα τη ΓΙΑ και μετά πάμε και σε ισοδυναμίες! 

Π.χ.

Κώδικας: ΓΛΩΣΣΑ

ΓΙΑ α ΑΠΟ 1 ΜΕΧΡΙ α+1
  ΓΡΑΨΕ α
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Σταματάει αυτό ποτέ στη ΓΛΩΣΣΑ; Γιατί σε Pascal και Basic σταματάει μια χαρά, τα άκρα και το βήμα αποτιμούνται μόνο μία φορά... Κι αν πούμε ότι όντως συμβαίνει αυτό και στη ΓΛΩΣΣΑ, τότε καλύτερα να ξεχάσουμε τις μετατροπές από ΓΙΑ σε ΟΣΟ ή ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ, είναι υπερβολικά εξεζητημένες.

https://alkisg.mysch.gr/steki/index.php?topic=1118.msg7185#msg7185

[dionissis]

ΕΛΠΙΖΩ ΝΑ ΚΑΛΥΠΤΕΙ ΤΙΣ ΜΕΤΑΤΡΟΠΕΣ ΤΗΣ ΓΙΑ ΣΤΙΣ ΑΛΛΕΣ ΔΥΟ ΔΟΜΕΣ ΕΠΑΝΑΛΗΨΗΣ

ΓΕΝΙΚΗ ΜΟΡΦΗ ΓΙΑ
ΓΙΑ ΜΤ ΑΠΟ ΑΤ ΜΕΧΡΙ ΤΤ ΜΕ_ΒΗΜΑ ΒΜ
   ΕΝΤΟΛΕΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Όπου ΜΤ ο μετρητής, ΑΤ η αρχική τιμή, ΤΤ η τελική τιμή και ΒΜ το βήμα

ΓΙΑ ΣΕ ΟΣΟ
ΜΤ <- ΑΤ
ΑΝ ΒΜ >= 0 ΤΟΤΕ
   ΟΣΟ ΜΤ <= ΤΤ ΕΠΑΝΑΛΑΒΕ
      ΕΝΤΟΛΕΣ
      ΜΤ <- ΜΤ + ΒΜ
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΛΛΙΩΣ
   ΟΣΟ ΜΤ >= ΤΤ ΕΠΑΝΑΛΑΒΕ
      ΕΝΤΟΛΕΣ
      ΜΤ <- ΜΤ + ΒΜ
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΑΝ

ΓΙΑ ΣΕ ΜΕΧΡΙΣ_ΟΤΟΥ (με μετατροπή σε ΟΣΟ πρώτα)
ΜΤ <- ΑΤ
ΑΝ ΒΜ >= 0 ΤΟΤΕ
   ΑΝ ΜΤ <= ΤΤ ΤΟΤΕ
      ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
         ΕΝΤΟΛΕΣ
         ΜΤ <- ΜΤ + ΒΜ
      ΜΕΧΡΙΣ_ΟΤΟΥ ΜΤ > ΤΤ
   ΤΕΛΟΣ_ΑΝ
ΑΛΛΙΩΣ
   ΑΝ ΜΤ >= ΤΤ ΤΟΤΕ
      ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
         ΕΝΤΟΛΕΣ
         ΜΤ <- ΜΤ + ΒΜ
      ΜΕΧΡΙΣ_ΟΤΟΥ ΜΤ < ΤΤ
   ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΑΝ


ΔΙΟΝΥΣΗΣ

[hatzaras]

Καλησπέρα. Θα ήθελα τη βοήθεια σας στα παρακάτω θέματα:

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

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

Ή μήπως αυτοί οι έλεγχοι είναι περιττοί;

[P.Tsiotakis]

Γεια σου φίλε, ελπίζω να είσαι καλά,

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

Αν όμως δεν είναι προφανές αλλά υπάρχουν περιπτώσεις τότε πρέπει να ελέγξεις. Κι αυτό γιατί τα δυο τμήματα αλγορίθμων πρέπει να έχουν την ΙΔΙΑ ΕΞΟΔΟ για την ΙΔΙΑ ΕΙΣΟΔΟ (τιμές μεταβλητών). Κι αυτό θα γίνει σωστά, μόνο αν διερευνήσεις όλες τις περιπτώσεις

http://users.kor.sch.gr/ptsiotakis/aepp/aepp_ask23_3.htm

[ntzios kostas]

Από όσο --> μέχρις_ότου
αν εκτελέσουμε βήμα βήμα την όσο και πούμε ότι είναι μία επαναλαμβανόμενη αν έχουμε

όσο συνθήκη επανάλαβε
     ομάδα εντολών
τέλος_επανάληψης

αυτό είναι εισοδύναμο με

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

αν συνθήκη τότε (που τη βγάλαμε εκτός επανάληψης)
  αρχή_επανάληψης
    οε
  μέχρις_ότου όχι(συνθήκη)
τέλος_αν
   


από μέχρις_ότου σε για


Αν γίνεται η επανάληψη την μετατρέπουμε πρώτα σε όσο και στη συνέχεια σε για.

η γενική μετατροπή αφού πρώτα την έκανα σε όσο είναι:

μτ<-ατ
αρχή_επανάληψης
   οε
   μτ<-μτ+β
μέχρις_ότου μτ ΤΣ τιμή


και σε για γίνεται:

μτ<-ατ
οε
μτ<-μτ +β
για μτ από ατ+β μέχρι ττ με_βήμα β
    οε
τέλος_επανάληψης

όπου ττ πρέπει να αναζητηθεί με βάση την μτ ΤΣ τιμή (για παράδειγμα αν έλεγε μτ >=100) θα έπρεπε να ήταν μέχρι 99

[gpapargi]

Καλημέρα

Η μετατροπή από τη μια δομή επανάληψης στην άλλη είναι μεγάλο θέμα και έχει ενδιαφέρον μια που πέφτει και στις εξετάσεις. Φοβάμαι πως τα πράγματα έχουν πάρει λάθος τροπή γενικότερα.

Να θέσω ένα ερώτημα πάνω στο οποίο στηρίζονται όλα:
Τι εννοούμε όταν λέμε ότι θέλουμε "ισοδύναμο αλγόριθμο" ή "μετατροπή" από τη μια δομή στην άλλη; Ποιος είναι ο ορισμός του ισοδύναμου αλγόριθμου (ή της κωδικοποίησης) έτσι ώστε να ελέγξουμε αν μια μετατροπή είναι ισοδύναμη; Τι θέλουμε να ελέγξουμε σε αυτές τις ασκήσεις;

Ζητάμε απλώς να έχουν την ίδια έξοδο όταν υπάρχει η ίδια είσοδος ή εννοούμε ότι πρέπει οι 2 δομές να κάνουν ακριβώς τα ίδια πράγματα με ακριβώς την ίδια σειρά;

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

Αν ξεκαθαρίσουμε αυτό τότε όλα τα άλλα προκύπτουν εύκολα.

[ntzios kostas]

Καλημέρα και από εμένα. 

Ζητάμε απλώς να έχουν την ίδια έξοδο όταν υπάρχει η ίδια είσοδος ή εννοούμε ότι πρέπει οι 2 δομές να κάνουν ακριβώς τα ίδια πράγματα με ακριβώς την ίδια σειρά;

Νομίζω ότι ζητάμε το δεύτερο. Για παράδειγμα ας υποθέσουμε είχαμε την δομή:
χ<-1
όσο χ<=10 επανάλαβε
    γράψε χ
    χ<-χ+1
τέλος_επανάληψης

και κάποιος την μετέτρεπε σε για ως εξής

για χ από 5 μέχρι 10000
    αν χ<=104 τότε
       γράψε χ-4
    τέλος_αν
τέλος_επανάληψης

Ο μαθητής αυτός θα έπρεπε να πάρει άριστα; Δεν νομίζω.

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

[gpapargi]

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

Επίσης είναι λάθος να ζητάμε μετατροπή της Όσο και της Μέχρις_ότου με τελεστή < ή >  σε Για αφού τελικά στη συνθήκη της Για γίνεται έλεγχος με τελεστή <= ή >=.
Επίσης είναι λάθος να ζητάμε μετατροπή από Όσο ή μέχρις_ότου με αλλαγή μετρητή στη μέση σε Για, αφού αλλάζουμε τη σχετική σειρά των εντολών.

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

Πολλά πράγματα μπαίνουν στη θέση τους αν ξεκαθαρίσουμε τι ακριβώς ζητάμε.

[ntzios kostas]

Επίσης είναι λάθος να ζητάμε μετατροπή της Όσο και της Μέχρις_ότου με τελεστή < ή >  σε Για αφού τελικά στη συνθήκη της Για γίνεται έλεγχος με τελεστή <= ή >=.

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

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

έστω τα τμήματα:
όσο χ<=100 επανάλαβε
   γράψε χ
   χ<-χ+1
   κ<-κ+χ
τέλος_επανάληψης

και

όσο χ<=100 επανάλαβε
   γράψε χ
   κ<-κ+(χ+1)
   χ<-χ+1
τέλος_επανάληψης

Να χαρακτηρίσετε αν τα παραπάνω τμήματα είναι ισοδύναμα.
Τι θα απαντούσαμε; Αν λέγαμε ναι τότε έχει νόημα η μετατροπή του πρώτου τμήματος σε για.