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

Ξεκίνησε από gpapargi, 04 Δεκ 2007, 02:10:46 ΜΜ

« προηγούμενο - επόμενο »

gpapargi

Το παρακάτω θέμα έπεσε στις εξετάσεις του 2001

Δίνεται τ΅ή΅α αλγορίθ΅ου
   Χ ← Α
   Αρχή_επανάληψης
       Χ ← Χ + 2
       Εκτύπωσε το Χ
   Μέχρις_ότου Χ >= Μ
Να δώσετε τη δο΅ή επανάληψης "Για … από … ΅έχρι …βή΅α" η οποία τυπώνει ακριβώς τις ίδιες τι΅ές ΅ε το πιο πάνω τ΅ή΅α αλγορίθ΅ου.

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

alkisg

Δεν ξέρω για την απάντηση της επιτροπής, αλλά τι λες για το παρακάτω;
Κώδικας: Ψευδογλώσσα
  Χ ← Α
  Χ ← Χ + 2
  Εκτύπωσε το Χ
  Για Χ από Α+2 μέχρι Μ με_βήμα 2
    Εκτύπωσε το Χ
  τέλος_επανάληψης


Όσο για το (=) στη Μέχρις_ότου Χ >= Μ, πιστεύω ότι είναι λάθος, θα έπρεπε να έχει Μέχρις_ότου Χ > Μ.

Αν για κάποιον διεστραμμένο λόγο όντως εννοούσαν Χ >= Μ, τότε μπορεί να γραφεί έτσι:
Κώδικας: Ψευδογλώσσα
  Χ ← Α
  Χ ← Χ + 2
  Εκτύπωσε το Χ
  τελική_τιμή ← Α+2
  Για Χ από Α+2 μέχρι Μ-2 με_βήμα 2
    Εκτύπωσε το Χ
    τελική_τιμή ← Χ
  τέλος_επανάληψης
  Αν τελική_τιμή < Μ τότε
    Χ ← Χ + 2
    Εκτύπωσε το Χ
  τέλος_αν


Τα παραπάνω χωρίς έλεγχο λόγω βιασύνης...

Laertis

Δεν είμαι σίγουρος αλλά αν θυμάμαι καλά (πέρασαν 6 χρόνια) δόθηκε η προφανής λάθος απάντηση απο την επιτροπή

Για Χ απο Α+2 μέχρι Μ+2 με_βήμα 2
..........
το οποίο ισύχει μόνο όταν Α<=Μ.

Θα ψάξω τα χαρτιά μου για να το επιβεβαιώσω. Ελπίζω να το βρω στο αρχείο μου ...
Νικολακάκης Γιώργος
Μηχανικός Η/Υ Συστημάτων
Καθηγητής Πληροφορικής
http://users.sch.gr/gnikola

Αλεξόπουλος Ανδρέας

Παράθεση από: alkisg στις 04 Δεκ 2007, 03:27:13 ΜΜ
Όσο για το (=) στη Μέχρις_ότου Χ >= Μ, πιστεύω ότι είναι λάθος, θα έπρεπε να έχει Μέχρις_ότου Χ > Μ.

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


Δηλαδή
1)γράφω μια φορά τις εντολές του βρόχου πριν από το Για, για να εξασφαλίσω ότι θα εκτελεστούν τουλάχιστον μια φορά, ανεξάρτητα από τις αρχικές τιμές του Α και του Μ,
2)αρχική τιμή του μετρητή βάζω το Α+2 αφού το Χ έχει αυξηθεί κατά 2 όταν αρχίζει η επανάληψη του Για, και τελική τιμή το (Μ-1) αφού υπάρχει το (Χ>=Μ) στο Μέχρις_Ότου
3)τυπώνουμε το (Χ+2) και όχι το Χ μέσα στην επανάληψη αφού αν προσέξουμε το βήμα (δηλαδή το Χ<-Χ+2), αυξάνεται πριν από το εκτύπωσε και όχι στο τέλος της επανάληψης όπως γίνεται συνήθως


alkisg

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

Δεν ορίζεται τύπος δεδομένων, άρα οι αριθμοί μπορεί να περιέχουν δεκαδικά. Επομένως το να αφαιρέσουμε -1 από το Μ δεν λύνει το πρόβλημα.

Ακολουθεί παράδειγμα με τις 3 υλοποιήσεις, όπου φαίνεται ότι δεν είναι ισοδύναμες.

Κώδικας: ΓΛΩΣΣΑ
ΠΡΟΓΡΑΜΜΑ Δοκιμή
ΣΤΑΘΕΡΕΣ
  Α = 1
  Μ = 3.5
ΜΕΤΑΒΛΗΤΕΣ
  ΠΡΑΓΜΑΤΙΚΕΣ: Χ, τελική_τιμή
ΑΡΧΗ
  ΓΡΑΨΕ 'Αρχικό:'
  Χ <- Α
  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    Χ <- Χ + 2
    ΓΡΑΨΕ Χ
  ΜΕΧΡΙΣ_ΟΤΟΥ Χ >= Μ

  ΓΡΑΨΕ 'ʼλκης'
  Χ <- Α
  Χ <- Χ + 2
  ΓΡΑΨΕ Χ
  τελική_τιμή <- Α + 2
  ΓΙΑ Χ ΑΠΟ Α + 2 ΜΕΧΡΙ Μ - 2 ΜΕ_ΒΗΜΑ 2
    ΓΡΑΨΕ Χ
    τελική_τιμή <- Χ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΑΝ τελική_τιμή < Μ ΤΟΤΕ
    Χ <- Χ + 2
    ΓΡΑΨΕ Χ
  ΤΕΛΟΣ_ΑΝ

  ΓΡΑΨΕ 'Ανδρέας'
  Χ <- Α
  Χ <- Χ + 2
  ΓΡΑΨΕ Χ
  ΓΙΑ Χ ΑΠΟ Α + 2 ΜΕΧΡΙ Μ - 1 ΜΕ_ΒΗΜΑ 2
    ΓΡΑΨΕ Χ + 2
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ


Κώδικας: Αποτελέσματα
Αρχικό:
3.00
5.00
ʼλκης
3.00
5.00
Ανδρέας
3.00


Υ.Γ. για μένα το να χρειαστούμε καμία 10ριά υλοποιήσεις μέχρι να βρούμε κάποια ισοδύναμη είναι από μόνο του απόδειξη ότι το = ήταν λάθος...   ::)

Αλεξόπουλος Ανδρέας

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

alkisg

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

Αλεξόπουλος Ανδρέας

Παράθεση από: alkisg στις 04 Δεκ 2007, 10:02:12 ΜΜ
Στην ψευδογλώσσα επειδή δεν έχουν οριστεί οι τύποι δεδομένων συνήθως θεωρούμε τους αριθμούς πραγματικούς, εκτός αν ζητάει συγκεκριμένα ακεραίους το πρόβλημα...

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

alkisg

Αντρέα αναλυτική αιτιολόγηση αύριο γιατί τώρα τρέχω με τις διορθώσεις του βιβλίου. :-\

gpapargi

Άλκη για Α=0 και Μ=4 νομίζω πως στραβώνει και η δικιά σου λύση.
Εννοείται φυσικά ότι θέλουμε και το = αφού αυτό ζητάει η εκφώνηση και μιλάμε για πανελλήνιες.
Νομίζω πως δίκαια διαμαρτύρομαι.
Εμένα η άσκηση με παίδεψε. Έχω κάνει μια απόπειρα απόδειξης (με ένα σωρό ακροβασίες) και πάλι δεν είμαι σίγουρος ότι δε σκαλώνει κάπου το πράγμα...
Αλήθεια... αν μας δώσουν ένα υποψήφιο ισοδύναμο κώδικα πως καταλαβαίνουμε αν είναι σωστή λύση; Κάνοντας ένα σωρό δοκιμές (που τελικά δεν αποδεικνύουν τίποτα) ή θα πρέπει να ζητάμε και απόδειξη από τα παιδιά; 

alkisg

Όντως στραβώνει, θέλει κοίταγμα λίγο στα όρια και στα +-2 αλλά νομίζω ότι το σκεπτικό είναι σωστό. Διόρθωση αύριο...

evry


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

ΓΙΑ Χ ΑΠΟ Α+2 ΜΕΧΡΙ Μ + (Μ mod 2) ΜΕ ΒΗΜΑ 2
      Εκτύπωσε το Χ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

alkisg

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

Με την παρακάτω αλλαγή νομίζω ότι δουλεύει σωστά είτε για ακέραιους είτε για πραγματικούς. Δοκίμασα ΓΙΑ Α, Μ ΑΠΟ -10 ΜΕΧΡΙ 10 ΜΕ_ΒΗΜΑ 0.5 οπότε το λέω με σχετική ασφάλεια.

Κώδικας: ΓΛΩΣΣΑ
      Χ <- Α 
      Χ <- Χ + 2 
      ΓΡΑΨΕ Χ   
      τελική_τιμή <- Χ
      ΓΙΑ Χ ΑΠΟ Α + 4 ΜΕΧΡΙ Μ - 2 ΜΕ_ΒΗΜΑ 2 
        ΓΡΑΨΕ Χ   
        τελική_τιμή <- Χ 
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ 
      Χ <- τελική_τιμή 
      ΑΝ Χ < Μ ΤΟΤΕ 
        Χ <- Χ + 2 
        ΓΡΑΨΕ Χ   
        ΑΝ Χ < Μ ΤΟΤΕ 
          Χ <- Χ + 2 
          ΓΡΑΨΕ Χ   
        ΤΕΛΟΣ_ΑΝ 
      ΤΕΛΟΣ_ΑΝ


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

Το τελική_τιμή το έβαλα επειδή δεν είναι σωστό να χρησιμοποιούμε την τιμή του μετρητή Χ μετά από τη ΓΙΑ.

Αλεξόπουλος Ανδρέας

Παράθεση από: alkisg στις 05 Δεκ 2007, 09:23:42 ΠΜ
Το τελική_τιμή το έβαλα επειδή δεν είναι σωστό να χρησιμοποιούμε την τιμή του μετρητή Χ μετά από τη ΓΙΑ.

Κι αυτό το λέει κάπου; Με ένα γρήγορο ξεφύλλισμα που έκανα πάλι τώρα στο βιβλίο δεν το είδα να αναφέρεται κάπου. Δηλαδή το ακόλουθο είναι λάθος;
α<-0
Για ι Από 0 Μέχρι 5 Με_Βήμα 2
   α<- α + ι
Τέλος_Επανάληψης
Εμφάνισε α, ι

Φαντάζομαι όλοι έχουμε δει τέτοιες ασκήσεις που ζητάν να εμφανιστεί η τιμή ενός μετρητή αφού έχει τελειώσει η ΓΙΑ. Αν ισχύει ότι δεν μπορούμε να τον χρησιμοποιήσουμε μετά το Τέλος_Επανάληψης, τότε είναι λάθος.

Επίσης, δεν μου απάντησες γιατί όταν σε έναν αλγόριθμο έχουμε 'ΔΙΑΒΑΣΕ Χ', θεωρούμε το Χ σαν πραγματικό αν δεν αναφέρεται κάτι άλλο;


alkisg

Αντρέα, για την τιμή μετά το ΓΙΑ κάνε μια αναζήτηση στο φόρουμ, έχει αναφερθεί παλιότερα.

Για τους πραγματικούς:
Παράθεση από: Βιβλίο καθηγητή, σελίδα 72
Όπως θα παρατήρησε ήδη ο αναγνώστης, στο ρεπερτόριο των εντολών της ψευδογλώσσας δεν υπάρχουν δηλώσεις τύπων δεδομένων των χρησιμοποιούμενων μεταβλητών. Κάτι τέτοιο δεν είναι απαραίτητο στο επίπεδο της αλγοριθμικής ψευδογλώσσας. Για παράδειγμα ένας αλγόριθμος που βρίσκει τον ελάχιστο ν αριθμών, είναι ο ίδιος είτε οι αριθμοί είναι ακέραιοι, είτε πραγματικοί. Αν από τα δεδομένα του προβλήματος πρέπει να δηλωθεί ο τύπος των μεταβλητών, τότε αυτό γίνεται στην εκφώνηση. Ωστόσο δεν είναι λάθος στις περιπτώσεις αυτές να συμπληρώνεται ο τύπος των μεταβλητών στη γραμμή των δεδομένων.

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

Κι αφού οι πραγματικοί είναι υπερσύνολο των ακεραίων, αρκεί οι αλγόριθμοι που φτιάχνουμε να ισχύουν για πραγματικούς.