مشکل در یه الگوریتم دارم

[k00r0sh]

سلام بچه ها.
توی یه تاپیک این سوال رو جواب دادن.

یک الگوریتم θ(nlog n) بنویسید که باقیمانده تقسیم X^n بر P را محاسبه نماید
(برای سهولت می توانید فرض کنید که n توانی از 2 است یعنی n=2^k و k یک عدد صحیح مثبت است)

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

من کامپیوتر نیستم.واسه خانمم میخوام. ممنون میشم ازتون:گیج:

[qwerty11]

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


a^(2k) = (a^k)^2
a^(2k+1) = (a^2k)*a


متوجه شدین دیگه !؟ اینجوری میتونین هر مرحله توان رو نصف کنین و در نتیجه الگوریتمی با پیچیدگی log n دارین.

[k00r0sh]

سلام
نه! متوجه نشدم. میشه کاملتر بگین؟

راستی کدشم میخواستم. ممنون میشم

[qwerty11]

خوب کجاشو نفهمیدین آخه !؟ فکر کنم به اندازه ی کافی واضح بود ! anyway :




If f(N) = x^N % P


N=1 ===> f(N) = x%P
N be even ===> f(N) = f(N/2)^2%P
N be odd ===> f(N) = f(N-1)*x%P



long f(long N){
if(N==1) return x%p;
if(N%2==0) return (long)(Math.pow(f(N/2),2)%p);
else return f(N-1)*x%p;
}

[k0r00sh]

ممنون.بررسی کنم ببینم چطوره.
دستت درد نکنه