الگوریتمی می خواهم که a به توان n را به روش تقسیم و حل بدست بیاورد

[student of software]

با سلام ؛

الگوریتم تقسیم و حل برای a به توان n

[برنامه نویس 2]

اگر aبه توان nرا برابر با mباشد و شما مقدار mو aرا داشته باشید
کافی است یک حلقه whileنوشته که در ان
while m>1
m=m/a
n=n+1
wend
print n

[MMMYousefMMM]

روش تقسیم و حل با حلقه 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;
}

[اَرژنگ]

روش تقسیم و حل با حلقه while نیست عزیز. بلکه برنامه باید بصورت بازگشتی باشد اگرچه از روشه که فرستاده شده بود سر درنیاوردم، ولی دلیلی نداره که روشه تقسیم و حل باید بصورت بازگشتی باشد، بلکه روشهایه بازگشتی معمولاً استعداد دارند که برایه روشه تقسیم و حل استفاده بشند.

[k.robot]

روش تقسیم و حل با حلقه 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;
}
1این که تقسیم و غلبه نیست استقراست
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
}

[MMMYousefMMM]

کاملا زیبا کار می کند و خیلی ساده و قابل درک است و این کد شماست که با وجود بهینگی نسبی درک آن مشکل است. در ضمن تقسیم و غلبه است

[k.robot]

my friend
let people judge about them;D

[اَرژنگ]

کاملا زیبا کار می کند و خیلی ساده و قابل درک است و این کد شماست که با وجود بهینگی نسبی درک آن مشکل است. در ضمن تقسیم و غلبه است
با سلام،
من تا ۲ ماه پیش مثله شما فکر میکردم منتها بعد از کلی برری به این نتیجه رسیدم که منظور از تقسیم (بعضیا بهش میگن غلبه) و حل با روشه اسنباطه یکمی فرق داره.
در همینجا یک پست بود در مورد اسفاده از تقسیم و حل برایه فاکتوریل.
من دقیاً همین اشکال شما را بازگو کردم ولی بد از بررسی ه این نکات پی بردم:
۱) روشه تقسیم و حل در هر قدم تقسیم مکنه و قسمهایه کوچکر را در دفعه بعد تقسیم مکنه.
روشه استنباط که جنابه کی رباط بهش اشار کردن فقط از قسمته قبلی یکی کم میکن،
برایه دیدن فرق بینه روشه استنباط (روشی که شما مثالش را زدید) و روشه تقسیم و حل که چنابه کی‌رباط مثال فرستادند،
با کاغذ و قلم ۲ را به توانه ۹ برسانید. روشه استنباط :


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



در ضمن کسی نگفت که روشه شما اشتباهه، فقط اینکه روشه استنباط را استفاده میکنه نه تقسیم و حل.
با تشکر از شما و جنابه کی‌رباط برایه این بحض که فرقه بین روشها را کاملاً آشکار میکنه

[ramkly]

این روش بهترین روش برای به توان رساندن است چون پیچیدگی اجرایی این الگوریتم 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

[rahnama66]

با عرض سلام خدمت دوستان ضمن احترام به نظر همه دوستان وقتی توان خیلی بزرگ میشه باید مبنای دو آن عدد را حساب کرد فرضا 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 چون باید خودم بنویسم :چشمک:

[reza6384]

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


این کد تقسیم و غلبه هست، (شرط Small داره و مسئله رو به 1 و n-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;
}

باید توجه کرد که فراخوانی بازگشتی برای سیستم سربار داره و اینکه ما بیایم یه الگوریتم رو بدون اینکه زمانشو بهبود ببخشیم از روش تقسیم و غلبه با کد بازگشتی حل کنیم فایده ای نداره.

در ضمن. یه کم با هم مهربونتر باشیییییییین!

[meysam_pro]

بهترین به نقل از 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
}