Χαριτάκης Γιάννης

Θεωρία

Από το βιβλίο μας, η δυαδική αναζήτηση βρίσκεται στην σελίδα 69 μέχρι 72.

sort1

Ασκήσεις

1.

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

Αν χρησιμοποιήσουμε για την ίδια λίστα δυαδική αναζήτηση, τότε πόσες συγκρίσεις θα γίνουν στην χειρότερη περίπτωση;

2.

Ποιά είναι η διαφορά της randint() από την randrange(); Βρείτε την απάντηση στο βήμα 1 της σελίδας 64 του βιβλίου μας (Δραστηριότητα : Μάντεψε τον αριθμό)

3.

Γράψτε πρόγραμμα που :

α) Να χρησιμοποιεί την randint() ή την randrange()  για να γεμίζει μία λίστα (append()) με 1000 τυχαίους αριθμούς από το 1 μέχρι το 10.000.

β) Να ταξινομεί τον πίνακα με τον αλγόριθμο φυσαλλίδας.

γ) Να εμφανίζει τον ταξινομημένο πίνακα στην οθόνη

δ) Να ζητάει από τον χρήστη ένα νούμερο

ε) Να αναζητάει με δυαδιακή αναζήτηση το νούμερο στην λίστα και να επιστρέφει την θέση του ή το μύνημα δεν βρέθηκε.

Θεωρία

Από το βιβλίο μας : παράγραφος 5.1 από σελίδα 69 μέχρι και 72.

sort1

Άσκηση

Αν έχουμε τον πίνακα:

n = [12, 15, 17, 23, 25, 28, 41, 54, 63, 68, 83, 100, 105, 123]

Γράψτε ποιές συγκρίσεις θα γίνουν όταν ψάχνουμε με δυαδική αναζήτηση:

1. Το νούμερο 41
2. Το νούμερο 83
3. Το νούμερο 15
4. Το νούμερο 170
5. Το νούμερο 11

Βοηθητικό βίντεο . (είναι για άλλη γλώσσα, αλλά η ιδέα είναι η ίδια.)

Θεωρία

Από το βιβλίο μας ολοκληρώσαμε την ταξινόμηση ευθείας ανταλλαγής.

Κάναμε τις σελίδες 73 έως 78 κλείνοντας την παράγραφο 5.2

Ασκήσεις

Πρώτη άσκηση

Γράψτε σε χαρτί τον αλγόριθμο που ταξινομεί σε αύξουσα σειρά μία λίστα L.

Δεύτερη άσκηση

Γράψτε πρόγραμμα που:

1. Δέχεται ονόματα μέχρι να γράψουμε “TELOS”
2. Βάζει κάθε όνομα σε μία λίστα ONOMATA
3. Ταξινομεί την λίστα με αύξουσα σειρα
4. Εμφανίζει την ταξινομημένη  λίστα

Τρίτη άσκηση

Αλλάξτε το προηγούμενο πρόγραμμα ώστε να ταξινομεί τα ONOMATA κατά φθίνουσα σειρά.

Τέταρτη άσκηση

Γράψτε πρόγραμμα που:

1. Δέχεται ονόματα μέχρι να γράψουμε “TELOS”
2. Βάζει κάθε όνομα σε μία λίστα ONOMATA
3. Για κάθε όνομα, δέχεται και έναν βαθμό
4. Τον βαθμό τον βάζει σε μία λίστα VATHMOI
5. Ταξινομεί την λίστα VATHMOI με αύξουσα σειρα
6. Εμφανίζει την ταξινομημένη  λίστα των βαθμών μαζί με τα ονόματα.