spaceman, είσαι σίγουρος γι αυτό που έγραψες? Ο τύπος είναι μεν ένας από τους πολλούς αναδρομικούς τύπους που παράγουν Catalan numbers, ο κώδικας όμως δεν τον υλοποιεί ούτε επιστρέφει τα σωστά αποτελέσματα - αν οι catalan, counter είναι ακέραιοι. Αν δεις π.χ. στο Wikipedia ή στο Wolphram Mathworld θα έπρεπε να δίνει 1, 2, 5, 14, 42, 132, 429 κλπ. Αντί γι αυτό όμως δίνει 1, 2, 4, 8, 24 ... καμμία σχέση.
Ο λόγος είναι ότι αν οι catalan, counter είναι ακέραιοι (int, long), η διαίρεση χάνει δεκαδικά πριν γίνει ο πολλαπλασιασμός με την τελευταία τιμή. Αν ήταν floating point, δεν θα είχες πρόβλημα.
Το σωστό θα ήταν να γράψεις το παρακάτω (σε C#):
public static int CIter(int n)
{
int previous = 1;
for (int i = 1; i <= n;i++ )
{
previous = (previous *(4 * i + 2)) / (i + 2);
}
return previous;
}
Θα μπορούσες ακόμα να γράψεις και last = last * (4*i +2) / (i+2) καθώς ο compiler εκτελεί τους πολλαπλασιασμούς με τη σειρά και δεν υπάρχει θέμα truncation. Καλό είναι πάντως να παραμείνουν οι παρενθέσεις για να μην έχει κάποιος το πρόβλημα που είχες κι εσύ.
spaceman, καλό θα ήταν να εξηγείς τον ψευδοκώδικα που γράφεις και να βάζεις και καμμία παραπομπή. Αλλιώς δίνεις την εντύπωση ότι έγραψες κάτι χωρίς ουσιαστικά να ελέγξεις αν δουλεύει. Άσε που όταν κάποιος ρωτάει πώς γίνεται κάτι, εννοείται ότι ζητάει και κάποια εξήγηση.
kgiann78, όταν έχεις ένα αναδρομικό αλγόριθμο ο οποίος αναφέρεται στην προηγούμενη τιμή του είναι εύκολο να τον μετατρέψεις σε επαναληπτικό, απλά αποθηκεύοντας κάπου το τελευταίο αποτέλεσμα του τελευταίου υπολογισμού. Αφού υπολογίσεις το νέο νούμερο, αντικαθιστάς το παλιό με το νέο. Η αρχική τιμή του "τελευταίου αποτελέσματος" είναι η αρχική τιμή του αλγόριθμου. Έτσι, μία επανάληψη από το 0 μέχρι το n είναι σαν να υπολογίζει όλες τις ενδιάμεσες τιμές από την πρώτη μέχρι την τελευταία, ενώ η αναδρομή δουλεύει με τον αντίθετο τρόπο.
Αν ο τύπος που θέλεις να χρησιμοποιήσεις είναι ο C(n+1)=C(n)*(4n+2)/(n+2), μπορείς αρχικά να τον κάνεις
nextValue=previousValue* (4*n +2) / (n + 2)
Μετά, απλά αντικαθιστάς το nextValue με το previousValue. Ή, για συντομία, κάνεις την αντικατάσταση απευθείας: previousValue=previousValue * (4*n +2) / (n+2). Φτάνει να θυμάσαι ότι o τελεστής *= δεν είναι τελικά το ίδιο με το = *, όταν υπάρχει πιθανότητα truncation.
Παναγιώτης Καναβός, Freelancer
Twitter: http://www.twitter.com/pkanavos