اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.
پرسش: برای یک عدد صحیح n، یک مبنای خوب k مبنایی است که همه ارقام عدد n در آن مبنا 1 باشد. برنامه ای بنویسید که یک رشته از ارقام را به عنوان n دریافت کند و کوچکتری مبنای خوب آن را برگرداند.
مثال: برای عدد 'n='13 پاسخ `3` می باشد زیرا ۱۳ در مبنای ۳ برابر 111 می باشد.
توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید و از این لینک به مساله دسترسی پیدا کنید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.
زمان بندی: ارسال پاسخ ها تا پایان روز 13 آوریل
یادآوری: انتخاب جواب بهتر بر اساس اولین پاسخ کامل هست. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح مختصری از حل خود را بنویسید و ارسال کنید.
توجه توجه: تبادل اطلاعات زیر این پست کاملا آزاد است. می توانید تکه کدهای خود را تبادل کنید، یا هرسوالی دارید بپرسید. اگر سوالی هم از من دارید من را بصورت #حسین تگ کنید.
ایشون درست و کامل مساله را حل کردن و تشریح راه حل رو نوشتند. تشریح حل مساله رو من در ویرایش و ساده سازی کردم.
ایمان فراحی http://professionalProgrammer.ir یک برنامه نویسی فوق العاده است و ریاضی اش هم خیلی خوبه و می تونه هم مسایل رو فرمول کنه و هم پیاده سازی کنه!
به Iman تبریک می گم و بهش می گم: عالی هستی! ادامه بده!
حل مساله را با یک مثال شروع میکنیم تا مطمئن شویم که مسئله را خوب درک کرده ایم. برای ورودی n=13 در مبنای 10، می توانیم آن را در مبناهای دیگر در نظر بگیریم. کوچکترین مبنای ممکن 2 می باشد. نمایش 13 در مبنای 2 به صورت 1101، و در مبنای 3 بصورت 111 می باشد. در این روند، با توجه به اینکه مبنای 3 اولین مبنایی است که تبدیل 13 به آن تنها شامل 1 می باشد، 3 جواب درست می باشد. بعنوان مثال دیگر، برای n=12 تبدیل آن به مبناهای دیگر را از مبنای 2 تا یافتن عددی متشکل از تنها 1 نشان می دهیم:
1100, 110, 30, 22, 20, 15, 14, 13, 12, 11
اولین مبنا که در آن 12 تنها از 1 تشکیل می شود مبنای 11 است. بنابراین پاسخ 11 می باشد. با این مثال همچنان متوجه می شویم که نمایش عدد 12 در مبنای 1-12=11 تنها شامل رقم 1 می باشد. اگر دقیق تر نگاه کنیم، نمایش هر عدد n در مبنای n-1 بصورت 11 می باشد. بنابراین برای هر ورودی n ، این مسئله یک پاسخ دارد که عددی است بین 2 تا n-1.
شناسایی مسئله در قالب این مثالها کمک می کند که ساده ترین الگوریتم، یعنی جستجوی کامل را ارائه نماییم. در این روش از مبنای دو شروع می کنیم و برای مبناها حداکثر تا مبنای n-1 مقدار عدد داده شده n رو توی اونها بدست می آوریم. هر وقت به یک عدد با همه ارقام 1 رسیدیم آن مبنا را به عنوان حاصل برمی گردونیم. در این روش n-2 (در بدترین حالت) مبنا برای یک عدد حساب می شود که برای محاسبه هر کدام (log(n محاسبه لازم است، زیرا سقف لگاریتم x در مبنای 2 برابر طول رشته اعداد ما در مبنای 2 (بدترین حالت) است.. بنابر این پیچیدگی کل این الگوریتم (O(log(n)*n می باشد.
مشکل این روش آن است که باید معادل عدد داده شده را در همه 2-n مبنا بین 2 تا 1-n محاسبه کند در حالی که تنها log(n)-1 رشته ممکن به عنوان نمایش عدد در مبنایی که پاسخ مسئله هست وجود دارد. بعنوان مثال، نمایش های مرتبط معادل 12 شامل 1111، 111 و 11 می باشند.
این مشاهده جرقه ارائه راه سریع تری برای حل این مسئله است. در واقع باید از طولانی ترین نمایش محتمل برای عدد n که شامل تنها 1 باشد شروع کنیم. برای هر چنین نمایشی باید بررسی کنیم که آیا مبنایی وجود دارد که این نمایش در آن معادل با مقدار n باشد. این کار را تا کوتاهترین نمایش محتمل عدد n که شامل تنها 1 می باشد (یعنی "11") ادامه می دهیم. بنابر این اولین نمایش متشکل از تنها 1 که مبنایی برای آن یافت شود پاسخ مسئله می باشد.
به عنوان مثال، برای یافتن پاسخ برای عدد 12 باید از طولانی ترین نمایش محتمل آن یعنی 1111 شروع کنیم. تعداد ارقام مربوط به طولانی ترین رشته احتمالی از 1 ها، سقف لگاریتم 12 در مبنای 2 می باشد. یک روش برای بررسی اینکه آیا مبنایی وجود دارد که در آن مقدار 1111 برابر 12 شود آن است که از مبنای 2 شروع کنیم و عدد 1111 را به آن مبناها محاسبه کنیم. در این صورت، با محاسبه 1111 در مبنای 2 به مقدار 15 میرسیم که از عدد 12 بیشتر است. مطمئنا تبدیل 1111 به مبناهای بزرگتر عدد بزرگتری را تولید خواهد کرد. به این دلیل نتیجه می گیریم که هیچ مبنایی وجود ندارد که در آن 1111 معادل عدد 12 شود.
با اندکی تامل متوجه می شویم که اگر برای طول رشته m+1 متشکل از تنها ارقام 1 مبنای k ای وجود داشته باشد که برابر n شود، خاصیت زیر برای آن صادق است:
بر اساس فرمول اصلی، مشاهده می کنیم که:
همچنین
در نتیجه نامساوی زیر برقرار است:
اگر از طرفین ریشه m ام بگیریم خواهیم داشت:
بنابر این ریشه mام n بین دو عدد متوالی k و k+1 قرار می گیرد. در نتیجه خواهیم داشت:
نتیجه اصلی این است که اگر برای رشته با m رقم 1 مبنای k ای وجود داشته باشد که در آن مقدار رشته معادل n شود، آن مبنا برابر است با ریشه m ام مقدار n.
می توانیم الگوریتم را با همین مشاهده بصورت زیر پیاده سازی نماییم.
ابتدا رشته ورودی عددی را به عدد تبدیل می کنیم (خط 3). سپس در یک حلقه کاهشی از رشته با حداکثر طول تا رشته با طول 2 (مربوط به رشته در مبنای n-1) متشکل از رقم 1 محاسبات زیر را تکرار می کنیم (خط 4 تا 7). برای هرچنین رشته ای مبنای k که گزینه ممکن برای تبدیل احتمالی آن به n در مبنای 10 هست را بدست می آوریم (خط 5). آنگاه محاسبه می کنیم که آیا رشته در مبنای k واقعا معادل n در مبنای 10 می باشد؟ (خط 6).برای این کار از عبارت سمت راست فرمول اصلی استفاده می کنیم. اگر رشته به طول m متشکل از تنها 1 در مبنای k معادل n در مبنای 10 شد، آنگاه مقدار k پاسخ مورد نظر است.
در الگوریتم ارایه شده، برای هر m باید مقدار k را بدست آوریم و سپس بررسی کنیم که آیا رشته متشکل از m تا رقم 1 برابر با n می شود. برای این کار باید رشته را طبق عبارت سمت راست فرمول اصلی تبدیل به مبنای 10 کنیم که زمان بر است.
اما یک مشاهده کمک می کند که این محاسبه را تسریع کنیم. عبارت سمت راست فرمول اصلی در واقع یک دنباله هندسی است. با استفاده از فرمول جمع دنباله هندسی خواهیم داشت:
بنابر این تبدیل رشته با تمام ارقام 1 به راحتی با استفاده از فرمول فوق انجام می شود.
با جایگزینی فرمول بالا در خط 6 برنامه خواهیم داشت:
با توجه به اینک در الگوریتم فوق یک حلقه تکرار داریم که (log(n بار تکرار می شود، درنتیجه پیچیدگی محاسباتی این الگوریتم ((O(log(n می باشد.
