Μπορεί να δημιουργηθεί τμήμα κώδικα που να δέχεται έναν πίνακα Ν θέσεων, με εισαγόμενες τιμές 0 και 1 σε ανακατωμένες θέσεις και με ένα πέρασμα των στοιχείων του πίνακα να τοποθετούνται τα 0 στις περιττές θέσεις και οι άσσοι στις άρτιες θέσεις του πίνακα;
Αν τελειώσουν οι άσσοι ή τα μηδενικά, από εκεί και έπειτα να εισάγονται μόνο οι τιμές που περισσεύουν;
Υπάρχει αυτή η δυνατότητα;
Για παράδειγμα έστω τα στοιχεία
01100001000100101010
σε πίνακα 15 θέσεων.
Με μια προσπέλαση η τελική κατάσταση των στοιχείων να είναι
01010101010101000000
Με μια πρόχειρη ματιά
Για i από 1 μέχρι Ν-1
Αν (Α[ι]=imod2) τότε
βρέθηκε <-- ψευδής
κ <-- i + 1
Όσο (κ <= Ν) και (βρέθηκε=ψευδής) επανάλαβε
Αν (Α[k] <> A(i)) και (Α[k] = kmod2) τότε
temp <-- A[k]
A[k] <-- A(i)
A(i) <-- temp
βρέθηκε <-- αληθής
Αλλιώς
κ <-- κ+1
Τέλος_Αν
Τέλος_Επανάληψης
Τέλος_Επανάληψης
Δεν το έλεγξα, στα γρήγορα γιατί είμαι από κινητό
1) Μετράς πόσα είναι τα 0 (έστω κ) και πόσα τα 1 (έστω λ)
2) Αν κ<λ τότε γεμίζεις τις πρώτες κ περιττές θέσεις με 0, αλλιώς τις πρώτες λ άρτιες θέσεις με 1 (εδώ πιθανόν να μπορεί να γραφεί ένας όμορφος κώδικας που να μην επαναλαμβάνει τα ίδια πράγματα για 0 και 1, ίσως με χρήση διαδικασίας)
3) Ότι απέμεινε το γεμίζεις με το άλλο ψηφίο που δεν χρησιμοποιήθηκε στο προηγούμενο βήμα.
Γενικά, κάπως δύσκολο το βρίσκω για θέμα.
Προφανώς όταν λέει με ένα πέρασμα εννοεί αλγόριθμο να έχει τουλάχιστον πολυπλοκότητα Ο(Ν), άρα αλγόριθμοι με Ο(Ν^2) δεν μπορούν να γίνουν αποδεκτοί.
Το θέμα είναι αν εννοεί και μόνο ένα πέρασμα από κάθε στοιχείο, δηλαδή δεν του αρκεί το Ο(Ν) αλλά θέλει και ένα μόνο πέρασμα από κάθε στοιχείο.
(Προσοχή!!! Μπορεί να γίνει με μια επανάληψη αλλά να μην είναι ουσιαστικά ένα πέρασμα)
Παρακάτω δίνω έναν αλγόριθμο ο οποίος είναι ότι πιο γρήγορο έχω σκεφτεί μέχρι στιγμής, μετράει πόσα είναι τα 0,1 και τα βάζει στον πίνακα,
αλλά δεν χρησιμοποιώ καμία σύγκριση εντός επανάληψης και από εκεί και πέρα έχει μόνο προσθέσεις.
Το μόνο πρόβλημα είναι ότι δεν τα κάνω όλα σε ένα πέρασμα αλλά σε 2 (δεν λέω σε τρία γιατί τα 2 παρακάτω περάσματα γίνονται σε ξεχωριστά στοιχεία του πίνακα άρα δεν μπορούν να θεωρούν ως 2 περάσματα)
μ[0] <-- μ[1] <-- 0
Για ι από 1 μέχρι Ν
μ[Α[ι]] <-- μ[Α[ι]] + 1
Τέλος_Επανάληψης
Αν μ[0]<μ[1] Τότε
τιμή <-- 0
αλλιώς
τιμή <-- 1
κ <-- 1 + τιμή
Για ι από 1 μέχρι μ[τιμή]
Α[κ] <-- τιμή
κ <-- κ + 2
Τέλος_Επανάληψης
θέση <-- κ
τιμή <-- 1 - τιμή
Για κ από θέση μέχρι Ν με βήμα 2
Α[κ] <-- τιμή
Τέλος_Επανάληψης
κ <-- 1+τιμή
Για ι από 1 μέχρι Ν με βήμα 2
Α[κ] <-- τιμή
κ <-- κ + 2
Τέλος_Επανάληψης
Δίνω επίσης έναν αλγόριθμο που ναι μεν κάνει ένα πέρασμα αλλά δεν γεμίζει τον πίνακα από την αρχή. Αυτό που κάνει είναι να βάζει τα 0 και 1 στις σωστές θέσεις, αλλά αυτό δεν σημαίνει ότι θα είναι όλα στην αρχή του πίνακα. Και αυτό όμως είναι πολύ καλή άσκηση.
Εξασφαλίζει όμως ότι στο τέλος δεν θα υπάρχει κανένα 0 σε ζυγή θέση και κανένα 1 σε μονή.
odd <-- 1
even <-- 2
Οσο odd<N και even<N Επανάλαβε
Αν ( Α[odd]==1 και Α[even]==0 ) Τότε
A[odd] <-- 0
A[even] <-- 1
odd <-- odd + 2
even <-- even + 2
Αλλιώς
Αν A[odd]==0 Τότε odd <-- odd + 2
Αν A[even]==1 Τότε even <-- even + 2
Τέλος_αν
Τέλος_Επανάληψης
Το θέμα τώρα είναι πως θα μαζέψεις τα σωστά 0,1 στην αρχή του πίνακα.
Αυτό είναι πολύ καλή άσκηση που αξίζει να ασχοληθεί κανείς. Η ιδέα εδώ είναι η ίδια που ισχύει και για την παρακάτω άσκηση:
Δεδομένου ενός πίνακα Α[Ν] που περιέχει μόνο 0 και 1 να διαχωρίσετε τα 0 από τα 1 έτσι ώστε όλα τα 0 να είναι πριν από όλα τα 1, με ένα μόνο πέρασμα
Την άσκηση αυτή μπορεί να την δείτε και με θετικούς και αρνητικούς αριθμούς. Το σκεπτικό είναι το ίδιο.
Μόνο που στην δική μας περίπτωση είναι πιο πολύπλοκο.
Το αφήνω μήπως θέλει να ασχοληθεί κανείς, γιατι έχει πολύ ενδιαφέρον
Παράθεση από: evry στις 22 Φεβ 2014, 03:41:56 ΜΜ
Δεδομένου ενός πίνακα Α[Ν] που περιέχει μόνο 0 και 1 να διαχωρίσετε τα 0 από τα 1 έτσι ώστε όλα τα 0 να είναι πριν από όλα τα 1, με ένα μόνο πέρασμα
i ← 1
j ← N
Όσο i < j επανάλαβε
Όσο Α[i] = 0 και i < j επανάλαβε
i ← i + 1
Τέλος_επανάληψης
Όσο Α[j] = 1 και i < j επανάλαβε
j ← j - 1
Τέλος_επανάληψης
Αντιμετάθεσε α[i], α[j]
τέλος_επανάληψης
Δείτε μια ακόμη ιδέα. Δεν το έλεγξα διεξοδικά, αλλά πρέπει να δουλεύει !
Αλγόριθμος ΜηδένΈνα
Δεδομένα // Ν, Α //
δ0 ← 0
δ1 ← 0
Για i από 1 μέχρι Ν
Αν Α[i] = 0 τότε
δ0 ← δ0 + 1
Αν 2*δ0 - 1 < i τότε
Αντιμετάθεσε Α[i], Α[2*δ0 - 1]
Τέλος_αν
αλλιώς
δ1 ← δ1 + 1
Αν 2*δ1 < i τότε
Αντιμετάθεσε Α[i], Α[2*δ1]
Τέλος_αν
Τέλος_αν
Τέλος_επανάληψης
Για i από 1 μέχρι Ν
Εμφάνισε Α[i], " "
Τέλος_επανάληψης
Τέλος ΜηδένΈνα
Φοβερή λύση, συγχαρητήρια!
Πράγματι φοβερή λύση.
Η χρήση του Αντιμετάθεσε σου εξασφαλίζει ότι δεν χάνεται πληροφορία.
@ssimaiof, respect! ο κώδικας σου είναι απ' αυτούς που λες, μα πως το σκέφτηκε;
@nikolasmer, μόνος σου τις σκέφτεσαι αυτές τις ασκήσεις ή τις ξεσηκώνεις από κάποιο βιβλίο;
Έχουμε κουβεντιάσει την άσκηση που μπήκε περισυνό θέμα Β με τις τιμές Αληθής και Ψευδής που έπρεπε να τις αναδιατάξεις χωρίς ταξινόμηση. Οπότε βλέπωντας και τις απαντήσεις των μαθητών σε ενα καλοκαιρινό thread, που έδωσαν στις πανελλήνιες, ήθελα να βάλω στα παιδιά κάτι πιο δύσκολο, για να ασχοληθούν, όχι με λογικές τιμές αλλά με 0 και 1. Δεν ήθελα να τους πάει κατευθείαν το μυαλό εκεί. Έτσι σκέφτηκα αν μπορεί να γίνει αυτή η ασκησούλα. Επίσης παρατήρησα, μετά απο πολύ ώρα σκέψης, ότι το μυαλουδάκι μου δεν μπορούσε να κατεβάσει τίποτα απολύτως οπότε την ανέβασα για να δώ αν μπορεί να λυθεί, με ενα προφανώς πέρασμα των στοιχείων.
Ήθελα να μπορεί να επεκταθεί και για λογικές τιμές η λύση της άσκησης φυσικά, πράγμα που νομίζω οτι η λύση του evry δεν το πετυχαίνει γιατί χρησιμοποιεί τα στοιχεία του πίνακα ως δείκτες.
Πραγματικά όλες οι παραπάνω λύσεις είναι φοβερές.
ΠαράθεσηΕπιτέλους ανακάλυψα οτι όλα τα πράγματα είχαν ονόματα. Μετά άρχισα να διερωτώμαι γιατί είχαν τα ονόματα που είχαν. Όταν τελικά εγκατέλειψα την προσπάθεια αυτή, τότε άρχισα να αναγνωρίζω τον κόσμο και να προσπαθώ να επικοινωνήσω με τους άλλους με τις λέξεις που άκουγα και είχα μάθει απλώς να ξεχωρίζω
Ιωάννης Κάβουρας
(Να είναι καλά εκεί που βρίσκεται. Τον ευχαριστώ)
Αφού με παίρνει μια ώρα να καταλάβω τον κάθε έναν από τους παραπάνω κώδικες, μάλλον ακόμα βρίσκομαι στο στάδιο που ανακαλύπτω πως όλα τα πράγματα έχουν ονόματα. :-[
Ακριβώς αυτό είναι το ωραίο με την λύση του evry. Ότι χρησιμοποιεί την τιμή του πίνακα ως δείκτη και έτσι κάνει οικονομία σε δύο θέσεις μνήμης!(και από την μύγα ξύγκι). Τροποποιείται όμως πολύ εύκολα, και για την περίπτωση που δεν έχεις 0 και 1.