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

[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;
}