Αποστολέας Θέμα: Τι θα εμφανιστεί??  (Αναγνώστηκε 6169 φορές)

solaris

  • Θαμώνας
  • ***
  • Μηνύματα: 28
Τι θα εμφανιστεί??
« στις: 16 Φεβ 2006, 09:26:33 πμ »
Καλημέρα σας,

Θα 'θελα να ρωτήσω τι θα εμφανίσει ο παρακάτω αλγόριθμος:

Για ι απο 1 μέχρι 100

   Εντολές

Τέλος_επανάληψης

Γράψε ι

Ευχαριστώ

Παναγιώτης Τσιωτάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 3176
  • I love you 3000
    • Panagiotis Tsiotakis
Απ: Τι θα εμφανιστεί??
« Απάντηση #1 στις: 16 Φεβ 2006, 09:35:59 πμ »
Η χρήση του μετρητή του Για, δεν έχει αξία μετά το βρόχο

Θα έχει τιμή 101

Το θέμα έχει συζητηθεί διεξοδικά (χωρίς να διαμορφωθεί κοινή άποψη) σε άλλα θέματα του forum

klitos

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 133
Απ: Τι θα εμφανιστεί??
« Απάντηση #2 στις: 16 Φεβ 2006, 01:24:15 μμ »
θα εμφανίσει 101

Τι θα εμφάνιζε αν μετατρέπαμε την ΓΙΑ σε ΟΣΟ ?
κλητος χατζηγεωργιου

andreas_p

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 1015
Απ: Τι θα εμφανιστεί??
« Απάντηση #3 στις: 16 Φεβ 2006, 01:42:34 μμ »
101

solaris

  • Θαμώνας
  • ***
  • Μηνύματα: 28
Απ: Τι θα εμφανιστεί??
« Απάντηση #4 στις: 16 Φεβ 2006, 01:45:31 μμ »
Ευχαριστώ

yiorgos_5

  • Οπαδός
  • **
  • Μηνύματα: 10
  • This thing is killing me....
Απ: Τι θα εμφανιστεί??
« Απάντηση #5 στις: 22 Φεβ 2006, 11:07:09 μμ »
Η περίπτωση να χρειαστεί ο μετρητής i μετά τον βρόγχο είναι από όσο μπορώ να σκεφτώ μόνο σε υπολογισμό μέσου όρου ν αριθμών...

Τώρα αν η επανάληψη είναι: Για i από λ μέχρι ν τότε στον Μέσο όρο μπορείς να γράψεις ΜΟ<--Σ(ν)/ν !όπου Σ(ν) το άθροισμα των αριθμών!

Αν όμως δεν ξέρουμε το πλήθος και χρησιμοποιήσουμε την όσο επανάλαβε τότε  ΜΟ<--Σ(ν)/(i-1)...
Θα πετάξω το o'clock και θα πάρω κομποlock!!!

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Τι θα εμφανιστεί??
« Απάντηση #6 στις: 23 Φεβ 2006, 10:10:37 πμ »
Η τιμή του μετρητή ι δε χρειάζεται ποτέ μετά την εκτέλεση του βρόχου. Δεν πρόκειται να πάρει καμία τιμή που δεν ήξερες από πριν ποια θα είναι.
Η αρχική τιμή του είναι γνωστή, το βήμα είναι γνωστό και το άνω όριο της εντολής «Για» είναι γνωστό. Άρα η μοίρα του ι είναι προδιαγεγραμμένη.

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


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

Μπορείτε να βρείτε ένα τύπο που να δίνει την τιμή του ι μετά την εκτέλεση του βρόχου, συναρτήσει των παραμέτρων τις εντολής «Για»;

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

Η απάντηση άυριο.

ʼντε μπας και ξεσκουριάσουμε λίγο :- )

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

solaris

  • Θαμώνας
  • ***
  • Μηνύματα: 28
Απ: Τι θα εμφανιστεί??
« Απάντηση #7 στις: 23 Φεβ 2006, 10:49:48 πμ »
Έθεσα την ερώτηση διότι πολλοί μαθητές κάνουν το εξής:
 
π.χ.
 μαξ <-- Π[1]
 Για ι από 2 μεχρι 100
        Αν Π[ι] > μαξ τότε
               μαξ <-- Π[ι]
       Τέλος_Αν
 Τέλος_Επανάληψης
 !και εδώ γράφουν
 Γράψε 'Το μεγιστο είναι το ', Π[ι]

Για να τους εξηγήσω το λάθος συνήθως τους λέω ότι τη στιγμή αυτή το Π[ι] είναι στην ουσία το Π[101]΄το οποίο ούτε καν υπάρχει...

kyramas

  • Νέος
  • *
  • Μηνύματα: 9
  • Γράψτε το προσωπικό σας σλόγκαν!
Απ: Τι θα εμφανιστεί??
« Απάντηση #8 στις: 23 Φεβ 2006, 01:12:50 μμ »
Έστω η εντολή ΓΙΑ με την παρακάτω σύνταξη:
ΓΙΑ μετρητής ΑΠΟ Τιμή1 ΜΕΧΡΙ Τιμή2 ΜΕ ΒΗΜΑ β
    εντολές
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Ο αριθμός επαναλήψεων δίνεται από τον παρακάτω τύπο:
Αρ_Επ = (Τιμή2 - Τιμή1) div β + 1
Συνεπώς η τιμή του μετρητή κατά την έξοδο από την εντολή ΓΙΑ είναι:

μετρητής = Τιμή1 + Αρ_Επ * β

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

Ο τύπος που δίνει την τιμή του μετρητή κατά τον τερματισμό της ΓΙΑ ισχύει επίσης σε κάθε περίπτωση.

Φιλικά
Κυραμάς Βαγγέλης



evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: Τι θα εμφανιστεί??
« Απάντηση #9 στις: 23 Φεβ 2006, 01:18:48 μμ »
Κατ'αρχήν το ερώτημα που θέτεις δεν είναι εκτός ΑΕΠΠ, θα μπορούσε να μπει σαν μια ερώτηση(τραβηγμένη), δεν είναι εύκολο φυσικά, αλλά είναι καλό θεματάκι.
Τώρα αυτή τη στιγμή μου έρχονται δυο απαντήσεις στο μυαλό, δες τες και τα λέμε:

Κώδικας: [Επιλογή]
1η    Άνω_Όριο - ((Ανω_Όριο - ʼρχική_Τιμη) mod β) + β

2η   Αρχική_Τιμή + ((Ανω_Όριο - ʼρχική_Τιμη) div β )*β + β



Μπορείτε να βρείτε ένα τύπο που να δίνει την τιμή του ι μετά την εκτέλεση του βρόχου, συναρτήσει των παραμέτρων τις εντολής «Για»;

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

Η απάντηση άυριο.

ʼντε μπας και ξεσκουριάσουμε λίγο :- )

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

What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

andreas_p

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 1015
Απ: Τι θα εμφανιστεί??
« Απάντηση #10 στις: 23 Φεβ 2006, 01:31:02 μμ »
Και για πραγματικούς ;

Συνεπώς

Αρ_Επ =Α_Μ( (Τιμή2 - Τιμή1) / β ) + 1

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4925
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Τι θα εμφανιστεί??
« Απάντηση #11 στις: 23 Φεβ 2006, 03:19:31 μμ »
Η λύση του Αντρέα καλύπτει και την περίπτωση β < 0. Μόνο που πρέπει να μπει μία
ΑΝ Αρ_Επ < 0 ΤΟΤΕ Αρ_Επ <- 0
για την περίπτωση που δε γίνεται καμία επανάληψη.

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2449
  • I 'm not young enough to know everything
Απ: Τι θα εμφανιστεί??
« Απάντηση #12 στις: 27 Φεβ 2006, 09:38:13 πμ »
Όταν έθεσα το ερώτημα δεν πίστευα ότι θα ασχοληθείτε τόσο με αυτό.
Έτσι έφτιαξα μια απόδειξη για τ2>τ1 και β>0 (για να ειμαι σίγουρος) και το έστειλα στο στέκι. Ο τύπος που κατέληξα ήταν αυτός του Αντρέα, αλλά επειδή δε θυμόμουν πως ορίζεται το ακέραιο μέρος για αρνητικούς αριθμούς απέφυγα να ασχοληθώ με τη γενική περίπτωση. Τώρα όμως νομίζω ότι αξίζει τον κόπο.

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

Παραθέτω παρακάτω μια απόδειξη του τύπου.

Ο μετρητής παίρνει τιμές
ι=τ1+ν*β     (σχέση 1)
όπου ν φυσικός αριθμός (0,1,2,3...)
Έστω ττ η τελική τιμή μετρητή. Άρα το ττ σίγουρα μπορεί να γραφτεί στη μορφή
Ττ=τ1+κ*β          (2)
για κάποιο κ.  Προσπαθούμε να εντοπίσουμε αυτό το κ.

Διακρίνουμε 3 περιπτώσεις

Περίπτωση 1
β=0. Σε αυτή την περίπτωση ο βρόχος είναι ατέρμων.

Περίπτωση 2
β>0
Εδώ η εντολή διακόπτεται για τη μικρότερη τιμή του κ που επαληθεύει την
ττ>τ2. Η σχέση αυτή λύνεται ως προς κ και προκύπτει κ>(τ2-τ1)/β

Επειδή θέλουμε το μικρότερο δυνατό κ έχουμε
Αν τ2<τ1, το κλάσμα βγαίνει αρνητικό και άρα κ=0
Αν τ2>τ1 ισχύει
κ=Α_Μ((τ2-τ1)/β)+1    (3)

Περίπτωση 3
β<0
Εδώ η εντολή διακόπτεται για τη μικρότερη τιμή του κ που επαληθεύει την
Ττ<τ2. Η σχέση αυτή λύνεται ως προς κ και προκύπτει πάλι κ>(τ2-τ1)/β. Το β είναι αρνητικό και με τη διαίρεση αλλάζει η φορά της ανισότητας.

Επειδή θέλουμε το μικρότερο δυνατό κ έχουμε
Αν τ2>τ1, το κλάσμα βγαίνει αρνητικό και άρα κ=0
Αν τ2<τ1 ισχύει
κ=Α_Μ((τ2-τ1)/β)+1

Βλέπουμε λοιπόν ότι αν τα τα τ2-τ1 και β είναι ομόσημα τότε ισχύει ο τύπος
κ=Α_Μ((τ2-τ1)/β)+1

Αν τα τ2-τ1 και β είναι ετερόσημα τότε κ=0.

Αν θέλουμε όλα να καλύπτονται από τον ίδιο τύπο (3) μπορούμε να γράψουμε το κ σαν
κ/2+Α_Τ(κ)/2
Έτσι αν τι κ είναι θετικό μένει αμετάβλητο. Αν είναι αρνητικό τότε μηδενίζεται.

Ο ν στη σχέση (1) παίρνει τιμές 0,1,2...κ. Για κάθε τιμή του ν (εκτός την κ που είναι η τελευταία) προκαλείται επανάληψη του βρόχου. ʼρα το πλήθος των επαναλήψεων είναι κατά 1 μικρότερο από το σύνολο των διαφορετικών τιμών που παίρνει ο ν (που είναι κ+1). Επειδή ο ν ξεκινάει από 0 καταλήγουμε στο ότι το πλήθος των επαναλήψεων είναι κ.

Αντικαθιστώντας  την (3) μέσα στη (2) βγαίνει η τελική τιμή του μετρητή

ττ=τ1+κ*β   (4)

Νομίζω κάλυψα τις περιπτώσεις αλλά μπορεί να μου ξέφυγε κάτι. Το κοιτάτε και μου λέτε.

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

Αρχικά πίστευα ότι μια τέτοια άσκηση ίσως δεν είναι για την ΑΕΠΠ γιατί η δυσκολία είναι κυρίως μαθηματική ενώ δεν παρουσιάζει κάποια δυσκολία σχετικά με το χειρισμό των δομών επιλογής, ακολουθίας. Τελικά όμως πρέπει να διακριθούν περιπτώσεις και η άσκηση είναι διδακτική.
Αν ξεχάσουμε τον έλεγχο για β=0 παραβιάζουμε την καθοριστικότητα.
Επίσης η άσκηση θα τιμωρήσει τον μαθητή που θα βάλει την εντολή «Για» να τρέξει και μετά θα τυπώσει το μετρητή, αφού μπορεί να πέσει σε ατέρμονα βρόχο και να παραβιάσει ο αλγόριθμος την περατότητα.

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

Τι λέτε;

nanosi

  • Επισκέπτης
Απ: Τι θα εμφανιστεί??
« Απάντηση #13 στις: 01 Μάρ 2006, 12:25:40 μμ »
typos epanalhpseon ep=ΑΤ((αρχ.τιμη-τελ.τιμη)mod βημα) + 1

το ι μετα το τελος του για ι=αρχ.τιμη +( βημα * ep)

andreas_p

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 1015
Απ: Τι θα εμφανιστεί??
« Απάντηση #14 στις: 01 Μάρ 2006, 12:55:26 μμ »
typos epanalhpseon ep=ΑΤ((αρχ.τιμη-τελ.τιμη)mod βημα) + 1

το ι μετα το τελος του για ι=αρχ.τιμη +( βημα * ep)

ΔΕΝ ΜΠΟΡΕΙΣ :  MOD  σε πραγματικούς !!!