زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۶:۳۶ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

لیست پیوندی - ساختمان مقسمی

ارسال:
  

wskf پرسیده:

لیست پیوندی - ساختمان مقسمی

سلام دوستان چرا این سوال زیر با فرمولی که تو پارسه گفته حل نمیشه
[/align]
2(n-2^logn)+1


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

Pure Liveliness پاسخ داده:

RE: لیست پیوندی - ساختمان مقسمی

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

۰
ارسال:
  

Pure Liveliness پاسخ داده:

RE: لیست پیوندی - ساختمان مقسمی

سلام. لطفا از این به بعد از 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 هستند حذف میشن.
خب ادامه میدیم. با این فرمولا میشه فهمید کدوم گزینه ها حذف میشن و کدوم میمونه.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  کیوان فر ؟ خلیلی؟ مقسمی؟ msnmkh ۰ ۶۷۴ ۱۵ آذر ۱۴۰۱ ۰۷:۰۴ ب.ظ
آخرین ارسال: msnmkh
  مهمترین فصل های ذخیره و بازیابی مقسمی enofcom ۱۰ ۵,۴۳۹ ۲۵ آبان ۱۳۹۸ ۰۵:۲۳ ب.ظ
آخرین ارسال: alma1988
Question لیست پیوندی porseshgar ۰ ۱,۴۱۸ ۲۸ بهمن ۱۳۹۷ ۰۳:۵۱ ب.ظ
آخرین ارسال: porseshgar
Question کدام یکی ؟ سیستم عامل مقسمی یا سیستم عامل موسوی طیبی (پوران پژوهش) javad94 ۲۲ ۲۴,۴۵۸ ۲۳ فروردین ۱۳۹۷ ۰۲:۱۸ ب.ظ
آخرین ارسال: agha_Yahya
  فعالین تبلیغات در تلگرام+لیست کامل zibaara ۱ ۱۶ ۲۳ دى ۱۳۹۶ ۱۰:۲۱ ق.ظ
آخرین ارسال: royka
  لیست کنفرانس های معتبر جهت ارسال مقاله alilash ۰ ۱,۷۳۱ ۲۸ شهریور ۱۳۹۶ ۰۲:۲۸ ب.ظ
آخرین ارسال: alilash
  موارد صف پشته و لیست پیوندی و.. در برنامه نویسی هم کاربرد داره؟ R.g- ۳ ۲,۶۴۴ ۰۵ شهریور ۱۳۹۶ ۰۱:۲۳ ق.ظ
آخرین ارسال: R.g-
  لیست انتخاب رشته پیشنهادی رشته آیتی هر دو گرایش alilash ۰ ۲,۰۱۷ ۲۲ خرداد ۱۳۹۶ ۱۲:۱۹ ب.ظ
آخرین ارسال: alilash
  روش تبدیل یک لیست صعودی از اعداد به max heap peace2013 ۳ ۲,۹۰۵ ۱۸ فروردین ۱۳۹۶ ۰۲:۴۰ ب.ظ
آخرین ارسال: msour44
Rainbow خریدار کتاب مدیریت دکتر پرچ+مقسمی farshad95 ۰ ۱,۲۹۸ ۰۵ آذر ۱۳۹۵ ۰۴:۳۱ ب.ظ
آخرین ارسال: farshad95

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close