سوال الگوریتمیک

[shokoofeh68]

الگوریتمی که باقیمانده تقسیم xبه توان nبر pرا محاسبه کند(صفحه 50 از کتاب نی÷ولیتان)
اگه کسی بتونه کمکم کنه ممنون میشم
در ضمن از مرتبه nlognباشه

[crazy_scientist2000]

به نظرِ من بهترين راه اينه كه اين كار و با ۲ 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]

الگوریتمی که باقیمانده تقسیم 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]

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

[zeinalkhani]

منظور از p یک عدده.

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

[shokoofeh68]

كدش رو ميتونين بذارين؟

[zeinalkhani]

کدشو گذاشتم. فقط دقت داشته باشید که برای داشتن مرتبه 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]

ببخشید.
ولی استاد ما این مسئله رو گفت که n= 2^k نه اینکه x=2^k

[nima898]

ببخشید.
ولی استاد ما این مسئله رو گفت که n= 2^k نه اینکه x=2^k

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