سوال ۱۹
فرض کنید آرایه‌ای به طول ۱۰۰۰ از بیت‌های ۰ و ۱ داریم. می‌گوییم این آرایه «۰- غالب» است اگر دست کم ٪۹۰ اعداد آن ۰ باشد (و در نتیجه حداکثر ٪۱۰ آن ۱ باشد). هم‌چنین آرایه «۱- غالب» است اگر دست کم ٪۹۰ اعداد آن ۱ باشد (و در نتیجه حداکثر ٪۱۰ آن ۰ باشد). می‌دانیم که آرایه‌یا ۰- غالب است یا ۱- غالب٬ ولی نمی‌دانیم کدام‌یک. چندتا از درایه‌های این آرایه را باید بررسی کنیم تا به طور قطع بتوانیم بگوییم که آرایه ۰- غالب است یا ۱- غالب؟
- ۱۹۱
- ۲۰۱
- ۲۱۰
- ۵۰۱
- ۹۰۱
پاسخ
گزینه (۲) درست است.
اگر آرایه صفر غالب باشد حداکثر ۱۰٪ آن یعنی ۱۰۰ تا یک و اگر ۱-غالب باشد حداکثر ۱۰۰ تا صفر دارد. حال چون می‌دانیم آرایه‌یا ۰-غالب است و یا ۱-غالب اگر در بررسی‌مان از هرکدام از صفرها یا یک‌ها بیش‌تر از ۱۰۰ تا داشته باشیم می‌توانیم با قطعیت بگوییم که آن غالب است. پس در بدترین شرایط $100+100+1$ یعنی ۲۰۱ بررسی لازم داریم.
| ▸ سوال قبل | سوال بعد ◂ |