και ναι και όχι... υπολογιστικό βήμα είναι κάθε πράξη που εκτελείται από τον υπολογιστή και έχει ως συνέπεια δέσμευση κάποιας θέσης μνήμης ή αλλαγή περιεχομένου της θέσης μνήμης ή εκτέλεση κάποιας πράξης. Η σειρά π.χ. a:=b+c μπορεί να θεωρηθεί ως ένα υπολογιστικό βήμα, ενώ η σειρά end if δεν είναι υπολογιστικό βήμα.
ΠαράδειγμαΥπολογιστικά βήματα είναι τα: a := 5; (δέσμευση)
i = i+1; (αλλαγή περιεχομένου)
if (a > b) (η σύγκριση είναι πράξη που δίνει true/false)
a := b + c; (εκτέλεση πράξης και αποθήκευση αποτελέσματος)
κτλ
Υπολογιστικά βήματα δεν είναι τα:end if;
repeat N times (το περιεχόμενό του υπολογίζεται ξεχωριστά) (**)
end repeat;
do; (Μιλάω για το do...while) (**)
end do; (Εννοώ το end do που κλείνει το do_while) (**)
print (a); (*)
κτλ.
(*) Προσοχή:
Το print (a+b) (ή οποιαδήποτε άλλη παράσταση) είναι υπολογιστικό βήμα αφού πρέπει να υπολογίσει πρώτα το a+b, να το αποθηκεύσει (προσωρινά) κάπου και στη συνέχεια να το τυπώσει.
(**) Το do...while και το do_while τα αναλύω παρακάτω:
Ειδική Περίπτωση Isum := 0;
do while(sum >= 2)
.....sum := sum+1
end do
Αριθμός βημάτων:
1. sum := 0; (sum = 0)
2. Έλεγχος sum >= 2; (Λάθος)
3. sum := sum+1; (sum = 1)
4. Έλεγχος sum >=2; (Λάθος)
5. sum := sum+1; (sum = 2)
6. Έλεγχος sum >= 2; (Σωστό)
Τέλος: 6 Βήματα
Ειδική Περίπτωση IΙsum := 0;
do
.....sum := sum+1
while (sum >= 2);
Αριθμός βημάτων:
1. sum := 0; (sum = 0)
2. sum := sum+1; (sum = 1)
3. Έλεγχος sum >=2; (Λάθος)
4. sum := sum+1; (sum = 2)
5. Έλεγχος sum >= 2; (Σωστό)
Τέλος: 5 Βήματα
Ειδική Περίπτωση IIIsum := 0
.....repeat 2 times
sum := sum +1;
end repeat
Αριθμός βημάτων:
1. sum := 0; (sum = 0)
2. sum := sum+1; (sum = 1)
3. sum := sum+1; (sum = 2)
Τέλος: 3 Βήματα
Στη πραγματικότητα υπάρχει ένας "αόρατος" μετρητής που μετράει το πόσες επαναλήψεις έχουν γίνει, αλλά δε το θεωρούμε ως ένα υπολογιστικό βήμα κάθε φορά που αυτός αυξάνει κατά το βήμα της επανάληψης.
---
Με αυτό το παράδειγμα ελπίζω να καταλάβατε 2 πράγματα:
1. Το πως υπολογίζουμε τα υπολογιστικά βήματα στις 3 περιπτώσεις βρόγχου (αν και δε νομίζω να σας χρειαστεί στο πρόγραμμα που θα πρέπει να γράψετε, εκτός ίσως από το III)
2. Τη διαφορά της do_while (Ι) με τη do...while (ΙΙ). Η dο...while θα εκτελέσει τουλάχιστον μια επανάληψη ενώ η do_while όχι απαραίτητα (αν π.χ. δώσουμε στην αρχή sum := 2) δε θα μπει ποτέ στο βρόγχο της do_while ενώ θα μπει στο βρόγχο της do...while και θα εκτελέσει μόνο μια φορά μια επανάληψη.
Γενικά σε ένα πολύπλοκο πρόγραμμα είναι αδύνατον να υπολογίσουμε τα υπολογιστικά του βήματα με συγκεκριμένο αριθμό, χρησιμοποιούμε συναρτήσεις [Συνήθως της μορφής: πολυωνύμου ή εκθετικές* ή nLogn (λογάριθμος του 2)] για να περιγράψουμε τη
πολυπλοκότητα του προγράμματος. Οπότε αυτό που θα σας ζητηθεί θα είναι μάλλον κάτι εξαιρετικά απλό εφόσον ζητάει συγκεκριμένο αριθμό βημάτων, μην αγχώνεστε ;)
(*): Ένα πρόγραμμα με εκθετική συνάρτηση πολυπλοκότητας δεν είναι
εφικτό από τους σημερινούς υπολογιστές. :P
---
Μια και αναφέρθηκα σε πράξεις να υπενθυμίσω ότι για ψευδοκώδικα (και για τις περισσότερες γλώσσες προγραμματισμού) ισχύει το εξης:
ακέραιος / ακέραιος = ακέραιος
Παραδείγματα:6/5 = 1
5/8 = 0
10/6 = 1
(Ακόμα και αν το αποτέλεσμα της διαίρεσης είναι 1,99999... θα έχουμε έξοδο 1 αφού χάνεται το δεκαδικό μέρος για να μετατραπεί σε ακέραιο)
ακέραιος / πραγματικός = πραγματικός
πραγματικός / ακέραιος = πραγματικός
πραγματικός / πραγματικός = πραγματικός
Παραδείγματα:9,2/4,5 = 2,044
5/2,5 = 2,0
9/2,0 = 4,5 (*)
(*) Προσοχή: Το 2,0 θεωρείται πραγματικός (float ή real) και το 2 ακέραιος (integer)
~~~
Αυτά τα πρόχειρα προς το παρόν, ελπίζω να σας καλύψω με το e-book που ετοιμάζω με τη νέα χρονιά ;)
Επειδή δε μπορώ να κάνω edit μια μικρή συμπλήρωση:
Είπα πως το a := b+c; μπορεί να θεωρηθεί ως ένα υπολογιστικό βήμα (το οποίο αποτελείται από ουσιαστικά από 2 στοιχειώδεις πράξεις: πρόσθεση b+c και αποθήκευση στο a).
Κατ' επέκταση μπορούμε να θεωρήσουμε
τμήματα παρόμοιου κώδικα ως
ένα υπολογιστικό βήμα
Το ποιο χαρακτηριστικό παράδειγμα είναι το εξής:
repeat N times
.....Κ εντολές;
end repeat;
N υπολογιστικά βήματα τα οποία αποτελούνται από Κ εντολές οι οποίες μπορούν να αναλυθούν σε Ζ στοιχειώδεις πράξεις.
Επίσης
if συνθήκη then
.....Χ εντολές
else
.....Υ εντολές
end if
μπορεί όλο αυτό το τμήμα να θεωρηθεί ως ένα υπολογιστικό βήμα το οποίο αποτελείται από Χ εντολές αν η συνθήκη είναι true ή Υ εντολές αν η συνθήκη είναι false.
Επομένως μπορούμε να ομαδοποιήσουμε τον έλεγχο στις εντολές Do_while και do...while μαζί με τις εντολές του βρόγχου σε 1 υπολογιστικό βήμα. Επομένως με αυτή τη λογική:
sum := 0;
do while(sum >= 2)
.....sum := sum+1
end do
sum := 0;
do
.....sum := sum+1
while (sum >= 2);
3 βήματα και τα δύο.
Start Program Paradeigma
a := a/b;
a := a/c;
a := a + c*b;
print(a)
End Program Paradeigma
Αυτές οι πράξεις δεν έχουν καμιά σχέση μεταξύ τους, δεν υπάγονται σε κανένα κοινό block εντολών κάποιου if/do_while/repeat κτλ. επομένως είναι 3 υπολογιστικά βήματα (το print(a) δεν υπολογίζεται ως βήμα όπως έχουμε πει).
Τέλος ένα γενικό παράδειγμα:
Start Program
integer a,b;
a := 1;
b := 3;
if((a+b)>5)
.....a := 10
.....repeat 2 times
..........print(a);
.....end repeat;
else
.....repeat 3 times
..........b := b+1;
..........b := b-a;
.....end repeat;
end if
End Program
a := 1; (1o)
b := 3; (2o)
if((a+b)>5) (3o)
Αν είναι true τότε: a := 10 (+1 υπολογιστικό βήμα)
Αν είναι false τότε: repeat 3 times (+3 υπολογιστικά βήματα που αποτελούνται από 2 επιμέρους εντολές)
Άρα μπορούμε να έχουμε από 4 έως 7 υπολογιστικά βήματα.
Συνήθως τη παραπάνω λογική ακολουθεί ο Γραββάνης όταν λέει υπολογιστικό βήμα και όχι την αναλυτική που έκανα εγώ στο προηγούμενο post. Απλά το έκανα τόσο αναλυτικά για να καταλάβετε τη διαφορά μεταξύ do_while και do...while
Τελευταία επεξεργασία από Stokos και 15 Σεπ 2008, 15:27, έχει επεξεργασθεί 1 φορά/ες συνολικά