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

[good-wishes]

سوالاش یادم نمیاد . بچه ها کمک کنید
- سوال اول : فرض کنید میانگین اجرای یک الگوریتم A بر روی داده ها ی به اندازه n ، تتا n^2 باشد چند مورد از موارد زیر درست است؟
I - ورودی وجود دارد که مرتبه آن امگا n به توان ۳n باشد
II - ورودی وجود دارد که مرتبه آن تتا n باشد
III - ورودی وجود دارد که مرتبه آن O(1) باشد

گزینه ۲ : ۱ مورد

- سوالی که ایندکس سورت داشت : گزینه ۴ : بیشترین جابجایی وقتی اتفاق می افتد که ورودی برعکس مرتب شده باشد
- درخت متوازن که بیشترین طول وزن دار : گزینه ۱ : log n
- سوال ۳۱ جعبه در بدترین حالت چند جعبه باید باز بشه : گزینه ۱ : ۳۱ اول فکرکردم نکته خاصی داره حالتهای مختلف رو بررسی کردم اما به این نتیجه رسیدم بدترین حالت وقتیه که آخرین جعبه باشه پس باید همش باز بشه.

[lvlina_r]

سوال اول، منم یک در آوردم، ولی ترسیدم بزنم...
سوال بعدی این نمیشه
مثلا اگه
۵ ۴ ۳ ۲ ۱
باشه با ۲ حرکت منظم می شه
۱ ۴ ۳ ۲ ۵
۱ ۲ ۳ ۴ ۵
سوال جعبه هم من به همین نتیجه رسیدم

[Adel01]

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

اینا را موافقم

[maryam.raz]

من همه سوالات یادم نیست
۱)یکی اونی که مرتبه زمانی از تتای (n^2 بود وگفته بود میتونه مرتبه n یا یک و.. باشه
۲)یکی اون ۳۱ جعبه
۳)درخت متوازن
۴)اون الگوریتمی که یال منفی هم داشت من زدم هر۳
نمیدونم بازم بود یانه

[fsi2013]

در مورد گراف که یال max وmin بود فقط گزاره اخری درست بود
۳۱ جعبه رو ۳۱ حرکت
اون سوال اولم زدم هیچکدوم درست نیست
اون ارایه رو من زدم حالتی وجود داره که n-1 حرکت انجام بشه یعنی ارایه مثال زدم چک کردم شد

---

تنها سوال تخصصی جواب ندادم درخت متوازن بود و الان تو بخش پایگاه دیدم سوال ۱۰۵ هم بوده که من ندیدم خدایااااااااا!(( اخه چرا من دیگ نگاه کردم پشت برگه رو من دفترچه B بودم اصن نداشن به نظرم این سوالو ((

[lvlina_r]

(۲۰ بهمن ۱۳۹۱ ۰۴:۰۳ ب.ظ)fsi2013 نوشته شده توسط:  اون ارایه رو من زدم حالتی وجود داره که n-1 حرکت انجام بشه یعنی ارایه مثال زدم چک کردم شد

منم همین را زدم...

[good-wishes]

(۲۰ بهمن ۱۳۹۱ ۰۳:۵۸ ب.ظ)lvlina_r نوشته شده توسط:  سوال اول، منم یک در آوردم، ولی ترسیدم بزنم...
سوال بعدی این نمیشه
مثلا اگه
۵ ۴ ۳ ۲ ۱
باشه با ۲ حرکت منظم می شه
۱ ۴ ۳ ۲ ۵
۱ ۲ ۳ ۴ ۵
سوال جعبه هم من به همین نتیجه رسیدم

مطمئنی؟ یادمه امتحان کردم . آره منم اول برا مورد آخر به n/2 رسیدم اما در آخرین لحظات ۲ تا از تست هامو جوابش روپاک کردم وعوض کردم .

[lvlina_r]

(۲۰ بهمن ۱۳۹۱ ۰۴:۲۰ ب.ظ)mmoharrer نوشته شده توسط:  مطمئنی؟ یادمه امتحان کردم . آره منم اول برا مورد آخر به n/2 رسیدم اما در آخرین لحظات ۲ تا از تست هامو جوابش روپاک کردم وعوض کردم .

مثالش را نوشتم دیگه....
نوشته بود
swap (A[i],A[A[i]]
خودت یه بار امتحان کن..

[maryam.raz]

منم اون جعبه رو زدم ۳۱ حرکت که میشه حالتی که همه صعودی باشن
واسه آرایه هم منم چک کردم n-1
درخت هم من logn

[mehrdadsecret]

مگر نه اینکه راجع به نوع قرار گرفتن کلید ها بحث نشده بود؟ یعنی میتونه هرجایی باشه مثل هیپ من زدم nlogn

[somaye_tex]

(۲۰ بهمن ۱۳۹۱ ۰۳:۵۸ ب.ظ)lvlina_r نوشته شده توسط:  سوال اول، منم یک در آوردم، ولی ترسیدم بزنم...
سوال بعدی این نمیشه
مثلا اگه
۵ ۴ ۳ ۲ ۱
باشه با ۲ حرکت منظم می شه
۱ ۴ ۳ ۲ ۵
۱ ۲ ۳ ۴ ۵
سوال جعبه هم من به همین نتیجه رسیدم

سؤال مین و ماکس گراف هم سومی فقط غلط بود.

مسیر رو من در نیاوردم.

ایندکس سورت بدترین حالت میشه این: از چپ به راست :

۲۳۴۵۱

نیاز به ۴ جابه جایی داره

سؤال جعبه من ۱۱ درآوردم. تو تاپیک خسته نباشید راه حلمو نوشتم. خوشحال میشم دوستان بررسی کنند.


سؤال اول به نظر من ۳ تاش غلط بودم! شما کدومو گفتین درسته؟

[fsi2013]

میخواست طولانی ترین مسیر رو پیدا کنه اگه میگفت طولانی ترین از یه راس مشخص مثلا ریشه با O N میشد ولی من دیدم چیزی اشاره نکرده دیگ بیشتر از این واسش فسفر نسوزوندم ولی امسال کاش ۵ تا دیگ ریاضی میزدم

[fsi2013]

منم سوال اولو سه تارو غلط به دست اوردم
سوال MIN و MAX بود راجب یال ها هم یه دونه اش غلط بود
سوال درخت متوازن و نزدم به نظرم تا ON که جواب نمیشد حالا بالاتر و دیگ استددلال ندارم
سوال جعبه ۳۱
سوال ارایه ایندکسی مثال زدم N-1 حرکت

---

راه حل تونو بنویسید ما هم جایگشت بدیم مثال نقض پیش بیاد می دونین چون راه حل نداده بود هر راه حلی ادم واسش پیشنهاد میداد میشد یه جایگشت پیدا کنی که ۳۱ تارو کامل باید باز شه من اول با ۸ تا جعبه مثال هارو زدم هی میدیدم هر الگوریتمی پیشنهاد میدم خودم مثال نقضشو میاوردم دیگ خسته شدم راستشو بخوای شما راه حل تون بدین!
شاید با الگوریتم تصادفی که دو تارو باز کنه به طور رندوم بشه ولی الان دیگ ذهنم خسته است شما راه حلو بگین اینجا

[mehrdadsecret]

ارایه ایندکسی در همه ی حالات n-1 میشد دیگه؟ اخه do while استفاده شده بود و در همه ی حالات جابه جایی رو داشت

[somaye_tex]

(۲۰ بهمن ۱۳۹۱ ۰۴:۵۴ ب.ظ)fsi2013 نوشته شده توسط:  منم سوال اولو سه تارو غلط به دست اوردم
سوال MIN و MAX بود راجب یال ها هم یه دونه اش غلط بود
سوال درخت متوازن و نزدم به نظرم تا ON که جواب نمیشد حالا بالاتر و دیگ استددلال ندارم
سوال جعبه ۳۱
سوال ارایه ایندکسی مثال زدم N-1 حرکت

---

راه حل تونو بنویسید ما هم جایگشت بدیم مثال نقض پیش بیاد می دونین چون راه حل نداده بود هر راه حلی ادم واسش پیشنهاد میداد میشد یه جایگشت پیدا کنی که ۳۱ تارو کامل باید باز شه من اول با ۸ تا جعبه مثال هارو زدم هی میدیدم هر الگوریتمی پیشنهاد میدم خودم مثال نقضشو میاوردم دیگ خسته شدم راستشو بخوای شما راه حل تون بدین!
شاید با الگوریتم تصادفی که دو تارو باز کنه به طور رندوم بشه ولی الان دیگ ذهنم خسته است شما راه حلو بگین اینجا

شما هر جایگشتی دوست دارین بدین من با این روش براتون حل می کنم.



البته بین ۱۱ و ۱۲ شک دارم. کامل وقت نشد حلش کنم.

راه حل من:

۵ تا جعبه با شماره های زیر رو باز می کنیم:

۱ و ۸ و ۱۶ و ۲۴ و ۳۱

از بین اینها یکی از بقیه بزرگتره. اگه ۱ و ۳۱ باشه بدترین حالت نمیشه . پس به فرض میگیریم شماره ۲۳/ پس حتماً از ۱۶ تا ۳۱ جعبه ای وجود داره که حاوی عددیه که از ۲ جعبه کناریش نا کوچکتر باشه. (البته این وجود یه همچین جعبه ای رو در نیمه اول نقض نمیکنه! ولی در این نیمه هم حتماً خواهیم داشت.....)

لطفاً حالتهای مختلف رو خودتون بررسی کنید چون یه کم توضیحش اینجا سخته. ولی به راحتی قابل اثباته و مثال نقضی وجود نداره!

و سپس ۲۰ و ۲۷ رو باز می کنیم و دوباره از بین این ۵ عدد بزرگترین رو پیدا و دوباره طبق الگوریتم بالا نصف دیگر از جعبه ها رو حذف میکنیم و به همین ترتیب این الگوریتم رو به صورت تکراری انجام میدیم. که برای هر مرحله ۲ جعبه باز می کنیم. به جز اول کار که برای ۵ جعبه باز کردیم.

با یه حساب سرانگشتی جمع جعبه هایی که باز میشه در بدترین حالت اگه جعبه ها رو به صورت هوشمندانه انتخاب کنیم میشه ۱۱ تا!

البته الگوریتم رو از خودم درآوردم ولی فکر میکنم کار میکنه.....