الگوریتمی که باقیمانده تقسیم xبه توان nبر pرا محاسبه کند(صفحه 50 از کتاب نی÷ولیتان)
اگه کسی بتونه کمکم کنه ممنون میشم
در ضمن از مرتبه nlognباشه:چشمک:
Printable View
الگوریتمی که باقیمانده تقسیم xبه توان nبر pرا محاسبه کند(صفحه 50 از کتاب نی÷ولیتان)
اگه کسی بتونه کمکم کنه ممنون میشم
در ضمن از مرتبه nlognباشه:چشمک:
به نظرِ من بهترين راه اينه كه اين كار و با ۲ trees انجام بدين
اول N رو بگذارین توى ریشه درخت بعد اين كارها رو دنبال كنين
leftchild=n*n ya (n * root->leftchild)ke oon paeen baratoon tozih midam
rightchild=(leftchild)/p
اگه دقت كرده باشين درختِ بعدى كه تشكيل ميشه ریشه اش n*n هست بنابر اين براى
بچه هاى بuدى بجاى n*n بهتره كه بنويسيم leftchild->root->info البته اگه c كار ميكنيد
اين كارها رو تا وقتى ادامه ميدين كه عمق درختتون به برابر با ايكس بشه
اگه برابرِ z شد كافى كه فقط به اشاره گره پیمایش كننده درخت بگين كه بچه راست رو براتون بخونه و آخرين بچه راست همان مقدار مورد نظرِ شماست
البته اين كارها رو بدونِ استفاده از درخت با يه stack هم ميتونين انجام بدين تقريبا مثل همين يكم فكر كنين حالا
فرض کنید:نقل قول:
نوشته شده توسط shokoofeh68
a = k1 * p + r1
b = k2 * p + r2
در این صورت باقیمانده حاصلضرب آنها (a * b) بر p برابر باقیمانده r1 * r2 بر p خواهد بود.
از طرفی با توجه به صورت سوال می توان n را توانی از 2 در نظر گرفت. پس باقیمانده 2 به توان n*k بر p برابر است با:
[(2^(nk-1)) mod p]*[2 mod p]
بنابراین کافیست مقدار بالا را تا رسیدن به یک مقدار آستانه محاسبه کنید.
دقيقا سوال 29 از صفحه 50 كتاب نيپوليتانه(ترجمه جعفر نژاد)
ولي دوست عزيز منظور از pيك چند جمله ايست يا يك عدده!!!
من خوب منظور شمارو متوجه نشدم
منظور از p یک عدده.
از روش تقسیم و غلبه استفاده کردم. کجاشو متوجه نشدین؟
كدش رو ميتونين بذارين؟
کدشو گذاشتم. فقط دقت داشته باشید که برای داشتن مرتبه nlgn به این صورت حل میشه، وگرنه راه حل خیلی ساده تری هم میشه براش نوشت، مثلابا نصف کردن x در هر مرحله مرتبه الگوریتم lgn خواهد شد.
/* Return (2^exp)%p */
int Remainder(int exp, int p)
{
if(exp == 1)
return 2 % p;
else
return ((2 % p)* Remainder(exp - 1, p)) % p;
}
/*
O(nlgn)
Return (x ^ n) % p
x = 2 ^ k
*/
int Remainder(int k, int n, int p)
{
return Remainder(n * k, p);
}
ببخشید.
ولی استاد ما این مسئله رو گفت که n= 2^k نه اینکه x=2^k
چه فرقی میکنه؟نقل قول:
ببخشید.
ولی استاد ما این مسئله رو گفت که n= 2^k نه اینکه x=2^k