کلاً هیچ نظری رو الگوریتم ندارم. فکر کنم هیچی نزدم . دو تا سوال را میخواستم بزنم که شک کردم و پاک شون کردم بر خلاف بقیه دوستان که میگن الگوریتم آسان بوده من میگم الگوریتم مشکوکه
بچه‌ها اون کد رو چی زدین؟
اون که گفته بود در نهایت k چند رو برمیگردونه ؟
من زدم الگوریتم تموم نمیشه یعنی با مثال به این جواب رسیدم.
آره منم مثال زدم دیدم تموم نمیشه یعنی به حالت اول برگشت!
(۳۰ بهمن ۱۳۸۹ ۱۱:۰۶ ب.ظ)afagh1389 نوشته شده توسط: آره منم مثال زدم دیدم تموم نمیشه یعنی به حالت اول برگشت!من با دو تا مثال دیدم اون ۳ تا نمیشه!
در نتیجه همینی که شما زدیو تو آخرین لحظه زدم.
دفترچه های کنکور کارشناسی ارشد کامپیوتر سال ۱۳۹۰
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
در مورد اون کد اره گزینه ۴ میشد کد تموم نمیشد.
در مورد اون سوال کا امین عنصر در اجتماع دو لیست میشه lgn
در مورد کد هافمن هم بگم که با جستجوی خطی میشه n به توان دو.
معیار دفترچه D است که در سایت لینکشو دوستان گذاشتن
نظرتون در مورد سوال ۳۱ چیه ؟ کدوم گزینه درست است ؟من خودم ۳ زدم
رو سوال چی بود؟
سوال ۳۰ هم من بین دو گزینه شک کردم بین ۲و۳ نزدم.
راستی بچه‌ها سوال ۳۲ گزینه ۲ جواب میشه؟
به نظر من که جواب ۲ میشه من اینو زدم.
۳۲ یا ۲ یا ۳ من روی عبارت آخر شک دارم . البته من نزدم
تو هر گرافی در نظر بگیری با هر کدوم الگوریتم کوتاهترین مسیر بری درست در میاد پس تنها یه عبارت درسته.
ملاک گزینه‌ها دفترچه ۵۰۱D است.
سوال ۳۱: گزینه ۳، [tex]f(i)=MAX\begin{Bmatrix} f(i-1), w_{i} f(i-2) \end{Bmatrix}[/tex]
در این سوال برای محاسبه f برای خانه i ام، توجه می کنیم که پوستر یا در خانه iام نصب می شود یا خیر، اگر نصب نشود که مسلما بیشینه خانه‌ها تا خانه i - 1ام جواب خواهد بود. اگر پوستر روی خانه iام نصب شود، اولا w آن به جواب اضافه خواهد شد و ثانیا چون یک پوستر روی دو تابلوی پشت سر هم نمی تواند نصب شود مجموع وزن iام با بیشینه تا خانه i - 2ام جواب خواهد بود.
سوال ۳۲: گزینه ۱، (۲ گزاره درست است. با یه مقدار شانس!)
گزاره ۱ درست است. فرض کنیم یال e = uv در درخت باشد. همان رئوس u و v را در نطر می گیریم. اگر e کوتاهترین مسیر بین آن‌ها نباشد پس راسی مثل w وجود دارد که uw+wv < uv . توجه داریم که uvw یک دور تشکیل خواهند داد. حال با توجه به این که چنین دوری موجود است، اگر بخواهیم MST را بسازیم، یال uv نمی تواند در درخت باشد.(تناقض) چرا که یکی از روش های ساخت MST این است که در هر دور یال های با وزن ماکسیمم را حذف کنیم تا زمانی که گراف همبند باقی بماند. با این روش یال uv در MST نخواهد بود.
گزاره ۲ هم راه حلی به غیر از دایجسترا به ذهنم نرسید. (از BFS نمی توان استفاده کرد چون گراف وزن دار است، پس ممکن است وزن یال‌ها متفاوت باشد.) من این گزاره رو غلط فرض کردم.
گزاره ۳ درست است. اگر این دو یال در دو دور مجزا باشند، یا یکی یا هر دوی آن‌ها یال برشی باشند، مسلما هر دوی آن‌ها در MST خواهند بود. اگر هر دو در یک دور باشند، واضح است که دور با حداقل ۳ یال تشکیل می شود. در هر دوری که شامل هر دوی آن‌ها باشند، باید بقیه یال‌ها حذف شوند، چون بقیه مسلما وزن بیشتری نسبت به این دو دارند و حذف هر کدام از این دو موجب افزایش وزن کل MST خواهد شد.
سوال ۳۳: گزینه ۳، log n جواب است. برای پیدا کردن میانه (سوال CLRS) هزینه log n است. برای دیگر آماره‌ها با تغییراتی می توان به این زمان رسید.
سوال ۳۴: نزدم، ولی فکر کنم، ممکن است تمام نشود، جواب باشد.
سوال ۳۵: گزینه ۲، n^2 جواب است. در هر مرحله دو مینیمم را با تتای i (از ۱ تا n) پیدا می کنیم. آن‌ها را با عناصر انتهای آرایه تعویض کرده و در همان انتهای آرایه ادغام را انجام می دهیم. در هر مرحله طول آرایه به اندازه یک کم خواهد شد. هزینه اصلی پیدا کردن مینیمم هاست. اگر بخواهیم آرایه را ابتدا مرتب کنیم، ادغام و درج در آرایه در هر مرحله به همین هزینه منتهی خواهد شد.
سوال ۳۲ گزاره ۱ غلطه من سر کنکور این گزاره را رد کردم یک مثلث با دو وزن ۱ و یک وزن ۲ مثال بزن
نظر من درباره سوال ۳۴:
من تا الان ۳ بار مثال زدم و هر سه بار به جواب رسیدم
با استفاده از این مثال‌ها میتونم دو گزینه ۲و۳ رو حذف کنم و تا الان بیشتر از logn زمان نبرده.
به نظر من جواب گزینه ۴ هست.
دوستان اگه مثال نقض دارن بگن که چک کنیم شاید من ذهنم همش یه مدل داره مثال میزنه
(۰۲ اسفند ۱۳۸۹ ۰۳:۳۹ ب.ظ)hatami84 نوشته شده توسط: سوال ۳۲ گزاره ۱ غلطه من سر کنکور این گزاره را رد کردم یک مثلث با دو وزن ۱ و یک وزن ۲ مثال بزن
درسته، نمی دونم چرا فرض کردم که گراف وزن هاش متفاوته...
ان شاا... که دومی و سوی درستند....
ویرایش: میشه یه مقدار توضیح بدی، آخه گفته حتما دو راسی وجود خواهند داشت، یعنی تو مثال شما هیچ دو راسی وجود ندارند؟
البته اثبات من که کاملا غلطه....
(۰۲ اسفند ۱۳۸۹ ۰۴:۰۳ ب.ظ)khoofi66 نوشته شده توسط: نظر من درباره سوال ۳۴:منم سر جلسه مثال زدم و log n رو زدم
من تا الان ۳ بار مثال زدم و هر سه بار به جواب رسیدم
با استفاده از این مثال‌ها میتونم دو گزینه ۲و۳ رو حذف کنم و تا الان بیشتر از logn زمان نبرده.
به نظر من جواب گزینه ۴ هست.
دوستان اگه مثال نقض دارن بگن که چک کنیم شاید من ذهنم همش یه مدل داره مثال میزنه
ولی مثال زیر رو حل کن
A[1]=3
A[2]=1
A[3]=2