Αποστολέας Θέμα: Θέμα Β  (Αναγνώστηκε 27112 φορές)

Dinos

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 86
  • Γράψτε το προσωπικό σας σλόγκαν!
Απ: Θέμα Β
« Απάντηση #15 στις: 29 Μάι 2013, 05:12:40 μμ »
Θέμα Β2

Κώδικας: [Επιλογή]
κ <-- 0
λ <-- 101
Για ι από 1 μέχρι 100
   Αν Π[ι] = αληθής τότε
        κ <-- κ + 1
        Β[κ] <-- αληθής
   Αλλιώς
        λ <-- λ - 1
        Β[λ] <-- ψευδής
   Τέλος_αν
Τέλος_επανάληψης

Για ι από 1 μέχρι 100
  Π[ι] <-- Β[ι]
Τέλος_επανάληψης

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Θέμα Β
« Απάντηση #16 στις: 29 Μάι 2013, 05:20:21 μμ »
Δοθέντων των στοιχείων α1, α2,...αn η ταξινόμηση συνίσταται στη μετάθεση της θέσης των στοιχείων, ώστε να τοποθετηθούν σε μία σειρά ακ1, ακ2,..., ακν έτσι ώστε, δοθείσης μιας συνάρτησης διάταξης f να ισχύει:
f(ak1) <= f(ak2) <= ...<=f(akn)
σχολικό βιβλίο σελ 66

Που ακριβώς υπάρχει η ταξινόμηση στον παραπάνω κώδικα;

Ορίζω f(Ψευδής)=0 και f(Αληθής)=1, και έτσι ο ζητούμενος πίνακας τελικά θα είναι ταξινομημένος ως προς αυτήν την f().
Το θέμα δηλαδή ουσιαστικά ζητάει να ταξινομηθεί ένας πίνακας λογικών μεταβλητών. Δεν έχει καμία σημασία που δεν ορίζονται οι σχέσεις > και < μεταξύ λογικών μεταβλητών, στον ορισμό της ταξινόμησης δεν συγκρίνουμε τα a1 ... an αλλά τα f(a1)...f(an).

Η διαφορά είναι ότι ήθελε να τους υποχρεώσει να το κάνουν με πολυπλοκότητα O(n) και όχι (n^2), χωρίς να αναφέρει τη λέξη πολυπλοκότητα. Ίσως είναι αμφιλεγόμενο το κατά πόσο η εκφώνηση καταφέρνει καλά αυτόν το στόχο.

Μια παρόμοια άσκηση θα ήταν "σε έναν πίνακα ακεραίων, βάλτε τους αρνητικούς στις πρώτες θέσεις ώστε να είναι πριν από τους θετικούς, αλλά χωρίς να «ταξινομήσετε» εντελώς τον πίνακα, δηλαδή να υπάρχουν και περιπτώσεις εισόδου κατά τις οποίες στην έξοδο να ΜΗΝ ισχύει an <= an+1 για κάθε n".

itt

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 428
  • Real stupidity beats ΑΙ any time
Απ: Θέμα Β
« Απάντηση #17 στις: 29 Μάι 2013, 05:31:45 μμ »
Για δείτε αυτό
πλ<-0
Για ι από 1 μέχρι 100
  Αν Π[ι]=ΑΛΗΘΗΣ τότε πλ<--πλ+1
Τέλος Επανάληψης

Για ι από 1 μέχρι πλ
Αν Π[ι]=ΨΕΥΔΗΣ τότε Π[ι]<--ΑΛΗΘΗΣ
Τέλος Επανάληψης

Για ι από πλ+1 μέχρι 100
Αν Π[ι]=ΑΛΗΘΗΣ τότε  Π[ι]<--ΨΕΥΔΗΣ
Τέλος Επανάληψης

ωραίο δεν είναι?

Υποθέτω πώς αυτό θα θεωρείται απολύτως σωστό σαν λύση;

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2212
Απ: Θέμα Β
« Απάντηση #18 στις: 29 Μάι 2013, 05:39:11 μμ »
Σωστό είναι
Ουσιαστικά μετράει πόσα "ΑΛΗΘΗΣ" πρέπει να υπάρχουν, έτσι χωρίζει τον πίνακα στα 2 και αντικαθιστά όλα τα "ΨΕΥΔΗΣ" στο πρώτο κομμάτι με "ΑΛΗΘΗΣ" και το ανάποδο στο δεύτερο
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

michaeljohn

  • Ομάδα διαγωνισμάτων 2010
  • *
  • Μηνύματα: 129
  • "Είναι παιδιά πολλών ανθρώπων τα λόγια μας"
Απ: Θέμα Β
« Απάντηση #19 στις: 29 Μάι 2013, 05:51:30 μμ »
Δείτε λίγο και αυτό :

μ<-- 0
Για κ από 1 μέχρι 100
      Αν Π[κ] = Αληθής τότε
           μ <-- μ + 1
           Αντιμετάθεσε Π[κ], Π[μ]
      τέλος_αν
τελος_επανάληψης

freedomst

  • Βετεράνος
  • ****
  • Μηνύματα: 82
Απ: Θέμα Β
« Απάντηση #20 στις: 29 Μάι 2013, 06:00:38 μμ »
Δείτε λίγο και αυτό :

μ<-- 0
Για κ από 1 μέχρι 100
      Αν Π[κ] = Αληθής τότε
           μ <-- μ + 1
           Αντιμετάθεσε Π[κ], Π[μ]
      τέλος_αν
τελος_επανάληψης



Πολύ ωραία λύση!
Σταματοπούλου Ελευθερία
ΠΕ19 - ΓΕΛ Κρύας Βρύσης

"Ουδέν κακόν αμιγές καλού"

Γιάννης Αναγνωστάκης

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 815
Απ: Θέμα Β
« Απάντηση #21 στις: 29 Μάι 2013, 06:08:37 μμ »
Δεδομένα //Π//
Κ<-0
Για ι από 1 μέχρι 100
Αν Π[ι]= ΑΛΗΘΗΣ τότε
      Κ<- Κ +1
Τέλος_αν
Τέλος_επανάληψης
Για ι από 1 μέχρι 100
Αν ι <=  Κ τότε
      Π[ι]<- ΑΛΗΘΗΣ
Αλλιώς
      Π[ι]<- ΨΕΥΔΗΣ
Τέλος_αν
Τέλος_επανάληψης
Αποτελέσματα //Π//

grdereken

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 30
Απ: Θέμα Β
« Απάντηση #22 στις: 29 Μάι 2013, 06:13:47 μμ »
Β2. Προσπαθώντας να λύσω την ταξινόμηση χωρίς 2ο πίνακα και χωρίς μετρητή count  σκέφτηκα το παρακάτω:

κ <-- 1
λ <-- 100
Οσο κ < λ επανάλαβε
    Αν Π[κ] = Αληθης τότε
            κ <-- κ + 1
   τελος_αν

   Αν Π[λ] = Ψευδης τότε
            λ <-- λ - 1
   τελος_αν

   Αν Π[κ] <> Π[λ] και Π[κ] = Ψευδης τότε
           Αντιμετάθεσε Π[κ], Π[λ]
           κ <-- κ + 1
           λ <-- λ - 1
   Τέλος_αν
Τέλος_επανάληψης

Βλέπει κανείς κανένα λογικό λάθος;


Δες λίγο τα τελευταία στοιχεία, δεν τα βάζει στη σωστή σειρά, λίγο που το έτρεξα. Τρέχει σωστά με τον επιπλέον έλεγχο κ < λ στην τρίτη ΑΝ. Παραμφερής λύση που μοιάζει όμως με τους αλγορίθμους ταξινόμησης  είναι η
 ΑΛ <-- 1
  Ψ <-- 100
  ΟΣΟ ΑΛ < Ψ  ΕΠΑΝΑΛΑΒΕ
   
    ΟΣΟ Π[ΑΛ] = "ΑΛΗΘΗΣ" ΕΠΑΝΑΛΑΒΕ
      ΑΛ <-- ΑΛ + 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
   
   ΟΣΟ Π[Ψ] = "ΨΕΥΔΗΣ" ΚΑΙ Ψ > ΑΛ ΕΠΑΝΑΛΑΒΕ
      Ψ <-- Ψ - 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

    ΤΕΜΠ <-- Π[ΑΛ] !Αντιμετάθεση
    Π[ΑΛ] <-- Π[Ψ]
    Π[Ψ] <-- ΤΕΜΠ


  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
« Τελευταία τροποποίηση: 29 Μάι 2013, 06:51:28 μμ από grdereken »

Αθανάσιος Πέρδος

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 288
Απ: Θέμα Β
« Απάντηση #23 στις: 29 Μάι 2013, 06:24:29 μμ »
Ορίζω f(Ψευδής)=0 και f(Αληθής)=1, και έτσι ο ζητούμενος πίνακας τελικά θα είναι ταξινομημένος ως προς αυτήν την f().
Το θέμα δηλαδή ουσιαστικά ζητάει να ταξινομηθεί ένας πίνακας λογικών μεταβλητών. Δεν έχει καμία σημασία που δεν ορίζονται οι σχέσεις > και < μεταξύ λογικών μεταβλητών, στον ορισμό της ταξινόμησης δεν συγκρίνουμε τα a1 ... an αλλά τα f(a1)...f(an).

Η διαφορά είναι ότι ήθελε να τους υποχρεώσει να το κάνουν με πολυπλοκότητα O(n) και όχι (n^2), χωρίς να αναφέρει τη λέξη πολυπλοκότητα. Ίσως είναι αμφιλεγόμενο το κατά πόσο η εκφώνηση καταφέρνει καλά αυτόν το στόχο.

Μια παρόμοια άσκηση θα ήταν "σε έναν πίνακα ακεραίων, βάλτε τους αρνητικούς στις πρώτες θέσεις ώστε να είναι πριν από τους θετικούς, αλλά χωρίς να «ταξινομήσετε» εντελώς τον πίνακα, δηλαδή να υπάρχουν και περιπτώσεις εισόδου κατά τις οποίες στην έξοδο να ΜΗΝ ισχύει an <= an+1 για κάθε n".

Είσαι πολύ σωστός. Ομολογώ ότι δεν το είχα σκεφτεί έτσι.
Έτσι όμως και ο πίνακας με τιμές -3, -5, -1, 2, 0, 4 είναι "εντελώς" ταξινομημένος αφού f(α) = 0 αν α <0 και και f(α) = 1 αν α >= 0. (Θεωρώ το 0 θετικό)
Πάντως με βάση την περιγραφή που υπάρχει στην παράγραφο 3.7 δεν νομίζω ότι οι μαθητές έχουν αυτή τη θεώρηση για την ταξινόμηση. Βέβαια για να λέμε την αλήθεια δεν φταίνε αυτοί αλλά ο καθηγητής τους που μάλλον βιάστηκα να μιλήσω. Σίγουρα πρέπει να αναθεωρήσω. Αφού λοιπόν υπάρχουν προσπελάσεις και συγκρίσεις ανά δύο γειτονικά, είναι ο αλγόριθμος της φυσαλίδας.

freedomst

  • Βετεράνος
  • ****
  • Μηνύματα: 82
Απ: Θέμα Β
« Απάντηση #24 στις: 29 Μάι 2013, 06:43:40 μμ »


Δες λίγο τα τελευταία στοιχεία, δεν τα βάζει στη σωστή σειρά, λίγο που το έτρεξα.


Το δοκίμασα στο χαρτί σε πίνακα 6 θέσεων τυχαίων περιεχομένων και δούλεψε κανονικά.
Έπειτα το έτρεξα και στη Γλωσσομάθεια 3 φόρες με διαφορετικές παραλλαγές περιεχομένων (συνδυασμούς Α - Ψ) πίνακα 10 θέσεων και δούλεψε επίσης κανονικά.
ποια συνθήκη δε σου βγήκε όταν το έτρεξες?
Σταματοπούλου Ελευθερία
ΠΕ19 - ΓΕΛ Κρύας Βρύσης

"Ουδέν κακόν αμιγές καλού"

grdereken

  • Ομάδα διαγωνισμάτων 2016
  • *
  • Μηνύματα: 30
Απ: Θέμα Β
« Απάντηση #25 στις: 29 Μάι 2013, 06:59:30 μμ »
Το δοκίμασα στο χαρτί σε πίνακα 6 θέσεων τυχαίων περιεχομένων και δούλεψε κανονικά.
Έπειτα το έτρεξα και στη Γλωσσομάθεια 3 φόρες με διαφορετικές παραλλαγές περιεχομένων (συνδυασμούς Α - Ψ) πίνακα 10 θέσεων και δούλεψε επίσης κανονικά.
ποια συνθήκη δε σου βγήκε όταν το έτρεξες?
Στο δείγμα που χρησιμοποίησα δεν έβαζε σωστά τα τελευταία στοιχειά, πρέπει να έκανε μία περιττή αντιμετάθεση στο τέλος, που διορθώνεται με τον επιπλέον έλεγχο κ<λ στην τρίτη ΑΝ.

alkisg

  • Τεχνικός / καθαρίστρια
  • *****
  • Μηνύματα: 4879
    • alkisg@im.sch.gr
    • Ο Διερμηνευτής της ΓΛΩΣΣΑΣ
Απ: Θέμα Β
« Απάντηση #26 στις: 29 Μάι 2013, 07:08:16 μμ »
Έτσι όμως και ο πίνακας με τιμές -3, -5, -1, 2, 0, 4 είναι "εντελώς" ταξινομημένος αφού f(α) = 0 αν α <0 και και f(α) = 1 αν α >= 0. (Θεωρώ το 0 θετικό)

Γι' αυτό έβαλα σε εισαγωγικά το «ταξινομημένος», γιατί παρακάτω ζητάω «an <= an+1» και δεν ζητάω να οριστεί κάποια f(), δηλαδή δεν θέλουμε "τυπική" ταξινόμηση.

Δηλαδή αν ήταν να το πούμε με πιο επίσημους όρους, ο πίνακας που έδωσες ως παράδειγμα, είναι όντως ταξινομημένος με βάση την
f(x) = sign(x),
...που είναι και το ζητούμενο,
αλλά δεν είναι ταξινομημένος με βάση την ταυτοτική συνάρτηση,
f(x) = x,
και αυτό μπαίνει σαν προϋπόθεση στην εκφώνηση ότι δεν θέλουμε να ισχύει, για να αποφευχθούν γενικές λύσεις full sorting.

...αν και μάλλον βγήκαμε λίγο εκτός θέματος πια, ας το αφήσουμε να μην μπλέκουμε τον κόσμο! :)

freedomst

  • Βετεράνος
  • ****
  • Μηνύματα: 82
Απ: Θέμα Β
« Απάντηση #27 στις: 29 Μάι 2013, 07:20:21 μμ »
Στο δείγμα που χρησιμοποίησα δεν έβαζε σωστά τα τελευταία στοιχειά, πρέπει να έκανε μία περιττή αντιμετάθεση στο τέλος, που διορθώνεται με τον επιπλέον έλεγχο κ<λ στην τρίτη ΑΝ.


Αντιμετάθεση γίνεται μόνο όταν:
οι δύο τρέχουσες εξεταζόμενες τιμές του πίνακα είναι διαφορετικές μεταξύ τους  και η πρώτη από αυτές (που είναι και πρώτη στη σειρά θέσεων του πίνακα) είναι Ψευδής οπότε η θέση της στον πίνακα δεν είναι σωστή,  άρα είναι αδύνατο να γίνει περιττή αντιμετάθεση και δε χρειάζεται ο έλεγχος κ <λ
Σταματοπούλου Ελευθερία
ΠΕ19 - ΓΕΛ Κρύας Βρύσης

"Ουδέν κακόν αμιγές καλού"

freedomst

  • Βετεράνος
  • ****
  • Μηνύματα: 82
Απ: Θέμα Β
« Απάντηση #28 στις: 29 Μάι 2013, 07:28:02 μμ »
@grdereken
 
 /quote

Αλ <-- 1
Ψ <-- 100
ΟΣΟ Αλ < Ψ επανάλαβε
    ΟΣΟ Π[ΑΛ] = "ΑΛΗΘΗΣ" ΕΠΑΝΑΛΑΒΕ
      ΑΛ <-- ΑΛ + 1
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

...

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

quote/

Για τον αλγόριθμο που προτείνεις:
Στην περίπτωση που όλες οι τιμές του πίνακα Π είναι "ΑΛΗΘΗΣ" μενεις στην εσωτερική επανάληψη μέχρι να βρεθείς εκτός πίνακα στη θέση 101 με τη συνθήκη Π[101] = 'ΑΛΗΘΗΣ':
   
 
Σταματοπούλου Ελευθερία
ΠΕ19 - ΓΕΛ Κρύας Βρύσης

"Ουδέν κακόν αμιγές καλού"

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 887
Απ: Θέμα Β
« Απάντηση #29 στις: 29 Μάι 2013, 07:59:26 μμ »
Δείτε λίγο και αυτό :

μ<-- 0
Για κ από 1 μέχρι 100
      Αν Π[κ] = Αληθής τότε
           μ <-- μ + 1
           Αντιμετάθεσε Π[κ], Π[μ]
      τέλος_αν
τελος_επανάληψης
Απίστευτο!
Αυτή είναι θαυμάσια λύση !!!
Φιλικά,
Γιώργος Θαλασσινός