C άσκηση !!!

[rambo12345]

Γεια σας, είμαι φοιτητής ΗΜΜΥ α εξάμηνο και έχουμε αυτή την άσκηση

 

Εκφώνηση Εργαστηριακής Άσκησης

Γράψτε μία ΑΝΑΔΡΟΜΙΚΗ συνάρτηση που να ελέγχει εάν σε μία διάταξη δέκα (10) ακεραίων

υπάρχει τετράδα συνεχόμενων στοιχείων με ακεραίους Α, Β, Γ και Δ έτσι ώστε να ισχύει

Α + Δ = Β + Γ

Για παράδειγμα, η διάταξη με τους ακέραιους 5 10 20 21 31 4 3 9 περιέχει την τριάδα 10 20 21

31 όπου ικανοποιείται η απαιτούμενη συνθήκη.

Η αναδρομική σας συνάρτηση να τυπώνει ένα μήνυμα για το αν η διάταξη εισόδου περιέχει μία

κατάλληλη τετράδα αριθμών, το δείκτη του πρώτου στοιχείου της τετράδας καθώς και την

τετράδα αυτή. Η αναδρομική σας συνάρτηση να επιστρέφει το δείκτη του πρώτου στοιχείου της

τετράδας. Σε περίπτωση αποτυχίας, να τυπώνεται κατάλληλο μήνυμα και η συνάρτηση να

επιστρέφει -1.

Η συνάρτηση που θα γράψετε θα είναι η:

τιμή_επιστροφής quadruple(ορίσματα)

ΑΠΑΓΟΡΕΥΕΤΑΙ ΡΗΤΑ Η ΧΡΗΣΗ ΒΡΟΧΩΝ ΕΠΑΝΑΛΗΨΗΣ ΚΑΙ Η ΧΡΗΣΗ ΚΑΘΟΛΙΚΩΝ KAI STATIC

ΜΕΤΑΒΛΗΤΩΝ.

 

1) Δεν μπορώ να καταλάβω γιατί και πως να χρησιμοποιήσω αναδρομική συνάρτηση, δηλαδή που καλεί τον εαυτό της..

2) Πώς θα το κάνω αν απαγορεύονται οι βρόγχοι;

 

Πείτε καμιά ιδέα αν ξέρετε και ευχαριστώ εκ των πρωτέρων!!

[albNik]

Ας πουμε εχεις πινακα με 10 θεσεις

Δες αν στα 4 τελευταια ισχυει αλλιώς πάρε τον υποπινακα [0,9]

κανε το ιδιο για τον υποπινακα [0 9], μετα [0 8]... μεχρι [0 4]

[rambo12345]

Ωραία και πως θα γίνει η αναδρομή;

[V.I.Smirnov]

Η γραφή αναδρομικών συναρτήσεων έχει μια συγκεκριμένη μεθοδολογία γραφής.

 

Π.χ., το πρώτο στάδιο της λύσης είναι να οριστεί η βασική υπόθεση που τερματίζει το πρόβλημα.

Μετά πρέπει να ορίσεις το υποπρόβλημα που θα λύνει.

Κάθε υποπρόβλημα πρέπει να είναι απλούστερο από το αρχικό ώστε η διαδικασία να συγκλίνει προς τη βασική υπόθεση - και άρα τον τετρματισμό και τη λύση.

Ένα άλλο πρόβλημα, τελείως διαφορετικό αλλά όπου κάπως φαίνονται αυτά έχει συζητηθεί εδώ  (posts 1,12) :

http://www.insomnia.gr/topic/349251-εργασια-σε-c/

και επίσης ένα άλλο εδώ :

http://www.insomnia.gr/topic/362089-προβλημα-με-αναδρομη/

 

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

Μια αναδρομική συνάρτηση που είναι "tail recursion" μπορεί εύκολα να γραφεί με βρόγχους, αλλιώς τα πράγματα δυσκολεύουν.

 

 

 

Τα παραπάνω είναι πολύ βασικά - αν δεν τα ξέρεις δεν έχει νόημα να προσπαθείς να λύσεις το πρόβλημα.

Όλα τα βιβλία αλγορίθμων τα συζητούν εκτενώς, θα τα βρεις εύκολα.

Αν σας ζητούν τέτοια άσκηση χωρίς να σας έχουν αναφέρει τα παραπάνω, είναι απαράδεκτοι....

 

-

[defacer]

Ωραία και πως θα γίνει η αναδρομή;

 

Γράψε μια αναδρομική συνάρτηση που να τυπώνει 3 - 2 - 1. Μπορείς;

[V.I.Smirnov]

Δύσκολο αλλά εξαιρετικά διδακτικό παράδειγμα αναδρομής είναι το κλασσικό 

πρόβλημα του ιππότη που είχα λύσει κάποτε εδώ.

Είναι τυπικό παράδειγμα προβλήματος που δεν μπορεί να λυθεί εύκολα με

επαναληπτικό τρόπο (βρόγχους) διότι δεν είναι "tail-recursion".

Όμοιο είναι και το πρόβλημα με τις εννιά βασίλισσες.

 

post #9 και #11 :

http://www.insomnia.gr/topic/349855-%CE%B1%CF%83%CE%BA%CE%B7%CF%83%CE%B7-%CF%80%CF%81%CE%BF%CE%B3%CF%81%CE%B1%CE%BC%CE%BC%CE%B1%CF%84%CE%B9%CF%83%CE%BC%CE%BF%CF%85/

 

 

Ήταν η περίοδος που είχα μελετήσει τα σχετικά με την αναδρομή και την εφάρμοζα όπου έβρισκα.

Το αποκορύφωμα ήταν ένα parser που έφτιαξα για να εισάγω συναρτήσεις on run-time (κατά την εκτέλεση).

Λειτουργούσε αναδρομικά αναλύοντας το string που έδινε ο χρήστης.

Γραμμένο σε Fortran (!!!), όσο απίστευτο κι αν ακούγεται - και δούλευε πολύ καλά.

 

Έκτοτε....μου πέρασε και δεν τα ξανάπιασα...   και σήμερα θυμάμαι πλέον μόνον τις ιδέες...

 

-