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

[combinatorics]

دنباله ای n عضوی داریم. الگوریتمی از اردر n ارایه دهید که عضوی را بیابد که در بیش از نصف دنباله آمده باشد.
توجه: اگر چنین عضوی وجود نداشت نیز باید بگویید وجود ندارد.

 

[rezashiri]

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

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

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

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

 

[combinatorics]

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

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

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

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

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