جستجوی باینری یا دودویی

برای جستجوی یک عدد در یک آرایه، راحت ترین راه این است که عدد مورد نظر را با تمام خانه های موجود در آرایه مقایسه کنیم. 

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

در برنامه ی زیر آرایه از بزرگ به کوچک با روش مرتب سازی حبابی، مرتب شده است. پس از آن می توانیم به شیوه ی زیر که به جستجوی دودویی شناخته شده است عمل کنیم: 

ابتدا عدد مورد نظر یا f را با خانه ی وسطی آرایه مقایسه میکنیم. خانه ی وسطی آرایه از مجموع دو مقدار start و end بدست می آید. start یعنی آغاز بخشی از آرایه که میخواهیم در آن جستجو کنیم که در اول کار 0 است. end یعنی پایان بخشی از آرایه که میخواهیم در آن جستجو کنیم که در ابتدا n-1 است. ( یعنی در فاز اول جستجو میخواهیم همه ی آرایه را در نظر داشته باشیم) 

بعد از مقایسه با خانه ی وسطی اگر f دقیقا همان خانه بود که کار تمام است و فقط باید شماره ی خانه ی وسطی(mid) را نمایش دهیم. 

اما اگر F از مقدار وسطی بزرگتر بود باید تکه ی اول آرایه را بگردیم( چون ارایه ما از بزرگ به کوچک مرتب شده است) پس نقطه ی آغاز تغییری نمیکند. ( همان 0 است) اما نقطه ی پایان به قبل از mid کاهش پیدا میکند و برابر mid-1 می شود. 

اگر f از مقدار وسطی یا mid کوچکتر بود باید نیمه ی دوم آرایه را بگردیم که در آن صورت مقدار end یا پایان تغییری نمیکند و n-1 است. اما نقطه ی آغاز تغییر میکند و به خانه ی بعد از خانه ی وسطی  یا mid+1 افزایش پیدا میکند. 

تمرین رشته ها

مثال 8- برنامه ای بنویسید که یک رشته از ورودی بگیرد و چک کند که همه ی خانه های آن بین حروف a تا z کوچک باشند، اگر این شرط برقرار بود عبارت معتبر و  اگر این گونه نباشد عبارت نامعتبر را نمایش دهد: 

#include <conio.h>
#include <iostream>
#include <string>

using namespace std;
int main()
{
    
    string a;
    cin>>a;
    int flag=1;
    int n=a.length();
    for(int i=0;i<n;i++) 
    {
        int asc=(int)a[i];
        if(asc>=97 && asc<=122)
            flag=0;
        else
        {   flag=1;
            break;
        }
    }
    if(flag==0)
        cout<<"Motabar";
    else
        cout<<"Namotabar";
    
    getch();
    return 0;
}

string یا رشته

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

برای این که عبارتی از کاراکترها را به صورت یکباره از ورودی بگیریم می توانیم از نوع دیگری استفاده کنیم که به رشته یا string معروف است. 

برای تعریف String  باید از یکی از دو فرمت زیر استفاده کنیم. 

string name;

or

string name(10,'a');

تمرین آرایه دوبعدی

مثال 5- برنامه ای بنویسید که mو n را از ورودی بگیرد و آرایه ای به طول و عرض n و m بسازد و آن را از ورودی گرفته، سپس عناصر سطرهای آرایه را در شماره سطر ضرب کند و دوباره آن را چاپ کند: 

#include <conio.h>
#include <iostream.h>

int main()
{
    int a[10][5],b[10][5];
    for(int i=0;i<10;i++)   //daryaft araye
    {
        for(int j=0;j<5;j++)
        {
            cin>>a[i][j];
        }
    }
     for(int i=0;i<10;i++)   //zarb dar i
    {
        for(int j=0;j<5;j++)
        {
            b[i][j]=i*a[i][j];
        }
    }
     for(int i=0;i<10;i++)   //chape araye varun
    {
        for(int j=0;j<5;j++)
        {
            cout<<b[i][j]<<"\t";
        }
        cout<<endl;
    }
    getch();
    return 0;
}

آرایه دو بعدی

برای تعریف آرایه دو بعدی به صورت زیر عمل میکنیم:

ستون][سطر]اسم آرایه  نوع آرایه]; 

مثلا آرایه ی  a  از نوع عدد صحیح و دارای 10 سطر و 5 ستون می باشد. شماره سطرهای آن از 0 تا 9 و شماره ستونهای آن از 0 تا 4 می باشند. 

int a[10][5];

مرتب سازی

فرض کنید که به شما آرایه ای بدهند و از شما بخواهند که بزرگترین عنصر این آرایه را در خروجی نمایش دهید. 

برای این کار برنامه ای خواهید نوشت که تنها عنصر ماکزیمم را به شما بدهد. 

حال فرض کنید که از شما بپرسند عنصر 5 ام این آرایه به ترتیب بزرگ به کوچک چیست؟ آن وقت چکار خواهید کرد؟

برای حل این قبیل مسائل باید کل آرایه را مرتب کنیم!

الگوریتمهای مختلفی تا امروز برای مرتب سازی آرایه ها ارائه شده است. اما از ساده ترین آنها می توان به سه نوع مرتب سازی زیر اشاره نمود:

1- مرتب سازی انتخابی یا selection sort

2- مرتب سازی درجی یا insertion sort

3- مرتب سازی حبابی یا bubble sort

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

حلقه ی تو در تو تمرینهای پیچیده تر

ادامه ی تمرینها تا حدودی پیچیده تر است. اما لازم است آنها را به صورت کامل یاد بگیرید! 

7- برنامه ای بنویسید که شکل زیر را نمایش دهد: 

*********

 *******

   *****

    ***

      *

برای تحلیل این سوال باید توجه کنیم که 5 خط داریم و در خط صفرم، صفر فاصله و 9 ستاره، در خط یکم، یک فاصله و 7 ستاره، در خط دوم، دو فاصله و 5 ستاره، در خط سوم، سه فاصله و 3 ستاره و در خط چهارم ، چهار فاصله و یک ستاره داریم. 

پس واضح است که حلقه ی بیرونی که تعداد خطوط را نشان میدهد 5 بار تکرار میشود. اما حلقه های درونی( برای فاصله ها و ستاره ها) را چه جور تفسیر کنیم؟

حلقه ی درونی اول که برای رسم فاصله هاست، به تعداد i بار تکرار خواهد شد. ( کافی است به توضیحات بالا کمی توجه کنیم) 

حلقه ی درونی دوم که برای رسم ستاره هاست را می توان به صورت روبه رو با استفاده از یک متغیر کمکی نوشت. به این صورت که متغیر a اول 9 باشد و هر بار 2 تا از آن کم شده و در حلقه ی درونی دوم هر بار a تا ستاره رسم بشود. 

برنامه ی آن به صورت زیر خواهد بود: 

#include <conio.h>
#include <iostream.h>

int main()
{   int a=9;
    for(int i=0;i<5;i++)    //dar kol 5 khat darim
    {
        for(int j=0;j<i;j++)    //rasme fasele ha
        {
            cout<<' ';
        }
        
        for(int j=0;j<a;j++)    //rasme a ta setare
        {
            cout<<'*';
            
        }
        a=a-2;                  // az a 2 ta kam mikonim baraye khate badi
        cout<<endl;
    }
        getch();
        return 0;
}

حلقه های تو در تو

 فرض کنید می خواهیم برنامه ای بنویسیم که یک کاراکتر * را در خروجی نمایش دهد. برای این کار به صورت زیر عمل میکنیم:

main()
{
    cout<<"*";
    cout<<endl;
    getch();
}

خب در این برنامه دستور cout تنها یک بار اجرا می شوند. حال فرض کنیم بخواهیم برنامه­ی بالا را به این صورت تغییر دهیم که یک عدد n را از ورودی گرفته و به تعداد آن یعنی n بار کاراکتر * را در خروجی پشت سر هم در یک خط نمایش دهیم.

برنامه بالا به صورت زیر تغییر خواهد یافت:

main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
       cout<<"*";
    }
    cout<<endl;
    getch();
}

تنها تفاوت این برنامه با برنامه ی قبلی در این است که کل کارهای برنامه ی اول را در یک حلقه قرار دادیم که این حلقه به تعداد n اجرا خواهد شد. پس از نمایش n کاراکتر * در خروجی، به ابتدای خط بعدی ( با استفاده از دستور cout<<endl ) می رویم.

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

خب با توجه به برنامه ی قبلی به این نتیجه می رسیم که باید برنامه ی بالا( که کشیدن یک خط از n ستاره است) را m بار تکرار کنیم. تا m خط که هر خط متشکل از n ستاره است را رسم کنیم.

 

برنامه ی بالا به صورت زیر تغییر خواهد کرد:

 main()
{
    int n,m;
    cin>>n>>m;
    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<=n;i++)
        {
           cout<<"*";
        }
        cout<<endl;
    }
    getch();
}

در واقع ما در این برنامه از حلقه ی تو در تو استفاده کرده ایم!

 

توجه کنید که همیشه حلقه ی تو در تو از دو حلقه ی for تشکیل نشده است و می توان به جای for از while  هم استفاده کرد!

 

main()
{
    int n,m,j=0;
    cin>>n>>m;
    while(j<m)
    {
        for(int i=1;i<=n;i++)
        {
           cout<<"*";
        }
        cout<<endl;
        j++;
    }
    getch();
}

در برنامه ی بالا حلقه ی بیرونی را از for به while تغییر داده ایم!

امیدوارم تا اینجای کار به این نتیجه رسیده باشید که در مواقع ضروری از حلقه ی تو در تو استفاده خواهیم کرد و برنامه ی بالا را می توان بدون حلقه ی تو در تو هم نوشت!

 

برای مثال چند نمونه از حلقه های تو در تو را با هم حل خواهیم کرد.

 

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

برنامه به صورت زیر نوشته می شود:

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cout<<'*';
        }
        cout<<endl;
    }
    getch();
}

برنامه ای بنویسید که شکل زیر را نمایش دهد:

برنامه به صورت زیر نوشته می شود:

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=11-i;j++)
        {
            cout<<'*';
        }
        cout<<endl;
    }
    getch();
}

برنامه ای بنویسید که شکل زیر را نمایش دهد:

برنامه به صورت زیر نوشته می­شود:

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=i-1;j++)
        {
            cout<<" ";
        }
        for(int j=1;j<=11-i;j++)
        {
           cout<<"*";
        }
        cout<<endl;
    }
    getch();
}
 

این برنامه را به صورت زیر هم میتوان نوشت( چرا؟)

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=i-1;j++)
        {
            cout<<' ';
        }

        for(int j=i;j<=11;j++)
        {
            cout<<'*';
        }
        cout<<endl;
    }
    getch();
}

 

برنامه ای بنویسید که شکل زیر را نمایش دهد:

برنامه به صورت زیر نوشته خواهد شد:

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=10-i;j++)
        {
            cout<<' ';
        }
        for(int j=1;j<=i;j++)
        {
            cout<<'*';
        }
        cout<<endl;
    }
    getch();
}

برنامه ی بالا را می توان به صورت زیر هم نوشت. ( چرا؟)

main()
{
    for(int i=1;i<=10;i++)
    {
        for(int j=i;j<=10;j++)
        {
            cout<<' ';
        }
        for(int j=1;j<=i;j++)
        {
            cout<<'*';
        }
        cout<<endl;
    }
    getch();
}

 برنامه ای بنویسید که شکل زیر را نمایش دهد:

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

برنامه ی آن به صورت زیر نوشته می شود:

main()
{
    for(int i=1;i<=19;i++)    
    {
        if(i<=10)    //rasme 10 khate aval
        {
            for(int j=1;j<=10-i;j++)
            {
                cout<<' ';
            }
            for(int j=1;j<=i;j++)
            {
                cout<<'*';
            }
        }
        else    //rasme 9 khate ba'di
        {
            for(int j=1;j<=i-10;j++)
            {
                cout<<' ';
            }
            for(int j=1;j<=20-i;j++)
            {
                cout<<'*';
            }
        }
        cout<<endl;
    }
    getch();
}

 برنامه ای بنویسید که شکل زیر را نمایش دهد:

جواب سوال به صورت زیر خواهد بود:

int main()
{
    for(int i=1;i<=19;i++)    
    {
        if(i<=10)        //rasme 10 khate aval
        {
            for(int j=1;j<=i;j++)
            {
                cout<<'*';
            }
        }
        else        //rasme 9 khate ba'di
        {
            for(int j=1;j<=20-i;j++)
            {
                cout<<'*';
            }
        }
        cout<<endl;
    }
    getch();
}

 

سوالات تکمیلی آرایه های یک بعدی

مثال 5- برنامه ای بنویسید که  n را از ورودی بگیرد و آرایه ای به طول n بسازد و آن را از ورودی گرفته و آن را چاپ کند. سپس عناصر آرایه را چهار برابر کند و دوباره آن را چاپ کند: 

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    int n;
    cout<<"enter lenght of your array"<<endl;
    cin>>n;
    int arr[n];
    cout<<"enter items of your array"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    cout<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<arr[i];
    }
    cout<<endl;
    for(int i=0;i<n;i++)
    {
        
        arr[i]=4*arr[i];
    }
    cout<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

فایل برنامه

آموزش نصب نرم افزار DevC