سلام دوستان
من هنوز در جستجوی راه حل ضرب یک عدد در خودش توسط همنهشتی هستم. البته اون الگوریتم دوست خوبمون نیز بسیار جالب بود ولی باید با همنهشتی نوشته بشه.
سوال اول:
بحث مربوط به مجموعه ها و زیر مجموعه ها در تئوری اعداد
یک مثالی در کتاب اومده. فرض کنید که می خواهیم عدد 2 را 5 بار در خودش ضرب کنیم. مجموعه حاصل که اون رو Z نامیده و پایین Z نیز عدد 6 گذاشته یعنی پیمانه 6.
1-حالا 2 به پیمانه 6 می شه 2
2-2*2 به پیمانه 6 می شه 4
3-2*2*2 به پیمانه 6 می شه 0
4-2*2*2*2 به پیمانه 6 می شه 2
5-2*2*2*2*2 به پیمانه 6 می شه 4
جواب های 2و4و0و2و4 را اینگونه حساب می کند که:
توان عدد 2 ضرب در خود عدد2 به پیمانه 6. مثلاً 8 برابر است با 2 به قوه 4، پس 2*4=8 و 8 به پیمانه 6 می شود عدد 2.
حالا می خواهیم زیر مجموعه های این مجموعه را به دست آوریم:
کد:
برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید
ولی من نمی دونم این زیر مجموعه ها چگونه حساب می شوند و چه ربطه ای می تونن به ضرب یک عدد در خودش به اندازه n بار داشته باشند؟
سوال دوم:
در کتاب آمده است که الگوریتمی وجود دارد که همنهشتی را در زمان
کد:
برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید
محاسبه می کند. زمان لازم برای gcd(a,n) نیز logn است.
حالا فرض کنیم که می خواهیم 2^6 را حساب کنیم. در ابتدا
کد:
برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید
حالا این مقدار در حافظه باقی می ماند و دیگر حساب نمی شود.
کد:
برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید
و حالا گام آخر:
کد:
برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید
پس در نهایت، ما 3 عمل ضرب و 8 عمل همنهشتی داشتیم.
آیا این استدلال درست است؟ آیا هزینه حساب همنهشتی ها نمایی نمی شود؟ چون دقیقاً به تعداد همنهشتی ها 2logn داریم.
چه ارتباطی بین سوال اول(مجموعه ها و زیر مجموعه ها) با سوال دوم وجود دارد؟