الگوریتم توان رسانی

[zahra6666]

سلام. یه الگوریتم توان رسانی هست تو درس طراحی الگوریتم..... با روش تقسیم و غلبه حل میشه...
میشه یه مثال برای خروجی بزنید.... با تابع بازگشتی نوشته میشه ولی من خروجی رو صحیح نمی تونم به دست بیارم... الگوریتمشو دارم ولی بلد نیستم چطوری کار می کنه....
#include <iostream>
using namespace std;
float xton(int base,int pow)
{
int y;
if(pow==0)
return 1;
else if(pow==1)
return base;
else
{
y=xton(base,pow/2);
if(!(pow%2))
return y*y;
else
return y*y*base;
}

}

int main()
{
int base,pow;
cout<<"please enter the base:";
cin>>base;
cout<<"please enter the power:";
cin>>pow;
cout<<xton(base,pow);
return 0;
}
درخت بازگشتی رو نشون بدین...
فقط اگه تاپیک جای بدی باز کردم نبندید منتقل کنید جای بهتر پیدا نکردم مرسی.

[a.r.khoshghalb]

سلام.
الگوریتمی که نوشتین یک الگوریتم سریع برای محاسبه توان است. زمان اجراش (log(pow هست.
توضیحش هم خیلی ساده است.
فرض کنید قراره a رو به توان b برسونیم.
اولین راه حل اینه که بگیم :

c = a * a * a * ... * a
ما توی این روش b تا عملیات ضرب رو انجام میدیم.
اگر b مساوی 8^10 باشه یک ثانیه طول میکشه. (*نگید اااووووهههه! این که خیلی خوبه! به توان 8^10 فقط یک ثانیه! در آخر مثالی میزنم تا متوجه بشید این خوب نیست)

چطور میشه این رو سریع ترش کرد؟ یک روش نوشتاری دیگه اون عبارت اینه :

c = (a*a) * (a*a) * ... * (a*a)
همونطوری که میبینید ما داریم عبارت a*a رو b/2 بار حساب میکنیم و ضرب در هم میکنیم! خوب چه کاریه! یک بار ضرب کنیم و مقدارش رو توی یه متغیر مثلا y بریزیم. حالا باید این رو حساب کنیم :

c = (y) * (y) * (y) * (y) * ... * (y)
یعنی b/2 عملیات ضرب که با یک ضرب برای حساب کردن y میشه b/2 + 1 عملیات ضرب. بهتر شده ولی بازم خوب نیست.

حالا بیا بیشتر ببریم تو پرانتز.
یعنی :

c = (a*a*a) * (a*a*a) * ... *(a*a*a)
این دفعه برای حساب کردن توی پرانتز 2 تا عملیات میخوایم و b/3 ضرب بین پرانتز ها هست. میشه مجموعا b/3 + 2 عملیات.

و اگر 4 تاش کنیم میشه:

c = (a*a*a*a) * (a*a*a*a) * ... * (a*a*a*a)
که میشه b/4 + 3 عملیات.
اما اگر عبارت داخل پرانتز رو هم همینطور حساب کنیم چی؟ الان حساب کردن a*a*a*a سه عملیات میخواد. اما میشه اون رو به این صورت نوشت :

a*a*a*a = (a*a)*(a*a)
که نشون دادیم این رو میشه با 2 عملیات حساب کرد.
پس یکی بهتر شد. شد : b/4 + 2

ایده اصلی این الگوریتم همینه. من الان یه شهودی بهت دادم که ببینی چه اتفاقی داره میوفته.
مشخصه که هر چی تعداد اعضای تو پرانتز بیشتر باشه بهتره. (تا زمانی که تو پرانتز ها تعداد یکسانی باشه)
پس میان میگن اینطوری بنویسیم:

c = (a*a*a*...*a)*(a*a*a*...*a)
حالا کلا یک عملیت ضرب بین پرانتز ها داریم.
هر پرانتز رو با چه قدر میشه حساب کرد؟ به صورت بازگشتی همین الگوریتم رو برای پرانتز هم اجرا میکنن.
به این ترتیب اگر b = 8 باشه الگوریتم میشه :

(a*a*a*a*a*a*a*a)

(a*a*a*a)*(a*a*a*a)

(a*a)*(a*a)*(a*a)*(a*a)

(a)*(a)*(a)*(a)*(a)*(a)*(a)*(a)

یعنی تابع توان ما شد این :

f(a,b): a^b

f(a,b) = f(a,b/2) * f(a,b/2)

نکته ای که وجود داره اینه که اگر b زوج باشه، میشه دقیقا 2 تا b/2. ولی اگر b فرد باشه میشه 2 تا b/2 با یه دونه دیگه.
یعنی مثلا برای b = 9

c = (a*a*a*a)*(a*a*a*a)*a
کد سی پلاس پلاس اش:

int f(int a, int b)
{
int c = f(a, b/2);
c *= c;
if (b % 2)
c *= a;
return c;
}


سوالی بود بپرس.
و در آخر باید بگم که چه قدر از ادیتور این فروم متنفرم. :لبخندساده:

[a.r.khoshghalb]

یادم رفت مثالی که گفتم رو بزنم و البته درخت رو هم نکشیدم و نگفتم هم چرا زمان اجراش log هست.
الان دیگه حال ندارم فردا میام می نویسم.
:لبخندساده:

[zahra6666]

سلام ممنون از توضیحات کاملتون...
ولی من نمی تونم درخت براش رسم کنم یعنی درخت جور نمیشه...
بی زحمت یه درخت براش رسم کنید.. ممنون

[zahra6666]

خوش قلب جان چی شد پس ... درخت می خواممممم....:لبخند:

[علیرضا.ا]

اینم ی روش تقریبا مشابه (بدون بازگشت البته) با (O(log n

long pow(int x,int y){ long r=1;
while(y!=0){
if(y%2==0){
x*=x;
}
else{
r*=x;
x*=x;
}
y/=2;
}
return r;
}

[zahra6666]

ممنون... ولی من درخت بازگشتب می خوام... میخوام مرحله به مرحله ببینم چی میشه... خودم نمی تونم درست رسمش کنم...پلیزززز

[chikar]

یادم رفت مثالی که گفتم رو بزنم و البته درخت رو هم نکشیدم و نگفتم هم چرا زمان اجراش log هست.
الان دیگه حال ندارم فردا میام می نویسم.
:لبخندساده:
فکر کنم فردا شده ها!!:قهقهه:

[zahra6666]

کمکککککککککککککک کمککککککککک کممکککککککک کممممممممممممممممکککککککک ککککککککککککککککککککککککک ککککککککککککککککککککک
اهای اهالی برنامه نویس

[zahra6666]

بابا کسی بلد نیست یعنی درختشو بکشه..... منو بگو که فک کردم اینجا خیلی مهندس هست..... اه:عصبانی++::عصبانی++::گریه::گ� �یه:

[golbafan]

مهندس هست حالش نیست!

[zahra6666]

خوب میخواید یه جک تعریف کنم حالشو پیدا کنید....
بیاید کمک دیگه عوضش 10 تا صلوات برای سلامتی تون می فرستمممم///// خوبه؟؟؟؟:تشویق::بامزه::متفک� �:

[ali chegini]

سلام. به نظر من در توابع بازگشتی ابتدا باید شرط های پایانی رو نوشت و فراخوانی تابع به صورت زیر باعث مشکل در برنامه میشه.


کد سی پلاس پلاس اش:

int f(int a, int b)
{
int c = f(a, b/2);
c *= c;
if (b % 2)
c *= a;
return c;
}





در توابع بازگشتی معمولا پایین به بالا هستن یعنی جواب از برگ های پایین میاد بالا.
131097

[zahra6666]

خیلی ممنون اقای چگینی..
ولی من درخت بازگشتی برای اولین کدی که گذاشتم را می خواهم....
لطفا کمک کنید...
با تشکر

[amirtork]

131175
سلام،
توضیحات رو سعی کردم به طور کامل تو عکس بدم.

[zahra6666]

ای با با ...
ببینید این درخت: برای پایه 2 و توان 4
(4و2)
.
.
.
(2و2)
.
.
.
(1و2)
در نهایت 2 برگشت داده میشه.....
که میشه: 2*2*2=8
خوب جواب دو به توان چهار که 16 میشه..
کجا رو دارم اشتب می رمممم؟؟؟؟

[ali chegini]

سلام . شما شرط رو درست بررسی نمیکنید. من قسمت شرط رو به صورت زیر تغییر دادم تا متوجه اشتباه تون بشید.

float xton(int base,int pow)
{
int y;
if(pow==0)
return 1;
else if(pow==1)
return base;
else
{
y=xton(base,pow/2);
if((pow%2)==0)
return y*y;
else
return y*y*base;
}


}




بررسی مرحله به مرحله :
مرحله یک :
(2,4)
تو این مرحله دوباره خود تابع فراخوانی میشه.
مرحله دو :
(2,2)
تو این مرحله دوباره خود تابع فراخوانی میشه.
مرحله سه :
(2,1)
چون مقدار توان یک شده 2 برگشت داده میشه . و از مرحله سه به مرحله دو بر می گردیم جایی که تابع دوباره فراخوانی شده بود . که مقدار y =2 میشه. بعد اگر توان که 2 هست به 2 بخش پذیر باشه مقدار 2 * 2 برگشت داده میشه.
که باعث میشه به مرحله یک برگردیم جایی که تابع رو صدا زدیم که مقدار y = 4 شده و توان که 4 هست و به 2 بخش پذیره پس مقدار 4 *4 برگشت داده میشه که باعٍث میشه به مرحله قبل تر برگردیم که پایان کاره و 4 * 4 میشه 16.

[a.r.khoshghalb]

سلام به همه عزیزان
zahra6666 معذرت میخوام بابت تاخیر! نبودم!
اول از همه اینکه ali chegini یه نکته ای رو اشاره کرد. تابعی که کدشو زدم اشتباهه. کد صحیح اینه :

int f(int a, int b)

{
if (b == 1) return a;
if (b == 0) return 1;

int c = f(a, b/2);
c *= c;
if (b % 2)
c *= a;
return c;
}





دوم درخت! درخت این تابع خیلی ساده است. در هر اجرا، فقط یک بار دیگه صدا زده میشه تابع.
کاغذ ندارم که درخت بکشم برات ولی میشه یه خط صاف. یعنی:

f(a,b) --> f(a,b/2) --> f(a,b/4) --> ...

موند اینکه چرا Log هست اوردرش.
اثبات سختی نمیخواد، میدونیم وقتی b=1 یا b=0 بشه الگوریتم تمومه، هر دفعه هم b داره تقسیم بر 2 میشه. طبق تعریف لگاریتم، (Log(b بار نصف میشه و زمان اجراش هم (Log(b هست.