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

[Developer Programmer]

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

1) با استفاده از ایده Partition در Quick Sort ؛ K امین کوچکترین عنصر، بین n عنصر نامرتب را بیابید

2)پیچیدگی زمانی K امین کوچکترین عدد و میانه n عنصر نامرتب چقدر است ؟

3 ) یک الگوریتم تقسیم و حل پیچیده، برای حل مساله ای به اندازه n ، آنرا به C زیرمساله به اندازه n/3 تقسیم میکند و راه حل زیرمسائل را در زمان O(n^2)( ترکیب میکند، اگر پیچیدگی زمانی این الگوریتم در بدترین حالت O(n^3) باشد، مقدار C را پیدا کنید.

4) جستجوی باینری را طوری دستکاری کنید که نمونه را به 3 قسمت مساوی تقسیم کند. پیچیدگی زمانی چند است ؟

5) مساله فوق را برای الگوریتم MergerSort پیاده کنید.

6) فرض کنید در تقسیم و حل، نمونه به 10 زیر نمونه به اندازه n/3 تقسیم میشود و مراحل تقسیم و ترکیب، از n^2 می باشد؛ معادله T(n را بیابید

[someCoder]

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

4- (t(n)=3*t(n/3 و در حالت اگر به k قسمت تقسیم کنی میشه: (t(n)=K*t(n/K
که اگر حلش کنی میشه k-1 ضربدر لگاریتم n در مبنای k-1
(چون امکان فرمول نویسی نیست، فارسی نوشتم)

ضمنا سوالات رو جدا جدا بپرسی فکر کنم بهتر جواب بگیری

[Developer Programmer]

ابتدا، از وقتی که گذاشتین و جوابی که بدون جملات اضافی دادین تشکر میکنم.

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

به نکته جالبی اشاره کردید، که من تا حال در مورد پارتیشن بندی دقت نکرده بودم و فقط حفظ کرده بودم(منظورم؛ عنصر محوری K در خونه K ام) ؛ احیانا اگه الگوریتم(شبه کد) رو دارید ممنون میشم. چون دنبال پیچیدگیش هم هستم.

4- (t(n)=3*t(n/3 و در حالت اگر به k قسمت تقسیم کنی میشه: (t(n)=K*t(n/K

خوب با توجه به فرمول شما، اگه لیست رو به دو قسمت تقسیم کنیم، میشه
[code]
t(n)=2t(n/2)
[/code[
که برابر n میشه (و نه log n)

[xxxxx_xxxxx]

با اين كه مدت زيادي ميگذره ولي كسي براي سوال 1 جواب كاملي نداره.
فكر نمي كنم روشي كه بالا گفته شده جواب بده.

تو اين سوال ما Kامين كوچكترين عنصر رو ميخايم.

[Developer Programmer]

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

[xxxxx_xxxxx]

به طور مثال براي اعداد 2 5 9 4 6 8
اگر k=3 باشه. خروجي=5
ok؟

پارتیشن میکنی لیستت رو و عنصر محوری رو بررسی میکنی که کجا قرار میگیره. اگر در خونه k بود که خودشه

k يك عنصر از آرايه است نه يك انديس

[xxxxx_xxxxx]

فكر مي كنم خود الگوريتم پارتيشن بايد تغيير كنه.
لطفاً همكاري كنيد/
اگه تو اون كتاب الگوريتم رو هم نوشته لطفاً اين جا قرار بديد.

[Developer Programmer]

نقل قول از کتاب طراحی الگوریتم ها نوشته بهروز قلی زاده؛ صفحه 106 و 107

مساله از ما میخواهد که K مین عنصر کوچک آرایه را پیدا کنیم

ُSelect(A,n,k)

low=1

up=n+1

a[n+1]=infinitive

repeat

{

partition(a,low,up,j)

if k=j then return

else 

if k<j then up=j

else low=j+1

}

until false

پیچیدگی Select در بدترین حالت n^2 است

[manager]

3- اگر داشته باشیم t(n)=ct(n/3)+O(n^3) سپس از طریق روش اصلی برای حل معادلات بازگشتی باید داشته باشیم c=9
4و5 - جواب هنوز لگارتمی منتها به جای لگاریتم بر پایه 2 بر پایه 3 است.
6 - t(n)=10*t(n/3)+O(n^2)

به نظرم اینا سوالای انتهای کتابه نه تست های ارشد.

[xxxxx_xxxxx]

برنامه كامل سؤال اول.
از كتاب مقسمي هست.
البته خطاهايي داشت كه رفع شد.

#include<conio.h>

#include<stdio.h>

int selection(int x[],int left,int right,int k);

int partition(int x[],int left,int right,int &pivotpoint);

void swap(int &a,int &b);

void main()

    {

    clrscr();

    int m,ans;

    int a[10]={20,89,11,5,34,22,16,93,64,1};

    printf("Enter Critical Area:");

    scanf("%d",&m);

    ans=selection(a,0,9,m);

    printf("No. is:%d",ans);

    getch();

    }

int selection(int x[],int left,int right,int k)

    {

    int pivotpoint;

    int low,high;

    low=left;

    high=right;

    if(left==right) return x[left];

    else

        {

        pivotpoint=partition(x,low,high,pivotpoint);

        if(k==pivotpoint)

            return x[pivotpoint];

        else if(k<pivotpoint)

            return selection(x,left,pivotpoint-1,k);

        else

            return selection(x,pivotpoint+1,right,k);

        }

    }

int partition(int x[],int left,int right,int &pivotpoint)

    {

    int i,j,pivot;

    j=left;

    pivot=x[left];

    for(i=left+1;i<=right;i++)

        if(x[i]<pivot)

            {

            j++;

            swap(x[i],x[j]);

            }

    swap(x[left],x[j]);

    pivotpoint=j;

    }

void swap(int &a,int &b)

    {

    int t;

    t=a;

    a=b;

    b=t;

    }