Υπολογιστής Αρχής Περιστερώνα

Τύπος

How this is calculated

Εισαγάγετε n, το πλήθος των αντικειμένων, και k, το πλήθος των κουτιών. Όσο έξυπνα κι αν απλώσετε τα αντικείμενα, το πιο γεμάτο κουτί πρέπει να περιέχει τουλάχιστον ceil(n / k) αντικείμενα — αυτή είναι η αρχή του περιστερώνα (Dirichlet). Αν τα χωρίσετε ομοιόμορφα, κάθε κουτί κρατά floor(n / k), και τα υπόλοιπα n − k·floor(n / k) κουτιά παίρνουν ένα επιπλέον αντικείμενο, που είναι ακριβώς ο λόγος που το μέγιστο στρογγυλοποιείται προς τα πάνω.

Η είσοδος στόχος m απαντά στην αντίστροφη ερώτηση: πόσα αντικείμενα πρέπει να τοποθετήσετε πριν εγγυηθεί ότι κάποιο κουτί κρατά τουλάχιστον m από αυτά. Η χειρότερη περίπτωση γεμίζει κάθε κουτί με m − 1 αντικείμενα χωρίς να φτάσει το m, αθροίζοντας k·(m − 1)· ένα ακόμη αντικείμενο, k·(m − 1) + 1, επιβάλλει το m-οστό αντικείμενο σε κάποιο κουτί. Αυτό είναι το ελάχιστο πλήθος που εγγυάται τον στόχο ανεξάρτητα από τη διάταξη.

Όλες οι είσοδοι αντιμετωπίζονται ως μη αρνητικοί ακέραιοι και στρογγυλοποιούνται προς τα κάτω εσωτερικά, οπότε οι κλασματικές καταχωρίσεις στρογγυλοποιούνται προς τα κάτω. Το πλήθος των κουτιών k πρέπει να είναι τουλάχιστον 1 για την αποφυγή διαίρεσης με το μηδέν, και ο στόχος m πρέπει να είναι τουλάχιστον 1 για να οριστεί το πλήθος επιβολής. Τα αποτελέσματα είναι εγγυήσεις για τη χειρότερη περίπτωση, όχι προβλέψεις μιας τυπικής ή τυχαίας κατανομής.