Άσκηση 9, σελ. 120, οδηγίες μελέτη μαθητή

Ξεκίνησε από gergerman, 20 Φεβ 2020, 05:36:59 ΜΜ

« προηγούμενο - επόμενο »

gergerman

Στην άσκηση 9, σελ. 120, ερώτημα3, τι θέλει να πει ο ποιητής;  Να γίνουν αυτά που ζητάει για τις ημερομηνίες του πίνακα που βρίσκονται εντός των 2 ημερομηνιών που διαβάζονται;
Μήπως μπορεί κάποιος να ανεβάσει κάποια λύση;

ολγα

#1
Προφανώς. (συμπεριλαμβανομένων και αυτών των ημερομηνιών αν υπάρχουν). Λύνεται με Όσο για να εκμεταλλευτούμε και το γεγονός ότι οι πίνακες είναι ταξινομημένοι. Προχωράμε μέχρι να βρούμε στους πίνακες ημερομηνία >= από την 1η ημερομηνία. Στη συνέχεια  κάνουμε αυτά που ζητάει και προχωράμε μέχρι να βρούμε ημερομηνία > από τη 2η ημερομηνία ή όταν εξαντλήσουμε τον πίνακα, οπότε σταματάμε. Όταν μπορέσω  θα ανεβάσω τη λύση.

ολγα

sum<-0
ΔΙΑΒΑΣΕ η1, μ1
ΔΙΑΒΑΣΕ η2, μ2
ΚΑΛΕΣΕ ΕΛΕΓΧΟΣ_ΗΜΕΡΟΜΗΝΙΑΣ (η1,μ1,η2,μ2)
flag <- ΨΕΥΔΗΣ
ι <- 1
ΟΣΟ flag = ΨΕΥΔΗΣ ΚΑΙ i <= 500 ΕΠΑΝΑΛΑΒΕ
    ΑΝ μ1 > Μήνα [ι] Η μ1 = Μήνα[ι]ΚΑΙ η1 > Ημέρα[ι] ΤΟΤΕ
          i <- i + 1
    ΑΛΛΙΩΣ
         ΑΝ μ2 > Μήνα[ι] Η μ2 = Μήνα[ι] ΚΑΙ η2 >= Ημέρα[ι] ΤΟΤΕ
              ΓΡΑΨΕ Περιγραφή[ι],Kόστος[ι]
              sum<sum+Kόστος[ι]
              ι <-ι + 1
         ΑΛΛΙΩΣ
              flag <- ΑΛΗΘΗΣ
        ΤΕΛΟΣ_ΑΝ
    ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ sum

eleniletta

Συνάδελφοι καλησπέρα,
τι γίνεται στην περίπτωση όπου ο μήνας αλλάζει και συνεπώς η 2η τιμή της ημέρας ενδέχεται να είναι μικρότερη της 1ης; Ή θεωρούμε ότι δεν υπάρχει τέτοια περίπτωση ως παραδοχή γιατί νομίζω ότι γίνεται ιδιαίτερα περίπλοκο μετά;

Ευχαριστώ

Επίσης έχει ασχοληθεί κάποιος με την επόμενη άσκηση ( σελ 121);

Ελένη

akalest0s

Για την άσκηση 10/121 (οδηγίες μελέτης), εδώ μια δική μου λύση:
Κώδικας: javascript
ΠΡΟΓΡΑΜΜΑ οδμελ121_10
ΣΤΑΘΕΡΕΣ
  Μ = 500
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: επιλογή, ν, θ
  ΧΑΡΑΚΤΗΡΕΣ: ΤΚ[Μ, 3] 
ΑΡΧΗ
  ν <- 0
  ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
    ΓΡΑΨΕ '1.Εισαγωγή νέου συνδρομητή'
    ΓΡΑΨΕ '2.Διαγραφή συνδρομητή'
    ΓΡΑΨΕ '3.Διόρθωση δεδομένων συνδρομητή'
    ΓΡΑΨΕ '4.Αναζήτηση συνδρομητή'
    ΓΡΑΨΕ '5.Εμφάνιση Τηλεφωνικού Καταλόγου'
    ΓΡΑΨΕ '6.Έξοδος'
    ΔΙΑΒΑΣΕ επιλογή
    ΑΝ επιλογή = 1 ΤΟΤΕ
      ΚΑΛΕΣΕ εισαγωγή(ΤΚ, ν) 
    ΑΛΛΙΩΣ_ΑΝ επιλογή = 2 ΤΟΤΕ
      ΚΑΛΕΣΕ διαγραφή(ΤΚ, ν) 
    ΑΛΛΙΩΣ_ΑΝ επιλογή = 3 ΤΟΤΕ
      ΚΑΛΕΣΕ διόρθωση(ΤΚ, ν) 
    ΑΛΛΙΩΣ_ΑΝ επιλογή = 4 ΤΟΤΕ
      ΚΑΛΕΣΕ αναζήτηση(ΤΚ, ν, θ) 
    ΑΛΛΙΩΣ_ΑΝ επιλογή = 5 ΤΟΤΕ
      ΚΑΛΕΣΕ εμφάνιση(ΤΚ, ν) 
    ΑΛΛΙΩΣ_ΑΝ επιλογή = 6 ΤΟΤΕ
      ΓΡΑΨΕ 'τερματισμός προγράματος...'
    ΤΕΛΟΣ_ΑΝ
  ΜΕΧΡΙΣ_ΟΤΟΥ επιλογή = 6
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
!=================================================       1
ΔΙΑΔΙΚΑΣΙΑ εισαγωγή(ΤΚ, ν) 
ΣΤΑΘΕΡΕΣ
  Μ = 500
ΜΕΤΑΒΛΗΤΕΣ
  ΧΑΡΑΚΤΗΡΕΣ: ΤΚ[Μ, 3], α, β, γ
  ΑΚΕΡΑΙΕΣ: ν, ι, ξ
ΑΡΧΗ
  ΑΝ ν < Μ ΤΟΤΕ
    ΓΡΑΨΕ 'Δώσε όνομα, διεύθυνση, τηλέφωνο'
    ΔΙΑΒΑΣΕ α, β, γ

    ν <- ν + 1
    ΤΚ[ν, 1] <- α
    ΤΚ[ν, 2] <- β
    ΤΚ[ν, 3] <- γ
 ! bubblesort
    ΓΙΑ ι ΑΠΟ 2 ΜΕΧΡΙ ν
      ΓΙΑ ξ ΑΠΟ ν ΜΕΧΡΙ ι ΜΕ_ΒΗΜΑ -1
        ΑΝ ΤΚ[ξ, 1] < ΤΚ[ξ - 1, 1] ΤΟΤΕ
          ΚΑΛΕΣΕ αντι(ΤΚ[ξ, 1], ΤΚ[ξ - 1, 1]) 
          ΚΑΛΕΣΕ αντι(ΤΚ[ξ, 2], ΤΚ[ξ - 1, 2]) 
          ΚΑΛΕΣΕ αντι(ΤΚ[ξ, 3], ΤΚ[ξ - 1, 3]) 
        ΤΕΛΟΣ_ΑΝ
      ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'πίνακας ήδη γεμάτος'
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
!=================================================       2
ΔΙΑΔΙΚΑΣΙΑ διαγραφή (ΤΚ, ν) 
ΣΤΑΘΕΡΕΣ
  Μ = 500
ΜΕΤΑΒΛΗΤΕΣ
  ΧΑΡΑΚΤΗΡΕΣ: ΤΚ[Μ, 3] 
  ΑΚΕΡΑΙΕΣ: ν, ι, θ
ΑΡΧΗ

  ΚΑΛΕΣΕ αναζήτηση(ΤΚ, ν, θ) 
  ΑΝ θ = 0 ΤΟΤΕ
    ΓΡΑΨΕ 'δεν βρέθηκε ο συνδρομητής'
  ΑΛΛΙΩΣ
    ΤΚ[θ, 1] <- " "
    ΤΚ[θ, 2] <- " "
    ΤΚ[θ, 3] <- " "
    ΓΙΑ ι ΑΠΟ θ ΜΕΧΡΙ ν - 1
      ΚΑΛΕΣΕ αντι(ΤΚ[ι, 1], ΤΚ[ι + 1, 1]) 
      ΚΑΛΕΣΕ αντι(ΤΚ[ι, 2], ΤΚ[ι + 1, 2]) 
      ΚΑΛΕΣΕ αντι(ΤΚ[ι, 3], ΤΚ[ι + 1, 3]) 
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    ν <- ν - 1
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
!=================================================       3
ΔΙΑΔΙΚΑΣΙΑ διόρθωση (ΤΚ, ν) 
ΣΤΑΘΕΡΕΣ
  Μ = 500
ΜΕΤΑΒΛΗΤΕΣ
  ΧΑΡΑΚΤΗΡΕΣ: ΤΚ[Μ, 3], α, β, γ
  ΑΚΕΡΑΙΕΣ: ν, επιλογή, θ
ΑΡΧΗ
  ΓΡΑΨΕ 'Δώσε όνομα ή τηλέφωνο προς διόρθωση'
  ΚΑΛΕΣΕ αναζήτηση(ΤΚ, ν, θ) 
  ΑΝ θ = 0 ΤΟΤΕ
    ΓΡΑΨΕ 'δεν βρέθηκε ο συνδρομητής'
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'δώσε τα νέα στοιχεία: όνομα, διεύθυνση, τηλέφωνο'
    ΔΙΑΒΑΣΕ α, β, γ
    ΤΚ[θ, 1] <- α
    ΤΚ[θ, 2] <- β
    ΤΚ[θ, 3] <- γ
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
!=================================================       4
ΔΙΑΔΙΚΑΣΙΑ αναζήτηση(ΤΚ, ν, θ) 
ΣΤΑΘΕΡΕΣ
  Μ = 500
ΜΕΤΑΒΛΗΤΕΣ
  ΧΑΡΑΚΤΗΡΕΣ: ΤΚ[Μ, 3], κλειδί
  ΑΚΕΡΑΙΕΣ: ν, επιλογή, αρχ, τελ, μέση, θ
  ΛΟΓΙΚΕΣ: φλαγ
ΑΡΧΗ
  ΓΡΑΨΕ 'Τι θέλετε να δώσετε; 1 για όνομα, 3 για τηλέφωνο'
  ΔΙΑΒΑΣΕ επιλογή
  ΔΙΑΒΑΣΕ κλειδί

  αρχ <- 1
  τελ <- ν
  φλαγ <- ΨΕΥΔΗΣ
  θ <- 0
  ΟΣΟ φλαγ = ΨΕΥΔΗΣ ΚΑΙ αρχ <= τελ ΕΠΑΝΑΛΑΒΕ
    μέση <- (αρχ + τελ) div 2
    ΑΝ ΤΚ[μέση, επιλογή] = κλειδί ΤΟΤΕ
      φλαγ <- ΑΛΗΘΗΣ
      θ <- μέση
    ΑΛΛΙΩΣ_ΑΝ ΤΚ[μέση, επιλογή] < κλειδί ΤΟΤΕ
      αρχ <- μέση + 1
    ΑΛΛΙΩΣ
      τελ <- μέση - 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
!=================================================       5
ΔΙΑΔΙΚΑΣΙΑ εμφάνιση(ΤΚ, ν) 
ΣΤΑΘΕΡΕΣ
  Μ = 500
ΜΕΤΑΒΛΗΤΕΣ
  ΧΑΡΑΚΤΗΡΕΣ: ΤΚ[Μ, 3] 
  ΑΚΕΡΑΙΕΣ: ν, ι, ξ
ΑΡΧΗ
  ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ ν
    ΓΙΑ ξ ΑΠΟ 1 ΜΕΧΡΙ 3
      ΓΡΑΨΕ ΤΚ[ι, ξ] 
    ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
!=================================================       Ε
ΔΙΑΔΙΚΑΣΙΑ αντι(x, y) 
ΜΕΤΑΒΛΗΤΕΣ
  ΧΑΡΑΚΤΗΡΕΣ: x, y, temp
  ΑΚΕΡΑΙΕΣ: ω
ΑΡΧΗ
  temp <- x
  x <- y
  y <- temp
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

Σημειωτέον ότι η λύση αυτή είναι μάλλον σε πειραγμένη/βελτιωμένη εκφώνηση, αν θυμάμαι καλά του Θ. Δρίβα:
ΠαράθεσηΝα γραφεί πρόγραμμα σε «ΓΛΩΣΣΑ» το οποίο να διαχειρίζεται πίνακα Τηλεφωνικού Καταλόγου 500 γραμμών, με 1η στήλη το Ονοματεπώνυμο, 2η στήλη την Διεύθυνση και 3η στήλη το Τηλέφωνο. Η διαχείριση γίνεται βάση του παρακάτω Μενού επιλογών:
1. Εισαγωγή νέου συνδρομητή  (αρχικά ο πίνακας είναι άδειος. Η εισαγωγή κάθε νέου συνδρομητή, γίνεται με διαδοχικές κλήσεις της συγκεκριμένης διαδικασίας. Η διαδικασία δέχεται και επιστρέφει τον πίνακα του καταλόγου και ένα δείκτη ν που δείχνει μέχρι ποια γραμμή έχει στοιχεία ο κατάλογος.)
2. Διαγραφή συνδρομητή  (Θα πρέπει η διαδικασία που καλείται, να διαβάζει ένα όνομα συνδρομητή ή το τηλέφωνό του, να γίνεται αναζήτηση, καλώντας την διαδικασία 4 και στη συνέχεια να διαγράφεται η συγκεκριμένη γραμμή συνδρομητή και να γεμίζει τα κενά που δημιουργούνται μετατοπίζοντας όλα τα επόμενα στοιχεία μια γραμμή πάνω στον πίνακα. Οι τιμές που περισσεύουν στο τέλος του πίνακα να γεμίζουν με κενά (πάλι δέχεται και επιστρέφει ΚΑΤ,ν))
3. Διόρθωση δεδομένων συνδρομητή (η διαδικασία θα διαβάζει όνομα ή τηλέφωνο και θα τα αναζητάει καλώντας την διαδικασία 4. Στη συνέχεια θα διαβάζει και τα 3 στοιχεία (όνομα, διεύθυνση, τηλέφωνο) και θα αντικαθιστά τα παλιά και θα επιστρέφει τον πίνακα.) (πάλι δέχεται και επιστρέφει ΚΑΤ,ν)
4. Αναζήτηση συνδρομητή (Με Όνομα ή Τηλέφωνο) (Η διαδικασία δέχεται τον πίνακα ΚΑΤ, τον δείκτη ν και διαβάζει όνομα ή τηλέφωνο μετά από ερώτηση: "Τι θέλετε να δώσετε; 1 για όνομα, 2 για τηλέφωνο" κάνει αναζήτηση και επιστρέφει τη θέση της γραμμής στην οποία υπάρχουν τα στοιχεία.)
5. Εμφάνιση Τηλεφωνικού Καταλόγου  (θα εμφανίζει απλά όλα τα στοιχεία του τηλεφωνικού καταλόγου)
6. Έξοδος
ΕΠΙΛΟΓΗ: ___
Η κάθε επιλογή αποτελεί ξεχωριστό υποπρόγραμμα.
Στην περίπτωση που έχει γεμίσει ο πίνακας να εμφανίζεται κατάλληλο μήνυμα

Εναλλακτικά, υπάρχουν διαθέσιμες και οι λύσεις του Παναγιώτη:
https://alkisg.mysch.gr/steki/index.php?topic=7987.msg88076#msg88076

Παράθεση από: eleniletta στις 24 Φεβ 2020, 10:03:58 ΜΜ
Συνάδελφοι καλησπέρα,
τι γίνεται στην περίπτωση όπου ο μήνας αλλάζει και συνεπώς η 2η τιμή της ημέρας ενδέχεται να είναι μικρότερη της 1ης; Ή θεωρούμε ότι δεν υπάρχει τέτοια περίπτωση ως παραδοχή γιατί νομίζω ότι γίνεται ιδιαίτερα περίπλοκο μετά;
Σε ποιο ακριβώς αναφέρεσαι, όταν λες ότι ο μήνας αλλάζει; Στο 2ο ή στο 3ο ερώτημα;

Αν σε βοηθάει, ρίξε μια ματιά και εδώ:
https://alkisg.mysch.gr/steki/index.php?topic=7010.msg88974#msg88974
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

bugman

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

eleniletta

Εννοώ την περίπτωση όπου δοθεί διάστημα ημερομηνιών π.χ. 20-4 έως 5-5. Εδώ δεν είναι λανθασμένη η περίπτωση η2<η1 για να γίνει η αντιμετάθεση

Ευχαριστώ

akalest0s

Η αντιμετάθεση της ταξινόμησης, θα γίνει σε στυλ
"Αν μήνας1 > μήνας2 Τότε
   αντιμετάθεσε
Αλλιώς_Αν μήνας1 = μήνας2 Τότε
   ΑΝ ημέρα1 > ημέρα2 Τότε
        αντιμετάθεσε"

Δηλαδή ασχολείσαι με τις ημέρες, αφού πρώτα έχεις ασχοληθεί με τους μήνες, και εφόσον έτυχε ίδιος μήνας σε δύο ημερομηνίες.
Δεν σε ενδιαφέρει το η2<η1, παρά μόνο αν μήνας2=μήνας1.
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

eleniletta

Ευχαριστώ συνάδελφε, τελικά δηλαδή αν μια δοθείσα ημερομηνία είναι φαινομενικά σωστή, εμείς τις αντιμεταθέτουμε σε λανθασμένη για να τηρείται το η1<η2.

Ευχαριστώ και πάλι

akalest0s

Δεν είμαι σίγουρος τι εννοείς "φαινομενικά σωστή και λάθος" ημερομηνία.
Οι μήνες και οι ημέρες αποθηκεύονται σε παράλληλους πίνακες. Αυτό σημαίνει, ότι για κάθε ι, τα περιεχόμενα Μ[ι] και H[ι] σου δίνουν τον μήνα και την ημέρα, κάθε ημερομηνίας που έδωσε ο χρήστης. Θέλει προσοχή πως διαβάζεις τους πίνακες, να γίνει σωστά η εισαγωγή. Σε αυτό το σημείο (του ποια μορφή έχει η ημερομηνία που εισάγει ο χρήστης) η εκφώνηση είναι ασαφής, όπως μπορείς να διαπιστώσεις από τις παλιότερες κουβέντες.

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

Ελπίζω μάλλον να βοήθησα παρά να σε μπέρδεψα χειρότερα.  :angel: Είναι μια τυπική περίπτωση ταξινόμησης σε παράλληλους πίνακες, όπου λαμβάνουμε υπόψιν την περίπτωση "ισοβαθμίας" στον πίνακα βάσει του οποίου ταξινομούμε. Δες και τη λύση στις λύσεις του Παναγιώτη, που παρέθεσα νωρίτερα ("πρόγραμμα δαπάνες").
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK

eleniletta

ευχαριστώ θερμά! Και βέβαια βοήθησες.

ολγα

Παράθεση από: akalest0s στις 25 Φεβ 2020, 09:57:47 ΠΜ
Η αντιμετάθεση της ταξινόμησης, θα γίνει σε στυλ
"Αν μήνας1 > μήνας2 Τότε
   αντιμετάθεσε
Αλλιώς_Αν μήνας1 = μήνας2 Τότε
   ΑΝ ημέρα1 > ημέρα2 Τότε
        αντιμετάθεσε"

ή (το ίδιο) πιο σύντομα:

Αν μήνας1 > μήνας2 ή μήνας1 = μήνας2 και ημέρα1 > ημέρα2 Τότε
        αντιμετάθεσε

ολγα

Παράθεση από: akalest0s στις 24 Φεβ 2020, 11:00:09 ΜΜ
Για την άσκηση 10/121 (οδηγίες μελέτης), εδώ μια δική μου λύση:

Μήπως θα βόλευε γι'αυτή ένα καινούριο θέμα γιατί εδώ μιλάμε για την άσκηση 9;

ολγα

#13
Παράθεση από: akalest0s στις 24 Φεβ 2020, 11:00:09 ΜΜ
Για την άσκηση 10/121 (οδηγίες μελέτης), εδώ μια δική μου λύση:
Αν επιτρέπεται δυο παρατηρήσεις:

1. μια βελτίωση για τη ΔΙΑΔΙΚΑΣΙΑ εισαγωγή(ΤΚ, ν)

Αν θέλουμε ο πίνακας να είναι ταξινομημένος (δεν απαιτείται από την εκφώνηση του βιβλίου, αλλά έστω ότι έτσι θέλουμε) αυτό που θα έπρεπε να κάνει η "εισαγωγή" θα ήταν να εισάγει το νέο συνδρομητή στη σωστή γραμμή του ταξινομημένου πίνακα μεταφέροντας τους συνδρομητές που πρέπει (αυτούς με όνομα μεγαλύτερο του ονόματος του συνδρομητή που θέλουμε να εισάγουμε) μία γραμμή προς τα κάτω (με σκεπτικό παρόμοιο με αυτό της ταξινόμησης ευθείας εισαγωγής) Αυτό έχει πολυπλοκότητα Ο(ν) και λύνεται με ένα ΟΣΟ.
Διαφορετικά έχουμε Ο(ν2)

2.Στη ΔΙΑΔΙΚΑΣΙΑ αναζήτηση(ΤΚ, ν, θ)
Δε μπορεί να γίνει δυαδική αναζήτηση στα τηλέφωνα γιατί δεν είναι ταξινομημένα.

bugman

Με ενα δεύτερο πίνακα, θα κρατούσαμε μια δεύτερη ταξινόμηση στα τηλέφωνα.

akalest0s

Παράθεση από: ολγα στις 26 Φεβ 2020, 06:00:08 ΜΜ
Αν επιτρέπεται δυο παρατηρήσεις:

1. μια βελτίωση για τη ΔΙΑΔΙΚΑΣΙΑ εισαγωγή(ΤΚ, ν)

Αν θέλουμε ο πίνακας να είναι ταξινομημένος (δεν απαιτείται από την εκφώνηση του βιβλίου, αλλά έστω ότι έτσι θέλουμε) αυτό που θα έπρεπε να κάνει η "εισαγωγή" θα ήταν να εισάγει το νέο συνδρομητή στη σωστή γραμμή του ταξινομημένου πίνακα μεταφέροντας τους συνδρομητές που πρέπει (αυτούς με όνομα μεγαλύτερο του ονόματος του συνδρομητή που θέλουμε να εισάγουμε) μία γραμμή προς τα κάτω (με σκεπτικό παρόμοιο με αυτό της ταξινόμησης ευθείας εισαγωγής) Αυτό έχει πολυπλοκότητα Ο(ν) και λύνεται με ένα ΟΣΟ.
Διαφορετικά έχουμε Ο(ν2)

2.Στη ΔΙΑΔΙΚΑΣΙΑ αναζήτηση(ΤΚ, ν, θ)
Δε μπορεί να γίνει δυαδική αναζήτηση στα τηλέφωνα γιατί δεν είναι ταξινομημένα.
1. Σύμφωνοι, αν και η πολυπλοκότητα είναι εκτός.
2. Προφανώς ήταν δική μου απροσεξία. Κάνεις μια σειριακή και οκ.
"Abstraction is not the first stage, but the last stage, in a mathematical development." MK
"I don't want to write about a high level thing, unless I fully understand about a low level thing" DK