Γενικό Λύκειο > Εισαγωγή στοιχείων, εμφάνιση και υπολογισμοί

Μονοδιάστατος με 0 σε άρτιες θέσεις και 1 σε περιττές

(1/3) > >>

nikolasmer:
Μπορεί να δημιουργηθεί τμήμα κώδικα που να δέχεται έναν πίνακα Ν θέσεων, με εισαγόμενες τιμές 0 και 1 σε ανακατωμένες θέσεις και με ένα πέρασμα των στοιχείων του πίνακα να τοποθετούνται τα 0 στις περιττές θέσεις και οι άσσοι στις άρτιες θέσεις του πίνακα;
Αν τελειώσουν οι άσσοι ή τα μηδενικά, από εκεί και έπειτα να εισάγονται μόνο οι τιμές που περισσεύουν;
Υπάρχει αυτή η δυνατότητα;
Για παράδειγμα έστω τα στοιχεία
01100001000100101010
σε πίνακα 15 θέσεων.
Με μια προσπέλαση η τελική κατάσταση των στοιχείων να είναι
01010101010101000000

petrosp13:
Με μια πρόχειρη ματιά

Για i από 1 μέχρι Ν-1
    Αν (Α[ι]=imod2) τότε
         βρέθηκε <-- ψευδής
         κ <-- i + 1
         Όσο (κ <= Ν) και (βρέθηκε=ψευδής) επανάλαβε
               Αν (Α[k] <> A(i)) και (Α[k] = kmod2) τότε
                     temp <-- A[k]
                     A[k] <-- A(i)
                     A(i) <-- temp
                     βρέθηκε <-- αληθής
                Αλλιώς
                     κ <-- κ+1
                Τέλος_Αν
        Τέλος_Επανάληψης
Τέλος_Επανάληψης

Δεν το έλεγξα, στα γρήγορα γιατί είμαι από κινητό
               

apoldem:
1) Μετράς πόσα είναι τα 0 (έστω κ) και πόσα τα 1 (έστω λ)
2) Αν κ<λ τότε γεμίζεις τις πρώτες κ περιττές θέσεις με 0, αλλιώς τις πρώτες λ άρτιες θέσεις με 1 (εδώ πιθανόν να μπορεί να γραφεί ένας όμορφος κώδικας που να μην επαναλαμβάνει τα ίδια πράγματα για 0 και 1, ίσως με χρήση διαδικασίας)
3) Ότι απέμεινε το γεμίζεις με το άλλο ψηφίο που δεν χρησιμοποιήθηκε στο προηγούμενο βήμα.

Γενικά, κάπως δύσκολο το βρίσκω για θέμα.

evry:
Προφανώς όταν λέει με ένα πέρασμα εννοεί αλγόριθμο να έχει τουλάχιστον πολυπλοκότητα Ο(Ν), άρα αλγόριθμοι με Ο(Ν^2) δεν μπορούν να γίνουν αποδεκτοί.
Το θέμα είναι αν εννοεί και μόνο ένα πέρασμα από κάθε στοιχείο, δηλαδή δεν του αρκεί το Ο(Ν) αλλά θέλει και ένα μόνο πέρασμα από κάθε στοιχείο.
(Προσοχή!!! Μπορεί να γίνει με μια επανάληψη αλλά να μην είναι ουσιαστικά ένα πέρασμα)

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


--- Κώδικας: Pascal ---μ[0] <-- μ[1] <-- 0Για ι από 1 μέχρι Ν       μ[Α[ι]] <-- μ[Α[ι]] + 1Τέλος_Επανάληψης Αν μ[0]<μ[1] Τότε   τιμή <-- 0αλλιώς   τιμή <-- 1 κ <-- 1 + τιμήΓια ι από 1 μέχρι μ[τιμή]     Α[κ] <-- τιμή     κ <-- κ + 2    Τέλος_Επανάληψης θέση <-- κτιμή <-- 1 - τιμήΓια κ από θέση μέχρι Ν με βήμα 2     Α[κ] <-- τιμήΤέλος_Επανάληψης κ <-- 1+τιμήΓια ι από 1 μέχρι Ν με βήμα 2     Α[κ] <-- τιμή     κ <-- κ + 2    Τέλος_Επανάληψης         

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


--- Κώδικας: Pascal ---odd <-- 1even <-- 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, με ένα μόνο πέρασμα
Την άσκηση αυτή μπορεί να την δείτε και με θετικούς και αρνητικούς αριθμούς. Το σκεπτικό είναι το ίδιο.
Μόνο που στην δική μας περίπτωση είναι πιο πολύπλοκο.
Το αφήνω μήπως θέλει να ασχοληθεί κανείς, γιατι έχει πολύ ενδιαφέρον

sstergou:

--- Παράθεση από: evry στις 22 Φεβ 2014, 03:41:56 μμ --- Δεδομένου ενός πίνακα Α[Ν] που περιέχει μόνο 0 και 1 να διαχωρίσετε τα 0 από τα 1 έτσι ώστε όλα τα 0 να είναι πριν από όλα τα 1, με ένα μόνο πέρασμα

--- Τέλος παράθεσης ---

--- Κώδικας: Ψευδογλώσσα ---i ← 1j ← NΌσο i < j επανάλαβε        Όσο Α[i] = 0 και i < j επανάλαβε                i ← i + 1        Τέλος_επανάληψης        Όσο Α[j] = 1 και i < j επανάλαβε                j ← j - 1        Τέλος_επανάληψης        Αντιμετάθεσε α[i], α[j]τέλος_επανάληψης

Πλοήγηση

[0] Λίστα μηνυμάτων

[#] Επόμενη σελίδα

Μετάβαση στην πλήρη έκδοση