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

[ashena1]

این تاپیک برای بررسی سوالات آزمون های آزمایشی مدرسان شریف در نظر گرفته شده تا بعد از هر آزمون پرسش و پاسخ های مربوطه در این تاپیک صورت بگیرد با آرزوی موفقیت برای همه ی دوستان.

[ashena1]

میشه راه حل شمارو برای این بدونم ؟مرسی
۱۱۵- فرض کنید یک لیست n عنصری از اعداد متمایز به همراه دو عدد k , m داریم (m<=k<=n). می خواهیم m بزرگترین عضو از بین k کوچکترین عضو لیست را از بزرگ به کوچک به دست آوریم . مرتبه ی زمانی بهترین الگوریتم برای انجام این کار کدام است؟
۱/Θ(n + k log k)
۲/Θ(n log n + m)
۳/Θ(n + m log m)
۴/Θ(n + m log k)

[raeika]

سلام سوال ۶۳ مدار میخوام بدونم چطور باید کری و اور فلو رو تشخیص داد؟ مرسی

[Fot30]

(۰۷ آذر ۱۳۹۴ ۰۳:۳۶ ق.ظ)raeika نوشته شده توسط:  سلام سوال ۶۳ مدار میخوام بدونم چطور باید کری و اور فلو رو تشخیص داد؟ مرسی

حاصل که صفر نیست z=0
چون مقدار دو تا کری مرحله n-1 و n ام باهم برابره پس v=0
مقدار کری خروجی ۱ هستش که c=1
مقدار s م صفر میشه

---

(۰۶ آذر ۱۳۹۴ ۰۵:۵۴ ب.ظ)ashena1 نوشته شده توسط:  میشه راه حل شمارو برای این بدونم ؟مرسی
۱۱۵- فرض کنید یک لیست n عنصری از اعداد متمایز به همراه دو عدد k , m داریم (m<=k<=n). می خواهیم m بزرگترین عضو از بین k کوچکترین عضو لیست را از بزرگ به کوچک به دست آوریم . مرتبه ی زمانی بهترین الگوریتم برای انجام این کار کدام است؟
۱/Θ(n + k log k)
۲/Θ(n log n + m)
۳/Θ(n + m log m)
۴/Θ(n + m log k)

اگر با روال سلکشن انجام بدید در زمان n میشه(منظورم بدست آوردن k+1 امین min تو آرایه هستش n+klogN) و طبق اون بیایم عناصر کوچکتر و بزرکتر از min k+1 مثل روال مرتب سازی سریع در دو طرفش جابجا کنیم طوری که چپش k تا کوچیکترین عنصر هستن
با مرتب سازی این k تا عنصر در زمان klogk میشه m تا از بزرگترین ها را با دسترسی مستقیم بدست آورد
و بنظرم چون m<K هستش باید لیست k تایی مرتب بشه نه اینکه لیست m تایی
جواب این سوال رو من n+k log k زدم به دلایلی که بالا گفتم
و از جواب مدرسان اجازه دارم قانع نشم!

[ashena1]

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

[raeika]

(۰۷ آذر ۱۳۹۴ ۱۱:۰۵ ق.ظ)Fot30 نوشته شده توسط:  

(07 آذر ۱۳۹۴ ۰۳:۳۶ ق.ظ)raeika نوشته شده توسط:  سلام سوال ۶۳ مدار میخوام بدونم چطور باید کری و اور فلو رو تشخیص داد؟ مرسی

حاصل که صفر نیست z=0
چون مقدار دو تا کری مرحله n-1 و n ام باهم برابره پس v=0
مقدار کری خروجی ۱ هستش که c=1
مقدار s م صفر میشه

---

من مشکلم تو همون کری n و n-1 هستش با یه مثال میشه توضیحش بدید متوجه نمیشم کدوم کری ها رو میگه

(۰۶ آذر ۱۳۹۴ ۰۵:۵۴ ب.ظ)ashena1 نوشته شده توسط:  میشه راه حل شمارو برای این بدونم ؟مرسی
۱۱۵- فرض کنید یک لیست n عنصری از اعداد متمایز به همراه دو عدد k , m داریم (m<=k<=n). می خواهیم m بزرگترین عضو از بین k کوچکترین عضو لیست را از بزرگ به کوچک به دست آوریم . مرتبه ی زمانی بهترین الگوریتم برای انجام این کار کدام است؟
۱/Θ(n + k log k)
۲/Θ(n log n + m)
۳/Θ(n + m log m)
۴/Θ(n + m log k)

اگر با روال سلکشن انجام بدید در زمان n میشه(منظورم بدست آوردن k+1 امین min تو آرایه هستش n+klogN) و طبق اون بیایم عناصر کوچکتر و بزرکتر از min k+1 مثل روال مرتب سازی سریع در دو طرفش جابجا کنیم طوری که چپش k تا کوچیکترین عنصر هستن
با مرتب سازی این k تا عنصر در زمان klogk میشه m تا از بزرگترین ها را با دسترسی مستقیم بدست آورد
و بنظرم چون m<K هستش باید لیست k تایی مرتب بشه نه اینکه لیست m تایی
جواب این سوال رو من n+k log k زدم به دلایلی که بالا گفتم
و از جواب مدرسان اجازه دارم قانع نشم!