Επιλογή Σελίδας

Είναι γνωστό από τα μαθηματικά ότι ο αριθμός των συνδυασμών των n πραγμάτων ανά k δίνεται από τον τύπο:

par2kef3temath

Να προταθεί ένας αλγόριθμος για τον υπολογισμό του αριθμού των συνδυασμών αυτών.
ΛΥΣΗ:

Ένας απλός τρόπος είναι να εφαρμοσθεί ο προηγούμενος μαθηματικός τύπος. Έτσι, δεδομένων των παραλλαγών του αλγορίθμου για τον υπολογισμό του n!, προκύπτει ο επόμενος αλγόριθμος που καλεί κάποια από αυτές τις παραλλαγές.

Αλγόριθμος Συνδυασμός
 Διάβασε n
 Διάβασε k
 a ← Παραγοντικό(n)
 b ← Παραγοντικό(k)
 c ← Παραγοντικό(n-k)
 combination ← a /(b*c)
 Γράψε combination
 Τέλος Συνδυασμός

Αν και ο αλγόριθμος αυτός είναι ιδιαίτερα απλός στην κατανόηση και στον προγραμματισμό του, εντούτοις δεν είναι ο καλύτερος δυνατός από την άποψη της αποτελεσματικότητας γιατί εκτελεί περιττούς πολλαπλασιασμούς. Αυτό φαίνεται ανάγλυφα αν θεωρήσουμε και πάλι το μαθηματικό τύπο του αριθμού των συνδυασμών. Στο κλάσμα του τύπου αυτού μπορεί να γίνει κάποια απλοποίηση μεταξύ αριθμητή και παρονομαστή. Για παράδειγμα, για τον υπολογισμό του αριθμού των συνδυασμών των 10 πραγμάτων ανά 5, με τον προηγούμενο τρόπο θα εκτελέσουμε 9 πολλαπλασιασμούς για τον υπολογισμό του αριθμητή (10!), και 4+4 πολλαπλασιασμούς για τον υπολογισμό του παρονομαστή (δύο φορές το 5!). Ενώ εύκολα προκύπτει ότι:

par2kef3temath2
όπου εκτελούνται από τέσσερις πολλαπλασιασμοί σε αριθμητή και παρονομαστή. Ο αντίστοιχος αλγόριθμος έχει ως εξής:

Αλγόριθμος Συνδυασμός2
 Διάβασε n
 Διάβασε k
 a ← 1
 Για i από n μέχρι n-k+1 με_βήμα -1
 a ← a*i
 Τέλος_επανάληψης
 b ← Παραγοντικό(k)
 combination ← a/b
 Εκτύπωσε combination
 Τέλος Συνδυασμός2
Share This