اعداد Hamming اعدادی هستند که بر پایه 2، 3 و 5 ساخته میشوند و فرمول آنها برابر است با:
مقادیر i و j و k از صفر به بالا هستند.
کوچکترین عدد hamming زمانی ساخته میشه که i و j و k صفر باشند و عدد یک به دست می آید که اولین عدد hamming حساب میشود.
دومین عدد hamming زمانی ساخته میشه که i برابر یک باشد و j و k صفر باشند. بنابر این عدد 2، دومین عدد hamming حساب میشود.
و به همین ترتیب رشته ای مرتب از کوچک به بزرگ به دست می آید که اعداد همینگ را شامل میشود.
میخواهیم تابعی بنویسیم که به ازای دریافت n (عددی طبیعی و بزرگتر از صفر)، nامین عدد همینگ را برگرداند.
الگوریتم تست همینگ بودن یک عدد ساده است. عدد را تا زمانی که بر 2 تقسیم پذیر باشد، بر 2 تقسیم میکنیم. بعد تا زمانی که بر 3 تقسیم پذیر باشد بر 3 تقسیم میکنیم. همین کار را برای 5 هم انجام میدهیم. اگر عدد نهایی برابر با یک بود، عدد مورد نظر ما عدد همینگ است.
اولین راه حلی که به نظر من رسید، این بود که به ازای یک حلقه بینهایت روی اعداد طبیعی بالا بروم و هر عدد را بررسی کنم که همینگ هست یا نه ، اگر همینگ بود یک تناظر به رشته همینگ اضافه میکنم. آن قدر ادامه میدهم تا به n اُمین عدد برسم.
این راه حل به نظر ساده می آید ولی به شدت زمانبر است. فرض کنید بخواهید همینگ 5000 را پیدا کنید. عدد متناظر آن 50837316566580 است و برای پیدا کردن hamming(5000)، باید از یک تا عدد گفته شده، تک تک اعداد را بررسی کنیم که همینگ هستند یا خیر. و اگر بخواهیم 5000 بار تابع را فراخوانی کنیم، به timeout میخوریم.
راه حل بهینه تری که به ذهنم رسید، این بود که روی ساخت اعداد همینگ (i و j و k) جلو بروم و nاُمین عدد همینگ را بسازم. برای این راه حل، فرض کنیم که یک عدد همینگ بنام h داریم. از این عدد، میتوانیم به سه عدد همینگ دیگه برسیم
h*2
h*3
h*5
حالا فرض کنیم آرایه ای داریم بنام sortedArray، از اعداد همینگ پیدا شده که از کوچک به بزرگ مرتب شده اند و سه عدد پیدا شده از عدد همینگ h را داخل این آرایه بگذاریم. در واقع الگوریتم نهایی این طوری میشه که هر بار اولین عنصر این آرایه (h0) را از داخل آرایه برمیداریم، داخل رشته همینگ میگذاریم و سه عدد بر اساس h0 تولید میکنیم و در آرایه مرتب شده قرار میدیم. قبل از اینکه سراغ تکرار این داستان برویم، چک میکنیم که nاُمین عدد همینگ موجود هست یا نه. اگر بود، برنامه را قطع و عدد را برمیگردانیم.
وقتی راه حل های دیگه رو بررسی کردم، به راه حلی رسیدم که فکم افتاد. چقدر ساده تر میشد به قضیه فکر کرد.
واقعا از این الگوریتم نهایی لذت بردم و امیدوارم شما لذت برده باشید :)
