Recursive

ΠΡΌΒΛΗΜΑ ΙΙ

Δίνεται ο παρακάτω αναδρομικός αλγόριθμος:
procedure count(A, left, right, elem)
if left = right then
if A[left] = elem
return 1;
else return 0;
mid := [(left + right) / 2];
x := count(A, left, mid, elem);
y := count(A, mid + 1, right, elem);
return(x + y);

Η διαδικασία count(A, left, right, elem) δέχεται ως παραμέτρους τον πίνακα ακεραίων
A,  τους φυσικούς αριθμούς  left  και  right  και τον ακέραιο  elem  και επιστρέφει σαν
έξοδο  το  πλήθος των εμφανίσεων του ακεραίου  elem  στον  πίνακα  A  από τις θέσεις
left έως και right. Υποθέτουμε ότι ισχύει πάντοτε ότι left ≤ right. Αν ο πίνακας Α έχει
n  στοιχεία, η αρχική κλήση είναι    count  (A, 1,  n,  elem). Ο συμβολισμός  A[left]
δηλώνει το στοιχείο του πίνακα  A  στη θέση  left.  Η παράσταση  [(left  +  right) / 2]
δηλώνει το κάτω ακέραιο μέρος της διαίρεσης, π.χ. [(1+4)/2]=2.
1)  Έστω ότι Α = [4, 3, -4, 3, 1, -7, 0, -4, 3, 3, -6, 8 ].
a)  Να εκτελεστούν όλα τα βήματα της κλήσης  count  (A, 1, 12, 3) με είσοδο τον
πίνακα Α.
b)  Ποιο  είναι το βάθος της αναδρομής της κλήσης count(A, 1, 12, 3);


2)  Να αποδείξετε με επαγωγή ότι ο αλγόριθμος είναι σωστός, δηλαδή, η κλήση
count  (A, 1,  n,  elem)  υπολογίζει  το  πλήθος των εμφανίσεων του ακεραίου  elem
στον  πίνακα  Α[1…n].  Στη συνέχεια να υπολογίσετε το βάθος της αναδρομής της
κλήσης count (A, 1, n, elem) ως συνάρτηση του n.

--------------------------------------------------------------------ΛΎΣΗ------------------------
α.

Έχουμε   Α = [4, 3, -4, 3, 1, -7, 0, -4, 3, 3, -6, 8 ] και left=1 , right =12 και elem=3

Η συνάρτηση δέχεται τον πίνακα Α και τρεις αριθμούς left right και elem και βρίσκει πόσες φορές υπάρχει o αριθμός elem στον πίνακα A μέσα στα άκρα left και right του πίνακα.

Έχουμε left=1 και right=12 και elem=3. Ο Πινάκας Α έχει δώδεκα στοιχειά επομένως θα μετρήσουμε  το πλήθος  του αριθμού 3 που  υπάρχει  στον πίνακα Α, από το πρώτο στοιχείο του πίνακα έως τον δωδέκατο.

Η συνάρτηση count είναι αναδρομική και μπορούμε ν αναπαραστήσουμε κάθε κλήση της συνάρτησης με ένα ορθογώνιο σχήμα και μέσα στο σχήμα τις τιμές που έχει κάθε μεταβλητή. Ακόμα προσθέτουμε σε κάθε ορθογώνιο έναν αριθμό που εκφράζει την σειρά που κλήθηκε η συνάρτηση count. Η σειρά ολοκλήρωσης κάθε αναδρομικής ολοκληρώνεται αφού ολοκληρωθούν όλες οι κλήσεις που αυτή προκάλεσε , στην περίπτωση μας σταματήσει όταν left=right και επιστέφει 1 όταν το στοιχείο που ελέγχουμε στο πίνακα  είναι ισο με elem ή  0 εάν δεν ισχύει .

 Κάθε κλήση της συνάρτησης καλεί τον εαυτό  της δυο φόρες την πρώτη φόρα υπολογίζει το X από την θέση left του πίνακα έως το mid και την δεύτερη φορά  υπολογίζει το y από την θέση mid+1 έως right του πίνακα. Όλα αυτά γίνονται αφού oορίσαμε την mid=(left+right)/2. Δηλαδή η συνάρτηση count  η πρώτη κλήση της θα υπολογίσει το χ και y με το χ να υπολογίζει το αριστερό κομμάτι του πίνακα και το y το δεξί.  Τέλος πρέπει να αναφερθεί  ότι πρώτα υπολογίζει το χ και όταν τελειώσει  ο υπολογισμός ( δηλαδή οι αναδρομικές κλήσεις ) τότε θα ξεκινήσει να υπολογίσει το  y. Μετά τον υπολογισμό του χ και του y αθροίζει το x και y. Όλα τα παραπάνω μπορούμε να τα δούμε καλυτέρα  στο Διάγραμμα που ακολουθεί. To return είναι η έξοδος κάθε συνάρτησης (είναι  x+y)

Στο τέλος η συνάρτηση επιστρέφει 4 όσο και το πλήθος των «3» που είναι καταχωρημένα στον πίνακα Α.

b.
Το βάθος της αναδρομής είναι το μέγιστο πλήθος τον αναδρομικών κλήσεων που μπορούν να υπολογιστούν  από το διάγραμμα και είναι η  μεγίστη απόσταση απo  την ριζά  του δέντρου (στο διάγραμμα) ως το φύλλο. Βλέποντας το διάγραμμα η απόσταση είναι τέσσερα.
Κάθε φορά που καλούμε την συνάρτηση count αυτή εκτελείται
2 φόρες μια για να (υπολογίσει το x και μια το y) εμείς ζητάμε την

2.
Θα  εφαρμόσουμε ισχυρή μαθηματική επαγωγή  στο πλήθος των στοιχείων του πίνακα και του Υποπίνακα Α , δηλαδή  η συνάρτηση είναι Count (A, left, right , elem ) θα εφαρμόσουμε  ως προς το  n=right-left+1 που n είναι το πλήθος των στοιχείων του πίνακα (με left =1).
Βασικό βήμα: Για n=1 δηλαδή για left=right. Τότε η συνάρτηση count θα είναι Count (A,1,1 elem) και ισχύει η συνθήκη left =right  όπου ελέγχετε  εάν το στοιχείο είναι ισο με elem και αντίστοιχα θα επιστραφεί 1 η μηδέν ,δηλαδή σωστά ελέγχει το μοναδικό στοιχείο του πίνακα εαν είναι ισο με το elem για να μας επιστρέψει 1 εάν ισχύει η 0 εάν δεν ισχύει  . Επομένως ισχύει.
Επαγωγική υπόθεση: Θα υποθέσω ότι η συνάρτηση ισχύει για k με 1≤ k

Επαγωγικό Βήμα: Θα δείξουμε ότι η συνάρτηση count επιστέφει το πλήθος των στοιχείων ενός πίνακα Α από την θέση 1 έως την θέση k+1 του πίνακα Α.
Έχουμε ότι το κ είναι τουλάχιστον 2 και από το κώδικα της συνάρτησης count δεν θα εκτελέσει το if για τον έλεγχο του μοναδικού στοιχείου αλλά θα προχωρήσει στις κάτω γραμμές και θα  εκτελέσει το
Mid=[(left+right)/2] και στην συνέχεια θα πραγματοποιηθούν οι αναδρομικές κλήσεις
Χ:=Count (A , left, mid);
Y:=Count (A , mid+1, right);

Ξέρουμε ότι το πλήθος των στοιχείων του πίνακα είναι n=right –left +1

Ακόμα το mid Mid=[(left+right)/2] και το  έχουμε ότι το left=1 και το right =k+1 θα έχουμε δηλαδή  Mid=[(left+right)/2]=[(1+κ+1)/2]=[(κ+2)/2]=[κ/2+1]
Έχουμε ότι κ/2<κ και κ-1<0 font="" nbsp="">

Επομένως  κ/2+1<κ-1⟹κ/2<κ
Δηλαδή ισχύει η επαγωγική υπόθεση  όπου έχουμε να εκτελεστεί η συνάρτηση count  για τον πίνακα Α[1..mid] με mid λιγότερα από κ στοιχεία. Έτσι θα μας επιστραφεί το σωστό πλήθος εμφανίσεων του elem στον πίνακα Α.  Δηλαδή το Χ υπολογίζεται σωστά

Αντίστοιχα και γα το Υ θα έχουμε  Y:=Count (A , mid+1, right);
 Όπου το πλήθος των στοιχείων είναι ισο με (right –mid+1)+1 έχοντας right =κ+1 δηλαδή θα είναι κ+1-mid-1+1=k+1-mid όπου το Mid=[(κ+2)/2] δηλαδή θα είναι
k+1-[(κ+2)/2]=   (2κ+2-κ-2)/2=κ/2

επομένως και για τον υπολογισμό του

Τέλος  το τελικό πλήθος των στοιχείων elem στον πίνακα Α προκύπτει από το άθροισμα Χ+Υ και επειδή τα χ και υ υπολογίζονται σωστά και το άθροισμα θα υπολογιστεί σωστά.

Ο αλγόριθμος είναι αναδρομικός στην δομή του και γα να λύση το πρόβλημα ακόλουθοι την τεχνική divide and conquer Η τεχνική αυτή χωρίζει το πρόβλημα σε μικρότερα όμοια προβλήματα μικρότερου μεγέθους όπου λύνει κάθε πρόβλημα αναδρομικά όπου στο τέλος συνδυάζονται όλα τα αποτελέσματα κάθε κλήσης.

Όλα τα στοιχεία του πίνακα που θα ελέγχουν είναι right-left+1

Όταν καλούμε την count η συνάρτηση κάνει 2 κλήσεις  της count μια για το δεξί μέρος και μια για το αριστερό δηλαδή το δέντρο είναι δυαδικό κάθε φόρα οι κλήσεις που γίνονται είναι  2

Κάθε επίπεδο της count εφαρμόζεται σε λιγότερα από τα αρχικά n στοιχεία κατά το μισο της προηγούμενης κλήσης.

Όσα περισσότερα τα στοιχεία του πίνακα δηλαδή η διαφορά right-left+1 είναι μεγαλύτερη τόσες πιο  μεγάλο θα είναι και το βάθος της αναδρομής.

Όταν το στοιχείο είναι 1  τότε η συνάρτηση θα τρέξει μια φόρα όπου θα μας επιστρέψει 1 η μηδέν ανάλογα με τιν τιμή του ελεγχόμενου πεδίου.

Ενώ εάν τα στοιχεία προς έλεγχο είναι 2 τότε η συνάρτηση θα εκτελεστεί 2 φόρες για να διασπαστούν τα  2 στοιχεία σε 1.

Για να αποτυπώσουμε  καλυτέρα το βάθος της αναδρομής σε συναρτήσαμε με το πλήθος των στοιχειών κατασκευάστηκε ο πινάκας που ακόλουθη που αναπαριστά το αριθμοο

Κλήση count	Εκτέλεση αναδρομικής συνάρτησης
0 0 επίπεδο	1 φόρα
1 0 επίπεδο	2  φόρες	21
2 0 επίπεδο	4	22
3 ο επίπεδο	8	24
4 0 επίπεδο	16	23
m ο επίπεδο	2m	2m

Καταλήγοντας ότι  όταν  φτάσουμε στο m επίπεδο της κλήσης η συνάρτηση θα εκτελεστεί 2^m φορες. Ακόμα κάθε επίπεδο διαιρεί το πλήθος των στοιχείων με το μισό έως ότου τα στοιχεία γίνουν 1. Παρακάτω ο πινάκας που αναπαριστά το πλίθος των στοιχείων σε συνάρτηση με το n. 

Κλήση count	Πλήθος στοιχείων με κάθε κληση  της συναρτησης
0 0 επίπεδο	-
1 0 επίπεδο
2 0 επίπεδο
3 ο επίπεδο
4 0 επίπεδο
m ο επίπεδο

Η συνάρτηση count σταμάτα  την εκτέλεση της όταν 

Επομένως για να υπολογίσουμε  το χ επίπεδο αναδρομής σε συνάρτηση του πλήθους n στοιχείων του πίνακα  παρατηρούμε ότι η συνάρτηση στο  χ επίπεδο εκτελείται  2^Χ φόρες επομένως το επίπεδο χ με το πλήθος στοιχείων είναι το ακέραιο μέρος του λογάριθμου με βάση το 2 του n πλήθος  στοιχειών του πινακα δηλαδή χ=〖[log2〗 n]