راه دومی که قطعا به جواب برسیم این هست:
این جا واسه ۸ تایی حل میکنم. ۲۰۴۸ تایی هم مثل همین هست. هر دو توانی از ۲ هستند. تنها حالتی که ممکن بود فرق کنه این بود که لیست رو با طول فرد در نظر بگیریم که نمی گیریم.
الان واسه ۸ تایی هر بار با اجرای دستورات به ترتیب گره های زیر در هر خط باقی میمونه:
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
توی مثال ۸ تایی هم دیدیم که آخرش ۸ موند و نصفش یعنی ۴
که حالا الآن ۱۰۲۴ حذف میشه و ۲۰۴۸ باقی میمونه.