Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:تئوری نهایی دوم:سوال ۲

سوال ۲

تعداد ‎n‎ جعبه داریم با شماره های ‎1‎ تا ‎n‎. در ابتدای کار میزی خالی داریم. حال در مرحله‌ی ‎i‎ام ‎0<in‎ اگر ‎k‎ جعبه روی میز بود به احتمال ‎1k+1‎ جعبه ‎i‎ در هر یک از جعبه‌های روی زمین قرار می‌گیرد و از بین می‌رود و به احتمال ‎1k+1‎ در جایی خالی روی میز قرار می‌گیرد. امید ریاضی تعداد جعبه‌هایی که در نهایت روی زمین قرار می‌گیرد را ‎e(n)‎ بگیرید.

2- الف (10 نمره) : ثابت کنید ‎e(n)‎ از ‎Ω(logn)‎ است.‎‎

2- ب (25 نمره) : ثابت کنید ‎e(n)‎ از ‎O(n)‎ است‎.

2- ج (10 نمره) :θ(e(n)) را بیابید.‎‎ مثلا ‎e(3)=2312‎ است.


ابزار صفحه