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

[H3NGAM3H]

اینجور که بررسی سوالا رو میبینم فقط شانس بیارم درصد مشترکم نیاد زیر ۲۰!
پارسال که نخونده بودم همین زدم ..

[navid_itboy]

خدا کنه درصدم زیر ۲۰ نشه ای خدا یعنی نوکرتم..... الو صدام میاد یا درخواستا زیاده خط رو خط شده

[flowerirani]

(۲۴ بهمن ۱۳۹۲ ۰۲:۴۰ ب.ظ)Orchid نوشته شده توسط:  من این سوال رو نزدم اما اینطور فکر کردم که با هزینه nlogn از مین هیپ بر میداریم و با هزینه nlogm به مکس هیپ اضافه می کنیم که میشه nlogn + nlogm که توی گزینه ها نبود احتمالا من اشتباه می کنم جواب درست چی بوده؟

=================
سلام من حسینی اماز شیراز ؛ دانشجوی دکتر یوسفی بر حسب علاقه ۱سال زندگیم شده ساختمان والگوریتم اما نتونستم بیشتر از ۷تا بزنم ادغام ۲هیچ خیلی ساده ست شما ۲تا هیپ مین وماکس مثلا۱-۲ -۳ و دومی هم ۵-۶-۷-۸ -۹ بکش ب هسادگی حالت بدتره هم یعنی ماکش هیپ بساز اما با ریشه مین هیه یعنی ۱ریشه باشه بعد از شماره ۴ یعنی n/2 تا ۱ رو به ترتیب هیپی فای کن به راحتی میفهمی که میشه o(m+n
یا اینکه تو فصل داده دکتر یوسفی صفحه۲۲۴ تست۸۴ مهندسی ۸۶ نرم افزار هادی یوسفی اثبات میکنه با مرتبه ۲ میشه هیپ ساخت منوط به اینکه اعداد همه داده باشنوچون ۲هیچ همه اعدادش هستن اصلا شما برو قاطی پاتیشون کن بعد یا مین یا ماکس بساز هرجور عشقته اثبات میشه اگه از n/2 تا ۱ رو هیپیفای کنی بی لامصب میشه هیپ درست چه مین چه ماکس بقول یوسفی اله اکبر

---

(۲۴ بهمن ۱۳۹۲ ۰۲:۴۰ ب.ظ)Orchid نوشته شده توسط:  من این سوال رو نزدم اما اینطور فکر کردم که با هزینه nlogn از مین هیپ بر میداریم و با هزینه nlogm به مکس هیپ اضافه می کنیم که میشه nlogn + nlogm که توی گزینه ها نبود احتمالا من اشتباه می کنم جواب درست چی بوده؟

=================
سلام من حسینی ام از شیراز ؛ دانشجوی دکتر یوسفی بر حسب علاقه ۱سال زندگیم شده ساختمان والگوریتم اما نتونستم بیشتر از ۷تا بزنم ادغام ۲هیپ خیلی ساده ست شما ۲تا هیپ مین وماکس مثلا۱-۲ -۳ و دومی هم ۵-۶-۷-۸ -۹ بکش به سادگی حالت بدتره هم یعنی ماکش هیپ بساز اما با ریشه مین هیپه یعنی ۱ریشه باشه بعد از شماره ۴ یعنی n/2 تا ۱ رو به ترتیب هیپی فای کن به راحتی میفهمی که میشه o(m+n
یا اینکه تو فصل ساختمان داده دکتر یوسفی صفحه۲۲۴ تست۸۴ مهندسی ۸۶ نرم افزار هادی یوسفی اثبات میکنه با مرتبه n میشه هیپ ساخت منوط به اینکه اعداد همه داده باشن وچون ۲هیپ همه اعدادش هستن اصلا شما برو قاطی پاتیشون کن بعد یا مین یا ماکس بساز هرجور عشقته اثبات میشه اگه از n/2 تا ۱ رو هیپیفای کنی میشه هیپ ساخت . چه مین چه ماکس هیپ. بقول دکتر یوسفی اله اکبر

[elynn66]

بچه ها میشه بگید سوال ۳۸ ۴۴ ۴۸ آخر جوابشون چی میشه؟؟؟

[farzad.arshad]

(۲۶ بهمن ۱۳۹۲ ۱۲:۰۴ ب.ظ)H3NGAM3H نوشته شده توسط:  اینجور که بررسی سوالا رو میبینم فقط شانس بیارم درصد مشترکم نیاد زیر ۲۰!
پارسال که نخونده بودم همین زدم ..

درصد ۲۰ یا ۴۰ که چیزیو تضمین نمیکنه
مهم اینه بقیه چه کردن. فرمول محاسبه تراز رو ببینید، مشخص میشه براتون که درصد اصلا اهمیتی نداره

[mohammad.ardeshiri]

(۲۴ بهمن ۱۳۹۲ ۰۵:۴۴ ب.ظ)amir_hossein نوشته شده توسط:  اون سواله که گفته بود :

۱ - داخل مرتب سازی های مقایسه ای ، هر دو عدد که اختلافشون یه واحده حتما با هم مقایسه میشن

۲ - کوچکترین و بزرگترین حتما با هم مقایسه می شن

دومی که مطمینم نادرسته.

اولی رو چی زدین ؟

اولی حبابی که مقایسه میشن
دومی merg که نمیشن

[flowerirani]

(۲۴ بهمن ۱۳۹۲ ۰۲:۵۸ ب.ظ)ka arman نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ)blue70 نوشته شده توسط:  سلام به همه
اون سوال ساختمان داده که درخت جستجوی دودویی متوازن بود یکی از مقادیر گره ها به خاطر نویز تغییر می کرد مرتبه اش چی میشد ؟

nlogn یا log n؟

سلام...
به نظر من میشه (O(n+lgn)=O(n

==================
نه عزیزم نه کاکام!!! پسر خوب وقتی اسم نود خاصی رو نمیبر هیعنی ادرسشو نداریم ذکر کلمه bstمتوازن یا همون avlکه معرف نام تولید کنندگان ای ندرخته بنام اقایان ادلسون و ولسکی از روسیه یعنی رد گم کنی وقتی میگه کمتین مرتب هبیشتر میپیچونه شک نکنید میشه o(n)
چر ا؟
چون یکی از نودها خراب شده بیا یه پیمایشش کن اگه صعودی نبود لامصب خراب شده و چون ممکنه گره اخر خراب شده پس حتما باید همه پیمایش بشه

---

(۲۴ بهمن ۱۳۹۲ ۰۳:۰۰ ب.ظ)AMTP نوشته شده توسط:  یکی از سوالا گفته بود چند جمله صحیح است جملاتشم نزدیک بودن: ساختمان داده ای با قابلیت پوش و پاپ و یافتن مین و ماکس از مرتبه ۱
فک کنم دو جملش صحیح بود درسته؟

چون ما رنج اعداد ر ونداریم با هش نمیشه پس با مرتبه یک هیچ ساختمان داده ایی نداری ماگه رنج اعداد ر وداشتیم میتونستی میه ساختمان داده درست کنیم بعد هرعددی دیدم بریزیم توش واسه خذف-- کنی مواسه درج ++ کنی متو هر خونه ولی این سوال لامصب نگفته بود هیچ اطلاعاتی از اعداد نداده بود پس هرسه گزینه غلط هست

---

(۲۴ بهمن ۱۳۹۲ ۰۳:۰۵ ب.ظ)راضیه اکبری نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۲:۵۹ ب.ظ)Fot30 نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۲:۵۵ ب.ظ)mehdi1902 نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۲:۴۵ ب.ظ)راضیه اکبری نوشته شده توسط:  برای ترکیب دو هیپ من اینطوری گفتم که در زمان nlogn و mlogm ماکس و مین هیپ تبدیل به دو ارایه مرتب میشن حالا در بدترین حالت برای ادغام دو ارایه m+n-1 میشود و ساخت یک ماکس هیپ با m+n عنصر در زمان o(m+n هستش پس نهایتا داریم nlogn+mlogm+o(m+n که میشه nlogn+mlogm اگه اشتباه میکنم بگین لطفا که فردا این اشتبا ه رو تو کنکور مهندسی نکنم احیانا

این سوالش اشتباه نبود :-؟
یه دونه O(n) برای تبدیل مین به ماکس. یه دونه min {logn , log m} هم برای اینکه به هم وصل بشن. مثلن ماکس یکی رو بیاریم ریشه و مرتبش کنیم درخت رو و فرزند دیگه شو بذاریم اون یه درخت. یعنی میشه
n + min {logn , logm}

شما وقتی دو تا آرایه رو به هم تو یه آرایه ادغام میکنید زمان m+n-1 نیازه فکر کنم
در نهایت شما یک آرایه m+n+1 عنصری نامرتب خواهید داشت که با مرتبه زمانی O(m+n) هیپ را با آرایه به صورت درجا خواهید ساخت. اصلا نیاز به logm یا logn و این چیزا نیستش بنظرم

من سرکلاس هادی یوسفی بودم همینو بدونین طبق یه قضیه تو سوال ۸۴صفحه ۲۲۴ داده دکتر یوسفی با هزینه o m+n میشه ۲تا هیپ ر وادغام کرد شک دارین ۲تا هیپ بسازین امتحان کنین

اخه اولش دو تا هیپ داریم برای اینکه ارایه بشن یه هزینه ای باید بکنیم دیگه , هوممم نمیدونم دیگه

---

(۲۴ بهمن ۱۳۹۲ ۰۳:۰۵ ب.ظ)mehdi1902 نوشته شده توسط:  

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

اون وزن های متمایز رو فک کنم اشتباه زدی. گزینه ۱ میشد. که گفته بود درخت است :دی
اگه ۳ تا یال باشه که وزن همه ۵ باشه مثلن. درخت پوشا یکی میشه

======================
سوال ۴۸ ایتی ابهام داره اگه احتمالی فکر کنیم هرگز متمایز نمیشه اما اگر منظور طراح نامرد که الهی خیر نبینه این حتما همیشه درحت پوشا ترتیب یالهاش یکسان شده متمایز درسته اگه احتمالی باشه یه دخت با سه یال ر وتصور کنید یال چپ ۱کی باشه ۲تا یال هم سمت راست بعدش به ترتیب یال اول سمت راست ۱ و دومی ۲باشن بعدش اگه پریم از ریشه اول سمت راست رو انتخاب کنه و کراسکال هم بره سمت چپ از ریشه چون کراسکال هم میتونه بر هراست هم چپ چون کراسکال نچسب هست یعنی میتونه ناهمبند باشه پس فرض اینه که پریم ار ریشه بخ چش یال ۱ ر وانتخاب کنه بعد بر ه راست باز م یال مساوی رو انتخاب کنه یعنی یال اولی سمت راست=۱ هزینه میشه ۲ یال اخرشم ۲میشه ۱+۱+۲=۴ پریم
اما کراسکا هم اگه از ریشه در بدو شروع بره چپ مسلما دومیه میره سمت راست ۱+۱=۲ بعدشم سمی+۲جمعا میشه ۴ ااااا هردوتاشوت یکی شدن با درخت و با یالهای یکسان به نظر من سوال ابهام داره و هر ۴گزینه مشکل دارن اما گراف کامل نزدیکترین گزینه به سوال هست
اگه غلط املایی هام زیاده ببخشید من دیگه حال ندار م برگردم قلم بگیرم

---

(۲۴ بهمن ۱۳۹۲ ۰۳:۰۶ ب.ظ)virtual girl نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۲:۵۹ ب.ظ)mehdi1902 نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۲:۵۴ ب.ظ)izadan11 نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ)blue70 نوشته شده توسط:  سلام به همه
اون سوال ساختمان داده که درخت جستجوی دودویی متوازن بود یکی از مقادیر گره ها به خاطر نویز تغییر می کرد مرتبه اش چی میشد ؟

nlogn یا log n؟

من زدم n
مشکل کار اینجاست که سوال مشخص نکرده ما گره رو داریم یا نه
چون گفته بود گرهی من فرض کردم که نداریم و با یک dfs میشه از پیچیدگی n
اگر هم منظور دونستن گره بوده میشه log n

منم n زدم. احتمالن منظورش این بوده که گره معلوم نیس

==============
وقتی تشخیص یعنی کل درخت ایا bst‌هست یا نه ؟اما چون ما ادرس نود خراب شده رونداریم پس حتما باید bst پیماشی بشه اگه بخای ارتفاعی حساب کنی که واسه هر شاخه یا هر نود باید شاخه ها ر وچک کنی میشه nبار واسه هر شاخه , iو هر بار مرتبه lg n که میشه جمعا nlog n پس n بهترین جواب هست
من زدم logn توجه داشته باشید گفته بود " تشخیص درخت" ! این کلمه تشخیص گفته منظورش چیه دیگه !

---

(۲۴ بهمن ۱۳۹۲ ۰۳:۱۶ ب.ظ)matt2007 نوشته شده توسط:  نه حرفتون درست نیست. ساختمان داده ای داریم که هم پوش و هم پاپ و هم پیدا کردن مینیمم از O(1) باشه
که نمونش در کنکور مهندسی کامپیوتر سال ۸۳ آورده شده
به نظر من با کمی تغییر میشه ماکسیمم رو هم در مرتبه ۱ حساب کرد
دو آرایه بگیرید که A و B باشند push و pop ذر A انجام میشه که قاعدتا O(1) هست در آرایه B درایه B[i] نشون دهنده کمترین عدد از ۱ تا i آرایه A هست
و ...

=======================
مهندس اون سوال رنج اعداد رو داده بود عزیز من از یک تارادیکال k استاد

[flowerirani]

(۲۴ بهمن ۱۳۹۲ ۰۳:۳۹ ب.ظ)mahsalove نوشته شده توسط:  من زدم
۲n-1 و n-1
مگه گزینه ۲n-1 و n هم داشت؟!:/

==========
تسلیت میگم به هردومون منم بخاطر کمبود وقت همین اشتباه روکردم عین شما وهمین گزینه ۴ر وزدم درحالی که ۱جواب بود حیف افسوس چقدر درس هوندم من رفتم داده الگوریتم ۱۰۰ بزنم خودمو کشتم ۸تا زدم۲تاش غلط شد

---

(۲۴ بهمن ۱۳۹۲ ۰۳:۵۸ ب.ظ)mohammad.ardeshiri نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۳:۴۶ ب.ظ)mahsalove نوشته شده توسط:  ا!
پس اینو هم غلط زدم
ظهر زنگ زدم به دکتر یوسفی یه سوال دیگم بود اونو هم غلط زدم که ادغام دو هیپ بود یوسفی گفت می شه n+m
من کلا شاهکارم
حالا خوبه امتحان اصلی فردا هست

اشتباه گفته nlogm+mlogn هست

==============
لطف ااظهار نظر نکن اقای باسواد دکتر یوسفی من شاگردش ودانشجوش بودم ای نمثال ر وبرام ۲بار حل کرد با o(n+m) یکم معلوماتتو اضاف هکنی بد نیست اگر هم بلد نیستی باسواد یه درخت بکش با سه نود و ۴نود یکی ماکس هیپ ویکی مین هیپ بعدش هرجور عشقته قاطیشون کن هرجود بعدشم هرجور عشقته مین یا ماکس بساز بعد از n/2 تا ۱ ر وهیپیفای کن هرنوعی بخای بدست میاد میشه o( m+n
اله اکبر شده که راجی دکتر یوسفی درحد اظهار نظر نیستی

[hamid88]

تا کلید رو سنجش مشخص نکنه همه این صحبتامون در حد فرض و احتمال
یه جا بود که همه موسسه ها میگفتن فلان سوال ۳ میشه در صورتی که سنجش گزینه ۱ رو درست اعلام کرد.
نهایتا ۵شنبه مشخص میشه

[flowerirani]

(۲۴ بهمن ۱۳۹۲ ۰۶:۴۲ ب.ظ)mahnaz31 نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۲:۴۰ ب.ظ)Orchid نوشته شده توسط:  من این سوال رو نزدم اما اینطور فکر کردم که با هزینه nlogn از مین هیپ بر میداریم و با هزینه nlogm به مکس هیپ اضافه می کنیم که میشه nlogn + nlogm که توی گزینه ها نبود احتمالا من اشتباه می کنم جواب درست چی بوده؟

دقیقا
من هم به این نتیجه رسیدم که تو گزینه ها نبود

===================
هرجوری عشقته قاطیشون کن میشه با مرتبه
o=m+n یا مین هیپ یا ماکس هیپ ساخت صرنفر اینو گفتن این سوال که موردی نداره سوال ۳۷ ۴۷۴۸ مور ددارن و یکم ۴۱

---

(۲۴ بهمن ۱۳۹۲ ۱۱:۰۳ ب.ظ)mahsalove نوشته شده توسط:  آخ جون ۲ تا سوال دیگه درست زدم
همین الان زنگ زدم به دکتر یوسفی گفتن اون که نویز بود می شه log n و اونم که تو الگوریتم مقایسه ای حتما با ید با هم مقایسه شن ۲ تا عنصر که اختلافشون ۱ میشه نا درست مثالشم heap sort
موفق باشید....

=============
هادی یوسفی خودش مردد بود درضمن باهاش شرط بستم میشه n‌چون خواهر گرامی من، هیچ اطلاعاتی از نود مورد نظر نداده بود هیچ اطلاعاتی وقتی اطلاعاتی نداری مبای دحتما پیماش بش هاین سوال بدتری نسوال امسال بود خیلی ابهام دار هفقط شانس دخیل توش نه علم

---

(۲۵ بهمن ۱۳۹۲ ۱۲:۰۲ ق.ظ)sohei.la نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۱۰:۲۷ ب.ظ)mehdi.m2 نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۱۰:۲۱ ب.ظ)mehdi1902 نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۱۰:۱۷ ب.ظ)sohei.la نوشته شده توسط:  منم درخت کشیدم nklogk بدست اوردم خدا کمک کنه بدبخت نشیم
اون سوال کصافط ادغام دو لیست به اندازه n کمترین بیشترین مقایسه n-1
۲n زدم آخه چرا زدم وقتی شک داشتممممممم چی میشد جوابش؟

فک کنم اونو درست زدی
۲n , n-1 میشه :-؟

نه n , 2n-1 می شه

شت!
از کجا بلدی؟

---

(۲۴ بهمن ۱۳۹۲ ۱۱:۴۷ ب.ظ)ka arman نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۱۱:۰۳ ب.ظ)mahsalove نوشته شده توسط:  آخ جون ۲ تا سوال دیگه درست زدم
همین الان زنگ زدم به دکتر یوسفی گفتن اون که نویز بود می شه log n و اونم که تو الگوریتم مقایسه ای حتما با ید با هم مقایسه شن ۲ تا عنصر که اختلافشون ۱ میشه نا درست مثالشم heap sort
موفق باشید....

به نظر من اون سوالی که نویز داشت n میشه شما احتمالا سوال رو بد به عرض دکتر رسوندی چون من از رو کتابای دکتر ساختمان و طراحی رو خوندم...

چی؟ نویز میشه logn???
مگه نباید پیمایش inorder بشه ک تشخیص بدیم دودوییه؟؟؟ سوالارو دکتر داشت؟

==========================
چرا منم نظر ماین چون اصلاعاتی از نود مربوطه نداده بای دپیمایش بش همیشه o n مگر طراح بیسواد باشه

[mahdiso]

(۲۸ بهمن ۱۳۹۲ ۰۴:۱۸ ب.ظ)mohammad-a نوشته شده توسط:  مثال نقض برای گزینه‌های ۱ و ۳ و ۴ سؤال ۴۸

(اینطور که مشخصه، گزینه ۲ هم نمونه نقض داره) احتمالاً سؤال حذف بشه!!

من با این که گزینه ۳ زدم ولی بعد از بررسی گزینه ۲ درسته، من نتونستم برای گزینه ۲ نقض گیر بیارم؛ اتفاقا کاملا هم منطقیه

ای کاش سرجلسه گیج بازی در نمیاوردم!

[*afsoon*]

(۲۸ بهمن ۱۳۹۲ ۰۴:۱۸ ب.ظ)mohammad-a نوشته شده توسط:  مثال نقض برای گزینه‌های ۱ و ۳ و ۴ سؤال ۴۸

(اینطور که مشخصه، گزینه ۲ هم نمونه نقض داره) احتمالاً سؤال حذف بشه!!

چطور برا گزینه سه نقض میشه اینجام که وزن یال ها متمایز هستن
این طور نیست؟

---

در مورد تعداد مقایسه های حداقل و حداکثر دو لیست مرتب شده من هنوز قانع نشدم!!!

[*afsoon*]

(۲۹ بهمن ۱۳۹۲ ۱۲:۱۳ ق.ظ)mohammad-a نوشته شده توسط:  

(29 بهمن ۱۳۹۲ ۱۲:۰۸ ق.ظ)*afsoon* نوشته شده توسط:  چطور برا گزینه سه نقض میشه اینجام که وزن یال ها متمایز هستن
این طور نیست؟

برای پریم به رأس شروع توجه کنید. ترتیب رو زیر شکل نوشتم

متوجه شدم اما گزینه دو هم که میتونه مثال نقض داشته باشه البته بستگی به مقدار K داره
پس جوابی نداره سوال

[shvh]

بچه ها با جوابای پارسه موافقید ؟؟؟
با همش موافقم جز : سوال ۴۱ !!!
من میگم میشه گزینه ۲
یعنی یکی درسته . اونم فقط infix
بقیه در صورتی درست میشد که از عملگر یکانی استفاده نشه !!!!

[pasbag]

(۲۴ بهمن ۱۳۹۲ ۰۹:۳۰ ب.ظ)itsgu88 نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۸:۰۹ ب.ظ)shvh نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۵:۳۰ ب.ظ)itsgu88 نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۴:۱۳ ب.ظ)hosshah نوشته شده توسط:  

(24 بهمن ۱۳۹۲ ۰۳:۰۹ ب.ظ)eli-77 نوشته شده توسط:  nklogk نمیشه به نظرتون؟؟؟؟

nklogk که نداره ولی من میگم همون nlogk میشه

فک میکنم گزینه آخر nklogk بود

---

من خودم ابتدا روی گزینه سوم یا چهارم فک میکردم اما اگه اونا رو انتخاب کنیم قسمت دوم صورت سئوال درست نمیشه!

مال من که nklogk داشت. جوابم همین میشه !

اثباتش رو میشه بگی؟

جواب این سوال صدرصد nk میشه با درخت بازگشتی میشه حل کرد
شما فرض کن n1=n/2,n2=n/2 و شروع به ساخت درخت می کینیم
در سطح صفر درخت مقدار nk به ما میده
در سطح ۱ مقدار nk/2
در سطح ۲ مقدار nk/4
در سطح ۳ مقدار nk/8
....
....
فک کنم تا سطح lon n+logk/2 میره
که اگر اینا رو با سیگما حل کنی می توان از nk فاکتور بگیری و داخل سیگما میشه [tex]\sum\frac{1}{2^i}[/tex] که اگر این سیگما به بی نهایت میل کنه فک کنم میشه تقریبا یک و از آنجا کا که از nk فاکتور گرفتیم جواب این تست میشود nk