Εισαγωγή
Μόλις αποφοίτησες από το πανεπιστήμιο και διοργανώνεις ένα τεράστιο πάρτι για να γιορτάσεις με φίλους και οικογένεια.
Πάνω από 70 άτομα έχουν έρθει, ανάμεσά τους και ο ελαφρώς εκκεντρικός θείος σου ο Ted.
Σε ένα από τα συνηθισμένα του καμώματα, σου βάζει στοίχημα 100 λίρες ότι τουλάχιστον δύο άτομα στον χώρο έχουν τα ίδια γενέθλια.
Αυτό ακούγεται γελοίο, αφού υπάρχουν πολύ περισσότερες πιθανές ημερομηνίες γενεθλίων απ' ό,τι καλεσμένοι, οπότε το δέχεσαι με σιγουριά.
Προς μεγάλη σου έκπληξη, αφού συγκέντρωσες τα γενέθλια μόλις 32 καλεσμένων, έχεις ήδη βρει δύο καλεσμένους που έχουν τα ίδια γενέθλια.
Παραδέχεσαι την ήττα σου και δίνεις στον θείο Ted τις 100 λίρες, αλλά κάτι δεν πάει καλά.
Την επόμενη μέρα, η περιέργεια σε νικά.
Μια γρήγορη αναζήτηση στο διαδίκτυο σε οδηγεί στο παράδοξο των γενεθλίων, το οποίο αποκαλύπτει ότι με μόλις 23 άτομα, η πιθανότητα να έχουν δύο άτομα τα ίδια γενέθλια ξεπερνά το 50%.
Αχά. Γι' αυτό λοιπόν ήταν τόσο σίγουρος ο θείος Ted.
Αποφασισμένος να αντιστρέψεις την κατάσταση, αρχίζεις να ψάχνεις άλλα παράδοξα. Την επόμενη φορά, εσύ θα είσαι αυτός που θα βάζει τα στοιχήματα.
Το παράδοξο των γενεθλίων είναι ένα αληθές παράδοξο: παρόλο που φαίνεται λάθος, στην πραγματικότητα ισχύει.
Οδηγίες
Το καθήκον σου είναι να εκτιμήσεις τις πιθανότητες του παραδόξου των γενεθλίων.
Για να το κάνεις αυτό, πρέπει να:
- Παράγεις τυχαίες ημερομηνίες γέννησης.
- Ελέγχεις αν μια συλλογή από τυχαία παραγόμενες ημερομηνίες γέννησης περιέχει τουλάχιστον δύο με τα ίδια γενέθλια.
- Εκτιμάς την πιθανότητα τουλάχιστον δύο άτομα σε μια ομάδα να έχουν τα ίδια γενέθλια, για διάφορα μεγέθη ομάδας.
Μια ημερομηνία γέννησης περιλαμβάνει την πλήρη ημερομηνία γέννησης (έτος, μήνα και ημέρα), ενώ τα γενέθλια αναφέρονται μόνο στον μήνα και την ημέρα, που επαναλαμβάνονται κάθε χρόνο.
Δύο ημερομηνίες γέννησης με τον ίδιο μήνα και την ίδια ημέρα αντιστοιχούν στα ίδια γενέθλια.
Το παράδοξο των γενεθλίων προϋποθέτει ότι:
- Υπάρχουν 365 πιθανά γενέθλια (χωρίς δίσεκτα έτη).
- Καθένα από τα γενέθλια είναι εξίσου πιθανό (ομοιόμορφη κατανομή).
Η υλοποίησή σου πρέπει να ακολουθεί αυτές τις προϋποθέσεις.
Ειδικές σημειώσεις για x86-64 Assembly
Η συνάρτηση random_birthdates() θα πρέπει να παράγει ημερομηνίες με τις ακόλουθες ιδιότητες:
- Το έτος θα πρέπει να είναι έγκυρο.
Ένα έγκυρο έτος
y είναι μη δίσεκτο και τέτοιο ώστε 1600 <= y < 2129.
- Το έτος είναι ομοιόμορφα κατανεμημένο σε ολόκληρο το εύρος των έγκυρων τιμών.
- Η ημερομηνία γέννησης είναι ομοιόμορφα κατανεμημένη σε όλες τις 365 ημέρες του έτους, έτσι ώστε κάθε ημερολογιακή ημέρα να είναι εξίσου πιθανή.
Σημείωσε ότι αυτό σημαίνει πως οι μήνες δεν είναι εξίσου πιθανοί: ένας μήνας 31 ημερών είναι πιο πιθανός από έναν μήνα 30 ημερών και οι δύο είναι πιο πιθανοί από τον Φεβρουάριο.
Και οι δύο κατανομές, του έτους και της ημερομηνίας γέννησης, ελέγχονται με έναν έλεγχο χι-τετράγωνο, στο επίπεδο p < 0,0001.
Αυτό σημαίνει ότι αν οι ημερομηνίες παράγονται σύμφωνα με τις οδηγίες, υπάρχει λιγότερο από 0,01% πιθανότητα να παραχθεί μια κατανομή τιμών που αποτυγχάνει στον έλεγχο.
