به دلیل مکان نامناسب تاپیک بسته میشه؛
(۱۶ بهمن ۱۳۹۲ ۰۵:۱۰ ب.ظ)neda140781 نوشته شده توسط: دوستان ممنون میشم کمک کنید بگید راه حل این سوال چه جوریه؟ هر راهی رفتم به جواب نرسیدبدترین حالت واسه وقتی هست که شما آرایه رو از اول شروع کردی به جستجو و تا الان n/3 یک دیده باشی و n/2 صفر
(۱۶ بهمن ۱۳۹۲ ۰۵:۵۴ ب.ظ)masoud67 نوشته شده توسط:(16 بهمن ۱۳۹۲ ۰۵:۱۰ ب.ظ)neda140781 نوشته شده توسط: دوستان ممنون میشم کمک کنید بگید راه حل این سوال چه جوریه؟ هر راهی رفتم به جواب نرسیدبدترین حالت واسه وقتی هست که شما آرایه رو از اول شروع کردی به جستجو و تا الان n/3 یک دیده باشی و n/2 صفر
تو این حالت هنوز نمیتونی تشخیص بدی که نوع یک هست یا نوع دو
چون بر اساس تعداد یکها هنوز نمیشه تصمیم گرفت . ممکنه یه دونه یک دیگه بیاد و بشه n/3+1 و دیگه نوع دوم نباشه و یا اینکه دیگه یک نیاد و همین تعداد بمونه و دست آخر نوع دوم بشه
اما میریم سراغ صفرها. تاحالا n/2 صفر دیدم ولی هنوز مشخص نیست که نوع یک هست یا نوع دو. چون اگه بگیم نوع یک هست ، اگر یه دونه دیگه از آرایه رو خوندیم و صفر شد، دیگه نوع اول نیست چون n/2+1 عنصر صفر تا حالا خوندیم. یا شاید تا آخر آرایه دیگه صفر نیاد و همینجوری مقدار n/2 بمونه و نوع یک باشه
پس با خوندن یه دونه دیگه از آرایه تکلیف نوع آرایه مشخص میشه که تعداد عناصر خونده شده میشه n/2+n/3+1
اینکه از کجا بفهمیم بدترین حالت ، خوندن n/3 یک و n/2 صفر هست یه کم فکر میخواد و مفهوم نداره. یعنی باید یه کاری بکنی که هرچه بیشتر از عناصر آرایه رو بخونی ولی بازهم نتونی تشخیص بدی که نوع آرایه چی میشه.
