جزو تمرین های کتاب طراحی الگوریتم بود؛ کسی تا حالا روش فکر کرده ؟ الگوریتمش رو داره؟ پیچیدگیش چقدره؟
جزو تمرین های کتاب طراحی الگوریتم بود؛ کسی تا حالا روش فکر کرده ؟ الگوریتمش رو داره؟ پیچیدگیش چقدره؟
خب اگه می شه توضیح بدید که اصلاً این روش غلبه و حل چیه؟
خب اگه می شه توضیح بدید که اصلاً این روش غلبه و حل چیه؟
salam azizam manam migam aslan avalesh begoo in raveshe ghalabe va hal chiye ta bad javabeto bedim ba tashakor
یا حداقل مشخصات این کتابو کامل تر بده
درس طراحی الگوریتم ها رو انتخاب کن.خب اگه می شه توضیح بدید که اصلاً این روش غلبه و حل چیه؟
آخه ماهیتش طوری نیست که بشه از D&C استفاده کردنوشته شده توسط Afshin_Zavar
You never know what you can do until you try
چرا؟ منطقش معلومه
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)
رو کال کنید
You never know what you can do until you try
ممنون.
فکر میکنی، پیچیدگیش چند باشه ؟
از اونجایی که
لیست رو دوبار نصف میکنه؛ فکر میکنم در بدترین حالت ، تتای n باشهfact:=fact(min,mid)*Fact(Mid+1,a);
باید حساب کرد ولی فکر نمیکنم پیچیدگی بدی داشته باشه.
در ضمن دو بار هم نصف نمی کنه دو بار کال میکنه که اونم هیچ راهی نداره
اگر اشتباه نکنم پیچیدگی اش N هست
You never know what you can do until you try
با سلام
دوستان به نظر من هم این تابع نمی تواند الگوی D&C باشد همانطور که می دانید حداقل بایستی بتوان مسئله رادر مرحله اول به دو نیمه تقسیم کرد که البته این کار در سایر مراحل نیز الزامیست . مثلا Quick Sort یک نمونه خوب تقسیم و غلبه است .
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول