Τώρα είναι Πέμ 28 Μαρ 2024 01:39 pm

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απαντήστε στο θέμα  [ 2 Δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
ΔημοσίευσηΔημοσιεύτηκε: Πέμ 23 Δεκ 2004 02:25 am 
Χωρίς σύνδεση

Εγγραφή: Τετ 15 Δεκ 2004 04:26 am
Δημοσιεύσεις: 10
Τοποθεσία: Πρέβεζα
Syntax: [ Download ] [ Hide ]
!---------------------------------------------------------------
! netnick
!---------------------------------------------------------------
! ΑΝΑΖΗΤΗΣΗ ΣΕ ΤΑΞΙΝΟΜΗΜΕΝΟ ΠΙΝΑΚΑ ΧΩΡΙς ΠΟΛΛΑΠΛΗ ΕΜΦΑΝΙΣΗ ΣΤΟΙΧΕΙΩΝ
! Το flag είναι έτσι κι αλλιώς πλεονασμος
! done =  true <=> ΘΕΣΗ > 0 <=> ΒΡΕΘΗΚΕ
! done = false <=> ΘΕΣΗ = 0 <=> ΔΕΝ ΒΡΕΘΗΚΕ
!---------------------------------------------------------------
ΠΡΟΓΡΑΜΜΑ ANAZHTHSH
ΣΤΑΘΕΡΕΣ
  Ν = 20
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Π[Ν],Ι,ΚΕΥ,ΘΕΣΗ
ΑΡΧΗ

!---------------------------------------------------------------
  ΓΙΑ Ι ΑΠΟ 1 ΜΕΧΡΙ Ν
    ΔΙΑΒΑΣΕ Π[Ι]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΓΡΑΨΕ

  ΓΡΑΨΕ 'ΔΩΣΕ ΣΤΟΙΧΕΙΟ ΓΙΑ ΑΝΑΖΗΤΗΣΗ:'
  ΔΙΑΒΑΣΕ ΚΕΥ

!---------------------------------------------------------------
! Η ΑΝΑΖΗΤΗΣΗ. ΟΣΟ ((ΔΕΝ ΒΡΕΘΗΚΕ) ΚΑΙ (ΥΠΑΡΧΟΥΝ ΣΤΟΙΧΕΙΑ) ΚΑΙ
! (ΕΙΜΑΣΤΕ ΑΚΟΜΑ ΣΕ ΜΙΚΡΟΤΕΡΑ ΤΟΥ ΚΕΥ ΣΤΟΙΧΕΙΑ)), ΨΑΞΕ,...
!---------------------------------------------------------------
  ΘΕΣΗ <-- 0
  Ι <-- 1
  ΟΣΟ ((ΘΕΣΗ=0) ΚΑΙ (Ι<=Ν) ΚΑΙ (Π[Ι] <= ΚΕΥ)) ΕΠΑΝΑΛΑΒΕ
    ΑΝ ΚΕΥ = Π[Ι] ΤΟΤΕ
      ΘΕΣΗ <-- Ι
    ΤΕΛΟΣ_ΑΝ
    Ι <-- Ι+1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

! ΕΜΦΑΝΙΣΕ ΕΝΑ ΜΗΝΥΜΑ ...
  ΑΝ ΘΕΣΗ>0 ΤΟΤΕ
    ΓΡΑΨΕ 'ΒΡΕΘΗΚΕ ΣΤΗΝ ΘΕΣΗ ',ΘΕΣΗ
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'ΔΕΝ ΒΡΕΘΗΚΕ'
  ΤΕΛΟΣ_ΑΝ


ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
!---------------------------------------------------------------


 


Κορυφή
 Προφίλ  
Απάντηση με παράθεση  
 Θέμα δημοσίευσης: Δυαδική Αναζήτηση
ΔημοσίευσηΔημοσιεύτηκε: Παρ 28 Ιαν 2005 12:44 pm 
Χωρίς σύνδεση

Εγγραφή: Πέμ 22 Απρ 2004 11:16 am
Δημοσιεύσεις: 60
Τοποθεσία: Θεσσαλονίκη
Δυαδική Αναζήτηση

Και μια ακόμη πρόταση για γρήγορη αναζήτηση, η οποια δεν είναι σειριακή (ΔΕΝ αναζητά δηλαδή με τη σειρά τα στοιχεία ενός πίνακα). Λειτουργεί όμως ΜΟΝΟΝ σε ΤΑΞΙΝΟΜΗΜΕΝΟ πίνακα.

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

Το επόμενο πρόγραμμα δημιουργεί έναν πίνακα Ν θέσεων (με Ν<=1000) και τοποθετεί με τη σειρά τους φυσικούς αριθμούς 1,2,3,4...Ν στις αντίστοιχες θέσεις του πίνακα. Διαβάζει στη συνέχεια έναν αριθμό (key) προς αναζήτηση. Φανταστείτε λοιπόν πως η τιμή key δεν υπάρχει στον πίνακα. Τότε μια σειριακή αναζήτηση θα έπρεπε να εκτελέσει Ν επαναλήψεις, για να αποφανθεί πως η τιμή key δεν υπάρχει. Η Δυαδική Αναζήτηση παρατειρείστε οτί είναι σαφώς πιο γρήγορη.
Στην περίπτωση δε, που η τιμή key υπάρχει στον πίνακα, μια σειριακή αναζήτηση θα εκτελούσε key επαναλήψεις, ενώ η Δυαδική Αναζήτηση παραμένει σημαντικά πιο γρήγορη.

Όλα τα προηγούμενα ισχύουν αν πίνακας έχει πάνω από περίπου 10-20 με στοιχεία, και δεν έχουν κανένα νόημα αν έχουμε ένα πίνακα με 5-10 στοιχεία.

Δοκιμάστε όμως να εκτελέσετε το επόμενο προγραμμα με Ν>400 και ίσως με έκπληξη θα διαπιστώσετε ότι η Δυαδική Αναζήτηση σπάνια εκετελεί πάνω από 7-8 ελέγχους (επαναλήψεις) (άσχετα με το αν η key υπάρχει ή οχι στον πίνακα). :lol:

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

Καλές δοκιμές.

Syntax: [ Download ] [ Hide ]
ΠΡΟΓΡΑΜΜΑ Δυαδική_Αναζήτηση
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: Ν,key,i,start,final,θεση,mid,ελ,Α[1000]
  ΛΟΓΙΚΕΣ: βρέθηκε
ΑΡΧΗ

  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΡΑΨΕ 'Δώσε πλήθος ακεραίων (1-1000)'
    ΔΙΑΒΑΣΕ Ν
  ΜΕΧΡΙΣ_ΟΤΟΥ (Ν>=1) ΚΑΙ (Ν<=1000)

  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
    Α[i] <-- i
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΓΡΑΨΕ 'Δώσε ακέραιο προς αναζήτηση'
  ΔΙΑΒΑΣΕ key

  βρέθηκε <-- ψευδής
  start <-- 1
  final <-- Ν
  θεση <-- 0
  ελ <-- 0

  ΟΣΟ (start<=final) ΚΑΙ (ΟΧΙ βρέθηκε) ΕΠΑΝΑΛΑΒΕ
    mid <-- (start+final) DIV 2
    ΑΝ Α[mid]=key ΤΟΤΕ
      θεση <-- mid
      βρέθηκε <-- αληθής
    ΑΛΛΙΩΣ_ΑΝ key>A[mid] ΤΟΤΕ
      start <-- mid+1
    ΑΛΛΙΩΣ_ΑΝ key<A[mid] ΤΟΤΕ
      final <-- mid-1
    ΤΕΛΟΣ_ΑΝ
    ελ <-- ελ+1
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

  ΑΝ βρέθηκε  ΤΟΤΕ
    ΓΡΑΨΕ 'Ο αριθμός ', key,' βρέθηκε στην ', θεση,'η θέση του πίνακα'
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Ο αριθμός ',key,' δεν βρέθηκε'
  ΤΕΛΟΣ_ΑΝ

  ΓΡΑΨΕ 'Πραγματοποιηθηκαν ', ελ,' έλεγχοι'

ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

 

_________________
Φρειδερίκος Κώστας
FreiderikosK@hotmail.com


Κορυφή
 Προφίλ  
Απάντηση με παράθεση  
Τελευταίες δημοσιεύσεις:  Ταξινόμηση ανά  
Δημιουργία νέου θέματος Απαντήστε στο θέμα  [ 2 Δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μέλη σε σύνδεση

Μέλη σε αυτή την Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επισυνάπτετε αρχεία σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
cron
Προβολές: