Θέμα Β

Ξεκίνησε από gpapargi, 29 Μαΐου 2013, 10:19:38 ΠΜ

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

Dinos

Θέμα Β2

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

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

alkisg

Παράθεση από: aperdos στις 29 Μαΐου 2013, 04:47:49 ΜΜ
Δοθέντων των στοιχείων α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

Παράθεση από: summer στις 29 Μαΐου 2013, 04:34:17 ΜΜ
Για δείτε αυτό
πλ<-0
Για ι από 1 μέχρι 100
  Αν Π[ι]=ΑΛΗΘΗΣ τότε πλ<--πλ+1
Τέλος Επανάληψης

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

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

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

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

petrosp13

Σωστό είναι
Ουσιαστικά μετράει πόσα "ΑΛΗΘΗΣ" πρέπει να υπάρχουν, έτσι χωρίζει τον πίνακα στα 2 και αντικαθιστά όλα τα "ΨΕΥΔΗΣ" στο πρώτο κομμάτι με "ΑΛΗΘΗΣ" και το ανάποδο στο δεύτερο
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

michaeljohn

Δείτε λίγο και αυτό :

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

freedomst

Παράθεση από: michaeljohn στις 29 Μαΐου 2013, 05:51:30 ΜΜ
Δείτε λίγο και αυτό :

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



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

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

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

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

grdereken

#22
Παράθεση από: freedomst στις 29 Μαΐου 2013, 03:27:15 ΜΜ
Β2. Προσπαθώντας να λύσω την ταξινόμηση χωρίς 2ο πίνακα και χωρίς μετρητή count  σκέφτηκα το παρακάτω:

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

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

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

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

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

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


  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

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

Παράθεση από: alkisg στις 29 Μαΐου 2013, 05:20:21 ΜΜ
Ορίζω 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

Παράθεση από: grdereken στις 29 Μαΐου 2013, 06:13:47 ΜΜ


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


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

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

grdereken

Παράθεση από: freedomst στις 29 Μαΐου 2013, 06:43:40 ΜΜ
Το δοκίμασα στο χαρτί σε πίνακα 6 θέσεων τυχαίων περιεχομένων και δούλεψε κανονικά.
Έπειτα το έτρεξα και στη Γλωσσομάθεια 3 φόρες με διαφορετικές παραλλαγές περιεχομένων (συνδυασμούς Α - Ψ) πίνακα 10 θέσεων και δούλεψε επίσης κανονικά.
ποια συνθήκη δε σου βγήκε όταν το έτρεξες?
Στο δείγμα που χρησιμοποίησα δεν έβαζε σωστά τα τελευταία στοιχειά, πρέπει να έκανε μία περιττή αντιμετάθεση στο τέλος, που διορθώνεται με τον επιπλέον έλεγχο κ<λ στην τρίτη ΑΝ.

alkisg

Παράθεση από: aperdos στις 29 Μαΐου 2013, 06:24:29 ΜΜ
Έτσι όμως και ο πίνακας με τιμές -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

Παράθεση από: grdereken στις 29 Μαΐου 2013, 06:59:30 ΜΜ
Στο δείγμα που χρησιμοποίησα δεν έβαζε σωστά τα τελευταία στοιχειά, πρέπει να έκανε μία περιττή αντιμετάθεση στο τέλος, που διορθώνεται με τον επιπλέον έλεγχο κ<λ στην τρίτη ΑΝ.


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

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

freedomst

@grdereken

/quote

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

...

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

quote/

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

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

gthal

Παράθεση από: michaeljohn στις 29 Μαΐου 2013, 05:51:30 ΜΜ
Δείτε λίγο και αυτό :

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