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

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

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 را بیابید

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

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

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

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

نقل قول:

---

فرض کن عنصر 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)

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

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

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

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

نقل قول:

---

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

---

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

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

نقل قول از کتاب طراحی الگوریتم ها نوشته بهروز قلی زاده؛ صفحه 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 است

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)

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

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

#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;

    }