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

[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]

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