انجمنصفحه اولجستجوی انجمن

[mosenabdoli]

(۲۹ بهمن ۱۳۸۹ ۰۲:۴۸ ب.ظ)shahryar نوشته شده توسط:  اون احتماله D می شد.
سوال جستجو هم زدم اولی BFS ودومی DFS.
سوال منطق رو زدم c and p
سوال هرس می شد اونی که با ۹ شروع می شد.
سوال quick sort زدم logn
سوال huresticرو زدم admisible هست ولیmonotonic نیست.
سوال زمان بندی ordersh چن بود؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

زمانبندیه مربوط به درخت قرمز و سیاه بود... خیلی نامردیه درخت قرمز و سیاه تو سرفصل نیست.

---

(۰۸ اسفند ۱۳۸۹ ۰۴:۲۵ ب.ظ)MJRS نوشته شده توسط:  

(08 اسفند ۱۳۸۹ ۰۱:۵۰ ب.ظ)nasr نوشته شده توسط:  سوال ۴۸ الگوریتم چراs-p/m+p نمیشه؟

کلید اولیه هم همین گزینه رو اعلام کرده.

همین درسته. مهندسی ۸۴ اومده بود. جزوه‌ی پارسه رو نیگا کن

[Mansoureh]

(۱۴ اسفند ۱۳۸۹ ۰۷:۱۹ ب.ظ)۱۲۳javad نوشته شده توسط:  سوال ۵۹ هوش رو دوباره با دقت بررسی کنی
فکر کنم
هم گزینه ای که با ۱۰ شروع میشه و هم گزینه ای که با ۹ شروع میشه جواب باشه

نه! گزینه ای که با ۱۰ شروع میشه گره‌ی ۸ هم هرس میشه!
اول گره‌ی ۱۰ رو بررسی میکنه و گره‌ی ۱۰ تا ریشه بالا میاد!
بعد گره‌ی ۹ رو بررسی میکنه،
بعد که میخواد گره‌ی ۸ رو بررسی کنه، چون پدرش Max هست پس همون ۹ انتخاب میشه یعنی اگر مقدار کمتر از ۹ باشه تاثیر نداره! حالا باید این فرض رو کرد که ممکنه به جای مقدار ۸ مقداری بیشتر از ۹ داشتیم که مقدارش از Max بگذره! فرض میکنیم مقدارش مثلاً ۹/۵ هست! مقدار به پدر یعنی Max منتقل میشه و بالا میاد یعنی پدر Max که گره‌ی Min هست هم مقدار ۹/۵ رو میگیره ولی چون ریشه، Max میخواد همون گره‌ی ۱۰ جواب مورد نظره، پس باز هم فرقی نمیکنه که مقداری بیشتر از ۹ داشته باشه (توجه بشه که اگه مثلاً مقدارش از ۱۰ بیشتر بود، اون موقع هرس نمیشد ولی اینجا گفته مقادیر بین بازه‌ی بسته‌ی ۰ تا ۱۰ هستند! حتی اگه مقدارش هم ۱۰ باشه (بیشترین مقدار) باز هم بررسی نمیشه)

نتیجه: چون گره‌ی ۸ هم هرس میشه پس جواب مورد نظر نیست...
موفق باشید...

---

(۱۴ اسفند ۱۳۸۹ ۱۰:۴۳ ب.ظ)mosenabdoli نوشته شده توسط:  زمانبندیه مربوط به درخت قرمز و سیاه بود... خیلی نامردیه درخت قرمز و سیاه تو سرفصل نیست.

اگر منظورت از زمان بندی سئوال ۴۸ هست! اشتباه میکنی! این ماله قسمت زمان بندی های حریصانه است! صورت سئوال رو اگر با حوصله میخواندی میتونستی جواب بدی! معمولاً در اینجور مواقع آدم از صورت سئوال میترسه!

[mosenabdoli]

گزینه یک‌: E حداکثر میتونه ۲V-1 باشه و این هیچ وخت از V^2 بزرگتر نمی شه.
گزینه دو‌: v همیشه بین E+1 و ۲E-1 هستش (طوقه رو هم باید در نظر گرفت) پس گزینه ۲ درسته
گزینه سه‌: اگر E از V-1 کمتر باشه دیگه همبند نیست
گزینه چهار‌: اگه چند تا مثال بیاری و به توضیح گزینه دو دقت کنی اینم همیشه درسته

من این تست رو نزدم، فکر کنم جواب تو گزینه‌ها نیست.

---

(۱۴ اسفند ۱۳۸۹ ۱۱:۱۴ ب.ظ)Mansoureh نوشته شده توسط:  

(14 اسفند ۱۳۸۹ ۰۷:۱۹ ب.ظ)۱۲۳javad نوشته شده توسط:  سوال ۵۹ هوش رو دوباره با دقت بررسی کنی
فکر کنم
هم گزینه ای که با ۱۰ شروع میشه و هم گزینه ای که با ۹ شروع میشه جواب باشه

نه! گزینه ای که با ۱۰ شروع میشه گره‌ی ۸ هم هرس میشه!
اول گره‌ی ۱۰ رو بررسی میکنه و گره‌ی ۱۰ تا ریشه بالا میاد!
بعد گره‌ی ۹ رو بررسی میکنه،
بعد که میخواد گره‌ی ۸ رو بررسی کنه، چون پدرش Max هست پس همون ۹ انتخاب میشه یعنی اگر مقدار کمتر از ۹ باشه تاثیر نداره! حالا باید این فرض رو کرد که ممکنه به جای مقدار ۸ مقداری بیشتر از ۹ داشتیم که مقدارش از Max بگذره! فرض میکنیم مقدارش مثلاً ۹/۵ هست! مقدار به پدر یعنی Max منتقل میشه و بالا میاد یعنی پدر Max که گره‌ی Min هست هم مقدار ۹/۵ رو میگیره ولی چون ریشه، Max میخواد همون گره‌ی ۱۰ جواب مورد نظره، پس باز هم فرقی نمیکنه که مقداری بیشتر از ۹ داشته باشه (توجه بشه که اگه مثلاً مقدارش از ۱۰ بیشتر بود، اون موقع هرس نمیشد ولی اینجا گفته مقادیر بین بازه‌ی بسته‌ی ۰ تا ۱۰ هستند! حتی اگه مقدارش هم ۱۰ باشه (بیشترین مقدار) باز هم بررسی نمیشه)

نتیجه: چون گره‌ی ۸ هم هرس میشه پس جواب مورد نظر نیست...
موفق باشید...

---

(۱۴ اسفند ۱۳۸۹ ۱۰:۴۳ ب.ظ)mosenabdoli نوشته شده توسط:  زمانبندیه مربوط به درخت قرمز و سیاه بود... خیلی نامردیه درخت قرمز و سیاه تو سرفصل نیست.

اگر منظورت از زمان بندی سئوال ۴۸ هست! اشتباه میکنی! این ماله قسمت زمان بندی های حریصانه است! صورت سئوال رو اگر با حوصله میخواندی میتونستی جواب بدی! معمولاً در اینجور مواقع آدم از صورت سئوال میترسه!

منظورم زمان بندی خطی سوال ۵۰ بود، قرمز سیاهه فکر کنم ...

---

(۰۳ اسفند ۱۳۸۹ ۱۰:۵۳ ق.ظ)msghasemi نوشته شده توسط:  سوال ۵۹
اول مکس مقدار ۸ رو انتخاب میکنه.
بعدش بین مقدار ۵ و ۲ در قسمت دوم مقدار ۵ رو انتخاب میکنه و مین موقتا مقدار ۵ رو بر میداره.
اولین شاخه‌ی هرس شده هرس میشه چون مقدار فعلی نسبت داده شده به مین باید کمتر از ۵ باشه تا عوض بشه و بهر حال مکس بین اون مقدار و ۸ قطعا ۸ رو انتخاب میکنه.
تو مرحله‌ی آخر اول مقدار ۹ رو به مین نسبت میدیم که قطعا اگر همین مقدار بمونه مکس اون رو به ۸ ترجیح میده و اون رو بر میداره.پس مین باید بره سراغ اینکه ببینه آیا میتونه مقدار خودش رو کمتر کنه یانه.و همین باعث میشه تا گره های سمت راستی رو ویزیت کنه و این یعنی هرس نمیشن.

---

(۰۳ اسفند ۱۳۸۹ ۰۳:۱۷ ق.ظ)MJRS نوشته شده توسط:  من هم بر اساس اینکه قبلا این سوال رو دیده بودم گزینه ۳ رو بدون اینکه فکر کنم زدم ولی الان که شما گفتی رفتم دوباره چک کردم و در نهایت تعجب دیدم که جواب نه گزینه ۱ و نه گزینه ۳ هست. جواب این سوال در کلید نهایی سال ۱۳۸۴ گزینه ۲ بوده یعنی S/ m - Pn !!!!

این لینک کلید این سال بوده:

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


سوال ۳۸ اون سال !!

MinCut در یک گراف یعنی یک سری از یال‌ها رو از بین ببری به طوری که گراف حاصله هم بند نباشه و مجموع یال هایی که cut شده مینیمم باشه.
وقتی اندازه همه یال‌ها یک واحد زیاد شه به وضوح هزینه Cut هم به اندازه تعداد یال هایی که cut میشه زیاد میشه و این دو مقدار برابر نیستند.

جواب سوال ۴۹ گزینه ۲ میشه که ویرایشش کردم. اولی و سومی غلط هستند به نظرم.

من جواب سوال ۴۸ رو با دو مرجع چک کردم و هردو گزینه‌ی ۱ رو تایید کردن.اگر هم شما عدد بذارین گزینه‌ی ۱ رو نزدیکتر میبینین.من هم از کلید تعجب کردم.این مساله اثبات ریاضی داره.

گزینه چهار مطمینا مقدارش از گزینه ۱ بیشتره و میشه یه مثالی زد که گزینه چهار دربیاد. (البته گزینه چهار اثبات هم داره) اگه میخوای مثالشو بزنم!؟
و اگه همچین مثالی وجود داشته باشه یعنی گزینه یک نمی تونه جواب باشه

---

(۳۰ بهمن ۱۳۸۹ ۱۲:۲۹ ق.ظ)javadjj نوشته شده توسط:  در اینکه درخت پوشا و کوتاه ترین مسیر یکی هستش شکی نیست اما مجموعه برش یعنی اون مجموعه ای که تا حالا در یک طرف جزو گره های انتخابی هستش و با اضافه شدن یال من با مثال به این رسیدم که فرق میکنه

کوتاهترین مسیر که یکی نیست رفیق. مسیری که دو یال داره ۲ واحد بهش اضافه می شه در صورتی که مسیری که ۴ یال داره ۴ واحد بهش اضافه می شه.(همونی که آفاق میگه)