جزو تمرین های کتاب طراحی الگوریتم بود؛ کسی تا حالا روش فکر کرده ؟ الگوریتمش رو داره؟ پیچیدگیش چقدره؟
Printable View
جزو تمرین های کتاب طراحی الگوریتم بود؛ کسی تا حالا روش فکر کرده ؟ الگوریتمش رو داره؟ پیچیدگیش چقدره؟
خب اگه می شه توضیح بدید که اصلاً این روش غلبه و حل چیه؟
خب اگه می شه توضیح بدید که اصلاً این روش غلبه و حل چیه؟
salam azizam manam migam aslan avalesh begoo in raveshe ghalabe va hal chiye ta bad javabeto bedim ba tashakor
یا حداقل مشخصات این کتابو کامل تر بده
درس طراحی الگوریتم ها رو انتخاب کن.نقل قول:
خب اگه می شه توضیح بدید که اصلاً این روش غلبه و حل چیه؟
آخه ماهیتش طوری نیست که بشه از D&C استفاده کردنقل قول:
نوشته شده توسط Afshin_Zavar
چرا؟ منطقش معلومه
4! = (4*3 *(2*1)
یعنی باید MID رو پیدا کنیم و از یک تا MID و از MID تا N رو به هم ضرب کنیم و بعد بهم JOIN کنیم.
منتها در پیاده سازیش مراحل بازگشتی رو گم میکنم.
function fact(Min , a:Integer):Integer;
var
Mid:Integer;
Begin
if min=a then
fact:=a
else if a<=1 then
fact:=1
else if (Min+1)=a Then
Fact:=min*a
else
Begin
mid:=Min+(a-Min) div 2;
fact:=fact(min,mid)*Fact(Mid+1,a);
end;
End;
برای محاسبه فاکتوریل 5 باید
Fact(1,5)
رو کال کنید
ممنون.
فکر میکنی، پیچیدگیش چند باشه ؟
از اونجایی که
لیست رو دوبار نصف میکنه؛ فکر میکنم در بدترین حالت ، تتای n باشهنقل قول:
fact:=fact(min,mid)*Fact(Mid+1,a);
باید حساب کرد ولی فکر نمیکنم پیچیدگی بدی داشته باشه.
در ضمن دو بار هم نصف نمی کنه دو بار کال میکنه که اونم هیچ راهی نداره
اگر اشتباه نکنم پیچیدگی اش N هست
با سلام
دوستان به نظر من هم این تابع نمی تواند الگوی D&C باشد همانطور که می دانید حداقل بایستی بتوان مسئله رادر مرحله اول به دو نیمه تقسیم کرد که البته این کار در سایر مراحل نیز الزامیست . مثلا Quick Sort یک نمونه خوب تقسیم و غلبه است .