الگوریتم Fast Exponentiation در زبان برنامه نویسی جاوا

راهبرد تقسیم و غلبه

راهبرد حل مسئله به روش تقسیم و حل, راهبردی نیست که جدیدا به دنیای الگوریتم ها وارد شده باشد.شاید حتی بیش از دو قرن از آن بگذرد. روشی که ناپلئون, امپراتور فرانسه در نبرد اوسترلیتز در دوم دسامبر 1805 به کاربرد .ارتشی مرکب از سربازان اتریشی و روسی به جنگ با ناپلئون امده بودند که تعداد‌ آنها به حدود 15000 نفر از افراد ناپلئون بیشتر بود. سپاه اتریشی-روسی حمله ای گسترده علیه فرانسویان آغاز کرد. ناپلئون به قلب سپاه حمله کرد و نیرو ها را به دو بخش تقسیم کرد.از آن رو که هر بخش به تنهایی از پس ارتش ناپلئون بر نمی‌آمد ,ارتش ناپلئون بر آنها چیره شد.

امروزه این روش را به نام Divide and conquer (تقسیم و حل/ غلبه) میشناسیم. روشی که در آن  حل مسئله ی اصلی به زیر مسئله های کوچکتر و راحت تر تقسیم شده و پس از حل زیر مسئله ها ترکیب گشته و مسئله ی اصلی حل میشود.

الگوریتم به توان رساندن اعداد

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

public static int pow(int base,int exp){
int n=base;
for(int i=1;i<exp;i++){
n=n*n;
}
return n;
}

زمان اجرای این الگوریتم, زمان نه چندان مطلوب O(n) است.اما با دیدگاه تقسیم و غلبه میتوان این زمان را به O(lgn) کاهش داد.

الگوریتم Fast Exponentiation (توان رسانی سریع)

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

حالا بیاید فرمول بالا رو از راست به چپ بخونید. متوجه میشید که درواقع ما میتونیم توان رسانی رو اینطوری انجام بدیم :

البته این برای حالتی هست که n زوج باشه. اگر فرد بود داریم یه دونه R اضافه داریم که باید ضربش کنیم :

مثلا اگر n = 5 باشه و R=3 داریم:

حالا که دقیقا فهمیدیم چی میخوایم بریم سراغ کد :

public static int fastExp(int base,int exponential){
if(exponential==0){
return 1;
} else if(exponential==1){
return base;
}
int R = fastExp(base,exponential/2);
if(exponential%2==0){
return R*R;
}
return R*base*R;
}

همانطور که در کد مشاهده میکنیم دو حالت زوج و فرد بودن توان رو چک کردیم و بر اساس اون یا R*R گذاشتیم و یا R*R * base.

دو شرط اول هم همان حالات پایه هستند.

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

موفق باشید.