menusearch
javapro.ir

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

جستجو
شنبه ۸ مهر ۱۴۰۲ | ۱۷:۱۲:۳۴
۱۴۰۲/۶/۲۰ دوشنبه
(14)
(0)
الگوریتم Fast Exponentiation در زبان برنامه نویسی جاوا
الگوریتم  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 اضافه داریم که باید ضربش کنیم :

 

Fast Exponentiation

 

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

مثال توان رسانی سریع

 

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

 

کد الگوریتم Fast Exponentiation
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.

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

 

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

موفق باشید.

نظرات کاربران
*نام و نام خانوادگی
* پست الکترونیک
* متن پیام

بستن
*نام و نام خانوادگی
* پست الکترونیک
* متن پیام

7 نظر
فائزه هاشمی
دوشنبه بیستم شهریور ۰۲
پاسخ
(4)
()
فائزه هاشمی
بسيار جامع و واضح. تشکر 🙏
عارف
دوشنبه بیستم شهریور ۰۲
پاسخ
(5)
()
عارف
يک کاربر ملموس در برنامه نويسي رو ميتونيد نام ببريد؟
امیر علی درفشان
دوشنبه بیستم شهریور ۰۲
پاسخ
(5)
()
امیر علی درفشان
عالي باز هم آموزش هاي اين چنيني بذاريد،لذت بردم
امیر علی درفشان
دوشنبه بیستم شهریور ۰۲
پاسخ
(5)
()
امیر علی درفشان
عالي لطفا باز آموزش هاي الگوريتمي بذاريد
محمدرضا
دوشنبه بیستم شهریور ۰۲
پاسخ
(7)
()
محمدرضا
عالي و کاملا شفاف. خسته نباشين
دیبا رشیدی
دوشنبه بیستم شهریور ۰۲
پاسخ
(7)
()
دیبا رشیدی
ممنون از مقاله خوبتون بسيار مفيد بود👌🏻
ساناز اردشیری
دوشنبه بیستم شهریور ۰۲
پاسخ
(10)
()
ساناز اردشیری
بسيار عالي و جامع بود🙏🏻
پاسخ مدیر سایت
خواهش میکنم،سپاس از همراهی تون
پاسخ مدیر سایت
هدر سایت
زودتر از دیگران از جدیدترین مطالب آموزشی برنامه نویسی جاواپرو اطلاع پیدا کن
 شاید برای شما کم اهمیت باشد; اما حمایت مالی به جاواپرو جان می‌دهد
سوالات متداول برنامه نویسی
گفتگو را شروع کنید
مشاوره ،تدریس خصوصی و سفارش انجام انواع پروژه های برنامه نویسی