Συμβουλες για ασκηση σε C

[Caiden]

Καλησπερα παιδια θα ηθελα μια μικρη βοηθεια για μια εργασια που μας εχουνε βαλει σε γλωσσα C. Την προσπαθω εδω και 5 μερες αλλα τελικα δεν καταφερα να το κανω να δουλεψει. Παραθετω την ασκηση:

 

/*

Εστω οτι εχουμε ενα πινακα με διαστασεις NxM ο οποιος περιεχει μη αρνητικους αριθμους και Θελουμε να τον διασχισουμε απο την πρωτη γραμμη προς την τελευταια. Αρχιζουμε απο καποιο κελι την πρωτης γραμμης και σε καθε βημα μπορουμε να παμε σε κελι της επομενης γραμμης ειτε στο ακριβως απο κατω ειτε σε διαγωνιο (αριστερα ή δεξια του). Επισης θεωρουμε οτι ο πινακας στα ακρα του αναδιπλωνεται, δηλαδη αν βρισκομαστε στο "τερμα" δεξιο ή αριστερο κελι μπορουμε να περασουμε στο "τερμα" αριστερο ή δεξι αντιστοιχα κελι της επομενης γραμμης. Το ζητουμενο ειναι να βρουμε ποιο ειναι το μεγιστο αθροισμα που μπορουμε να παρουμε διασχιζοντας ενα μονοπατι του πινακα. Επισης δινεται οτι:

Si,j =

-- array[N-1][j] εαν z=(n-1)

-- array[z][0] + max(S(z+1,M-1),S(z+1,1),S(z+1,0)) εαν z<(n-1) και j=0

-- array[z][j] + max(S(z+1,j-1),S(z+1,j),S(z+1,j+1))εαν z<(n-1) και 0<j<(M-1)

-- array[z][M-1] + max(S(z+1,M-2),S(z+1,M-1),S(z+1,0)) εαν z<(n-1) και j=(M-1)

*/

 

 

Εγω πρεπει να φτιαξω μια αναδρομικη συναρτηση εστω func() η οποια να μου υπολογιζει το παραπανω μεγιστο αθροισμα. Oμως θα πρεπει να χρησιμοποιησω ενα επιπλεον πινακα με διαστασεις NxM στον οποιο θα περιεχονται τα επιμερους αθροισμα. Σκοπος ειναι να υπολογιζω μονο μια φορα τα επιμερους αθροισματα ωστε να μειωσω το χρονο εκτελεσης. Την συναρτηση την καλω με απο μια main και παιρνει σαν ορισματα τις διαστασεις, τον αρχικο πινακα, τον βοηθητικο πινακα και επισης τον δεικτη των γραμμων (υπολογιζω για j=0...j=N-1).

Επειδη αποτελει μερος μιας ευρητερης εργασιας δεν θα ηθελα να ποσταρω τον κωδικα μου. Να πω ακομα οτι την εχω ηδη υλοποιησει με μια αναδρομικη συναρτηση(χωρις χρηση του επιπλεον πινακα) και με επαναληπτικη διαδικασια και μου εχει μεινει αυτος ο τροπος. Φυσικα και δεν ζηταω ετοιμο κωδικα (γιατι αν δεν την γραψω εγω πως θα μαθω ) απλα θα ηθελα λιγη βοηθεια προς τα που να κοιταξω και την λογικη που πρεπει να ακολουθησω.

Ελπιζω να ειναι κατανοητη η εκφωνηση μου και φυσικα καθε απαντηση και βοηθεια δεκτη.

[defacer]

Πρόκειται για περίπτωση top-down dynamic programming: σε κάθε βήμα, θέλεις να υπολογίσεις το μέγιστο άθροισμα που μπορείς να φτάσεις δεδομένου ότι θα ξεκινήσεις από το κελι (x,y), το οποίο φαντάσου ότι μπορεί να είναι οποιοδήποτε στον πίνακα (όχι απλά στην πρώτη γραμμή). Αυτό είναι πολύ εύκολα υπολογίσιμο αν ξέρεις ήδη τα μέγιστα αθροίσματα στα οποία μπορείς να φτάσεις ξεκινώντας από κάθε ένα από τα τρια "απο κάτω" κελιά -- είναι το μέγιστο των τριών αθροισμάτων συν την τιμή στο (x,y), όπως λένε και οι σχέσεις που δίνεις.

 

Για να υπολογίσεις το κάθε ένα από τα 3 μέγιστα αυτά θα πρέπει γενικά να υπολογίσεις άλλα 3 μέγιστα με τον ίδιο τρόπο (αναδρομή). Η συνθήκη τερματισμού της αναδρομής είναι πως όταν βρίσκεσαι στην τελευταία γραμμή τότε το μέγιστο που μπορείς να φτάσεις ξεκινώντας από το κελί (Ν-1, y) είναι προφανώς η τιμή του (δεν έχει άλλο απο κάτω).

 

Η καταλληλότητα του dynamic programming (δηλαδή της χρήσης του βοηθητικού πίνακα όπου σώζεις τα μέγιστα αθροίσματα που ήδη έχεις υπολογίσει) εδώ βασίζεται στο γεγονός πως έχοντας υπολογίσει το μέγιστο άθροισμα έστω K από το κελί (1,1) στα πλαίσια της εύρεσης της λύσης για το (0, 0), η τιμή του Κ μπορεί να χρησιμοποιηθεί αυτούσια για να βρεις τη λύση και για το (0, 1) και για το (0, 2).

 

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

1. Μπορείς για κάθε κελί να κρατάς μια ακόμα τιμή (σε τρίτο πίνακα) που να λέει αν έχει ήδη υπολογιστεί το μέγιστο άθροισμα γι' αυτό το κελί.
2. Μπορείς να χρησιμοποιήσεις μια guard value όπως π.χ. την INT_MIN (ορίζεται στο limits.h) η οποία θα αντιπροσωπεύει το ότι δεν έχει υπολογιστεί ακόμα το μέγιστο άθροισμα.
3. Δεδομένου ότι το πρόγραμμά σου θα διατρέχει τον πίνακα πάντα με τον ίδιο τρόπο, πάντα ξέρεις απο πριν αν έχει υπολογιστεί ήδη το κάθε υπο-άθροισμα ή όχι (σκέψου το). Μπορείς επομένως να βάλεις στην αναδρομική συνάρτηση μια επιπλέον boolean παράμετρο η οποία θα της λέει αν πρέπει να υπολογίσει ή να επιστρέψει την ήδη υπολογισμένη τιμή.

Εγώ θεωρώ από άποψη ποιότητας κώδικα ότι το καλύτερο είναι το #1, αλλά δεν είμαι σίγουρος από την εκφώνηση αν θέλει να κάνετε το #3 (που είναι μάλλον το χειρότερο). Στα πλαίσια της εργασίας βέβαια δεν είναι έγκλημα, αλλά καλό είναι να μη μάθεις έτσι αν σκοπεύεις να ασχοληθείς με προγραμματισμό.

 

Σε κώδικα λοιπόν θα έχεις κάτι σαν το εξής:

 

 

 

int values[M][N], max_sums[M][N];

int max_sum(int i, int j) {
    if (ξέρεις_ήδη_το_μέγιστο_άθροισμα) {
        // dynamic programming
        return max_sums[i][j];
    }

    int max_sum;

    if (i == M - 1) {
        // συνθήκη τερματισμού αναδρομής
        max_sum = values[i][j];
    }
    else {
        // η 2η παράμετρος στην κλήση της max_sum για τα s2, s3 μπορεί να 
        // υπολογιστεί απλούστερα -- το αφήνω έτσι για να καταλάβεις το πνεύμα
        int s1 = values[i][j] + max_sum(i + 1, (N + j - 1) % N);
        int s2 = values[i][j] + max_sum(i + 1, (N + j + 0) % N);
        int s3 = values[i][j] + max_sum(i + 1, (N + j + 1) % N);
        max_sum = max(s1, max(s2, s3));
    }

    return max_sums[i][j] = max_sum;
}

 

 

[Caiden]

Defacer ευχαριστω για την απαντηση σου. Μολις βρω internet απο καποιον σταθερο θα την κοιταξω. Απο το κινητο ειναι λιγο δυσκολο αφου δεν μπορω να δω και το spoiler.

 

Sent from HTC Desire via Insomnia App