الگونَوَرد ۱۰ (حل شد): تعداد اعداد با ارقام یکتا

اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.

دسترسی و حل سوال از منبع اصلی

پرسش: یک عدد صحیح نامنفی n داده شده است. تعداد اعداد با ارقام یکتا بین صفر تا ۱۰ به توان n را بیابید.

توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.

زمان بندی: ارسال پاسخ ها تا پایان روز 8 ژوئن

نکات مهم:

• انتخاب برنده هر هفته بر اساس اولین پاسخ کامل هست که شرح حل مساله را فراهم آورد. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح حل خود را زیر پست بنویسید. تنها زبان برنامه نویسی مورد قبول پایتون می باشد.
• طبق روال برنده مسابقه هر هفته پس از انتخاب باید شرح کامل حل مساله را بنویسد. در انتها من شرح مساله نوشته شده را ویرایش و ارسال خواهم کرد.
• لطفا خودتان مسایل را حل کنید و پاسخ را ارسال نمایید. استفاده از پاسخ های دیگر و ارسال آن جهت الگونوردی با اهداف این حرکت مغایرت دارد. لطفا در این زمینه همکاری نمایید. با ارسال پاسخ زیر این پست تایید می کنید که کد متعلق به خودتان هست و آنرا شخصا حل کرده اید.
• بحث های علمی زیر این پست کاملا آزاد است. اگر در مورد نحوه مدیریت این حرکت پیشنهادی دارید به ایمیل من s.h.siadaty@gmail.com ارسال نمایید.

قوانین اهدای جایزه:

• مبلغ جایزه نقدی 50,000 تومان می باشد.
• تنها یک نفر برنده برای هر هفته اعلام خواهد شد که طبق اولین پاسخ درست و شرح خلاصه می باشد.
• جهت ایجاد مشارکت، در هر فرد تنها می تواند یکبار برنده جایزه در طول یک ماه باشد.
• جایزه نقدی تنها در صورت نوشتن شرح کامل مساله تقدیم خواهد شد.

حل مساله

الگونورد برتر: الگونورد برتر الگونورد 9، کاربر با ای دی ariaman5 هست.

ایشون درست و کامل مساله را حل کردن و تشریح راه حل رو نوشتند. شرح مساله را با ویرایش من می خونید.

به ایشون تبریک می گم و بهش می گم: عالی هستی! ادامه بده!

و حالا شرح پاسخ:

حل مساله را با یک مثال شروع میکنیم تا مطمئن شویم که مسئله را فهمیده ایم. اگر n برابر 1 باشد باید اعداد یک رقمی (شامل 0 تا 9) که رقم تکراری ندارند را بشماریم. این تعداد برابر ۱۰ می باشد. ساده ترین روش حل این مساله این است که اعداد 0 تا

 را یک به یک بررسی کنیم و آنهایی که رقم تکراری ندارند را بشماریم. قطعه کد زیر این الگوریتم جستجوی کامل را پیاده سازی می کند.

علت اینکه نیاز به بررسی اعداد بزرگتر از

نمی باشد آن است که برای اعداد با تعداد ارقام بزرگتر از ۱۰ حتما یک رقم تکراری دارند. این الگوریتم بسیار کند است زیرا در بدترین حالت نیاز به مقایسه میلیارد عدد می باشد.

روش سریعتر استفاده از اصول شمارش در ریاضیات گسسته می باشد. برای این کار باید تعداد اعداد X رقمی با ارقام یکتا را برای X های بین 1 تا n (که در آن n حداکثر 10 می باشد) محاسبه کنیم. مثلا برای شمارش تعداد تا 5 رقم که ارقام تکراری ندارند باید تعداد اعداد یک رقمی، دو رقمی، سه رقمی، چهار رقمی و ۵ رقمی که رقم تکراری ندارند را جدا از هم بشماریم و نهایتا با جمع این تعداد حاصل را محاسبه نماییم.

حال باید راه حلی را بیابیم که تعداد اعداد X رقمی با ارقام یکتا را بشماریم. به عنوان مثال تعداد اعداد سه رقمی با ارقام یکتا با استفاده از اصل شمارش به این صورت است:

از چپ به راست اولین رقم می تواند یک از ارقام 1 تا 9 باشد. بنابر این 9 انتخاب داریم. رقم بعدی می تواند یکی از 9 رقمی که قبلا استفاده نشده اند (یعنی 8 رقم باقیمانده مابین 1 تا 9 و همچنین 0 که در رقم سمت چپ استفاده نشد). بنابراین 9 انتخاب داریم. برای موقعیت بعدی یکی از 8 رقم استفاده نشده در دو جایگاه قبلی قابل استفاده اند. بنابر این جواب نهایی 9x9x8 می باشد.

برای یک عدد 4 رقمی این فرمول برابر است با 7*8*9*9 بنابر این از نتایج محاسبات برای تعداد ارقام عدد X رقمی می توان برای محاسبه تعداد اعداد X+1  رقمی با ارقام غیر تکراری استفاده نمود.

بنابراین برای هر عدد یک تا n رقمی این فرمول رو حساب کنیم و تعداد آنها را به هم جمع کنیم و جواب نهایی را بدست آوریم.