(۲۵ بهمن ۱۳۹۵ ۱۲:۰۲ ب.ظ)wskf نوشته شده توسط:  سلام دوستان
سوال زیر رو بر چه اساسی حل کرده ؟

اول به جواب این سوال نگاه کنید

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


این سوالی که پرسیدید در نگاه اول سخت به نظر میرسه ولی آسونه فقط باید روش رو بدونید (به ذهن خودم هم الان رسید).
گزینه‌ی ۱ رو در نظر بگیرید. اگه از چپ شروع کنیم، E و F و G هیچ کدوم در جای خودشون نیستند ولی A در جای خودش به درستی درج شده. B هم درست درج شده ولی فعلا همین A رو در نظر بگیرید. یعنی فرض میکنیم اول A اومده و چون ۳ خالی بوده، در اون درج شده.
بعدش فرض میکنیم B اومده و در جای درست خودش درج شده. اول سعی یا در واقع فرض میکنیم اونایی که توو جای درست هستند رو درج کنیم بره. یعنی فرض کنیم زودتر اومدند چون مثلا اگه فرض نکنید که B همین اوایل اومده، ممکنه مثلا یه Z داشته باشیم که توو ۴ درج شده، بعدش هم یه W داشتیم که اونم میخواسته توو ۴ درج بشه ولی چون جا نبوده اومده ۵ رو که خالی بوده گرفته! پس برای اینکه چنین مشکلی پیش نیاد، اول فرض میکنیم که اونایی که جاشون درست هست رو اختصاص بدیم تا بلکه یه ترتیبی از اومدن‌ها یا ورود متغیرها رو به دست بیاریم که بتونند این جدول رو بسازند.
خلاصه اول A و سپس B اومدند و در جای خودشون درج شدند. D جاش باید ۴ باشه در جالی که در ۶ درج شده. پس نتیجه میگیریم که قبلش یکی اومده جای D در ۴ رو گرفته. این میتونسته یه عنصری باشه که خودش ۴ رو میخواسته، ِیا اینکه یکی بوده که ۳ رو میخواسته ولی چون قبلش A در ۳ درج شده، اومده اولین خالی که ۴ باشه رو گرفته. هیچ عنصری به جز D خونه‌ی ۴ رو نمیخواسته و C اونجا نشسته که جور هم در میاد. چون C 3 رو میخواسته ولی A اونجا بوده، پس C اومده به خونه‌ی ۴/ فعلا ترتیب از چپ به راست اینطوری شد: A,D,C و خونه‌های ۳ و ۴ و ۵ هم پر شدند.
حالا از آنجایی که D اومده در ۶ نشسته (در حالی که ۴ رو میخواد در اصل) پس اینطوری میگیریم که بعد از اون ۳ متغیر، D اومده بوده و به ۴ نیاز داشته ولی چون پر بوده، میاد به اولین خالی که ۶ باشه.
پس ترتیب میشه A,B,C,D و خونه‌های ۳ و ۴ و۵ و ۶ پر میشن.
بعدش باید فرض کنیم که E اومده چون که در خونه‌ی ۰ قرار گرفته. یعنی E میخواسته بره ۵ ولی چون پر بوده، ۶ هم پر بوده، از اونور شروع میکنه و در اولین خالی که ۰ باشه میشینه.
بعدش هم که F و G میان به ترتیب و چون خونه‌هایی که میخوان پر هستند، از اونور آرایه شروع میکنند و به ترتیب در ۱ و ۲ میشینن.

برای گزینه‌ی ۳ هم یه ترتیب میتونه اینطوری باشه مثلا:
A,E,C,G,B,D,F

برای ۴ هم اینطوری:
A,D,E,F,C,G,B

ولی گزینه‌ی ۲ همون اول به تناقض میخوره. فقط G در جای درست هست پس اول از همه اومده. حالا اگه بعدش A اومده باشه، باید در ۴ بشینه که نیست. پس A نبوده. اگه B اومده باشه باید در ۵ بشینه چون خالی هست هنوز ولی اونجا نرفته. C اگه اومده باشه باید در ۴ بشینه که اونجا نیست. D باید در ۴ بشینه (که خالی هست) ولی رفته به ۵ پس D هم نبوده دومین ورودی. اگه E دومین بوده باشه باید باید بره ۵ که خالی هست ولی نرفته. اگه هم F بوده باشه که باید بره به ۶ ولی نرفته. پس با هیچ منطقی جور در نمیاد.
دقت شود که اولین ورودی حتما باید G بوده باشه چون اولش همه خالی هستند و هر چی اومده باشه باید مکانش درست باشه که فقط G اینطوری هست.