با سلام ؛
الگوریتم تقسیم و حل برای a به توان n
با سلام ؛
الگوریتم تقسیم و حل برای a به توان n
اگر aبه توان nرا برابر با mباشد و شما مقدار mو aرا داشته باشید
کافی است یک حلقه whileنوشته که در ان
while m>1
m=m/a
n=n+1
wend
print n
روش تقسیم و حل با حلقه while نیست عزیز. بلکه برنامه باید بصورت بازگشتی باشد که کدش چنینه
int power( int ,int );
void main(){
clrscr();
int x = power(2, 5);
cout<<x;
getch();
}
int power(int m, int n){
if(n > 0 )
return m*power(m,n-1);
return 1;
}
اگرچه از روشه که فرستاده شده بود سر درنیاوردم، ولی دلیلی نداره که روشه تقسیم و حل باید بصورت بازگشتی باشد، بلکه روشهایه بازگشتی معمولاً استعداد دارند که برایه روشه تقسیم و حل استفاده بشند.نقل قول:
نوشته شده توسط MMMYousefMMM
1این که تقسیم و غلبه نیست استقراستنقل قول:
نوشته شده توسط MMMYousefMMM
2 بهینه نیست
3 درستش اینه:
نقل قول:
float pow(float x, int n)
{
if (n==1)
return x;
y=pow(x,n/2);
if(n==n/2*2)
return y*y;
else
return y*y*x
}
کاملا زیبا کار می کند و خیلی ساده و قابل درک است و این کد شماست که با وجود بهینگی نسبی درک آن مشکل است. در ضمن تقسیم و غلبه است
my friend
let people judge about them;D
با سلام،نقل قول:
نوشته شده توسط MMMYousefMMM
من تا ۲ ماه پیش مثله شما فکر میکردم منتها بعد از کلی برری به این نتیجه رسیدم که منظور از تقسیم (بعضیا بهش میگن غلبه) و حل با روشه اسنباطه یکمی فرق داره.
در همینجا یک پست بود در مورد اسفاده از تقسیم و حل برایه فاکتوریل.
من دقیاً همین اشکال شما را بازگو کردم ولی بد از بررسی ه این نکات پی بردم:
۱) روشه تقسیم و حل در هر قدم تقسیم مکنه و قسمهایه کوچکر را در دفعه بعد تقسیم مکنه.
روشه استنباط که جنابه کی رباط بهش اشار کردن فقط از قسمته قبلی یکی کم میکن،
برایه دیدن فرق بینه روشه استنباط (روشی که شما مثالش را زدید) و روشه تقسیم و حل که چنابه کی‌رباط مثال فرستادند،
با کاغذ و قلم ۲ را به توانه ۹ برسانید. روشه استنباط :
Pow(2,9) =
2* Pow(2,8)=
2*2* Pow(2,7)
2*2*2* Pow(2^6)
.
.
.
2*2*2*2*2*2*2*2*2
روشه تقسیم و حل:
Pow(2,9)
Pow(2,1)*Pow(2,8)
Pow(2,1)*Pow(2,4)*Pow(2,4)
Pow(2,1)*Pow(2,4)*Pow(2,2)
Pow(2,1)*Pow(2,4)*Pow(2,1)*2
2*2^4*2^2
در ضمن کسی نگفت که روشه شما اشتباهه، فقط اینکه روشه استنباط را استفاده میکنه نه تقسیم و حل.
با تشکر از شما و جنابه کی‌رباط برایه این بحض که فرقه بین روشها را کاملاً آشکار میکنه
این روش بهترین روش برای به توان رساندن است چون پیچیدگی اجرایی این الگوریتم log n است و در تمام الگوریتمهای به توان رساندن بهترین الگوریتم است البته من به صورت pcudocode نوشتم اگر غیر بازگشتی این الگوریتم را هم خواستی بگو تا برات بنویسم.
;(procedure power (a,n
begin
(if n=1 return(a
if ((n mod 2)=0) then
begin
(p:= power(a,n div 2
(return (p*p
end
else
begin
(p:=power(a,n div 2
(return (p*p*a
;end
;end
با عرض سلام خدمت دوستان ضمن احترام به نظر همه دوستان وقتی توان خیلی بزرگ میشه باید مبنای دو آن عدد را حساب کرد فرضا 100=1100100
حال ه این شکل میشه توان 100 را نوشت
a*a=a^2*a^2=a^4*a^4=a^8*a^8=a^16*a^16=a^32*a^32=a^ 64*a^64
100=a^64*a^32*a^4
پیچیدگی زمانی محاسبه مبنای 2 برابر است با log n
با این روش خیلی سریع میتوان توان ها را حساب کرد که که log n مرحله است سپس آن های که لازمه در هم ضرب میکنیم
فکر کنم توضیحات کامل باشه واسه کدش اول بیاین مبنا دئ حساب کنید بعدم حاصل اونهایی که لازمه اگه نتونستین بگین تا بذارم codesho چون باید خودم بنویسم :چشمک:
این کد تقسیم و غلبه هست، (شرط Small داره و مسئله رو به 1 و n-1 زیر مسئله می شکنه ) . اما باید توجه کنی که آنالیز الگوریتم شما اینه :نقل قول:
int power( int ,int );
void main(){
clrscr();
int x = power(2, 5);
cout<<x;
getch();
}
int power(int m, int n){
if(n > 0 )
return m*power(m,n-1);
return 1;
}
T(n) = T(n-1) + 1 , T(1) = 1 ; => T(n) = n
این تابع هم همین کار رو می کنه و از زمان n هست :
int pow(int m,int n)
{
int i,sum;
sum = 1;
for(i=0;i<n;i++)
{ sum *= m; }
return sum;
}
باید توجه کرد که فراخوانی بازگشتی برای سیستم سربار داره و اینکه ما بیایم یه الگوریتم رو بدون اینکه زمانشو بهبود ببخشیم از روش تقسیم و غلبه با کد بازگشتی حل کنیم فایده ای نداره.
در ضمن. یه کم با هم مهربونتر باشیییییییین!
بهترین به نقل از k.robot
float pow(float x, int n)
{
if (n==1)
return x;
y=pow(x,n/2);
if(n==n/2*2)
return y*y;
else
return y*y*x
}