الگوریتم محاسبه فاکتوریل؛ به روش غلبه و حل

[Developer Programmer]

جزو تمرین های کتاب طراحی الگوریتم بود؛ کسی تا حالا روش فکر کرده ؟ الگوریتمش رو داره؟ پیچیدگیش چقدره؟

[msnasiri]

خب اگه می شه توضیح بدید که اصلاً این روش غلبه و حل چیه؟

[msnasiri]

خب اگه می شه توضیح بدید که اصلاً این روش غلبه و حل چیه؟

[kiani_behzad]

salam azizam manam migam aslan avalesh begoo in raveshe ghalabe va hal chiye ta bad javabeto bedim ba tashakor

[msnasiri]

یا حداقل مشخصات این کتابو کامل تر بده

[Developer Programmer]

خب اگه می شه توضیح بدید که اصلاً این روش غلبه و حل چیه؟
درس طراحی الگوریتم ها رو انتخاب کن.

[mzjahromi]

جزو تمرین های کتاب طراحی الگوریتم بود؛ کسی تا حالا روش فکر کرده ؟ الگوریتمش رو داره؟ پیچیدگیش چقدره؟
آخه ماهیتش طوری نیست که بشه از D&C استفاده کرد

[Developer Programmer]

چرا؟ منطقش معلومه


4! = (4*3 *(2*1)

یعنی باید MID رو پیدا کنیم و از یک تا MID و از MID تا N رو به هم ضرب کنیم و بعد بهم JOIN کنیم.
منتها در پیاده سازیش مراحل بازگشتی رو گم میکنم.

[mzjahromi]

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)

رو کال کنید

[Developer Programmer]

ممنون.
فکر میکنی، پیچیدگیش چند باشه ؟
از اونجایی که

fact:=fact(min,mid)*Fact(Mid+1,a);

لیست رو دوبار نصف میکنه؛ فکر میکنم در بدترین حالت ، تتای n باشه

[mzjahromi]

باید حساب کرد ولی فکر نمیکنم پیچیدگی بدی داشته باشه.
در ضمن دو بار هم نصف نمی کنه دو بار کال میکنه که اونم هیچ راهی نداره

اگر اشتباه نکنم پیچیدگی اش N هست

[raha_hakhamanesh]

با سلام
دوستان به نظر من هم این تابع نمی تواند الگوی D&C باشد همانطور که می دانید حداقل بایستی بتوان مسئله رادر مرحله اول به دو نیمه تقسیم کرد که البته این کار در سایر مراحل نیز الزامیست . مثلا Quick Sort یک نمونه خوب تقسیم و غلبه است .