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

Δίνεται η λίστα με τους αριθμούς [60, 38, 98, 54, 32, 90, 20] . Πως θα γίνει η λίστα μετά από 3 περάσματα μιας αύξουσας ταξινόμησης;

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

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

Ο παρακάτω αλγόριθμος επιλέγει έναν αριθμό από το 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 'Δυστυχώς δεν το βρήκες'

Η αντιμετάθεση (αμοιβαία αλλαγή τιμών των μεταβλητών α, β) γίνεται στην Pyhton με την απλή εντολή:

a, b = b, a

Πως μπορεί να γίνει με επιπλέον μεταβλητή;

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

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

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

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

if students[4] < students[3]:

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

Ο παρακάτω αλγόριθμος βελτιστοποιεί την ταξινόμηση, ώστε όταν η λίστα ταξινομηθεί να μην κάνει άσκοπα περάσματα

def optimizedBubbleSort(A):

        N = len(A)

        isSorted = False

        i = 0

       while i < N-1  and not isSorted:

                isSorted = True

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

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

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

                               isSorted = False

                i + = 1

πόσα περάσματα θα γίνουν για τη λίστα [7, 8, 9, 12, 4, 5, 11] χρησιμοποιώντας τη βελτιστοποιημένη ταξινόμηση και πόσα άσκοπα θα γινόταν με τον απλό αλγόριθμο ταξινόμησης;

Η δυαδική αναζήτηση βρίσκει το ζητούμενο πολύ πιο αργά από ότι η σειριακή αναζήτηση

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

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

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

για την παρακάτω λίστα 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]

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

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

επειδή 45>35 θα ελέγξει από το δείκτη 6+1 = 7 έως το τέλος της λίστας.

Άρα ο επόμενος έλεγχος θα είναι με το στοιχείο στο δείκτη: (7 + 13) / 2 = 10, άρα με το 60

Με ποιο στοιχείο θα ελεγχθεί μετά;

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

 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)

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

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

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

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

Δίνεται το πρόβλημα: Να βρεθούν οι τρεις μεγαλύτεροι αριθμοί σε μια λίστα

Τι λύση θα επιλέγατε;

Η παρακάτω συνάρτηση υπολογίζει σωστά το πλήθος των True σε μια λίστα; Τι θα εμφανίσει το πρόγραμμα;

def count_True(lista):

        pl_true=0

        for item in lista:

                if item:

                        pl_true + = item

        return pl_true

L = [True, True, True, False, False]

print count_True(L)

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

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

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

if students[4] < students[3]:

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

if students[3] < students[2]:

        students[3], students[2] = students[2], students[3]