Σε μια ταξινομημένη λίστα 1000 στοιχείων, πόσες είναι οι περισσότερες συγκρίσεις που θα χρειαζόταν για να βρεθεί οποιοδήποτε στοιχείο χρησιμοποιοώντας τη δυαδική αναζήτηση;

Η σειριακή αναζήτηση σαρώνει όλα τα στοιχεία μιας ταξινομημένης λίστας χωρίς να εκμεταλλεύεται τη διάταξη των στοιχείων

Τι θα συμβεί στο παρακάτω τμήμα αλγορίθμου;

students = ['Δημήτρης', 'Ευγενία', 'Ναταλία', 'Ρένια', 'Αλέξανδρος']

if students[4] < students[3]:

        students[4], students[3] = students[3], students[4]

για την παρακάτω λίστα a=[9, -2, 6, 4, -8, 12, 5, 18] Συμπληρώστε τα κενά για να γίνει αύξουσα ταξινόμηση

a = [9, -2, 6, 4, -8, 12, 5, 18]

N = len(a)

for i in range(N-1):

        for j in range( ___  ,  _____ , -1):

                if a[j+1] > a[j]:

                       a[j], a[j + 1] = a[j + 1], a[j]

O παρακάτω αλγόριθμος της αύξουσας ταξινόμησης Ν στοιχείων σε τι μειονεκτεί;

for i in range(N-1):

        for j in range(N-1, 0, -1):

                if A[j] < A[j-1]:

                       A[j], A[j-1] = A[j-1], A[j]

Για την παρακάρω λίστα με 7 αριθμούς ποια θα είναι η τιμή της λίστας μετά από πέντε περάσματα, αν χρησιμοποιήσουμε τον αλγόριθμο της αύξουσας ταξινόμησης (φυσαλίδα);

[55, 34, 5, 3, 2, 1, 1]

Η δυαδική αναζήτηση μπορεί να χρησιμοποιηθεί τόσο σε αύξουσα ταξινομημένη λίστα, όσο και σε φθίνουσα

Ο παρακάτω αλγόριθμος δυαδικής αναζήτησης χρησιμοποιείται σε λίστες με αύξουσα ταξινόμηση:

def binarySearch(lista, key):

        first = 0

        last = len(lista) - 1

        found = False

        while not found and first <= last:

                mid = (first + last) / 2

                if  key == lista[mid] :

                      found = True

                elif key > lista[mid]  :

                      last = mid - 1

                else:

                    first  = mid +1

        return found

Ο παρακάτω αλγόριθμος δυαδικής αναζήτησης χρησιμοποιείται σε λίστες με φθίνουσα ταξινόμηση:

def binarySearch(lista, key):

        first = 0

        last = len(lista) - 1

        found = False

        while not found and first <= last:

                mid = (first + last) / 2

                if lista[mid] == key:

                      found = True

                elif lista[mid] < key:

                      first = mid + 1

                else:

                     last = mid - 1

        return found

Η δυαδική αναζήτηση μπορεί να γίνει μόνο σε ταξινομημένες λίστες με αριθμούς, όχι σε λίστες με συμβολοσειρές

Τι θα εμφανίσει το παρακάτω πρόγραμμα;

 def check_D(mylist):

        d = True

        i = 0

        N = len(mylist)

        while d and i < N-1:

                if myList[i] < myList[i + 1]:

                        d = False

                i = i + 1

        return d

L = [20, 12, 4, 2]

print check_D(L)

Στην παρακάτω αύξουσα ταξινομημένη λίστα  L ψάχνουμε το 45.

η πρώτη σύγκριση για τον αριθμό 45 θα είναι με το στοιχείο στο δείκτη: (0+13)/2 =6 άρα με τον L[6] άρα με το 35.

Ποιος είναι ο επόμενος αριθμός που θα συγκριθεί το 45;

Η δυαδική αναζήτηση μπορεί να γίνει σε στοιχεία που βρίσκονται σε κάποια λογική διάταξη, είτε αυτά είναι αριθμοί είτε αλφαριθμητικά

Σε μια ταξινομημένη λίστα 100 στοιχείων, πόσες είναι οι περισσότερες συγκρίσεις που θα χρειαζόταν για να βρεθεί οποιοδήποτε στοιχείο χρησιμοποιοώντας τη δυαδική αναζήτηση;

Ο παρακάτω αλγόριθμος επιλέγει έναν αριθμό από το 1 έως και το 100 και ο χρήστης προσπαθεί να τον μαντέψει. Βελτιώστε τον αλγόριθμο στην  else:  ώστε το πρόγραμμα να δίνει μια βοήθεια στο χρήστη, ώστε αν ο αριθμός που έδωσε είναι μικρότερος ή μεγαλύτερος να εμφανίζεται αντίστοιχο μήνυμα

import random

secret_number = random.randint(1, 100)  # ο αριθμός που επιλέγει τυχαίο ο Η/Υ

guesses = 0   #προσπάθειες

found = False

while not found:

        guess = input(' Μάντεψε τον αριθμό')  # Ο αριθμός που δίνει ο χρήστης

        guesses + = 1

        if guess == secret_number:

                print 'Μπράβο το βρήκες με', guesses, 'προσπάθειες'

                found = True

        else:

                print 'Δυστυχώς δεν το βρήκες, ξαναπροσπάθησε'
 

Ο παρακάτω αλγόριθμος επιλέγει έναν αριθμό από το 1 έως και το 1000 και ο χρήστης προσπαθεί να τον μαντέψει με τη βοήθεια μηνυμάτων από το Η/Υ (αν ο αριθμός που έδωσε ο χρήστης είναι μικρότερος ή μεγαλύτερος). Βελτιώστε τον αλγόριθμο στην  while ώστε ο χρήστης να σκεφτεί με καλύτερη στρατηγική και να μειώσει τις προσπάθειές του για να βρει τον κρυφό αριθμό. Οι προσπάθειες που θα μπορεί να δώσει είναι 10

import random

secret_number = random.randint(1, 1000)  # ο αριθμός που επιλέγει τυχαίο ο Η/Υ

guesses = 0   #προσπάθειες

found = False

while not found:

        guess = input(' Μάντεψε τον αριθμό')  # Ο αριθμός που δίνει ο χρήστης

        guesses + = 1

        if guess == secret_number:

                print 'Μπράβο το βρήκες με', guesses, 'προσπάθειες'

                found = True

        else:

                if guess < secrtet_number:

                        print ' Ο αριθμός σου είναι μικρότερος από τον ζητούμενο'

                else:

                        print ' Ο αριθμός σου είναι μεγαλύτερος από τον ζητούμενο'  

#Τέλος της while

if  found :  # αφού αν είναι True αρκεί (μπορούμε και found == True:)

        print 'Μπράβο το βρήκες με ', guesses, ' προσπάθειες'

else:

        print 'Δυστυχώς δεν το βρήκες'

Τι θα εμφανιστεί όταν θα γίνει η κλήση της συνάρτησης binarySearch για τη λίστα: L [7, 9, 15, 67, 77, 85];

def binarySearch(array, key):

        first = 0

       last = len(array) - 1

        pos = 'Δεν υπάρχει'

        while first <= last and pos == -1:

                mid = (first + last) / 2

                if array[mid] == key:

                        pos = mid

                elif array[mid] < key:

                        first = mid + 1

               else:

                       last = mid - 1

        return pos

print binarySearch(L, 5):

 

Πόσα περάσματα θα γίνουν για την αύξηση ταξινόμηση της λίστας:

[4, 6, 8, 18, 30, 50, 56, 68, 70, 3, 1]

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

Σε μια ταξινομημένη λίστα 16 στοιχείων, πόσες είναι οι περισσότερες συγκρίσεις που θα χρειαζόταν για να βρεθεί οποιοδήποτε στοιχείο χρησιμοποιοώντας τη δυαδική αναζήτηση;