PDA

View Full Version : سوال الگوریتمیک



shokoofeh68
دوشنبه 12 اسفند 1387, 14:43 عصر
الگوریتمی که باقیمانده تقسیم xبه توان nبر pرا محاسبه کند(صفحه 50 از کتاب نی÷ولیتان)
اگه کسی بتونه کمکم کنه ممنون میشم
در ضمن از مرتبه nlognباشه:چشمک:

crazy_scientist2000
جمعه 16 اسفند 1387, 00:59 صبح
به نظرِ من بهترين راه اينه كه اين كار و با ۲ 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 هم ميتونين انجام بدين تقريبا مثل همين يكم فكر كنين حالا

zeinalkhani
جمعه 16 اسفند 1387, 04:28 صبح
الگوریتمی که باقیمانده تقسیم xبه توان nبر pرا محاسبه کند(صفحه 50 از کتاب نی÷ولیتان)
اگه کسی بتونه کمکم کنه ممنون میشم
در ضمن از مرتبه nlognباشه:چشمک:
فرض کنید:
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]
بنابراین کافیست مقدار بالا را تا رسیدن به یک مقدار آستانه محاسبه کنید.

shokoofeh68
جمعه 16 اسفند 1387, 21:44 عصر
دقيقا سوال 29 از صفحه 50 كتاب نيپوليتانه(ترجمه جعفر نژاد)
ولي دوست عزيز منظور از pيك چند جمله ايست يا يك عدده!!!
من خوب منظور شمارو متوجه نشدم

zeinalkhani
جمعه 16 اسفند 1387, 22:21 عصر
منظور از p یک عدده.

از روش تقسیم و غلبه استفاده کردم. کجاشو متوجه نشدین؟

shokoofeh68
جمعه 07 فروردین 1388, 14:40 عصر
كدش رو ميتونين بذارين؟

zeinalkhani
چهارشنبه 12 فروردین 1388, 03:31 صبح
کدشو گذاشتم. فقط دقت داشته باشید که برای داشتن مرتبه 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);
}

k0r00sh
پنج شنبه 02 اردیبهشت 1389, 01:50 صبح
ببخشید.
ولی استاد ما این مسئله رو گفت که n= 2^k نه اینکه x=2^k

nima898
یک شنبه 05 اردیبهشت 1389, 10:53 صبح
ببخشید.
ولی استاد ما این مسئله رو گفت که n= 2^k نه اینکه x=2^k

چه فرقی میکنه؟