[تصویر: images?q=tbn:ANd9GcSjxWUKRWd2vrGSQvyfk9m...DOVMhm3vQQ]

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

مسئله :
Count Inversions in an array
با ما در ادامه مطلب همراه باشید .

شرح مسئله:

فرض کنید آرایه زیر را در اختیار داریم :

 5,4,9,2,1,15,3

حال فرض کنید برای عنصر i ام میخواهیم عدد  Xi به صورت زیر  حساب کنیم :
به ازای هر Array[k]  :
 به صورتی که n>k>i  اگر Array[k]>Array[i] باشد , X یک واحد اضافه میشودو در نهایت جواب مسئله میشود :

X t= X 1 + X 2 + … +X n

یا به عبارت ساده تر برای مثال بالا  :

اعداد 4، 3، 2 ، 1 از عنصر 5 کوچکتر میباشد پس X 1 میشود 4.
برای عنصر 4 ، عناصر 2 ،3 و 1  و    X 2 میشود 3.
برای عنصر 9 به همین ترتیب   X 3 میشود 3  .
و
X 4 =1  ، X 5= 0 ، X 6=1 و X 7 =0
و جواب مسأله یا همون X t میشه :
X t = 4+ 3+ 3 + 1 + 0 + 1 + 0 =12

اگر ابهامی راجب کلیت مسئله  وجود داشت در همین پست بپرسد Cool

حال برای جل این مسأله 3 الگوریتم را مطرح میکنیم .
(اگر دوستان الگوریتم دیگری برای حل این مسأله پیدا کردید ، در همین تاپیک مطرح کرده تا دیگر دوستان نیز استفاده کنند Smile  )

الگوریتم شماره 1 :

راه حل اول و سادش اینه که برای هر عنصر بیایم تمامی عناصر کوچکتر بعد از خودش رو حساب کنیم که دارای پیچیدگی زمانی O (N^2) میباشد .
(2 تا for داره دیگه Big Grin  )

سورس کد این الگوریتم :

کد c++:
#include<iostream>
using namespace std;
int getInvCount(int arr[], int n)
{
int inv_count = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
inv_count++;
return inv_count;
}/* Driver progra to test above functions */
int main(int argv, char** args)
{
int arr[] = { 1, 20, 6, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << getInvCount(arr, n);
return 0;
}

الگوریتم شماره 2 :

در این الگوریتم سعی شده با استفاده از روش تقسیم و غلبه بتوان الگوریتم سریع تری ارائه داد.

برای حل مسائل به روش تقسیم و غلبه باید مسئله رو به مسائل کوچکتری شکست . برای این کار ما مسئله رو به دو قسمت میشکنیم و سپس با حل زیر مسائل ساده تر ، سپس آن دو زیر مسئله رو با هم ادغام میکنیم (عملا یه چیزی مثل مرتب سازی ادغامی )

حال فرض کنید ما بتونیم جواب دو زیر مسأله مورد نظر رو حل کنیم .

[تصویر: inv_count1.GIF]
و جواب هر زیر مسأله باشه Inv 1 و Inv 2 .
مطمئنا جواب کل مسئله میشه Inv 1 + Inv 2 + جواب هایی که به دلیل نصف شدن مسئله از دست داده شده که باید هنگام ادغام 2 زیر مسئله بدست بیایند و جواب مسئله اصلی ساخته شود .
برای به دست آوردن جواب هنگام ادغام به شکل زیر توجه کنید :

[تصویر: inv_count2.GIF]

فرض کنید 2 متغیر i (اندیس ابتدای قسمت اول ) و j (اندیس ابتدای قسمت دوم) باشند . اگر 2 قسمت مرتب باشند (چون شرط خاتمه تابع ما 1 عنصری بودن آرایه میباشد و 1 عنصر مرتب میباشد ، این فرض نیست و میتوان هنگام محاسبه مرتب هم کرد ؛ در کد این الگوریتم واضح تر میبینید اینو)، اگر عنصر B j از عنصر A i کوچکتر باشد مطمئنا  از تمامی عناصر A i+1 تا وسط 2 قسمت (عنصر mid ) نیز کوچکتر میباشد و جواب ما نیز باید با این مقدار (mid – i ) جمع میشود و j ++ میشود و اگر a i کوچکتر باشد ، i++ میشود (مثل تابع ادغام در مرتب سازی ادغامی Wink )

راجب پیچیدگی زمانی این الگوریتم  :

T(n) = 2T(n/2) + n
که 2 تا T(n/2)  برای محاسبه دو زیر مسئله و n برای ادغام هستش که به سادگی (قضیه اصلی یا جایگذاری ) میشه nlogn

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

کد c++:

/*

www.Persianstudent.ir
By :Amir Mohammad Rostami
*/
#include<iostream>
using namespace std;
int * temp;
int Merge(int * arr, int fst, int mid, int lst)
{
int count = 0;
temp = new int[lst-fst];
int k = 0, i = fst, j = mid;
while ((i <= mid – 1) && (j <= lst))
{
if (arr[i] > arr[j])
{
count += (mid – i);
temp[k++] = arr[j++];
}
else
temp[k++] = arr[i++];
}
while (i <= mid – 1)
temp[k++] = arr[i++];
while (j <= lst)
temp[k++] = arr[j++];
k = 0;
for (i = fst; i <= lst; i++)
arr[i] = temp[k++];

return count;
}
int count_inversions(int * arr, int fst, int lst)
{
int Count = 0;
if (lst > fst)
{
int mid = (lst + fst) / 2;
Count = count_inversions(arr, fst, mid);
Count += count_inversions(arr, mid + 1, lst);
Count += Merge(arr, fst, mid+1, lst);
}

return Count;
}
void main()
{
int * a, n;
cin >> n;
a = new int[n];
for (int i = 0; i < n; i++)
cin >> a[i];

cout << count_inversions(a, 0, n-1);
}

 اسلاید های زیر نیز به فهم این الگوریتم کمک میکنه (تصویری و مرحله به مرحله Big Grin )

دانلود

الگوریتم شماره 3 :

با استفاده از درخت BST

به زودی . . .

0

130 views

نویسنده: admin
درباره admin:


  1. دلشاد گفت:

    سلام.وقتتون بخیر
    چرا در (اعداد 4 ، 2 ، 1 از عنصر 5 کوچکتر میباشد پس X 1 میشود 3 .
    برای عنصر 4 ، عناصر 2 و 1 و X 2 میشود 2 .)
    عدد 3 رو حساب نکردید با اینکه از 4 و 5 کوچکتر است؟
    میشه توضیح بدید.

    0
  2. admin گفت:

    با سلام ، با تشکر از دقت نظر شما اصلاح شد

    0
  3. دلشاد گفت:

    سلام.
    ببخشید میشه این خط رو هم دوباره بررسی کنید
    (برای عنصر 9 به همین ترتیب X 3 میشود 3)

    0

طراحی سایت توسط تیم طراحی دانشجوی ایرانی

© تمامی حقوق مادی و معنوی این وب سایت متعلق به دانشجوی ایرانی می باشد.