سلام دوستان چرا این سوال زیر با فرمولی که تو پارسه گفته حل نمیشه
[/align]
2(n-2^logn)+1
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام. لطفا از این به بعد از tex استفاده کنید.
فرمولش مشخص نیست و هم این که کتابش رو ندارم.
اما کلا توضیح سوال این هست که دفعه ی اول تمامی گره های فرد از لیست حذف میشن. علتش این هست که [tex]p\uparrow.next\: [/tex] یعنی اون گره ای که p داره بهش اشاره میکنه که دفعه ی اول ۱ هست، حالا [tex]p\uparrow.next\: \uparrow.next\: ==\: node1\uparrow.next[/tex]
node i رو گره ی حاوی data i در نظر گرفتم. این [tex]p\uparrow.next\: \uparrow.next\: [/tex] یعنی ۲. حالا این دستور [tex]p\uparrow.next\: =p\uparrow.next\uparrow.next\: [/tex] یعنی الان اون جایی که گره ی ۱ اشاره میکنه یعنی ۲ بشه جایی که p داره اشاره میکنه. اشاره گر به گره ی ۱ نداریم، گره ی ۱ حذف میشه. حالا توی دستور [tex]p=p\uparrow.next[/tex] یعنی حالا اون جایی که p داره اشاره میکنه رو بذار توی p یعنی در واقع بهش یکی اضافه کن. حالا به ۳ اشاره میکنه.
دوباره الان که به ۳ داره اشاره میکنه همون بلایی سرش میاد که سر ۱ اومد. ۳ حذف میشه دفعه ی بعد به ۴ اشاره میکنه و با دستور بعدی به ۵ اشاره میکنه. بعد ۵ حذف میشه و …. یعنی فرد ها حذف میشن.
بعدش الان گره هایی که باقی مونده :
۲۰۴۸ ………… ۸ ۶ ۴ ۲
الان همون روال رو این جا داریم. یعنی ۲ اول حذف میشه بعد ۶ بعد ۱۰ و … یعنی گام حذف شدن ۴ هست اینجا و از ۲ هم شروع کردیم پس تمامی گره هایی که به صورت ۲+۴k هستند حذف میشن.
سری بعدی چیزی که مونده :
۲۰۴۸ ….. ۱۲ ۸ ۴ این دفعه ۴ و ۱۲ و ۲۰ و … حذف میشن یعنی گام ۸ هست و از ۴ شروع شده. تمامی گره هایی که به فرم ۸k+4 هستند حذف میشن.
خب ادامه میدیم. با این فرمولا میشه فهمید کدوم گزینه ها حذف میشن و کدوم میمونه.
راه دومی که قطعا به جواب برسیم این هست:
این جا واسه ۸ تایی حل میکنم. ۲۰۴۸ تایی هم مثل همین هست. هر دو توانی از ۲ هستند. تنها حالتی که ممکن بود فرق کنه این بود که لیست رو با طول فرد در نظر بگیریم که نمی گیریم.
الان واسه ۸ تایی هر بار با اجرای دستورات به ترتیب گره های زیر در هر خط باقی میمونه:
p=8 1,2,3,4,5,6,7,8
p=2 2,3,4,5,6,7,8
p=4 2,4,5,6,7,8
p=6 2,4,6,7,8
p=8 2,4,6,8
اولش خب ۱ حذف شده و p شده ۲. از ۸ شروع شده p (توی سوال از ۲۰۴۸) در واقع کد میاد عنصرِ بعدی رو حذف میکنه و و سریِ بعدی عنصر بعدیِ بعدی رو. یعنی وقتی از ۸ شروع میکنه و ۱ رو حذف میکنه، بعد از ۸ میاد از ۲ شروع میکنه. باید دقت کنیم هر توی هر خط p آپدیت میشه.
خب الان توی خط دوم p از ۲ شروع کرده و ۳ رو حذف میکنه و ادامه پیدا میکنه، آخرش هم p=6 میشه و ۷ رو حذف میکنه که الان p=8 میشه دوباره. میبینیم که دوباره رسیدیم به سر خط. اگه از ۲۰۴۸ هم شروع کنیم همین طوری هست و دوباره میرسیم بهش. یعنی بعد از اولین بار اجرای دستورات:
p=2048 2,4,6,8,…..,۲۰۴۸
یه بار دیگه که اجرا کنیم، اینا میمونه:
۲۰۴۸،……۴،۸،۱۲
*در اصل هر بار اونایی میمونه که indexشون زوج هست (از ۱ شروع کردیم اندیس رو و اندیس ۴ در بالا ۱ هست و اندیس ۸ ۲ هست….)
یه بار دیگه که اجرا کنیم:
۲۰۴۸,……۸,۱۶,۲۴,۳۲
پس: بار اول تمامی اعداد هستند. بار دوم فقط مضارب ۲. بار سوم مضارب ۴. بار چهارم فقط مضارب ۸. یه بار دیگه ادامه میدیم:
۲۰۴۸,….۱۶,۳۲
مضارب ۱۶ موندن. سری بعدی فقط مضارب ۳۲ میمونه و همین طور تا آخر یعنی بار kام مضارب [tex]2^k[/tex] باقی میمونه. نهایتا مضارب ۱۰۲۴ باقی میمونه:
p=2048 1024,2048
توی مثال ۸ تایی هم دیدیم که آخرش ۸ موند و نصفش یعنی ۴
که حالا الآن ۱۰۲۴ حذف میشه و ۲۰۴۸ باقی میمونه.