سلام.
حالتون خوبه؟
میشه راجع به این سوال راهنمائیم کنید؟
اینم لینک عکسش:
[attachment=20700]
در بدترین حالت ما n/3 عدد یک و n/2 عدد صفر میبینیم.اینطوری هیچ کدوم از گونه ها مشخص نیست.
با بررسی بیت بعدی اگر مقدارش یک بود تعداد از n/3 بیشتر میشود و اگر صفر بود تعداد از n/2 بیشتر میشود. پس در بدترین حالت داریم :
[tex]\frac{n}{2} \frac{n}{3} 1=\frac{5n}{6} 1[/tex]
می توان گونه آرایه را با قطعیت مشخص کرد.
یه آرایه A , یه آرایه B داریم.
آرایه A داراری [tex]\frac{n}{2}[/tex] صفر و [tex]\frac{n}{2}[/tex] یک هست.
آرایه B دارای [tex]\frac{2n}{3}[/tex] صفر و [tex]\frac{n}{3}[/tex] یک هست.
حالا به من یه آرایه دادن و من نمیدونم کدومه.
باید با برداشتن عناصرش پیش بینی کنم کدومشونه. مسئله از ما میخواد بعد از برداشتن چند تا عنصر میتونیم با قطعیت بگیم که آرایه داده شده A هست یا B.
این کار رو باید براساس تعداد ۰ و ۱ در آرایه داده شده انجام بدیم.
میدونیم که [tex]\frac{2n}{3}>\frac{n}{2}[/tex] و [tex]\frac{n}{2}>\frac{n}{3}[/tex]
پس اگه آرایه داده شده بیشتر از [tex]\frac{n}{2}[/tex] تا صفر داشته باشه حتما آرایه B هست و اگه بیشتر از [tex]\frac{n}{3}[/tex] تا یک داشته باشه حتما آرایه A است.
ضمنا میدونیم که قراره یه ترتیبی از ۰ و ۱ ها رو برداریم.و اون اول ممکنه هر چند تا صفر یا هر چند تا ۱ بیان و (در بدترین حالت) تا مراحل آخر نمیدونیم که کدوم آرایه رو به ما دادن.
پس اگه تو ترتیب انتخاب صفر و یک تا حالا [tex]\frac{n}{3}[/tex] تا ۰ و [tex]\frac{n}{2}[/tex] تا ۱ دیده باشیم نمیتونیم بگیم کدوم آرایه داده شده. مجموع این دو تا [tex]\frac{n}{2} \frac{n}{3}=\frac{5n}{6}[/tex] هست . در نهایت برای اینکه بدونم آرایه من کدومه باید یه عنصر دیگه بردارم که اگه صفر باشه مطمئنم آرایه B و اگه یک باشه مطمئنم آرایه A به من داده شده.
جواب نهایی [tex]\frac{5n}{6} 1[/tex] هست.