3.7 / 5. 3

فهرست مطالب

فهرست مطالب

الگوریتم تشخیص عدد اول به زبان ساده به همراه جدول دیباگ

الگوریتم تشخیص عدد اول ، الگوریتمی است که بتواند تشخیص دهد آیا یک عدد اول است یا خیر. 

بر اساس تعریف، عدد اول یک عدد صحیح مثبت است که تنها بر خودش و ۱ تقسیم‌پذیر است. برای مثال، ۲، ۳، ۳، ۵ و ۷ اعداد اول هستند.

از طرف دیگر، برای فهم و تحلیل بهتر الگوریتم ها و اینکه بدانیم ایا نتیجه الگوریتمی که نوشته ایم درست می باشد، بهترین راه ترسیم جدول دیباگ است.

حالا بیایید، الگوریتم تشخیص عدد اول را بنویسیم و در هر مرحله جدول دیباگ را تکمیل کنیم.

1- الگوریتم تشخیص عدد اول

  • مرحله اول

مرحله اول دریافت ورودی می باشد. یعنی عددی که می خواهیم ببینیم اول است یا خیر. سپس، این عدد را در یک متغیر دلخواه مثل n قرار می دهیم(مثلا n=9).

حالا جدول دیباگ آن را به این شکل رسم می کنیم:

الگوریتم تشخیص عدد اول- به همراه جدول دیباگ
شکل 1- جایگزاری متغیر N در جدول دیباگ
  • مرحله دوم

در این مرحله ما نیاز به یک شمارنده داریم که مقدار اولیه آن یک و مقدار نهایی آن n می باشد. 

اسم این شمارنده دلخواه می باشد و من در اینجا نام آن را C می گذارم. مقدار اولیه این متغیر 1 می باشد (یعنی C=1).

همچنین مانند مرحل قبل، جدول دیباگ را تکمیل می کنیم:

الگوریتم تشخیص عدد اول- به همراه جدول دیباگ
شکل 2- جایگزاری متغیر C در جدول دیباگ
  • مرحله سوم

در مرحله سوم به یک شمارنده دیگر نیاز داریم که در اینجا من اسم آن را R می گذارم. 

این متغییر در واقع هر بار که باقیمانده n بر c ،برابر با صفر شود، به آن یک واحد اضافه می کنیم.

مقدار اولیه R برابر صفر است (یعنی R=0) و آن را مانند شکل زیر در جدول دیباگ اضافه میکنیم:

الگوریتم تشخیص عدد اول- به همراه جدول دیباگ
شکل 2- جایگزاری متغیر C در جدول دیباگ
  • مرحله چهارم

 عدد n را بر C تقسیم میکنیم اگر با قیمانده صفر بود، کارهای زیر را انجام میدهیم:

  • اگر حاصل باقیمانده ی n بر C برابر با صفر بود، به R یک واحد اضافه کن.
  • اگر C کوچکتر یا مساوی با n بود ، به C یک واحد اضافه کن و مرحله چهار را دوباره انجام بده . در غیر اینصورت اگر C با n برابر بود ، برو به مرحله پنچم.

این مرحله در واقع یک حلقه می باشد، یعنی چند دور اجرا می شود. در این جا، این حلقه را انقدر تکرار می کنیم تا c برابر با n شود.

حالا بیایید این مرحله را بیشتر بررسی و جدول دیباگ را با دقت و مرحله به مرحله تکمیل کنیم:

  • دور  اول

همانطور که در تصویر می بینید، در هنگام شروع الگوریتم مقدار n برابر با 9  و مقدار c برابر با 1 می باشد. 

حالا باید 9 را بر 1 تقسیم کنیم و ببینیم باقیمانده آن یک می شود یا نه.

در اینجا، باقیمانده صفر شده است، پس به r یک واحد اضافه می کنیم. همچنین، چون قرار است در قدم بعدی، ببینیم که 9 بر 2 بخش پذیر است یا نه، پس به c هم یک واحد اضافه می کنیم.

الگوریتم تشخیص عدد اول- به همراه جدول دیباگ
شکل 4- مرحله چهارم: دور اول
  • دور  دوم

در دور قبلی، مقدار c برابر با 2 شد. پس در این مرحله 9 را بر 2 تقسیم می کنیم. چون باقیمانده صفر نیست، پس به r هیچ مقداری اضافه نمی شود.

اما چون قرار است که در قدم بعدی ببینیم آیا 9 بر 3 بخش پذیر است یا خیر، پس به c یک واحد اضافه می کنیم.

الگوریتم تشخیص عدد اول- به همراه جدول دیباگ
شکل 5- مرحله چهارم: دور دوم
  • دور  سوم

در دور قبلی، مقدار c برابر با 3 شد. پس در این مرحله 9 را بر 3 تقسیم می کنیم. چون باقیمانده صفر است، پس به r یک واحد اضافه می شود و r می شود 2.

اما چون قرار است که در قدم بعدی ببینیم آیا 9 بر 4 بخش پذیر است یا خیر، پس به c یک واحد اضافه می کنیم.

الگوریتم تشخیص عدد اول- به همراه جدول دیباگ
شکل 6- مرحله چهارم: دور سوم
  • دور  چهارم تا دور نهم

حالا، دورها را انقدر تکرار می کنیم و در هر دور به C یک واحد اضافه می کنیم، تا  c بزرگتر از n شود.

سپس، می توانیم به مرحله پنجم برویم.

الگوریتم تشخیص عدد اول- به همراه جدول دیباگ
شکل 7- مرحله چهارم: دور چهارم تا نهم
  • مرحله پنجم

اگر R بزرگتر از 2 بود یعنی عدد به غیر از یک و خودش ، بر اعداد دیگری نیز بخش پذیر بوده است پس عدد اول نیست.
از طرف دیگر اگر R مساوی با 2 بود یعنی عدد فقط بر خودش و یک بخش پذیر بوده است پس عدد اول است.

همانطور که در جدول دیباگ مشاهده کردید، در دور نهم، مقدار R برابر با 3 شد و این بدین معناست که 9 به غیر از 1 و خودش بر عدد دیگری نیز بخش پذیر بوده است.

پس عدد 9، اول نمی باشد.

حالا شما الگوریتمی بنویسید که یک عدد را بگیرد و تعداد مقسوم علیه های آن را محاسبه کند(مثلا مقسوم علیه های عدد 8 عبارتند از 1،2،4،8 . پس عدد 8 دارای 4 مقسوم علیه می باشد) همچنین جدول دیباگ آن را رسم کنید.

مطالب مرتبط و تکمیلی: