تشخیص عدد کامل در پایتون با توضیح کامل و کد
«عدد کامل» (Perfect Number)، عدد صحیح مثبتی است که با مجموع مقسومعلیههای خود بهجز خودش برابر است. کاربرد عدد کامل تا برنامهنویسی پایتون گسترش یافته است. در واقع عملیات تشخیص عدد کامل در پایتون به عنوان مسئلهای آموزشی برای تمرین و درک بهتر مفاهیم بنیادین همچون حلقهها، عبارات شرطی و توابع در پایتون بهکار گرفته میشود. در این مطلب از مجله فرادرس به مبحث اعداد کامل پرداختهایم. تلاش کردیم که از طریق این مطلب آموزشی بهطور کامل به اهمیت این اعداد و نقش قدرتمندشان در پرورش مهارتهای برنامهنویسی افراد بپردازیم.
عدد کامل به هر عددی میگویند که برابر با مجموع مقسومعلیههای خودش بهغیر از خودش باشد. این عدد باید صحیح و مثبت نیز باشد. در زبان برنامهنویسی پایتون این اعداد در تمرینات جذابی بهکار گرفته میشوند. این تمرینات باعث پیشرفت مهارتهای الگوریتمی و درک عددی میشوند. این نوع از اعداد برای دانشجویان برنامهنویسی تجربه یادگیری چالش برانگیز و ارزشمندی را فراهم میکنند.
تشخیص عدد کامل در پایتون چگونه است؟
برای تشخیص عدد کامل روشهای مختلفی وجود دارد که در طول زمان توسط ریاضیدانان کامل شده است. بعضی از این روشها توسط مهندسان برنامهنویسی بهصورت الگوریتمهای قابل فهم برای ماشین ترجمه شدهاند. در نهایت هم توسعه دهندگان پایتون این الگوریتمها را در زبان برنامه نویسی پایتون پیادهسازی کردهاند.
الگوریتمهای متفاوت پیچیدگیهای زمانی و فضایی متفاوتی نیز دارند. بعضی از الگوریتمهای مدرن میتوانند اعداد کامل بسیار بزرگ را نیز پیدا کنند. در فهرست زیر ۴ روش اصلی را نام بردهایم. در بخشهای بعدی مطلب این روشها را توضیح دادهایم.
- سنجش تقسیمی
- فرمول اقلیدسی
- آزمون لوکاس لمر
- منحنیهای بیضوی
تشخیص عدد کامل جزو مسائلی است که معمولا جنبه آموزشی دارند. از جمله مسائل آموزشی میتوان به جمع ارقام یک عدد در پایتون نیز اشاره کرد. کار کردن بر روی چنین مسائلی باعث میشود که برنامهنویسان روشهای طراحی الگوریتم و تفکر منطقی را در کنار هم تمرین کنند. این چنین مسائلی به ارتقا مهارت کدنویسی هم منتج میشوند.
تسلط به پایتون با فرادرس
برای اینکه بتوانیم بهطور بهتری مسائل و کدهای پیادهسازی شده در این مطلب را درک کنیم باید حداقل آشنایی را با زبان برنامهنویسی پایتون داشته باشیم. خوشبختانه بهجز مطالبی که در مجله فرادرس تهیه شدهاند، وبسایت آموزشی فرادرس نیز دورههای آموزشی خوبی را به اینمنظور تهیه کرده است. بهخصوص، کسانی که به تازگی با زبان برنامهنویسی پایتون آشنا شدهاند، میتوانند از فیلم آموزشی رایگان پایتون در ۱۴۰ دقیقه استفاده کنند. دورههای زیر نیز چند نمونه از فیلمهای آموزشی هستند که اگر در سطح مبتدی باشید برای شما بسیار مفید خواهد بود.
- فیلم آموزش برنامهنویسی پایتون، دوره مقدماتی فرادرس
- فیلم آموزش برنامهنویسی پایتون به همراه مثال های عملی فرادرس
برای افرادی که حرفهایتر هستند و میخواهند با مسائل پیشرفتهتری کار کنند میتوانیم از چند فیلم آموزشی دیگر مثال بزنیم.
- فیلم آموزش نکات برنامهنویسی پایتون و حل مسائل الگوریتمی فرادرس
- فیلم آموزش محاسبات عددی در پایتون فرادرس
- فیلم آموزش برنامه نویسی پیشرفته و ترفندهای Python فرادرس
چند نمونه از الگوریتم های تشخیص عدد کامل در پایتون
در این بخش به بررسی اعداد خواهیم پرداخت و میبینیم که چگونه میتوان کامل بودن عددی را مشخص کرد.
مثال اول: الگوریتم اولیه و ساده برای تشخیص عدد کامل در پایتون
این الگوریتم هم از جهت قابل درک بودن و هم از جهت پیادهسازی، سادهترین گزینه است. برای انجام این عملیات ۵ مرحله کلی وجود دارد.
- عدد را وارد کنید: با کمک تابع input در پایتون عدد صحیح مثبتی را از کاربر دریافت کنید. این عدد همان عددی خواهد بود که کامل بودن آن را بررسی میکنیم.
- مقسومعلیهها را پیدا کنید: در این مرحله باید همه مقسومعلیههای عدد داده شده را پیدا کنیم. مقسوم علیهها باید اعداد صحیح مثبت باشند و همچنین عدد دریافت شده بهطور کامل به آنها بخشپذیر باشد.
- مجموع مقسومعلیهها را محاسبه کنید: همه مقسومعلیهها به غیر از خود عدد را با یکدیگر جمع میبندیم و نتیجه را برای مقایسه نگهداری میکنیم.
- بررسی کامل بودن عدد: حاصل جمع بدست آمده از مقسومعلیهها را با عددی که از کاربر دریافت شده مقایسه میکنیم. اگر این دو مقدار با هم برابر بودند پس نتیجه میگیریم عدد اصلی از نوع اعداد کامل است.
- نمایش دادن نتیجه: در بخش آخر این برنامه در خروجی برای کاربر باید نتیجه کامل بودن یا نبودن عدد را نمایش دهیم.
کدی که در پایین دیده میشود، مراحل بالا را برای تشخیص عدد کامل در پایتون پیادهسازی کرده است.
در کد بالا فرایندی که اتفاق میافتد به شرح زیر است.
- تابع is_perfect_number() عددی را از ورودی تحویل میگیرد و به عنوان خروجی اگر عدد کامل بود مقدار True و در غیر این صورت مقدار False بر میگرداند.
- این کد در ابتدا همه مقسومعلیههای عدد ورودی را پیدا میکند. حاصل جمع آنها را محاسبه میکند و سپس حاصل جمع را با عدد اصلی که از ورودی دریافت شده مقایسه میکند.
- در این مرحله، کاربر «عدد صحیح» (Integer) مثبتی را وارد میکند و تابع فراخوانی میشود تا کامل بودن عدد وارد شده را بررسی کند.
- در نهایت با توجه به اینکه تابع مقدار Trueیا False برگردانده نتیجه بر روی خروجی توسط برنامه چاپ میشود.
به یاد داشته باشید که اعداد کامل نسبتا کمیاب هستند و با پیشروی در امتداد زنجیره اعداد کامل تمایل به بزرگتر شدن دائمی دارند. برای مثال چند عضو اول اعداد کامل بهصورت ۶، ۲۸، ۴۹۶ و ۸۱۲۸ هستند. برای همین با پیشروی در امتداد زنجیره تشخیص عدد کامل در پایتون میتواند کمی چالش بر انگیز باشد.
مثال دوم: در پایتون برای بررسی کامل بودن عدد داده شده
در کد پایین برنامهای نوشتیم که کامل بودن اعداد را بررسی میکند. فرایند اجرای عملیات این الگوریتم را در ۶ مرحله میتوان شرح داد. اول نگاهی به کد بیاندازید.
فرایند اجرای عملیات الگوریتم آمده در بالا را در پایین شرح دادهایم.
- در این مثال، تابع is_perfect_number() عددی را از ورودی تحویل میگیرد و به عنوان خروجی اگر عدد کامل بود مقدار Trueو در غیر این صورت مقدار False بر میگرداند.
- تابع در ابتدا بررسی میکند که آیا عدد ورودی کوچکتر یا مساوی صفر است یا نه. اگر این عدد از نوع اعداد صحیح مثبت نباشد، پس نمیتواند عدد کامل باشد. در نتیجه تابع مقدار False را بر میگرداند.
- سپس تابع شروع به پیمایش بر روی اعداد از عدد 1 تا یک واحد کمتر از عدد ورودی میکند. در این پیمایش به هر عددی که میرسد، مقسومعلیه بودنش را برای عدد وارد شده بررسی میکند.
- اگر عددی نسبت به عدد دریافت شده، مقسومعلیه بود آن عدد را به لیست اعداد مقسومعلیه divisors وارد میکند.
- بعد از پیدا کردن همه مقسومعلیهها، تابع حاصل جمع همه این اعداد را با یکدیگر محاسبه میکند.
- در نهایت، اگر حاصل جمع مقسومعلیهها برابر با عدد اصلی باشد تابع به نشانه کامل بودن عدد مقدار Trueرا بر میگرداند و در غیر این صورت مقدار False برگشت داده میشود.
به همین صورت، برنامه مقدار عدد ورودی را از کاربر دریافت میکند. سپس تابع را با ارسال عدد ورودی به آن فراخوانی میکند و مطابق با مقدار خروجی تابع، نتیجه را در خروجی نمایش میدهد.
مثال سوم: برای تشخیص عدد کامل در پایتون
در ابتدا به کد زیر که نمایانگر روش دیگری برای تشخیص عدد کامل در پایتون است توجه کنید. تلاش کنید تا عملکرد کد را درک کنید. البته در ادامه مطلب رفتار کد را بهصورت کلی در چند بند توضیح دادهایم. میتوانید دانستههای خود را با توضیحات بعدی مقایسه کنید.
فرایند اجرای عملیات الگوریتم بالا را در پایین توضیح دادهایم.
- در این مثال، تابع is_perfect_number() عددی را از ورودی تحویل میگیرد. به عنوان خروجی اگر عدد کامل بود مقدار Trueو در غیر این صورت مقدار False بر میگرداند.
- برنامه در ابتدا بررسی میکند که آیا عدد ورودی کوچکتر یا مساوی صفر است. اگر این عدد از نوع اعداد صحیح مثبت نباشد، پس نمیتواند عدد کامل نیز باشد. در نتیجه تابع مقدار False را بر میگرداند.
- اگر این عدد از نوع اعداد صحیح مثبت باشد، پس لیست خالی به نام divisors ایجاد میکنیم تا مقسومعلیههای عدد ورودی را در این لیست ذخیره کنیم.
- سپس تابع شروع به پیمایش بر روی اعداد از عدد 1 تا یک واحد کمتر از عدد ورودی میکند. در این پیمایش به هر عددی که میرسد به کمک تکه کد number % i == 0 بررسی میکند که آیا جزو مقسوم علیههای عدد اصلی است یا نه. اگرنتیجه Trueبود به این معنی است که این عدد باید در لیست مقسومعلیهها به نام divisors وارد شود.
- بعد از اینکه همه مقسوم علیهها را پیدا کردیم. با استفاده از تابع sum() حاصل جمع همه این مقسوم علیهها را با یکدیگر محاسبه میکنیم.
- سپس در صورتی که حاصل جمع همه اعداد برابر با مقدار عدد اصلی باشد، تابع مقدار True را بر میگرداند. برگرداندن مقدار Trueبه معنی این است که عدد از نوع اعداد کامل است. در غیر این صورت تابع مقدار False را بر میگرداند.
بررسی مثالها
در مثال اول کامل بودن عدد ۶ را بررسی میکنیم. از آنجا که مقسومعلیههای عدد ۶ برابر با ۱، ۲ و ۳ هستند و مجموع این اعداد برابر با عدد ۶ میشود در نتیجه ۶ عددی کامل است. در خروجی پیغام 6 is a perfect number. نمایش داده میشود. در مثال دوم کامل بودن عدد ۲۸ را بررسی میکنیم. مقسوم علیههای عدد ۲۸ برابر با ۱، ۲، ۴، ۷ و ۱۴ هستند. مجموع این اعداد نیز برابر با مقدار ۲۸ میشود. بنابراین در خروجی برنامه پیغام 6 is a perfect number. چاپ میشود.
الان میتوانیم از تابع is_perfect_number() برای بررسی کامل بودن هر عدد صحیح مثبتی استفاده کنیم.
مثال چهارم: راه حل بهینه برای تشخیص عدد کامل در پایتون
رویکرد سنتی برای تشخیص عدد کامل در پایتون شامل پیدا کردن مقسومعلیههای آن عدد و جمع بستن آنها با یکدیگر میشود. اگرچه که راه بهینهسازی شدهای هم برای تشخیص کامل بودن اعداد وجود دارد. برای این کار باید به ويژگی ریاضی مرتبط با اعداد زوج توجه کنید. به این نکته دقت کنید که همه اعداد کامل شناخته شده زوج هستند.
بیان ویژگی ریاضی: هر عدد کاملی شامل فرمول2**(p-1) * ((2**p)-1) است. به شرطی که هر دو معادله 2**(p-1) و (2**p)-1 از نوع اعداد اول باشند. در ضمن خود p نیز باید عدد اول باشد.
در کد پایین میتوانید روش پیادهسازی این رویکرد کارآمد را برای حل مسئله ببینید.
توضیح مراحل بالا در زیر آورده شده است.
- در این الگوریتم در خطهای اول کد تابع is_prime() برای تشخیص عدد اول بهکار گرفته میشود. این تابع از این قانون طبعیت میکند که همه اعداد اول بزرگتر از ۳ میتوانند به شکل 6k±1 نوشته شوند.
- در این مثال، تابع is_perfect_number() عدد صحیح مثبتی را از ورودی دریافت میکند. اگر عدد کامل بود مقدار Trueو در غیر این صورت مقدار False را به عنوان خروجی بر میگرداند.
- درون تابع از p=2 شروع میکنیم و بررسی میکنیم که آیا مقدار 2**(p-1) * ((2**p)-1) کوچکتر یا مساوی مقدار ورودی است یا نه.
- اگر جواب در مرحله قبل مثبت بود این بار اول بودن اعداد p و 2**(p-1) را با استفاده از تابع is_prime() بررسی میکنیم.
- در صورت برآورده شدن همه شرایط بالا میتوانیم در نهایت نتیجه بگیریم که عدد ورودی از نوع عدد کامل است.
چند الگوریتم برای تشخیص پیچیدگی عدد کامل در پایتون وجود دارد؟
میزان پیچیدگی تشخیص اعداد کامل در پایتون وابسته به الگوریتمی است که استفاده میکنیم. چندین الگوریتم مختلف برای بررسی کامل بودن اعداد وجود دارد. در ادامه چهار مورد از این الگوریتمها را معرفی کردهایم.
- «سنجش تقسیمی» (Trial Division): این روش رویکرد بسیار مستقیمی برای حل مسئله دارد. در واقع بر روی همه مقسومعلیههای ممکن پیمایش و بررسی میکنیم که آیا مجموع این مقسومعلیهها برابر با عدد اصلی هست یا نه. پیچیدگی زمانی این روش تقریبا برابر با O(n) است. در اینجا n همان عددی است که بر روی آن بررسی انجام میدهیم.
- «فرمول اقلیدسی» (Euclidean Formula): این فرمول اعداد کامل زوج را به کلاس خاصی از اعداد اول مربوط میکند. این روش از روش «سنجش تقسیمی» (Trial Division) سریعتر عمل میکند اما به اندازه الگوریتمهای مدرنتر کارآمدی ندارد. پیچیدگی این الگوریتم بسته به جزییات پیادهسازی تغییر میکند.
- «آزمون لوکاس لمر» (Lucas-Lehmer): این متد برای پیدا کردن اعداد کامل زوجی استفاده میشود که با اعداد اول «مرسن» (Mersenne) در ارتباط هستند. این روش از روشهای قبلی بسیار سریعتر عمل میکند و پیچیدگی زمانیاش برابر با O(log^2n) است.
- «منحنیهای بیضوی» (Elliptic Curves): این روش پیشرفته از تکنیک منحنی بیضوی برای پیدا کردن اعداد کامل استفاده میکند. این روش بهطرز چشمگیری سریعتر از روشهای قبلی عمل میکند و برای کشف اعداد کامل بزرگ استفاده میشود. این روش پیچیدگی بیشتری دارد اما از روشهای قبلی برای پیدا کردن اعداد کامل بزرگ بسیار سریعتر کار میکند.
پیچیدگی الگوریتمهای تشخیص عدد کامل، بسته به الگوریتمی که انتخاب کردهایم و عدد مورد بررسی تغییر میکند. الگوریتمهای مدرن میتوانند بهصورت کارآمدی اعداد کامل بزرگ را پیدا کنند، اما پیچیدگی دقیق عملیات، وابسته به جزییات الگوریتم مورد استفاده است.
بهطور خلاصه، پیچیدگی زمانی بررسی کامل بودن اعداد میتواند از O(n) برای سنجش تقسیمی پایه تا الگوریتمهای توسعهیافتهتر با پیچیدگیهای زمانی بسیار بهتر تغییر کند. به یاد داشته باشید همانطور که فضای جستوجو بهطور قابل توجهی بزرگتر میشود باید از الگوریتمهای پیشرفته و مدرن برای پیدا کردن اعداد کامل بسیار بزرگ استفاده کرد. همه این الگوریتمها برای تشخیص عدد کامل در پایتون قابل پیادهسازی هستند.
اگر به کار کردن با الگوریتمها -که مشخصه برنامهنویسان حرفهای است- علاقهمند باشید، بهتر است از فیلم آموزش رایگان داده ساختارها و الگوریتم ها در برنامه نویسی پایتون که در سایت فرادرس تهیه شده نیز استفاده کنید. این دوره تاثیر بسیار خوبی در آشنایی و افزایش مهارت کار با الگوریتمها دارد.
اعداد کامل چه کاربردی دارند؟
از آنجا که اعداد کامل در ریاضیات به عنوان یکی از مفاهیم جذاب و جاودانه ریاضی، اهمیت بسیاری دارند. در پایتون هم کاربردهای خاص خود را پیدا کردهاند. این اعداد برای قرنهای موضوع تحقیقات ریاضی بهطور ویژه درباره تئوری اعداد بودهاند.
چون که اعداد کامل در ریاضیات ریشهدار شدهاند، برنامههای کاربردی مختلفی در زبان برنامهنویسی پایتون و سایر زبانهای برنامهنویسی با موضوعات مختلف در ارتباط با اعداد کامل طراحی شده است.
- تحقیقات ریاضی: اعداد کامل برای قرنها یکی از موضوعات مطالعات ریاضی بودهاند. این اعداد در شاخهای از ریاضیات به نام نظریه اعداد مورد مطالعه قرار گرفته و با ویژگیها و مفاهیم ریاضی گستردهای ارتباط برقرار کردهاند.
- الگوریتمهای نظریه اعداد: در علوم کامپیوتر و ریاضیات، اغلب اوقات الگوریتمها برای شناسایی نوع خاصی از اعداد، مانند مبحث تشخیص عدد کامل در پایتون، بهکار گرفته میشوند. وقتی در حال توسعه الگوریتمهایی در ارتباط با نظریه اعداد باشیم دانستن روش کار با اعداد کامل میتواند بسیار ارزشمند و مفید باشد.
- تمرین کدنویسی: پیادهسازی الگوریتمهایی که اعداد کامل را پیدا میکنند میتواند یکی از پرفایدهترین روشهای تمرین کدنویسی محسوب شود. اجرای این عملیات به برنامهنویسها کمک میکند که بر روی مهارتهایشان تمرین کنند. مخصوصا مهارتهایی مانند استفاده از حلقهها، عبارتهای شرطی و عملیات محاسباتی ریاضی که در این الگوریتمها بهکار میروند.
- طبقهبندی اعداد: اعداد کامل نوعی از اعداد هستند که قابل طبقهبندیاند. پیادهسازی توابع برای بررسی کامل بودن اعداد یا توابعی که اعداد کامل را درون محدوده خاصی پیدا میکنند، میتوانند به اجرای برنامههای بسیار زیادی کمک کند.
- اهداف آموزشی: اعداد کامل معمولا در فضاهای آموزشی برای آموزش مفاهیم برنامهنویسی و ویژگیهای ریاضی بهکار میرود. این نوع از اعداد معمولا به عنوان مثال در دروههای آموزشی و تمرینی استفاده میشوند.
- معماها و سرگرمیهای ریاضی: اعداد کامل برای حل معماهای ریاضی یا مسائل مربوط به سرگرمیهای عملی و ریاضی نیز استفاده میشوند. این اعداد موضوع مورد علاقه مردمی هستند که از بررسی الگوها و خواص ریاضیات به عنوان سرگرمی لذت میبرند.
- کارایی الگوریتمها: دنبال کردن اعداد کامل بزرگتر شامل بهینهسازی الگوریتمها برای بدست آوردن کارایی بیشتر است. این تمرین میتواند مهارتهای حل مشکل الگوریتمها را تقویت کند و باعث ایجاد دستاوردهای مثبتی در رشته طراحی الگوریتم شود.
- کاربردهای «بین رشتهای» (Cross-Disciplinary): اعداد کامل، پلی بر روی فاصله بین ریاضیات و علوم کامپیوتر میزنند. این اعداد با اعداد اول، رمزنگاری و حوزههای دیگری نیز ارتباط دارند. این مسئله باعث اهمیتیافتن آنها در رشتههای مختلف مطالعاتی میشود.
- مدلسازی ریاضی: مفاهیمی مانند اعداد کامل و نظریه اعدادِ مرتبط، با اینکه بهطور مستقیم قابل استفاده نیستند اما در مدلسازیهای ریاضی برای سیستمهای بر پایه تکنولوژی بالا بهکار برده میشوند. برای مثال میتوان از سیستمهایی مانند سامانههای تحلیل شبکه یا بهینهسازی دادهها نام برد.
آموزش های تکمیلی پایتون
در این قسمت از مطلب، به عنوان آموزشهای تکمیلی پایتون چند مورد از فیلمهای آموزشی پروژه محور فرادرس را معرفی کردهایم. این فیلمهای آموزشی از ابتدا تا انتهای مراحل کدنویسی پروژه را نمایش میدهند و از سادهترین تکنیکهای برنامهنویسی مانند تعریف متغیر تا تکنیکهای پیچیده را نمایش میدهند. به همین دلیل، گزینه بسیار مناسبی برای تمرین همه آموختههای دانشجویان برنامهنویسی پایتون هستند.
- فیلم آموزش درباره هفت پروژه کاربردی با تکنولوژی شی گرایی در پایتون فرادرس
- فیلم آموزش پروژه محور ساخت کتابخانه با کتابخانه Tkinter در پایتون فرادرس
- فیلم آموزش ساخت بازی Snake در پایتون فرادرس
- فیلم آموزش پروژه محور پایتون درباره طراحی گرافیکی با PyQt و بدون کدنویسی با QT Designe فرادرس
جمع بندی
عملیات تشخیص عدد کامل در پایتون شامل ترکیبی از مهارتهای ریاضی و برنامهنویسی است. این اعداد برابر با مجموع مقسومعلیههای خود بهجز خودشان هستند. اعداد کامل هم برای کدنویسی و هم برای یادگیری خارقالعادهاند. این اعداد بین دنیای ریاضی و زبان برنامهنویسی پایتون ارتباط برقرار میکنند.
فراتر از ارزش آموزشی که این اعداد دارند در توسعه الگوریتمها، تحقیقات ریاضی و پُر کردن فاصله بین نظریه و عمل نیز بهصورت گستردهای کاربرد دارند. این مجموعه از خواص باعث شده که فرایند تشخیص عدد کامل در پایتون به موضوعی جالب برای پژوهش و ارزشمند برای تقویت مهارتهای برنامهنویسی تبدیل شود.
چه عاشق ریاضی باشیم و چه یکی از دوستداران پایتون، در این مطلب از مجله فرادرس درباره مبحثی صحبت شده که تواناییهای حل مسئله این دو قشر را به چالش میکشد.