الگوریتم پیدا کردن عضوی که بیش از نصف در دنباله آمده است

combinatorics

New Member
ارسال ها
199
لایک ها
268
امتیاز
0
#1
دنباله ای n عضوی داریم. الگوریتمی از اردر n ارایه دهید که عضوی را بیابد که در بیش از نصف دنباله آمده باشد.
توجه: اگر چنین عضوی وجود نداشت نیز باید بگویید وجود ندارد.
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#2
پاسخ : الگوریتم پیدا کردن عضوی که بیش از نصف در دنباله آمده است

میایم 2 تا 2 تا تقسیم می کنیم . بعد اگه دو تا عدد برابر بودن یکیش رو بر می داریم اون یکی رو کنار می ذاریم و اگه با هم فرق داشتن هر دو رو کنار می ذاریم(چون شرط حداکثر نصف بین دنباله جدید برقراره) . با این کار هر دفعه حداقل تعداد اعداد نصف می شه و با n-1 مرحله یک عدد باقی می مونه!

حالا میایم تعداد اون عدد رو در دنباله پیدا می کنیم اگه بیش از نصف بود که حله در غیر این صورت چنین عددی وجود نداره(چرا؟)

درسته یا جوب داره؟
 

combinatorics

New Member
ارسال ها
199
لایک ها
268
امتیاز
0
#3
پاسخ : الگوریتم پیدا کردن عضوی که بیش از نصف در دنباله آمده است

میایم 2 تا 2 تا تقسیم می کنیم . بعد اگه دو تا عدد برابر بودن یکیش رو بر می داریم اون یکی رو کنار می ذاریم و اگه با هم فرق داشتن هر دو رو کنار می ذاریم(چون شرط حداکثر نصف بین دنباله جدید برقراره) . با این کار هر دفعه حداقل تعداد اعداد نصف می شه و با n-1 مرحله یک عدد باقی می مونه!

حالا میایم تعداد اون عدد رو در دنباله پیدا می کنیم اگه بیش از نصف بود که حله در غیر این صورت چنین عددی وجود نداره(چرا؟)

درسته یا جوب داره؟
به نظر من درسته. ولی من یه راه دیگه دارم.
یه m و a تعریف می کنیم. در ابتدا m = 1 و a = a1 قرار می دهیم. بعد از عضو دوم شروع می کنیم. و جلو میریم. اگه m = 0 بود، m = 1 قرار میدیم و a = ai قرار میدیم. در غیر این صورت اگر a = ai بود m-- و در غیر این صورت m++. در انتها اگر دنباله چنین عضوی داشته باشد برابر با a است. (چرا؟)
حالا دوباره از اول دنباله میریم جلو تعداد اعدادی که با a برابرند رو می شمریم. اگه از نصف بیش تر بود میشه a و در غیر این صورت جوابی ندارد.
 
بالا