Προβλήματα Μαθηματικών

Οκτωβρίου 21, 2012

Όγκος n-διάστατης σφαίρας

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 1:06 πμ

Ο όγκος της n-διάστατης μοναδιαίας σφαίρας δίνεται από τον τύπο

\displaystyle V_n=\frac{{\pi}^{n/2}}{\Gamma\big(\frac{n}{2}+1\big)}.

Χρησιμοποιώντας τον τύπο του Stirling για τη συνάρτηση Γάμμα μπορεί κανείς να δει ότι V_n\to 0 καθώς n\to\infty.

Μπορείτε να το δείξετε αυτό χωρίς να χρησιμοποιήσετε ή να γράψετε κανένα μαθηματικό τύπο;

Οκτωβρίου 19, 2012

Υπολογίστε γρήγορα τους αριθμούς Fibonacci

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 11:39 μμ

Αν θέλουμε να υπολογίσουμε γρήγορα τη δύναμη K^n ενός φυσικού αριθμού K (όπου ο εκθέτης n είναι ένας πολύ μεγάλος αριθμός) τότε δε χρειάζεται να κάνουμε n πολλαπλασιασμούς. Αρκούν O(\log n) αριθμητικές πράξεις (πάντα μεταξύ ακεραίων): η πιο απλή περίπτωση όπου αυτό φαίνεται είναι όταν n=2^r είναι δύναμη του 2. Τετραγωνίζοντας κάθε φορά το προηγούμενό μας αποτέλεσμα μπορούμε με r=O(\log n) πράξεις να πάρουμε το αποτέλεσμά μας.

Βρείτε ένα αντίστοιχα γρήγορο τρόπο υπολογισμού του n-οστού αριθμού Fibonacci F_n. Οι αριθμοί Fibonacci ορίζονται από τον αναδρομικό τύπο:

F_n = \begin{cases} 1 & (n=1,2)\\ F_{n-1}+F_{n-2} & (n\ge 3).\end{cases}

Μόνο πράξεις ανάμεσα σε ακεραίους είναι επιτρεπτές.

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

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: