دانشگاه آزاد اسلامی واحد تهران شرق- کامپیوتر- نرم افزار

جزوه طراحی الگوریتم (دستنویس)

نمونه سوال امتحان

برای اجرای الگوریتم‌ها

1-  visual stadio 2010

2- New Project

3- Win32 Console Application

کد را کپی کنید و اجرا بفرمایید.

الگوریتم جستجوی ترتیبی simpleSearch

// simpleSearch.cpp : Defines the entry point for the console application//


#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;

int i, n, x;
int *a = new int [];

int simpleSearch();

int _tmain(int argc, _TCHAR* argv[])
{
    cout << "please enter number of array: ";
    cin >> n;
   
    for(i = 1; i <= n; i++)
    {
        cout << "a[" << i << "]= ";
        cin >> a[i];
    }
    cout << "please enter the number that you want find it: ";
    cin >> x;
   
    if(simpleSearch())
        cout << "I find";
    else cout << "I didn"t find";

    getch();
    return 0;
}

int simpleSearch()
{
    for(i = 1; i <= n; i++)
        if(a[i] == x)
            return 1;
    return 0;
}

الگوریتم مرتب‌سازی ترتیبی  simpleSort

توجه: پیچیدگی اجرایی (O(n2 دارد.

// simpleSort.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;

int i, j, n, x;
int *a = new int [];

int simpleSort();

int _tmain(int argc, _TCHAR* argv[])
{
    cout << "please enter number of array: ";
    cin >> n;
   
    for(i = 1; i <= n; i++)
    {
        cout << "a[" << i << "]= ";
        cin >> a[i];
    }
       
    simpleSort();
    cout << endl;

    for(i = 1; i <= n; i++)
        cout << "a[" << i << "]= " << a[i] << endl;

    getch();
    return 0;
}

int simpleSort()
{
    int temp = 0;
    for(i = 1; i <= n; i++)
        for(j = i + 1; j <= n; j++)
            if(a[i] > a[j])
            {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;           
            }
                   
    return 0;
}

الگوریتم جمع

// Sum.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;

int i, n, x;
int *a = new int [];

int mySum();

int _tmain(int argc, _TCHAR* argv[])
{
    cout << "please enter number of array: ";
    cin >> n;
   
    for(i = 1; i <= n; i++)
    {
        cout << "a[" << i << "]= ";
        cin >> a[i];
    }
       
    cout << "Sum= " << mySum();

    getch();
    return 0;
}

int mySum()
{
    int S = 0;
    for(i = 1; i <= n; i++)
        S = S + a[i];
       
    return S;
}

الگوریتم مرتب‌‌سازی حبابی BubbleSort

توجه: پیچیدگی اجرایی (O(n2 دارد.

// bubbleSort.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;

int i, j, n, x;
int *a = new int [];

int bubbleSort();

int _tmain(int argc, _TCHAR* argv[])
{
    cout << "please enter number of array: ";
    cin >> n;
   
    for(i = 1; i <= n; i++)
    {
        cout << "a[" << i << "]= ";
        cin >> a[i];
    }
       
    bubbleSort();
    cout << endl;

    for(i = 1; i <= n; i++)
        cout << "a[" << i << "]= " << a[i] << endl;

    getch();
    return 0;
}

int bubbleSort()
{
    int temp = 0;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n - i ; j++)
            if(a[j] > a[j + 1])
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;           
            }
                   
    return 0;
}

الگوریتم جستجوی دودویی binarySearch

الگوریتم جستجوی دودویی (Binary Search)‏، تکنیکی است برای یافتن یک مقدار عددی از میان مجموعه‌ای از اعداد مرتب. این متد محدوده ی جستجو را در هر مرحله به نصف کاهش می‌دهد، بنابراین هدف مورد نظر یا به زودی پیدا می‌شود و یا مشخص می‌شود که مقدار مورد جستجو در فهرست وجود ندارد.

جستجوی دودویی فقط در آرایه های مرتب استفاده می شود. در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه می شود اگر با این خانه برابر بود جستجو تمام می شود اگر عنصر مورد جستجو از خانه وسط بزرگتر بود جستجو در بخش بالایی آرایه و در غیر این صورت جستجو در بخش پایینی آرایه انجام می شود (فرض کرده ایم آرایه به صورت صعودی مرتب شده است) این رویه تا یافتن عنصر مورد نظر یا بررسی کل خانه های آرایه ادامه می یابد.

جستجوی دودویی نمونه‌ای از الگوریتمهای تقسیم و غلبه (Divide and conquer)‏ می‌باشد.

// BinarySearch.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;

int n , value;
int *a = new int;
int binarySearch(int *b,int n,int value);

int _tmain(int argc, _TCHAR* argv[])
{
    cout << "Please enter number of array:";
    cin >> n;
    cout << endl;
    cout << "please enter array" << endl;
    for(int i = 0; i < n; i++)
    {
        cout << "a[" << (i + 1) << "]=";
        cin >> a[i];
    }

    cout << "plaese enter value for search:";
    cin >> value;
    if(binarySearch(a,n,value))
        cout << "I find";
    else
        cout << "I can not find";
   
    getch();   
    return 0;
}

int binarySearch(int *b,int n,int value)
{
    int low, high, mid;
    low = 0;
    high = n-1;

   while(low <= high)
   {
        mid = (low + high)/ 2;
        if (a[mid] == value)
              return 1;
        if (a[mid] > value)
              high = mid - 1;
        else
              low = mid + 1;
   }
  
   return 0;
}

الگوریتم مرتب سازی ادغامی mergeSort

روش مرتب سازی ادغامی از الگوریتم تقسیم و حل (Divide and conquer) و همچنین ادغام برای مرتب کردن داده‌ها استفاده می‌کند. در این الگوریتم مساله به چند جزء کوچک‌تر تقسیم می‌شود. هر کدام از این قسمت‌ها را به طور مجزا حل کرده، و با ترکیب آنها به مساله اصلی می‌رسیم. و اما طرح کلی مرتب سازی ادغام:

در این روش داده‌ها به دو قسمت مساوی تقسیم می‌شوند. و هر کدام از این قسمت‌ها - به صورت بازگشتی - مرتب، و با ادغام آنها دادها به صورت کامل مرتب می‌شوند. اما توجه به این نکته ضروری است که اگر پس از یک بار تقسیم باز هم لیست های ایجاد شده بزرگ باشند، می توانیم برای هر زیر لیست مراحل بالا را دوباره انجام دهیم تا به زیر لیست هایی با تنها 1 عضو برسیم و واضح است که لیست تک عنصری خود مرتب است.

مثال:

الگوریتم مرتب سازی سریع QuickSort

مرتب سازی سریع (Quick Sort) از جمله روش های محبوب و با سرعت بالا برای مرتب کردن داده‌ها محسوب می‌شود. این روش هم مثل روش ادغام از تقسیم و حل (Divide and Conqure) برای مرتب کردن داده‌ها استفاده می‌کند. به این ترتیب که داده‌ها را به دو قسمت مجزا تقسیم، و با مرتب کردن آنها کل داده‌ها رو مرتب می‌کند. برای اینکار یکی از داده‌ها (مثلاً داده اول) به عنوان محور انتخاب می‌شود. داده‌ها بر اساس محور طوری چینش می‌شوند که همه داده‌های کوچک‌تر از محور سمت چپ و داده‌های بزرگ‌تر یا مساوی آن سمت راستش قرار می‌گیرند. با مرتب کردن دو قسمت به دست آمده کل داده‌ها مرتب می‌شوند. در این حالت مثل روش ادغام نیازی به ادغام کردن داده‌ها نیست. چرا که قسمت سمت راست همگی از قسمت سمت چپ کوچک‌تر هستند و بالعکس.

الگوریتم Floyd

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

منبع: http://fa.wikipedia.org