Μετατροπές αλγορίθμων-Ισοδύναμοι αλγόριθμοι

[dafnib3]

Α. Όταν λέμε ότι δύο αλγόριθμοι είναι ισοδύναμοι εννοούμε ότι εμφανίζουν τα ίδια δεδομένα στην οθόνη και ότι στο τέλος του αλγορίθμου οι τιμές των μεταβλητών είναι ίδιες;

Β. Έχω τον παρακάτω αλγόριθμο:


α <-- 5
γ <-- 1
Όσο α >=0 Επανάλαβε
  α <-- α - 3
  γ <-- γ * 3
Τέλος_επανάληψης
Εμφάνισε γ

Οι τιμές των μεταβλητών α και γ είναι

αρχ.                        5, 1
1η.  επαν.               2, 3
2η. επαν.                -1, 9

Άρα στην οθόνη θα εμφανιστεί το 9.

Ο παραπάνω αλγόριθμος ζητείται να μετατραπεί σε
ισοδύναμο με ΓΙΑ.

Προτείνω τον παρακάτω:

γ<-- 1
ΓΙΑ α από 2 Μέχρι -1 Με_βήμα -3
           γ <-- γ * 3
Τέλος_Επανάληψης
Εμφάνισε γ.

Οι τιμές των α, γ θα είναι οι παρακάτω:

αρχ.                    1
1η επ.             2, 3
2η επ.            -1, 9

Β. Μία άλλη ερώτηση.

ΓΙΑ Ι ΑΠΟ Τ1 ΜΕΧΡΙ Τ2 ΜΕ_ΒΗΜΑ Τ3
            .....
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗς
΄

Έστω ότι ο βρόχος εκτελείται 4 φορές .  Η τελική τιμή του μετρητή Ι θα είναι η τιμή της  Ι στην τέταρτη επανάληψη, ή η Ι + Τ3 (που μπορεί να έιναι μεγαλύτερη της Τ2 οότε και γίνεται έξοδος από την επανάληψη).

Ευχαριστώ            

[EleniK]

Σχετικά με την μετατροπή δε βλέπω κανένα πρόβλημα.

H τελική τιμή του Ι θα είναι Ι+Τ3. Αυτό μπορείς να το καταλάβεις καλύτερα και από το διάγραμμα ροής ή αν μετατρέψεις την Για σε Όσο.

[kinik]

Μια άλλη απάντηση είναι η εξής:
γ<--1
Για α από 5 μέχρι 0 με_βήμα -3
    γ<--γ*3
Τέλος_επανάληψης

[kinik]

Θέμα στις πανελλήνιες  εξετάσεις:
X<--A
Αρχή_επανάληψης
   Χ<--Χ+2
   Εκτύπωσε Χ
Μέχρις_ότου Χ>=Μ

Μετατροπή σε Για με βάση το σκεπτικό της dafnib3 :

Για Χ από Α +2 μέχρι Μ+1 με_βήμα 2
    Εκτύπωσε Χ
Τέλος_επανάληψης
Αν όμως πάρω ως παράδειγμα τιμές A=3, M=1 είναι ισοδύναμοι αλγόριθμοι? Όχι.
Στη ΜΕΧΡΙΣ_ΟΤΟΥ σίγουρα θα γίνει μία επανάληψης στη ΓΙΑ δεν είναι σίγουρο. Συνεπώς μία άλλη μετατροπή είναι πρώτα σε ΟΣΟ:
X<--A
Χ<--Χ+2
Εκτύπωσε Χ
ΟΣΟ Χ<Μ ΕΠΑΝΑΛΑΒΕ
   Χ<--Χ+2
   Εκτύπωσε Χ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
και μετά σε ΓΙΑ

Χ<--Α
Χ<--Χ+2
Εκτύπωσε Χ
ΓΙΑ Χ ΑΠΟ Α+2 ΜΕΧΡΙ Μ-1 ΜΕ_ΒΗΜΑ 2
     Εκτύπωσε Χ+2
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Ποια η γνώμη των μελών του forum πάνω σε αυτή τη μετατροπή?

[evry]

Πιστεύω πως μια λύση η οποία έχει κάποιο σκεπτικό αλλά και ενδιαφέρον είναι η παρακάτω

ΓΡΑΨΕ Α+2
ΓΙΑ Χ ΑΠΟ Α+4 ΜΕΧΡΙ Μ + (Μ-Α) mod 2 ME BHMA 2
   ΓΡΑΨΕ Χ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΕΙΝΑΙ ΛΟΓΙΚΟ ΝΑ ΣΚΕΦΤΕΙ ΚΑΠΟΙΟΣ ΟΤΙ Ο ΑΛΓΟΡΙΘΜΟΣ ΤΕΡΜΑΤΙΖΕΙ ΣΤΟ Μ ΟΤΑΝ ΕΧΩ ΔΥΟ ΑΡΙΘΜΟΥΣ ΠΟΥ ΕΙΝΑΙ ΚΑΙ ΟΙ ΔΥΟ η ΠΕΡΙΤΤΟΙ η ΑΡΤΙΟΙ ΑΛΛΙΩΣ ΠΑΕΙ ΣΤΟ Μ+1

Πάντως όσον αφορά την ισοδυναμία τον αλγορίθμων πιστεύω ότι όλη αυτή η υπόθεση είναι στον αέρα. Η ισοδυναμία δυο αλγορίθμων κατ'αρχήν είναι μη υπολογίσιμο πρόβλημα (από τα λίγα που θυμάμαι από την θεωρία υπολογισμού). Από την άλλη δεν μπορούμε να λέμε ότι δυο αλγόριθμοι είναι ισοδύναμοι επειδή βγάζουν ακριβώς τα ίδια αποτελέσματα. Δεν είναι μόνο η απόδοση αλλά και πολλά άλλα πράγματα. Ακόμα και στην ισοδυναμία δομών επανάληψης που τα πράγματα είναι ελεγχόμενα, κάποια στιγμή μπορεί να βρεθεί ένα διφορούμενο θέμα με περισσότερες από μια λύσεις όχι ισάξιες μεταξύ τους. (Βλέπε gauss και άθροισμα από 1-->Ν)

[EleniK]

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

[dafnib]

Στους πίνακες τιμών της ΓΙΑ σε κάθε επανάληψη βάζουμε την τελική τιμή του μετρητή; Δηλ.

ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ 10 ΜΕ_ΒΗΜΑ 2
  Α <-- Ι * 2
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

ΠΙΝΑΚΑΣ ΤΙΜΩΝ:

1. Ι = 1, Α = 2 (Μετά όμως από την εντολή εκχώρησης τιμής στο Α, ο μετρητής αυξάνεται κατά 2 και συγκρίνεται η τιμή του με την τελική τιμή του Ι, σωστά; Σύμφωνα πάντα με το διάγραμμα ροής της ΓΙΑ. άρα στον
πίνακα τιμών, στην πρώτη επανάληψη το Ι τί τιμή πρέπει να γράψουμε ότι έχεί;
2. Ι = 3, Α = 6 κ.λπ.


Ευχαριστώ

[Φίλιππος]

Η τιμή της μεταβλητής ελέγχου του ΓΙΑ αλλάζει "με το τέλος_επανάληψης".

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

Στο παράδειγμα που αναφέρεις, οι τιμές του i σε όλες τις επαναλήψεις είναι:
1) 1
2) 3
3) 5
4) 7
5) 9

ενώ τελειώνοντας και η πέμπτη επανάληψη, το i παίρνει την τιμή 11 οπότε και τελειώνει η επανάληψη