Είναι γνωστό από τα μαθηματικά ότι ο αριθμός των συνδυασμών των n πραγμάτων ανά k δίνεται από τον τύπο:
Να προταθεί ένας αλγόριθμος για τον υπολογισμό του αριθμού των συνδυασμών αυτών.
ΛΥΣΗ:
Ένας απλός τρόπος είναι να εφαρμοσθεί ο προηγούμενος μαθηματικός τύπος. Έτσι, δεδομένων των παραλλαγών του αλγορίθμου για τον υπολογισμό του n!, προκύπτει ο επόμενος αλγόριθμος που καλεί κάποια από αυτές τις παραλλαγές.
Αλγόριθμος Συνδυασμός Διάβασε n Διάβασε k a ← Παραγοντικό(n) b ← Παραγοντικό(k) c ← Παραγοντικό(n-k) combination ← a /(b*c) Γράψε combination Τέλος Συνδυασμός
Αν και ο αλγόριθμος αυτός είναι ιδιαίτερα απλός στην κατανόηση και στον προγραμματισμό του, εντούτοις δεν είναι ο καλύτερος δυνατός από την άποψη της αποτελεσματικότητας γιατί εκτελεί περιττούς πολλαπλασιασμούς. Αυτό φαίνεται ανάγλυφα αν θεωρήσουμε και πάλι το μαθηματικό τύπο του αριθμού των συνδυασμών. Στο κλάσμα του τύπου αυτού μπορεί να γίνει κάποια απλοποίηση μεταξύ αριθμητή και παρονομαστή. Για παράδειγμα, για τον υπολογισμό του αριθμού των συνδυασμών των 10 πραγμάτων ανά 5, με τον προηγούμενο τρόπο θα εκτελέσουμε 9 πολλαπλασιασμούς για τον υπολογισμό του αριθμητή (10!), και 4+4 πολλαπλασιασμούς για τον υπολογισμό του παρονομαστή (δύο φορές το 5!). Ενώ εύκολα προκύπτει ότι:
όπου εκτελούνται από τέσσερις πολλαπλασιασμοί σε αριθμητή και παρονομαστή. Ο αντίστοιχος αλγόριθμος έχει ως εξής:
Αλγόριθμος Συνδυασμός2 Διάβασε n Διάβασε k a ← 1 Για i από n μέχρι n-k+1 με_βήμα -1 a ← a*i Τέλος_επανάληψης b ← Παραγοντικό(k) combination ← a/b Εκτύπωσε combination Τέλος Συνδυασμός2
Πρόσφατα σχόλια