سوال برنامه نویسی:
۵۰۰۰۰۰ عدد که هر کدام در ۶۴ بیت جا می‌شوند داریم. تضمین میکنیم عددی بیش از ۲۵۰۰۰۰ بار (نصف تعداد اصلی) آمده. آن را پیدا کنید.
محدودیت حافظه: ۱ مگابایت
سلام:) . برای حل کردن این چند چیز باید بلد باشید :
- در کامپیوتر اعداد به صورت مبنای دو ذخیره می‌شوند. یعنی ۱۵ به صورت ۱۱۱۱ ذخیره میشود و به هر رقم آن بیت میگویند یعنی ۱۵، ۴ بیت دارد.(برای کسب اطلاعات بیشتر در گوگل مبنای دو یا اعداد باینری را سرچ کنید)
- به هر ۸ بیت، یک بایت میگویند . مثلا اینترنت ۱۶ مگابیتی(واحد انتقال داده) خریداری میکنید حداکثر سرعت دانلود شما ۲ مگابایت(واحد مرسوم حافظه) است!
- کامپیوتری که توانایی ذخیره ی ۶۴ بیتی را دارد، در صورت ذخیره ی عدد عادی و علامتدار(signed) بیت اول آن برای تعیین علامت عدد (مثبت یا منفی) و ۶۳ بیت دیگر را برای خود عدد اختصاص میدهد. یعنی حداکثر در نوع علامتدار میتواند ۲ به توان ۶۳ منهای ۱ را ذخیره کند(چرا؟) (در بعضی زبان ها مثل پایتون با متد Big Num میتوان عددهای بیشتری ذخیره کرد که البته دیگر عدد نیستند و سرعت کار کردن با آنها کند است.
- پس یعنی اگر یک آرایه ۵۰۰۰۰۰ تایی را بخواهیم ذخیره کنیم ۶۴×۵۰۰۰۰۰ بیت معادل ۸×۵۰۰۰۰۰ بایت نیاز داریم. یعنی ۴ میلیون بایت معادل ۴ مگابایت! پس عملا با توجه به محدودیت حافظه که ۱ مگابایت در سوال ذکر شده نمیتوانیم لیست اعداد را ذخیره کنیم.
راهنمایی : روی بیت های عددی که بیش از نصف بار تکرار شده و منطقا پرتکرار ترین عدد است حالت بتدی کنید
تذکر: برای درک بهتر مساله حداقل یک ربع روی مساله فکر کنید.
راه حل: بجای ذخیره کردن آرایه ی ۵۰۰۰۰۰ تایی یک آرایه ۶۴ بیتی میسازیم. شروع به خواندن اعداد میکنیم ولی آنهارا ذخیره نمیکنیم. هر عددی را که خواندیم بیت هایی که برای این عدد یک است را در آرایه ۶۴ تایی یکی اضافه میکنیم. یعنی در آخر شمرده ایم که هر بیت از بیت اول تا ۶۴ ام در چند عدد از لیست ۵۰۰۰۰۰ تایی آمده. حالا هر بیتی که بیش از ۲۵۰۰۰۰ بار ۱ باشد و شمرده باشیم یعنی قطعا عدد جواب نهایی هم در آن بیت ۱ است(اثبات ساده با برهان خلف)