آموزش برنامه نویسی به زبان ++C

این وبلاگ جهت آموزش برنامه نویسی به زبان ++C برای دانش آموزان دبیرستان فرزانگان ایجاد شده است.
پنجشنبه, ۱۶ آذر ۱۳۹۱، ۰۶:۲۱ ب.ظ

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

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

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

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

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

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

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

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

خب تا اینجای کار فهمیدیم که f در کدام سمت آرایه قرار دارد. قسمت انتهایی یا ابتدایی. 

اعین این فرآیند باید برای آن قسمتی که  f در آن قرار دارد، یعنی مثلا قسمت ایتدایی، نیز دوباره اجرا شود. پس می توانیم که نتیجه بگیریم که این فرآیند را باید در حلقه ای قرار دهیم که شرط حلقه این است : start<=end

یعنی تا زمانی ادامه میدهیم که start از end بزرگتر نشود و از آن رد نشود تا در حلقه بینهایت گیر نکنیم!


پس از اتمام حلقه اگر start ازend بزرگتر شده بود یعنی همه ی آرایه را گشته و f را پیدا نکرده و start از روی end رد شده است. پس f در آرایه نبوده و باید پیغام مناسبی مبنی بر وجود نداشتن F در آرایه چاپ شود. 


شکل زیر نمایشگر این روش جستجو است: 


برنامه ی این مرتب سازی در زیر آمده است: 


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

main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        a[i]=rand()%50;
    }
    
    
    cout<<endl;
        
    for(int i=0;i<n;i++)        //sort
    {
        for(int j=0;j<n-1;j++)
        {
            if(a[j+1]>a[j])
            {
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    
    for(int i=0;i<n;i++)        //namayesh
    {
        cout<<a[i]<<" ";
    }
    
    int f;
    cin>>f;
    int start=0;                 //Binary search
    int end=n-1;
    while(start<=end)        
    {
        int mid=(start+end)/2;
        if(a[mid]==f)
        {
            cout<<"found at "<<mid;
            break;
        }
        if(a[mid]<f)
            end=mid-1;
        else if(a[mid]>f)
            start=mid+1;
    }
    if(start>end)
        cout<<"Not found!"; 
    
    getch();
    
}





نوشته شده توسط سارا نازاری
ساخت وبلاگ در بلاگ بیان، رسانه متخصصان و اهل قلم

آموزش برنامه نویسی به زبان ++C

این وبلاگ جهت آموزش برنامه نویسی به زبان ++C برای دانش آموزان دبیرستان فرزانگان ایجاد شده است.

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

پنجشنبه, ۱۶ آذر ۱۳۹۱، ۰۶:۲۱ ب.ظ

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

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

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

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

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

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

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

خب تا اینجای کار فهمیدیم که f در کدام سمت آرایه قرار دارد. قسمت انتهایی یا ابتدایی. 

اعین این فرآیند باید برای آن قسمتی که  f در آن قرار دارد، یعنی مثلا قسمت ایتدایی، نیز دوباره اجرا شود. پس می توانیم که نتیجه بگیریم که این فرآیند را باید در حلقه ای قرار دهیم که شرط حلقه این است : start<=end

یعنی تا زمانی ادامه میدهیم که start از end بزرگتر نشود و از آن رد نشود تا در حلقه بینهایت گیر نکنیم!


پس از اتمام حلقه اگر start ازend بزرگتر شده بود یعنی همه ی آرایه را گشته و f را پیدا نکرده و start از روی end رد شده است. پس f در آرایه نبوده و باید پیغام مناسبی مبنی بر وجود نداشتن F در آرایه چاپ شود. 


شکل زیر نمایشگر این روش جستجو است: 


برنامه ی این مرتب سازی در زیر آمده است: 


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

main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        a[i]=rand()%50;
    }
    
    
    cout<<endl;
        
    for(int i=0;i<n;i++)        //sort
    {
        for(int j=0;j<n-1;j++)
        {
            if(a[j+1]>a[j])
            {
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    
    for(int i=0;i<n;i++)        //namayesh
    {
        cout<<a[i]<<" ";
    }
    
    int f;
    cin>>f;
    int start=0;                 //Binary search
    int end=n-1;
    while(start<=end)        
    {
        int mid=(start+end)/2;
        if(a[mid]==f)
        {
            cout<<"found at "<<mid;
            break;
        }
        if(a[mid]<f)
            end=mid-1;
        else if(a[mid]>f)
            start=mid+1;
    }
    if(start>end)
        cout<<"Not found!"; 
    
    getch();
    
}



موافقین ۱ مخالفین ۰ ۹۱/۰۹/۱۶
سارا نازاری

نظرات  (۲۸)

tu barname age f >a[mid] mage nabaiad start=mid+1 bezarym???
پاسخ:
این آرایه از بزرگ به کوچیک مرتب شده هاااا .... اونی که تو میگی برای از کوچک به بزرگه!
سلام
خسته نباشید.
من وی بی رو بلدم خوب
تو نت میگشتم سایت شمارو دیدم.
طراح وب و ... کار میکنم
میخواستم c++  رو یاد بگیرم
کسی از چ دانشاموزان چ استاد بتونه راهنماییم کنه خوشحال میشم.
مرسی از همگی
منتظرتون هستم اگ میشه
ali_tootoonchi@yahoo.com
علی هستم 17 ساله از تهران
یا حق

 سلام ممنون از وبلاگ خوب شما مطالب وبلاگ شما به من کمک زیادی کرد مرسی 
خانم پس تکالیف نوروزی فرزانگان4کجاست؟
پاسخ:
اضافه شد
بابا دمتون گرم عالی بود

عاشقتمممممممممممممممممم

مرسی نجاتم دادی از دست استادمون خخخخ

سلام

اون آخر نوشتید:

if(start>end)
        cout<<"Not found!";

چرا اگه استارت از اند بزرگتر بود .... ؟

پاسخ:
جدول بکشی متوجه میشی چرا ... مثال بزن برای خودت..
سلام مرسی واقعا  خیلی کامل بود
استاد ِ ما که سر این موضوع  نیم ساعت هنگ بود :D
پاسخ:
سلام منو به استادت برسون! ;)
این جوری تعریف کردن ارایه که درست نیست، این که یک n بگیریم و بعد هم اون رو تعداد عناصر آرایه بزاریم ، مقدار constant نیست و باید vector باشه
پاسخ:
درسته. لینک زیر رو ببینید: 
مرسی از پیاده سازی اش واقعا خوشمم اومد متشکرم. ,mer30000
پاسخ:
خواهش! 
دمتون واقعآ گرم .
۲۲ آذر ۹۲ ، ۱۹:۱۹ سجاد سوری
برنامه مشکل داره.از کلمه ی End نمیشه به عنوان متغیر استفاده کرد.کلمه کلیدیست.
سلام .خانم چرا بچه های فرزانگان 6 را تنها گذاشتید ؟
پاسخ:
تنها نذاشتم که ... ;)
liiiiiiiiiiiiiiiiiikeeeeeeeeeeee

liiiiiiiiiiiiiiiiiikeeeeeeeeeeee

واقا ممنون از این کمکتون
ممنووووووووووووووووووووووووووووووووووووووووووووون ( ;
متشکرم راستی امتحان سخته؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
جوابمو بدید لطفا
سلام.بسیارعالی.
خیلی به دردم خورد.متشکرم خانم.
واقعا عالی.
بانام سارانازاری لینکتون میکنم.
پاسخ:
خواهش میکنم عزیزم :)
سلام بزرگوار راستش استادمون یه برنامه داده فعلا تو کفش موندم اگه میشه راهنماییم کنید.
خدا خیرتان دهد.
برنامه ای بنویسید که ارایه ای n عضوی (پویا)دریافت نموده سپس همه ی عناصر آرایه را بر عنصر وسط آرایه تقسیم نموده چاپ کند چنانچه عنصر وسط ارایه صفر باشد این کار را با عنصر ماقبل وسط اگر ان هم صفر با عنصر ما بعد وسط اگر آن هم صفر بود با عنصر دو تا ماقبل و ... مقایسه کند. 
بزرگوار لطف کنید زودتر جوابم را بدهید.
با تشکر
سلام.بسیار عالی.سایت خیلی خوبی دارید.توروخدا راهنماییم کنید استادم یه پروژه داده که نمیدونم چجوری باید بنویسم.توروخدا کمکم کنید.منتظرم.با تشکر
پیاده سازی ساختمان داده درخت به زبان اسمبلی که میتوانید ترجیحا از ساختمان داده های آرایه,لیست پیوندی,پشته و صف استفاده کنید.


با سلام
از گویا بودن مطالب ممنون
damet garm
۲۲ تیر ۹۴ ، ۲۰:۱۲ وحید ایمانی
سلام آخرش ایراد داره آ

if(a[mid]<f)
            end=mid-1;
        else if(a[mid]>f)
            start=mid+1;
------------->
if(a[mid]<f)
          start=mid+1  
        else if(a[mid]>f)
            ;end=mid-1;
خیلی خوب بود
مچکرم از سایت خوبتون

سلام این چکار میکنه .

خط دهم برنامه دستور بعد اولین حلقه ی فور ؟


خیلی لازم دارم لطفا توضیح بدین
سلام لطفا کمکم کنید جستجو کلمه در متن به زبان c++ چجوریه؟؟؟؟
سلام خسته نباسید ..ممنون از این که برنامه ها را در اختیار ما میگذارید ...لطفا اگه میشه این برنامه رو برایم بنویسید خیلی ممنونم .....وبرنامه ای بنویسید که 10عدد را بصورت یکجا و باینری از فایلی خوانده و عبد از مرتب سازی بصورت باینری در فایل دیگری بنویسد.......خیلی برام مهم هست سپاسگذارم اگه دستورش رو بنویسید ...منتظرم//

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی