αναδρομικές συναρτήσεις

[takis_tz]

Έχω δυο απορίες ως προς το αποτέλεσμα που εμφανίζουν δυο αναδρομικές συναρτήσεις:

Ουσιαστικά δεν κατανοώ την απάντηση.

 

1) Έστω ότι καλείται η παρακάτω συνάρτηση έξι φορές με αρχικά ορίσματα τους αριθμούς 1 έως 6 αντίστοιχα. Για κάθε κλήση της συνάρτησης βρείτε ποιοι είναι οι αριθμοί που θα χρησιμοποιηθούν ως ορίσματα για κάθε αναδρομική κλήση της συνάρτησης. Εξηγείστε με λεπτομέρεια τις απαντήσεις σας.

int puzzle(int n) {

if (n == 1)

return 1;

if (n % 2 == 0)

return puzzle(n/2);

else

return puzzle(3*n+1);

}

ΑΠΑΝΤΗΣΗ:

Εκτέλεση με αρχικό όρισμα 1:

Εκτέλεση με αρχικό όρισμα 2: 1

Εκτέλεση με αρχικό όρισμα 3: 10 5 16 8 4 2 1

Εκτέλεση με αρχικό όρισμα 4: 2 1

Εκτέλεση με αρχικό όρισμα 5: 16 8 4 2 1

Εκτέλεση με αρχικό όρισμα 6: 3 10 5 16 8 4 2 1

 

 

2) Έστω η παρακάτω αναδρομική συνάρτηση:

int fn(int v)

{

if(v==1 || v==0)

return 1;

if(v%2==0)

return fn(v/2)+2;

else

return fn(v-1)+3;

}

Ποια θα είναι η τιμή της fn(7);

ΑΠΑΝΤΗΣΗ:

fn(7)=11

[pinball_elf]

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

>
ΑΠΑΝΤΗΣΗ:
Εκτέλεση με αρχικό όρισμα 3: 10 5 16 8 4 2 1

 

Όταν καλέσουμε την puzzle συνάρτηση με αρχικό όρισμα το 3, θα κάλεσει το εαυτό της

επιπλέον 7 φόρες ώσπου να βρεί την λύση και τα ορίσματα που θα έχει κάθε φορά είναι 10, 5, 16, 8, 4, 2, 1 αντίστοιχα.

[takis_tz]

Και για το δεύτερο, έχεις να πεις κάτι;

Πως προκύπτει εκείνο το 11;

[Harkon]

ξεκίνα να την λύνεις στο χαρτί να δεις τί όμορφα που βγαινει το 11

[takis_tz]

Αυτό προσπαθώ να κάνω αλλά μου βγαίνει 9. Κάτι λάθος έκανα και ψάχνω να το βρω.

[pinball_elf]

ΑΠΑΝΤΗΣΗ:

>
fn(7):      7!=1 && 7!=0 && 7%(mod)2=1 return fn(7-1) + 3   (1)
fn(7-1=6):  6!=1 && 6!=0 && 6%(mod)2=0 return fn(6/2) + 2   (2)
fn(6/2 =3): 3!=1 && 3!=0 && 3%(mod)2=1 return fn(3-1) + 3   (3)
fn(3-1 =2): 2!=1 && 2!=0 && 2%(mod)2=0 return fn(2/2) + 2   (4)
fn(2/2 =1): 1==1 && 1!=0 && 1%(mod)2=1 return 1             (5)

 

>
από (1) έχουμε:
fn(7) = fn(7-1) + 3 =                     (2) 
       (fn(6/2) + 2) + 3 =               (3)
       ( (fn(3-1) + 3) + 2 ) + 3 =       (4)
       ( ((fn(2/2) + 2) + 3) + 2 ) + 3 = (5)
       ( ((1 + 2) + 3) + 2 ) + 3 = 11

[Thorndale]

ουσιαστικα, στη 2η ασκηση δεν κανει κληση αναδρομικης συναρτησης η κανω λαθος? απλα καθε την καλεις μονος σου για να κωδικοποιησεις το εκαστοτε fn(x)