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

[rezareza2]

دوستان سوال ۹۷ رو چی زدید؟
من گزینه ۳ رو زدم یعنی ۲ جمله درست داره که درواقع گزینه ۲ و ۳ بود. گزینه ۱ هم دیگه نیاز به گفتن نداره و غلطه!!

[damavand_kellap]

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

[arta.66]

(۲۳ بهمن ۱۳۹۱ ۰۲:۳۱ ب.ظ)rezareza2 نوشته شده توسط:  دوستان سوال ۹۷ رو چی زدید؟
من گزینه ۳ رو زدم یعنی ۲ جمله درست داره که درواقع گزینه ۲ و ۳ بود. گزینه ۱ هم دیگه نیاز به گفتن نداره و غلطه!!


۰ [url=jvoid(0);][/url] [url=jvoid(0);][/url] ۰

سلام به نظر من چون بحث رو n عنصر هست O(1) نمیتونه درست باشه چون گفته یه اجرای تصادفیش n^2 شده پس یعنی ساختار هش هم نمیتونه باشه چون توو اونجام نهایتا n میشد!! به نظر من فقط یه جمله درست داره

[damavand_kellap]

دوستان وقتی تتای n^2 داده پس تو حالت میانگین مسئله رو تو زمان n^2 حل میکنه پس دیگه تتای n معنی نمیده ممکنه تو بهترین حالت تو زمان n حل کنه ولی دیگه تو زمان میانگین که n نمیشه از طرفی دیگه تو بهترین حالت هم نمیتونه تو زمان n^3n حلش کنه و البته تو بد ترین حالت در زمان O(1) به نظر من هر سه گزینه غلطه

[amink_aut]

(۲۰ بهمن ۱۳۹۱ ۰۴:۳۷ ب.ظ)fsi2013 نوشته شده توسط:  درخت که فک نکنم LOG N بشه من تا ON هم زفتم ولی بازم جواب نمیداد راه حلم بیخیال شدم )

با برنامه نویسی پویا میشه n log n

[sy_NBA]

سوال ۹۷
گزینه ۱ درسته یعنی همه موارد غلط هست.
دقت کنید که الگوریتم تصادفی هست. در الگوریتم تصادفی حالت خوب و بد باهم فرقی نداره. اگه مایل هستید میتونید کتاب CLRS رو بخونید، چون اونجا کامل در مورد الگوریتم های تصادفی و مرتبه زمانی اونها در شرایط مختلف بحث کرده

---

سوال ۱۰۰ که همون درخته باشه هم با یه الگوریتمی شبیه پیمایش پس ترتیب حل میشه و با مرتبه n.
اگه لازمه الگوریتمش رو توضیح بدم

[۱۲۳aaa]

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

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

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

درود
در مورد سوال ایندکس سورت من برای تمام گزینه ها به جز یکی (که گفته بود برای یک ورودی خاص n-1جابجایی داریم )مثال نقض اوردم
بنابر این همون گزینه رو زدم

---

(۲۱ بهمن ۱۳۹۱ ۰۲:۱۷ ب.ظ)ffss نوشته شده توسط:  چرا هیچ کس درباره سوال repeat-until صحبت نمیکنه،البته مربوط به طراحی پیاده سازی میشه،من گزینه ۱ زدم ؟

این شکلا عینا تو کتاب گسترش اومده در repeatابتدا دستور اجرا میشه سپس شرط چک میشه با دفترچه سی میشد گزینه یک

[rezareza2]

اره دقیقا سوال ۹۸ گزینه ۱ درسته یعنی ارایه ای وجود داره که با دقیقا n-1 جابجایی عمل کنه.
برای سایر گزینه ها براحتی میشه مثال نقض آورد.

[nelli]

دوستان اگه ممکنه جوابتون به سوال ۹۹ رو با دلیل توضیح بدین،اینجا جوابای متفاوت دارم می بینم

[۶۶الی]

منم زدم n-1 جابه جایی
ورودی معکوس n/2

[Computer92]

(۲۶ بهمن ۱۳۹۱ ۰۱:۴۶ ق.ظ)nelli نوشته شده توسط:  دوستان اگه ممکنه جوابتون به سوال ۹۹ رو با دلیل توضیح بدین،اینجا جوابای متفاوت دارم می بینم

سوال ۹۹ مورد ۳ رو با شکل پیوست نقض کردم. آیا روشم اشکال داره؟

دور BCD در گراف هست که فقط یال BC با وزن مینمم را دارد ولی یال BC لزوما انتخاب نمی شود یعنی حتما در هر MST وجود ندارد. طبق کروسکال AB و AC و BD می توانند انتخاب شوند.

مورد ۲ درسته که یال مینمم در MST هست. طبق کروسکال که یالها را سورت می کند همیشه اولین یال که یال مینمم است انتخاب می شود.

مورد ۱ هم مثال نقض دارد.

[abasalimaleki]

(۲۳ بهمن ۱۳۹۱ ۱۱:۱۰ ب.ظ)rezareza2 نوشته شده توسط:  اره دقیقا سوال ۹۸ گزینه ۱ درسته یعنی ارایه ای وجود داره که با دقیقا n-1 جابجایی عمل کنه.
برای سایر گزینه ها براحتی میشه مثال نقض آورد.

چرا ۳ نمیشه؟

[rezareza2]

(ترتیب اعداد رو از چپ به راست بخونید )
ترتیب ۱ ۲ ۳ ۴ که عکس ترتیب هست رو در نظر بگیرید. این ترتیب اعداد ۲ بار عمل جابجایی نیاز داره.
یکبار با تعویض ۴ و ۱ تبدیل به ۱۳۲۴ میشه.دوباره با تعویض ۲ و ۳ تبدیل به ۱۲۳۴ میشه
..................................
حالا ترتیب ۱۳۲۴ رو در نظر بگیرید.
این ترتیب فقط با تعویض ۳ و ۲ مرتب میشه یعنی ۱ تعویض.
................
۲۴۱۳ رو در نظر بگیرید.
یکبار با تعویض ۲ و ۴ تبدیل به ۴۲۱۳ میشه.دوباره با تعویض ۴ و ۳ تبدیل به ۳۲۱۴ میشه.یکبار دیگه با تعویض ۳ و ۱ تبدیل به ۱۲۳۴ میشه که مرتب هست یعنی ۳ تعویض یا همون n-1.

مثال دومی که زدم گزینه ۳ و ۲ رو رد میکنه. مثال اول هم گزینه ۴ رو د میکنه و مثال سوم هم گزینه ۱ رو اثبات.

[farhad6800]

درخت متواز o [n میشه.شک نکنید.

[nelli]

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

(26 بهمن ۱۳۹۱ ۰۱:۴۶ ق.ظ)nelli نوشته شده توسط:  دوستان اگه ممکنه جوابتون به سوال ۹۹ رو با دلیل توضیح بدین،اینجا جوابای متفاوت دارم می بینم

سوال ۹۹ مورد ۳ رو با شکل پیوست نقض کردم. آیا روشم اشکال داره؟

دور BCD در گراف هست که فقط یال BC با وزن مینمم را دارد ولی یال BC لزوما انتخاب نمی شود یعنی حتما در هر MST وجود ندارد. طبق کروسکال AB و AC و BD می توانند انتخاب شوند.

مورد ۲ درسته که یال مینمم در MST هست. طبق کروسکال که یالها را سورت می کند همیشه اولین یال که یال مینمم است انتخاب می شود.

مورد ۱ هم مثال نقض دارد.

دوست عزیز تو صورت سوال(مورد سوم) گفته گراف یک دور داره،ولی تو مثال شما بیشتر از یک دور وجود داره
این نظر من بوده..لطفا بقیه هم نظرشون رو بگن