Σε μια ταξινομημένη λίστα 1000 στοιχείων, πόσες είναι οι περισσότερες συγκρίσεις που θα χρειαζόταν για να βρεθεί οποιοδήποτε στοιχείο χρησιμοποιοώντας τη δυαδική αναζήτηση;
10
20
5
50
Ο παρακάτω αλγόριθμος δυαδικής αναζήτησης χρησιμοποιείται σε λίστες με φθίνουσα ταξινόμηση:
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 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
Ο αλγόριθμος της σειριακή αναζήτησης μπορεί να χρησιμοποιηθεί μόνο σε ταξινομημένες λίστες
Επιλέξτε το σωστό πρόγραμμα που θα εμφανίζει σε φθίνουσα σειρά ως προς τους βαθμούς, τα ονόματα των μαθητών της τάξης
Θεωρήστε ότι η λίστα nameL με τα ονόματα και η λίστα gradeL με τους βαθμούς είναι γεμάτες
for i in range(N-1): for j in range(N-1, i , -1): if gradeL[j] > gradeL[j-1]: gradeL[j], gradeL[j-1] = gradeL[j-1], gradeL[j] nameL[j], nameL[j-1] = nameL[j-1], nameL[j] for i in range(N): print nameL[i]
for i in range(N-1):
for j in range(N-1, i , -1):
if gradeL[j] > gradeL[j-1]:
gradeL[j], gradeL[j-1] = gradeL[j-1], gradeL[j]
nameL[j], nameL[j-1] = nameL[j-1], nameL[j]
for i in range(N):
print nameL[i]
for i in range(N-1): for j in range(N-1, i , -1): if gradeL[j] < gradeL[j-1]: gradeL[j], gradeL[j-1] = gradeL[j-1], gradeL[j] for i in range(N-1,-1,-1): print nameL[i]
if gradeL[j] < gradeL[j-1]:
for i in range(N-1,-1,-1):
for i in range(N-1): for j in range(N-1, i , -1): if gradeL[j] > gradeL[j-1]: gradeL[j], gradeL[j-1] = gradeL[j-1], gradeL[j] nameL[j], nameL[j-1] = nameL[j-1], nameL[j] for i in range(N-1, -1, -1): print nameL[i]
for i in range(N-1, -1, -1):
for i in range(N-1): for j in range(N-1, i , -1): if gradeL[j] < gradeL[j-1]: gradeL[j], gradeL[j-1] = gradeL[j-1], gradeL[j] nameL[j], nameL[j-1] = nameL[j-1], nameL[j] for i in range(N): print nameL[i]
Να επιλεξετε τον σωστό αλγόριθμο της Δυαδικής αναζήτησης ενός στοιχείου key σε μια αύξουσα ταξινομημένη λίστα array
def binarySearch(array, key): first = 0 last = len(array) - 1 found = False while first <= last and not found: mid = (first + last) / 2 if array[mid] == key: found = True elif array[mid] < key: first = mid + 1 else: last = mid - 1 return found
def binarySearch(array, key):
last = len(array) - 1
while first <= last and not found:
if array[mid] == key:
elif array[mid] < key:
def binarySearch(array, key): first = 0 last = len(array) - 1 found = False while first <= last and not found: mid = (first + last) / 2 if array[mid] == key: found = True elif array[mid] < key: first = mid - 1 else: last = mid + 1 return found
first = mid - 1
last = mid + 1
def binarySearch(array, key): first = 0 last = len(array) - 1 found = False while first <= last and not found: mid = (first + last) / 2 if array[mid] == key: found = True elif array[mid] > key: first = mid + 1 else: last = mid - 1 return found
elif array[mid] > key:
def binarySearch(array, key): first = 0 last = len(array) - 1 found = False while first <= last and not found: mid = (first + last) / 2 if array[mid] == key: found = True elif array[mid] < key: last = mid + 1 else: first = mid - 1 return found
Η παρακάτω συνάρτηση υπολογίζει σωστά το πλήθος των 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)
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)
Τα υπολογίζει σωστώ, αφού η τιμή True που προσθέτει έχει αριθμητική αξία 1
Δηλαδή True+True+True = 3
Άρα θα εμφανίσει 3
True+True+True θα δώσει μήνυμα λάθους
rue+True+True θα δώσει ΤrueTrueTrue, άρα θα εμφανίσει: ΤrueTrueTrue
Σε μια ταξινομημένη λίστα 16 στοιχείων, πόσες είναι οι περισσότερες συγκρίσεις που θα χρειαζόταν για να βρεθεί οποιοδήποτε στοιχείο χρησιμοποιοώντας τη δυαδική αναζήτηση;
16
2
8
4
Πόσα περάσματα θα γίνουν για την αύξηση ταξινόμηση της λίστας:
[28, 28, 28, 28, 28, 28, 28, 30, 30, 30, 30]
1
0
Δίνεται το πρόβλημα: Να βρεθούν οι τρεις μεγαλύτεροι αριθμοί σε μια λίστα
Τι λύση θα επιλέγατε;
Αύξουσα ταξινόμηση και μετά με τη for i in range(3) θα εμφάνιζα τους τρεις πρώτους
Φθίνουσα ταξινόμηση και μετά με τη for i in range(Ν-1, Ν-4, -1) θα εμφάνιζα τους τρεις πρώτους
Φθίνουσα ταξινόμηση και μετά με τη for i in range(3) θα εμφάνιζα τους τρεις πρώτους
Επιλέξτε έναν πιο συνοπτικό τρόπο εκτέλεσης των παρακάτω εντολών, που δηλώνουν το πρώτο πέρασμα της αύξουσας ταξινόμησης σε μια λίστα 5 στοιχείων:
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] if students[2] < students[1]: students[2], students[1] = students[1], students[2] if students[1] < students[0]: students[1], students[0] = students[0], students[1]
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]
if students[2] < students[1]:
students[2], students[1] = students[1], students[2]
if students[1] < students[0]:
students[1], students[0] = students[0], students[1]
for j in range( 4, 0, -1): if studnets[j-1] < students[j-2]: students[j-1], students[j-2] = students[j-2], students[j-1]
for j in range( 4, 0, -1):
if studnets[j-1] < students[j-2]:
students[j-1], students[j-2] = students[j-2], students[j-1]
for j in range( 4, -1, -1): if studnets[j] < students[j-1]: students[j], students[j-1] = students[j-1], students[j]
for j in range( 4, -1, -1):
if studnets[j] < students[j-1]:
students[j], students[j-1] = students[j-1], students[j]
for j in range( 4, 0, -1): if studnets[j] < students[j-1]: students[j], students[j-1] = students[j-1], students[j]
for j in range( 5, 0, -1): if studnets[j] < students[j-1]: students[j], students[j-1] = students[j-1], students[j]
for j in range( 5, 0, -1):
Ο αλγόριθμος αυθείας ανταλλαγής, αν και θεωρείται από τους πιο αργούς αλγορίθμους ταξινόμησης, έχει ένα πολύ σημαντικό πλεονέκτημα: ότι μπορεί να τροποποιηθεί, ώστε να τερματίσει μόλις διαπιστώσει ότι η λίστα έχει ταξινομηθεί
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]
for j in range(N-1, 0, -1):
if A[j] < A[j-1]:
A[j], A[j-1] = A[j-1], A[j]
Αφού τα στοιχεία είναι N, τα περάσματα από την εξωτερική for θα πρέπει να είναι N και όχι N-1
Σε κάθε πέρασμα, το μικρότερο στοιχείο ταξινομείται. Άρα στην εσωτερική επανάληψη είναι περιττό το να συγκρίνουμε πάντα έως και το ήδη ταξινομημένο στοιχείο, δηλαδή έως και το στοιχείο 0
Δε μειονεκτεί σε τίποτα αφού είναι η βέλτιστη ταξινόμηση....τι να κάνουμε τώρα;
Ο αλγόριθμος ταξινόμησης ευθείας ανταλλαγής είναι γνωστός και ως αλγόριθμος ταξινόμησης φυσαλίδας γιατί σε κάθε πέρασμα το μικρότερο στοιχείο ανεβαίνει, όπως συμβαίνει και σε και μια φυσαλίδα, στην επιφάνεια του νερού
Η δυαδική αναζήτηση ισχύει για όλους τους τύπους δεδομένων για τους οποίους έχουμε ορίσει του συγκριτικούς τελεστές. Αυτό το χαρακτηριστικό ονομάζεται πολυμορφισμός και είναι από το βασικά πλεονεκτήματα της Python
Η αντιμετάθεση (αμοιβαία αλλαγή τιμών των μεταβλητών α, β) γίνεται στην Pyhton με την απλή εντολή:
a, b = b, a
Πως μπορεί να γίνει με επιπλέον μεταβλητή;
temp = a b = a b = temp
temp = a
b = a
b = temp
temp = b a = b a = temp
temp = b
a = b
a = temp
temp = a a = b b = temp
Ο παρακάτω αλγόριθμος βελτιστοποιεί την ταξινόμηση, ώστε όταν η λίστα ταξινομηθεί να μην κάνει άσκοπα περάσματα
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
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):
i + = 1
πόσα περάσματα θα γίνουν για τη λίστα [7, 8, 9, 12, 4, 5, 11] χρησιμοποιώντας τη βελτιστοποιημένη ταξινόμηση και πόσα άσκοπα θα γινόταν με τον απλό αλγόριθμο ταξινόμησης;
2 περάσματα με το βελτιστοποιημένο αλγόριθμο ταξινόμησης και Ν-1 = 7 - 1 = 6 συνολικά περάσματα ή 6 - 2 = 4 άσκοπα περάσματα με τον απλό αλγόριθμο
4 περάσματα με το βελτιστοποιημένο αλγόριθμο ταξινόμησης και Ν-1 = 7 - 1 = 6 συνολικά περάσματα ή 6 - 4 = 2 άσκοπα περάσματα με τον απλό αλγόριθμο
3 περάσματα με το βελτιστοποιημένο αλγόριθμο ταξινόμησης και Ν-1 = 7 - 1 = 6 συνολικά περάσματα ή 6 - 3 = 3 άσκοπα περάσματα με τον απλό αλγόριθμο
Τι θα εμφανίσει το παρακάτω πρόγραμμα;
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)
def check_D(mylist):
d = True
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)
True
False
None
[2, 4, 12, 20]
Τι θα συμβεί στο παρακάτω τμήμα αλγορίθμου;
students = ['Δημήτρης', 'Ευγενία', 'Ναταλία', 'Ρένια', 'Αλέξανδρος'] if students[4] < students[3]: students[4], students[3] = students[3], students[4]
students = ['Δημήτρης', 'Ευγενία', 'Ναταλία', 'Ρένια', 'Αλέξανδρος']
Η λίστα θα γίνει:
['Δημήτρης', 'Ευγενία', 'Ναταλία', 'Αλέξανδρος', 'Ρένια']
Θα γίνει αύξουσα ταξινόμηση όλης της λίστας:
['Δημήτρης', 'Ευγενία', 'Ρένια', 'Ναταλία', 'Αλέξανδρος']
temp = a a = b a = temp
temp = b b = a a = temp
temp = a b = a a = temp
Για την παρακάρω λίστα με 7 αριθμούς ποια θα είναι η τιμή της λίστας μετά από τρία περάσματα, αν χρησιμοποιήσουμε τον αλγόριθμο της αύξουσας ταξινόμησης (φυσαλίδα);
[55, 34, 5, 3, 2, 1, 1]
[1, 1, 55, 34, 5, 3, 2]
[1, 2, 3, 55, 34, 5, 1]
[1, 1, 2, 55, 34, 5, 3]