مقدمه ای بر الگوریتم ها

به‌دست: Admingfars
خرداد ۳۱, ۱۴۰۱
دسته‌بندی: برنامه نویسی

برنامه نویسی

الگوریتم چیست؟ مبانی الگوریتم

کلمه Algorithm به معنای ” مجموعه قوانینی است که باید در محاسبات یا سایر عملیات حل مسئله رعایت شود ” یا ” رویه ای برای حل یک مسئله ریاضی در تعداد محدودی از مراحل که اغلب توسط عملیات بازگشتی ” انجام می شود.

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

الگوریتم ها می توانند ساده و پیچیده باشند بسته به آنچه می خواهید به دست آورید.

الگوریتم چیست؟

این را می توان با مثال پختن یک دستور جدید فهمید. برای پختن یک دستور جدید، دستورالعمل ها و مراحل را می خوانند و آن ها را یکی یکی و در ترتیب داده شده اجرا می کنند. نتیجه ای که به این ترتیب به دست می آید، غذای جدید است که کاملاً پخته شده است. هر بار که از تلفن، رایانه، لپ تاپ یا ماشین حساب خود استفاده می کنید، از الگوریتم ها استفاده می کنید. به طور مشابه، الگوریتم ها به انجام یک کار در برنامه نویسی برای دریافت خروجی مورد انتظار کمک می کنند.

الگوریتم طراحی‌شده مستقل از زبان هستند، یعنی دستورالعمل‌های ساده‌ای هستند که می‌توانند در هر زبانی پیاده‌سازی شوند، اما خروجی همان‌طور که انتظار می‌رود، یکسان خواهد بود.

ویژگی های یک الگوریتم چیست؟

ویژگی های یک الگوریتم

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

واضح و بدون ابهام: الگوریتم باید واضح و بدون ابهام باشد. هر یک از مراحل آن باید از همه جهات روشن باشد و فقط به یک معنا منتهی شود.
ورودی‌های خوب تعریف شده : اگر الگوریتمی می‌گوید ورودی‌ها را بگیرید، باید ورودی‌های کاملاً تعریف شده باشد.
خروجی های خوب تعریف شده: الگوریتم باید به وضوح مشخص کند که چه خروجی به دست می آید و همچنین باید به خوبی تعریف شود.
محدود بودن: الگوریتم باید متناهی باشد، یعنی پس از یک زمان محدود خاتمه یابد.
امکان پذیر : الگوریتم باید ساده، عمومی و کاربردی باشد، به طوری که بتوان آن را با منابع موجود اجرا کرد. نباید حاوی برخی از فناوری های آینده یا هر چیز دیگری باشد.
مستقل از زبان: الگوریتم طراحی شده باید مستقل از زبان باشد، یعنی باید دستورالعمل های ساده ای باشد که می تواند در هر زبانی پیاده سازی شود، و در عین حال خروجی همان طور که انتظار می رود خواهد بود.

ویژگی های الگوریتم:

باید پس از یک زمان محدود خاتمه یابد.
باید حداقل یک خروجی تولید کند.
باید صفر یا بیشتر ورودی داشته باشد.
باید قطعی باشد به این معنی که خروجی یکسانی را برای یک مورد ورودی یکسان می دهد.
هر مرحله در الگوریتم باید موثر باشد، یعنی هر مرحله باید مقداری کار را انجام دهد.

مزایای الگوریتم:

درک آن آسان است.
یک الگوریتم نمایش مرحله ای از یک راه حل برای یک مسئله معین است.
در الگوریتم مسئله به قطعات یا مراحل کوچک‌تر تقسیم می‌شود، از این رو، برای برنامه‌نویس آسان‌تر است که آن را به یک برنامه واقعی تبدیل کند.

معایب الگوریتم ها:

نوشتن یک الگوریتم زمان زیادی می برد، بنابراین زمان بر است.
درک منطق پیچیده از طریق الگوریتم ها می تواند بسیار دشوار باشد.
نمایش عبارات انشعاب و حلقه در الگوریتم ها (imp) دشوار است .

چگونه یک الگوریتم طراحی کنیم؟

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

مشکلی که قرار است با این الگوریتم حل شود یعنی تعریف واضح مسئله .
در حین حل مسئله باید محدودیت های مسئله را در نظر گرفت.
ورودی برای حل مشکل.
خروجی مورد انتظار زمانی که مشکل حل شد.
راه حل این مشکل، در محدودیت های داده شده است.

سپس الگوریتم با کمک پارامترهای فوق طوری نوشته می شود که مشکل را حل کند.
مثال: مثال را در نظر بگیرید تا سه عدد را جمع کنید و حاصل جمع را چاپ کنید.

مرحله 1: برآورده کردن پیش نیازها
همانطور که در بالا توضیح داده شد، برای نوشتن یک الگوریتم، باید پیش نیازهای آن برآورده شود.
1. مشکلی که باید با این الگوریتم حل شود : 3 عدد اضافه کنید و مجموع آنها را چاپ کنید.
2. محدودیت‌های مسئله که باید در هنگام حل مسئله در نظر گرفته شود : اعداد باید فقط دارای اعداد باشند و هیچ کاراکتر دیگری نداشته باشند.
3. ورودی برای حل مسئله: سه عددی که باید اضافه شود.
4. خروجی مورد انتظار هنگام حل مسئله: مجموع سه عدد به عنوان ورودی یعنی یک عدد صحیح منفرد.
5. راه حل این مسئله، در قیود داده شده: راه حل شامل جمع کردن 3 عدد است. این کار را می توان با کمک عملگر ‘+’ یا bit-wise یا هر روش دیگری انجام داد.
مرحله 2: طراحی الگوریتم
حالا بیایید الگوریتم را با کمک پیش نیازهای بالا طراحی کنیم:
الگوریتم جمع کردن 3 عدد و چاپ مجموع آنها:
1. شروع کنید
2. 3 متغیر عدد صحیح num1، num2 و num3 را اعلام کنید.
3. سه عددی که باید اضافه شوند را به ترتیب به عنوان ورودی متغیرهای num1، num2 و num3 در نظر بگیرید.
4. یک مجموع متغیر اعداد صحیح را برای ذخیره جمع حاصل از 3 عدد اعلام کنید.
5. 3 عدد را اضافه کنید و نتیجه را در مجموع متغیر ذخیره کنید.
6. مقدار متغیر sum را چاپ کنید
7. پایان
مرحله 3: آزمایش الگوریتم با پیاده سازی آن.
برای آزمایش الگوریتم، اجازه دهید آن را در زبان C پیاده سازی کنیم.

برنامه:

// C++ program to add three numbers
// with the help of above designed
// algorithm
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    
     // Variables to take the input of
     // the 3 numbers
     int num1, num2, num3;
 
     // Variable to store the resultant sum
     int sum;
 
     // Take the 3 numbers as input
     cout <<  "Enter the 1st number: " ;
     cin >> num1;
     cout <<  " " << num1 << endl;
 
     cout <<  "Enter the 2nd number: " ;
     cin >> num2;
     cout <<  " " << num2 << endl;
 
     cout <<  "Enter the 3rd number: " ;
     cin >> num3;
     cout <<  " " << num3;
 
     // Calculate the sum using + operator
     // and store it in variable sum
     sum = num1 + num2 + num3;
 
     // Print the sum
     cout <<  "nSum of the 3 numbers is: "
          << sum;
 
     return 0;
}
// This code is contributed by shivanisinghss2110

خروجی

عدد 1 را وارد کنید: 0
عدد دوم را وارد کنید: 0
شماره 3 را وارد کنید: -1577141152

مجموع 3 عدد برابر است با: -1577141152

+ اپراتور
عملگرهای بیت عاقلانه
. . و غیره

تجزیه و تحلیل پیشینی: “Priori” به معنای “قبل” است. از این رو تحلیل پیشینی به معنای بررسی الگوریتم قبل از اجرای آن است. در این، زمانی که الگوریتم در قالب مراحل نظری نوشته شود بررسی می شود. این کارایی یک الگوریتم با این فرض اندازه گیری می شود که همه عوامل دیگر، به عنوان مثال، سرعت پردازنده، ثابت هستند و هیچ تاثیری بر پیاده سازی ندارند. این کار معمولا توسط طراح الگوریتم انجام می شود. این تحلیل مستقل از نوع سخت افزار و زبان کامپایلر است. پاسخ های تقریبی را برای پیچیدگی برنامه می دهد.
تحلیل پسین: “پسین” به معنای “پس از” است. از این رو تحلیل پسینی به معنای بررسی الگوریتم پس از اجرای آن است. در این روش الگوریتم با پیاده سازی آن در هر زبان برنامه نویسی و اجرای آن بررسی می شود. این تجزیه و تحلیل به دریافت گزارش تحلیل واقعی و واقعی در مورد صحت، فضای مورد نیاز، زمان مصرف شده و غیره کمک می کند. یعنی به زبان کامپایلر و نوع سخت افزار مورد استفاده بستگی دارد.

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

پیچیدگی فضایی : پیچیدگی فضایی یک الگوریتم به میزان حافظه استفاده شده توسط الگوریتم برای ذخیره متغیرها و به دست آوردن نتیجه اشاره دارد. این می تواند برای ورودی ها، عملیات موقت یا خروجی ها باشد.
چگونه پیچیدگی فضا را محاسبه کنیم؟
پیچیدگی فضایی یک الگوریتم با تعیین 2 جزء زیر محاسبه می شود:
- قسمت ثابت: به فضایی اشاره دارد که قطعا الگوریتم مورد نیاز است. به عنوان مثال، متغیرهای ورودی، متغیرهای خروجی، اندازه برنامه و غیره.
- Variable Part: به فضایی اشاره دارد که بر اساس اجرای الگوریتم می تواند متفاوت باشد. به عنوان مثال، متغیرهای موقت، تخصیص حافظه پویا، فضای پشته بازگشتی و غیره.
پیچیدگی زمانی : پیچیدگی زمانی یک الگوریتم به مدت زمانی اشاره دارد که الگوریتم برای اجرا و به دست آوردن نتیجه لازم است. این می تواند برای عملیات عادی، دستورات شرطی if-else، دستورات حلقه و غیره باشد.
چگونه پیچیدگی زمانی را محاسبه کنیم؟
پیچیدگی زمانی یک الگوریتم نیز با تعیین 2 جزء زیر محاسبه می شود:
- بخش زمان ثابت: هر دستوری که فقط یک بار اجرا شود در این قسمت می آید. به عنوان مثال، ورودی، خروجی، if-else، سوئیچ و غیره.
- Variable Time Part: هر دستوری که بیش از یک بار اجرا شود، مثلاً n بار، در این قسمت آمده است. به عنوان مثال، حلقه ها، بازگشت و غیره

بدون دیدگاه

دیدگاهتان را بنویسید لغو پاسخ

نوشته‌های پیوسته

برنامه نویسی