Ζευγάρια

Πρόβλημα

Ένας καθηγητής γυμναστικής ζητάει δύο εθελ-οντές/όντριες από την σχολική τάξη προκειμένου να παρουσιάσει μία άσκηση γυμναστικής για δύο άτομα. Γράψτε μία συνάρτηση με μια ακέραια παράμετρο η οποία αντιστοιχεί στο πλήθος των μαθητών της τάξης, η οποία επιστρέφει το πλήθος όλων των δυνατών επιλογών δύο ατόμων. Για παράδειγμα αν η τάξη έχει 3 άτομα με σύνολο ονομάτων {Μαρία, Νίκος, Ελένη} οι δυνατές επιλογές είναι 3: {Μαρία, Νίκος}, {Μαρία, Ελένη} και {Νίκος, Ελένη}.

Λύση

Απόδειξη ορθότητας

Προκειμένου να βρούμε όλα τα δυνατά ζευγάρια ν διακεκριμένων στοιχείων χωρίς να μας ενδιαφέρει η διάταξη των ζευγαριών, δηλαδή τα υποσύνολα με πλήθος στοιχείων 2 των ν διακεκριμένων στοιχείων, μπορούμε να διατρέξουμε το σύνολο των στοιχείων συνδυάζοντας κάθε στοιχείο με όλα τα υπόλοιπα. Μ’ αυτό τον τρόπο σίγουρα δεν παραλείπουμε κάποιο υποσύνολο, όμως κάποια υποσύνολα θα συμπεριληφθούν περισσότερες από μία φορές. Ας εφαρμόσουμε αυτή τη μέθοδο στο παράδειγμα της διατύπωσης του προβλήματος:

1) Συνδυάζουμε την Μαρία με τα υπόλοιπα άτομα:

{Μαρία, Νίκος}, {Μαρία, Ελένη}

2) Συνδυάζουμε τον Νίκο με τα υπόλοιπα άτομα:

{Νίκος, Μαρία}, {Νίκος, Ελένη}

3) Συνδυάζουμε την Ελένη με τα υπόλοιπα άτομα:

{Ελένη, Μαρία}, {Ελένη, Νίκος}

Παρατηρούμε ότι μ’ αυτόν τον τρόπο κάθε ζευγάρι αναφέρεται δύο φορές. Ας δούμε πως μπορούμε να αποφύγουμε τα “διπλότυπα” στην γενική περίπτωση ν στοιχείων:

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

Εναλλακτική λύση 1

Απόδειξη ορθότητας

Στο πρόγραμμα της αρχικής λύσης παρατηρούμε ότι για κάθε επανάληψη του εξωτερικού βρόγχου ο εμφωλευμένος βρόγχος προσθέτει στην μεταβλητή “πλήθος” την ποσότητα ν – (ι+1) + 1 = ν – ι (αφού ο τελευταίος βρόγχος εκτελείται για κ από ι+1 ως ν). Το ι όμως παίρνει τιμές από 1 ως ν, οπότε στην πρώτη επανάληψη του εξωτερικού βρόγχου αυξάνεται η τιμής της “πλήθος” κατά ν-1, στην δεύτερη κατά ν-2, στην τρίτη κατά ν-3 κοκ. Αυτή όμως είναι και η λειτουργία του παραπάνω προγράμματος.

Εναλλακτική λύση 2

ΣΥΝΑΡΤΗΣΗ count_2combination3(ν): ΑΚΕΡΑΙΑ
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: ν
ΑΡΧΗ
count_2combination3 <- (ν*ν – ν) DIV 2
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

Η απόδειξη ορθότητας αφήνεται ως άσκηση.

Άσκηση για εμβάθυνση

Υποθέστε ότι ο καθηγητής γυμναστικής ζητάει τρεις εθελ-οντές/όντριες. Πόσες είναι οι δυνατές επιλογές;

Υπόδειξη:

Στον εμφωλευμένο βρόγχο της βασικής λύσης εμφωλεύστε έναν ακόμα βρόγχο…