Λοιπά θέματα

Απ: Καταλανοί, Βάσκοι και λοιποί... Catalan numbers στη C...

kgiann78 — Fri, 17 Dec 2010 01:14:04 GMT

Πω πω... Είχα κολήσει από την προηγούμενη μέθοδο με recursion και δεν το έβλεπα... Δεν είχα σκεφτεί καθόλου να χρησιμοποιήσω πίνακα...

Σε ευχαριστώ πολύ!

Απ: Καταλανοί, Βάσκοι και λοιποί... Catalan numbers στη C...

Παναγιώτης Καναβός — Thu, 16 Dec 2010 20:04:40 GMT

Ο τύπος αυτός απαιτεί όλες τις προηγούμενες τιμές για να υπολογίσεις την επόμενη. Σε αυτή την περίπτωση δεν μπορείς φυσικά να ορίσεις n μεταβλητές γι αυτό και θα πρέπει να χρησιμοποιήσεις ένα πίνακα με n πεδία. Αν k είναι η τρέχουσα θέση, σε ενδιαφέρουν όλες οι προηγούμενες, δηλαδή οι 0 ... k-1. Αν ξεκινήσεις να υπολογίζεις με k=1 (το k=0 είναι πάντα 1), για κάθε αυξανόμενο k θα έχεις υπολογίσει ήδη όλες τις προηγούμενες τιμές και θα τις έχεις και στην κατάλληλη θέση. Για παράδειγμα (C#)

public static int CIter2(int n)
{
    int[] sums=new int[ n];
    sums[0]=1;

    for (int k=1;k<n;k++)
	for (int i=0;i<k;i++)
	{					
            sums[ k] +=sums[ i]* sums[k-i-1];
	}

    return sums[n-1];
}

Σε C θα πρέπει να φτιάξεις δυναμικά τον πίνακα με τη malloc και να τον καθαρίσεις μετά με τη free

Απ: Καταλανοί, Βάσκοι και λοιποί... Catalan numbers στη C...

kgiann78 — Thu, 16 Dec 2010 16:22:37 GMT

Μια διευκρίνηση... Ο τύπος που δινόταν ήταν ο παρακάτω...

              1            , n=0

Cn =
              n-1
               Σ (Ci*Cn-i-1), n!=0
              i=0

Αν δινόταν κάποιος διαφορετικός τύπος ίσος σκεφτόμουν κάτι διαφορετικό εξίσου...

Απ: Καταλανοί, Βάσκοι και λοιποί... Catalan numbers στη C...

Παναγιώτης Καναβός — Thu, 16 Dec 2010 08:03:11 GMT

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.

Απ: Καταλανοί, Βάσκοι και λοιποί... Catalan numbers στη C...

spaceman — Thu, 16 Dec 2010 06:56:17 GMT

Catalan numbers:

C 0 = 1

C n + 1 = (4 n + 2) C n / (n + 2)

catalan = 1
counter = 1
while (counter <= n)
{
catalan *= (4*(counter-1) + 2)/(counter-1+2);
counter++;
}

--HTH--

Καταλανοί, Βάσκοι και λοιποί... Catalan numbers στη C...

kgiann78 — Thu, 16 Dec 2010 01:09:18 GMT

Αυτές τις μέρες δίνω κατατακτήριες εξετάσεις για να μπώ στην Πληροφορική & Τηλ/νιες Αθηνών. Είναι ένα project - στοίχημα που θέλω πάρα πολύ να κερδίσω αλλά για την ώρα μου φαίνεται δύσκολο...
Που κολάνε τώρα οι Βάσκοι και οι Καταλανοί?

Εχθές δίναμε εισαγωγή στον προγραμματισμό, μάθημα στο οποίο διδάσκεται η C.
Το ζητούμενο ενός θέματος ήταν να γράψουμε 2 συναρτήσεις, την int catalanrec(int n) και την int catalaniter(int n).
Η μια υπολογίζει έναν αριθμό Catalan αναδρομικά ενώ η άλλη με επανάληψη.

Η πρώτη έγινε πολύ γρήγορα και άνετα, ούτως ή άλλως η αναδρομή είναι "μανούλα" για κάτι τέτοιες καταστάσεις. Εκεί που κόλησα ήταν η δεύτερη. Δυστυχώς ακόμη και αν έψαξα σε διάφορα σχετικά sites δεν μπορώ να πω ότι βρήκα επίλυση ενός αριθμού Catalan με επανάληψη...

Έτσι το θέμα έμεινε μισό... Το ερώτημα μου είναι απλό. Μήπως κάποιος γνωρίζει κάτι σχετικό? Πως γκένειν η δεύτερη συνάρτηση?

PS Άραγες μπορεί να ληφθεί υπόψη λύση από το πρόχειρο μήπως και τονώσει λίγο τη βαθμολογία??? Κλαψ... το χάσαμε αλλιώς το μάθημα πατριώτη...