Αναζητηση αριθμου σε μονο-διαστατο ταξινομημενο πινακα..

Ξεκίνησε από Mouzenides Panayiotis, 21 Δεκ 2011, 02:34:32 ΜΜ

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

Mouzenides Panayiotis

Εγραψα αλγοριθμο ο οποιος ελεγχει και εμφανιζει αν υπαρχει ενας αριθμος μεσα σε ταξινομημενο πινακα με τη Δυαδικη Μεθοδο...
δυο ερωτησεις εχω...

1) αν για παραδειγμα ο πινακας ξεκιναει Τ[1]=5 και εγω δωσω στο Χ τιμη 4 τοτε μου βγαζει προβλημα.. Εδω..
               
ΠαράθεσηΑΝ Χ=Τ[ΜΕΣΟ] ΤΟΤΕ
      ΕΜΦΑΝΙΣΕ "ΤΟ Χ ΒΡΙΣΚΕΤΕ ΣΤΗ ΘΕΣΗ", ΜΕΣΟ
      Ι← Ξ
Μου λεει: Ο δείκτης του πίνακα δεν είναι ακέραιος θετικός αριθμός.
δεν μπορω να βρω γιατι συμβαινει αυτο και πως να το διορθωσω..

2) υπαρχει αναλογος αλγοριθμος ο οποιος να διαιρει ενα πινακα σε τρια κομματια...ή κατα ποσο ειναι εφικτο αυτο..?
Μπορει να προσαρμοστει η συγκεκριμενη λογικη εκει ή οχι?


ΠαράθεσηΑΛΓΟΡΙΘΜΟΣ ΔΥΑΔΙΚΗ_ΑΝΑΖΗΤΗΣΗ
ΔΙΑΒΑΣΕ Ν
Χ← Ν
! Ο ΠΙΝΑΚΑΣ ΜΠΟΡΕΙ ΝΑ ΔΕΙΧΘΕΙ ΕΥΚΟΛΑ ΟΤΙ 2^Χ<=Ν<=2^(Χ+1)-1 ΣΥΝΕΠΩΣ Ο ΠΙΝΑΚΑΣ ΔΙΑΙΡΕΙΤΑΙ ΤΟ ΠΟΛΥ Χ+1 ΦΟΡΕΣ (Χ+1=Ξ)
Ξ← 0
ΟΣΟ Χ<> 0 ΕΠΑΝΑΛΑΒΕ
   Χ← Χ DIV 2
   Ξ← Ξ+1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
! ΒΑΖΩ ΕΓΩ ΚΑΠΟΙΑ ΤΑΞΙΝΟΜΗΜΕΝΑ ΣΤΟΙΧΕΙΑ ΑΠΛΑ ΚΑΙ ΜΟΝΟ ΓΙΑ ΠΑΡΑΔΕΙΓΜΑ (ΑΣΧΕΤΑ ΜΕΤΑΞΥ ΤΟΥΣ)
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν
   Λ ← Ξ*Ι + Ν*Ι
   Τ[Ι]← Ι + Λ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΔΙΑΒΑΣΕ Χ
ΑΡΧΗ_Π ←  1
ΤΕΛΟΣ_Π ←  Ν
ΜΕΣΟ← (ΑΡΧΗ_Π + ΤΕΛΟΣ_Π)DIV 2
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ξ
   ΑΝ Χ > Τ[ΜΕΣΟ] ΤΟΤΕ
      ΑΡΧΗ_Π← ΜΕΣΟ+1
      ΜΕΣΟ←  (ΑΡΧΗ_Π + ΤΕΛΟΣ_Π)DIV 2
   ΑΛΛΙΩΣ_ΑΝ Χ<Τ[ΜΕΣΟ] ΤΟΤΕ
      ΤΕΛΟΣ_Π←  ΜΕΣΟ-1
      ΜΕΣΟ←  (ΑΡΧΗ_Π + ΤΕΛΟΣ_Π)DIV 2
   ΤΕΛΟΣ_ΑΝ
   ΑΝ Χ=Τ[ΜΕΣΟ] ΤΟΤΕ
      ΕΜΦΑΝΙΣΕ "ΤΟ Χ ΒΡΙΣΚΕΤΕ ΣΤΗ ΘΕΣΗ", ΜΕΣΟ
      Ι← Ξ

   ΑΛΛΙΩΣ_ΑΝ Ι=Ξ ΚΑΙ Χ<>Τ[ΜΕΣΟ] ΤΟΤΕ
      ΕΜΦΑΝΙΣΕ "ΤΟ Χ ΔΕΝ ΥΠΑΡΧΕΙ ΣΤΟΝ ΠΙΝΑΚΑ"
   ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ ΔΥΑΔΙΚΗ_ΑΝΑΖΗΤΗΣΗ

gpapargi

#1
Παράθεση από: Mouzenides Panayiotis στις 21 Δεκ 2011, 02:34:32 ΜΜ
2) υπαρχει αναλογος αλγοριθμος ο οποιος να διαιρει ενα πινακα σε τρια κομματια...ή κατα ποσο ειναι εφικτο αυτο..?
Μπορει να προσαρμοστει η συγκεκριμενη λογικη εκει ή οχι?

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

Αν κατάλαβα καλά θα ήθελες να φτιάξεις κάτι σαν τριαδική αναζήτηση που να πηγαίνει πιο γρήγορα. Νομίζω ότι κάθε υγειές μυαλό είναι λογικό μετά τη δυαδική αναζήτηση να ψάξει να βρει κάτι πιο γρήγορο ή ένα επιχείρημα που να εξηγεί γιατί δεν υπάρχει κάτι πιο γρήγορο.
Για να τελειώσεις όσο το δυνατό γρηγορότερα θα πρέπει κάθε φορά να περιορίζεις την αναζήτησή σου σε όσο το δυνατό μικρότερη περιοχή. Αυτό που μας ενδιαφέρει είναι στη χειρότερη περίπτωση (και όχι στην καλύτερη) πόσο μπορείς να περιορίσεις την περιοχή στην οποία είναι μέσα αυτό που ψάχνεις.
Στη δυαδική αναζήτηση ψάχνεις στη μέση, οπότε έχεις διαιρέσει στα 2 την περιοχή σου και όπου και να βρίσκεται το στοιχείο που ψάχνεις το έχεις περιορίσει σίγουρα στη μισή περιοχή από την αρχική. Αν κόψεις την περιοχή στα 3 τότε αν είσαι τυχερός με τη σύγκρισή σου  έχει περιορίσει την περιοχή στο 1/3. Αν όμως είσαι άτυχος την έχεις περιορίσει στα 2/3 που είναι χειρότερο από το 1/2 της δυαδικής αναζήτησης.
Σαν ακραία περίπτωση σκέψου τη σειριακή αναζήτηση. Με μια σύγκριση αν είσαι τυχερός έχεις περιορίσει την περιοχή στην οποία ψάχνεις σε μέγεθος 1 (δηλαδή το βρήκες), αλλά αν είσαι άτυχος  το έχεις περιορίσεις σε μέγεθος ν-1 (που είναι χάλια). Επειδή μας νοιάζει η χειρότερη περίπτωση το καλύτερο που μπορούμε να πετύχουμε με μια σύγκριση είναι περιορίσουμε την περιοχή στο μισό. Οτιδήποτε άλλο θα χώριζε την αρχική μας περιοχή σε  μικρότερες εκ των οποίων η μεγαλύτερη (επειδή μας νοιάζει η χειρότερη περίπτωση) θα ήταν μεγαλύτερη από το μισό.

Mouzenides Panayiotis

#2
καλησπερα...ευχαριστω πολυ για την απαντηση πριν απο καιρο δοθηκε βεβαια..
εφτιαξα εναν αλγοριθμο ο οποιος δουλευει μεν οταν υπαρχει ο αριθμος αλλα οταν ο αριθμος δεν υπαρχει ο αλγοριθμος δεν εχει τελος...ενω εχω βαλλει εναν ελεγχο
υπεθεσα οτι αν ο αριθμος δεν υπαρχει το τελος θα πλησιασει τοσο την αρχη ωστε η διαφορα τους να ειναι συνεχως ιση με το ενα...ισχυει κατι τεοιο ή λαθος υποθεση εκανα?

ΠαράθεσηΑΛΓΟΡΙΘΜΟΣ ΤΡΙΑΔΙΚΗ_ΑΝΑΖΗΤΗΣΗ
ΔΙΑΒΑΣΕ Ν
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν
   ΔΙΑΒΑΣΕ Τ[Ι]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΔΙΑΒΑΣΕ Χ
ΑΡΧΗ_Π ←  1
ΤΕΛΟΣ_Π ←  Ν
ΕΛΕΓΧΟΣ ← ΨΕΥΔΗΣ
ΑΝΥΠΑΡΚΤΟΣ← ΨΕΥΔΗΣ
ΟΣΟ ΟΧΙ (ΕΛΕΓΧΟΣ Ή ΑΝΥΠΑΡΚΤΟΣ) ΕΠΑΝΑΛΑΒΕ
   ΜΕΣΟ1 ← ((ΤΕΛΟΣ_Π-ΑΡΧΗ_Π)DIV 3)+ΑΡΧΗ_Π
   ΜΕΣΟ2 ← ((ΤΕΛΟΣ_Π-ΑΡΧΗ_Π)DIV 3)*2+ΑΡΧΗ_Π
   ΑΝ Χ > Τ[ΜΕΣΟ2] ΤΟΤΕ
      ΑΡΧΗ_Π ← ΜΕΣΟ2
   ΑΛΛΙΩΣ_ΑΝ Χ>Τ[ΜΕΣΟ1] ΤΟΤΕ
      ΑΡΧΗ_Π ← ΜΕΣΟ1
      ΤΕΛΟΣ_Π ← ΜΕΣΟ2
   ΑΛΛΙΩΣ_ΑΝ Χ=Τ[ΜΕΣΟ1] Ή Χ=Τ[ΜΕΣΟ2] ΤΟΤΕ
      ΕΛΕΓΧΟΣ ← ΑΛΗΘΗΣ
      ΑΝ Χ=Τ[ΜΕΣΟ1] ΤΟΤΕ
         ΕΜΦΑΝΙΣΕ "ΤΟ Χ ΒΡΙΣΚΕΤΕ ΣΤΗ ΘΕΣΗ ",ΜΕΣΟ1
      ΑΛΛΙΩΣ_ΑΝ Χ=Τ[ΜΕΣΟ2] ΤΟΤΕ
         ΕΜΦΑΝΙΣΕ "ΤΟ Χ ΒΡΙΣΚΕΤΕ ΣΤΗ ΘΕΣΗ ",ΜΕΣΟ2
      ΤΕΛΟΣ_ΑΝ
   ΤΕΛΟΣ_ΑΝ
   ΑΝ ΤΕΛΟΣ_Π-ΑΡΧΗ_Π=1 ΤΟΤΕ
      ΑΝΥΠΑΡΚΤΟΣ ← ΑΛΗΘΗΣ
      ΕΜΦΑΝΙΣΕ "ΤΟ Χ ΔΕΝ ΒΡΙΣΚΕΤΕ ΣΤΟΝ ΠΙΝΑΚΑ"
   ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ ΤΡΙΑΔΙΚΗ_ΑΝΑΖΗΤΗΣΗ


Υ.Γ. για τον αλγοριθμο που εφτιαξα βασιστηκα σε μια βελτιωση που εκανα στο αρχικο της δυαδικη αναζητησης ο οποιος ειναι πολυ πιο απλος τροπος...

Παράθεση
ΑΛΓΟΡΙΘΜΟΣ ΔΥΑΔΙΚΗ_ΑΝΑΖΗΤΗΣΗ
ΔΙΑΒΑΣΕ Ν
ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν
   Τ[Ι]← 10*Ι
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΔΙΑΒΑΣΕ Χ
ΑΡΧΗ_Π ←  1
ΤΕΛΟΣ_Π ←  Ν
ΜΕΣΟ← (ΑΡΧΗ_Π + ΤΕΛΟΣ_Π)DIV 2
ΟΣΟ Τ[ΜΕΣΟ] <> Χ ΚΑΙ ΤΕΛΟΣ_Π-ΑΡΧΗ_Π=1 ΕΠΑΝΑΛΑΒΕ
   ΑΝ Χ > Τ[ΜΕΣΟ] ΤΟΤΕ
      ΑΡΧΗ_Π← ΜΕΣΟ+1
      ΜΕΣΟ←  (ΑΡΧΗ_Π + ΤΕΛΟΣ_Π)DIV 2
   ΑΛΛΙΩΣ_ΑΝ Χ<Τ[ΜΕΣΟ] ΤΟΤΕ
      ΤΕΛΟΣ_Π←  ΜΕΣΟ-1
      ΜΕΣΟ←  (ΑΡΧΗ_Π + ΤΕΛΟΣ_Π)DIV 2
   ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ Τ[ΜΕΣΟ]=Χ ΤΟΤΕ
   ΕΜΦΑΝΙΣΕ "ΤΟ Χ ΒΡΙΣΚΕΤΕ ΣΤΗ ΘΕΣΗ", ΜΕΣΟ
ΑΛΛΙΩΣ
   ΕΜΦΑΝΙΣΕ "ΤΟ Χ ΔΕΝ ΥΠΑΡΧΕΙ ΣΤΟΝ ΠΙΝΑΚΑ"
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ ΔΥΑΔΙΚΗ_ΑΝΑΖΗΤΗΣΗ

Mouzenides Panayiotis

καλησπερα..μαλλον εκανα και αλλο λαθος...σημερα βρηκα και τιμες για τις οποιες δεν δουλευει ο αλγοριθμος....
μαλλον πρεπει να το δουλψω και αλλο..

evry

Αν σε ενδιαφέρει η αναζήτηση και ψάχνεις μια βελτίωση της δυαδικής, η πρότασή μου είναι η εξής:
Μην ασχολείσαι με την τριαδική, δεν έχει νόημα. Αυτό το οποίο έχει ενδιαφέρον είναι να προσπαθήσεις να φτιάξεις ένα πρόβλημα στο οποίο οι αριθμοί δεν είναι μόνο ταξινομημένοι σε αύξουσα σειρά, αλλά ακολουθούν και κάποιου είδους κατανομή. Δηλαδή η ιδέα πάντα είναι να εκμεταλλευτούμε κάποιου είδους πληροφορία για να βελτιώσουμε τον αλγόριθμό μας.. Στην δυαδική αναζήτηση η πληροφορία είναι ότι οι αριθμοί είναι "στη σειρά". Προσπάθησε να σχεδιάσεις ένα πρόβλημα στο οποίο οι αριθμοί θα ακολουθούν μια κατανομή την οποία θα μπορούσες να εκμεταλλευτείς στην αναζήτηση, αυτό θα είχε ενδιαφέρον.

Τώρα αν θέλεις να κάνεις κάτι "τριαδικό" σκέψου το εξής:

Πρόβλημα : Εύρεση Μεγίστου σε πίνακα Ν στοιχείων

Ιδέα: Σπάμε τον πίνακα σε τρία κομμάτια
                    Βρίσκουμε το μέγιστο κάθε κομματιού
                    Το μέγιστο των τριών είναι το μέγιστο.

Προφανώς για να βρούμε το μέγιστο σε κάθε κομμάτι, το σπάμε και αυτό σε τρία κομμάτια και πάει λέγοντας
Ερώτηση 1: Πότε σταματάμε να σπάμε?
Ερώτηση 2: Είναι ο αλγόριθμος αυτός πιο γρήγορος από τον γνωστό αλγόριθμο που γνωρίζουμε για την εύρεση μεγίστου?

Υπόδειξη: Προσπάθησε να εκτελέσεις τον παραπάνω αλγόριθμο στο χαρτί για έναν μικρό πίνακα 9, 12 ή 27 στοιχείων και μετά προσπάθησε να τον υλοποιήσεις σε ΓΛΩΣΣΑ.

Ένα ενδιαφέρον πρόβλημα αν έχεις χρόνο είναι και το παρακάτω:
Πρόβλημα
Δεδομένου ενός πίνακα Α, Ν ακέραιων αριθμών να βρεθεί ο υποπίνακάς του με το μεγαλύτερο άθροισμα στοιχείων. [Στο τέλος να εμφανίζει το μέγιστο άθροισμα και όχι τον υποπίνακα]
Σκέψου αν η πρώτη λύση που θα σκεφτείς είναι η καλύτερη δυνατή ή υπάρχει τρόπος να βρεις το μέγιστο αυτό άθροισμα με μια μόνο σάρωση.

ΥΓ. Αν πάλι έχεις "κολλήσει" με την δυαδική αναζήτηση τότε σκέψου πως θα μπορούσε να εφαρμοστεί αυτή έτσι ώστε να φτιάξεις έναν αλγόριθμο ο οποίος θα συγκλίνει στη ρίζα της εξίσωσης f(x)=0, [a,b] με f(a)f(b)<0 με διαδοχικές εφαρμογές του Θεωρήματος Bolzano. (Υπάρχει και στο βιβλίο αυτή η μέθοδος που είναι γνωστή ως μέθοδος της διχοτόμησης)
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr