۰
subtitle
ارسال: #۱
دو سوال از آزمون نهم مدرسان شریف
با عرض سلام
دوستان در مورد سوالات زیر راهنمایی می فرمایید لطفا؟
با تشکر
دوستان در مورد سوالات زیر راهنمایی می فرمایید لطفا؟
با تشکر
۰
ارسال: #۲
RE: دو سوال از آزمون نهم مدرسان شریف
هیپ یه درخت دودوییه کامله. درخت دودویی کامل ،از ۱ تا n/2 گره های داخلین و از کف n/2 به اضافه ۱، تا n برگ ها هستن. خب وقت میگه ۱۰ تا بزرگترین توی min heap ،یعنی میریم پایین این درخت، اونجاست که بزرگا نشستن.....پایین درخت برگاشه ،پس تو برگا دنبال اون ۱۰ تا میگردیم....که مرتبش تتای n میشه....
یه تابع درهم ساز در نظر بگیرید. یه عدد بهش میدیم یه جا به ما میده.هر عمل تتای یکه ، nتا عمل تتا n میشه. عملیاتی مثل این جستجو در حالت میانگین توی ارایه در هم ساز تتای n هست. اگه گفته بودبد ترین حالت،با درهم سازی میشد تتایn2 و درهم سازی اصلا خوب نبود. در این صورت به صورت سوال نگاه میکنیم اگه بازه عدد صحیح داده بود از روش دوستمون که گفتن میریم و و مرتب سازی شمارشی مرتب میکنیم و بقیه کارا که میشد تتای n . ولی اگه تو صورت سوال قید نکرده بود عدد صحیحه دراون صورت مرتب سازی معمولی میرفتیم که میشو تتای nlogn.
شما اگه میخواستید همینکارا رو توی ارایه معمولی.انجام بدید، تتایn2 میشد. چون ارایه مرتب نبود و یا ارایه درهم ساز هم نبود.
یه تابع درهم ساز در نظر بگیرید. یه عدد بهش میدیم یه جا به ما میده.هر عمل تتای یکه ، nتا عمل تتا n میشه. عملیاتی مثل این جستجو در حالت میانگین توی ارایه در هم ساز تتای n هست. اگه گفته بودبد ترین حالت،با درهم سازی میشد تتایn2 و درهم سازی اصلا خوب نبود. در این صورت به صورت سوال نگاه میکنیم اگه بازه عدد صحیح داده بود از روش دوستمون که گفتن میریم و و مرتب سازی شمارشی مرتب میکنیم و بقیه کارا که میشد تتای n . ولی اگه تو صورت سوال قید نکرده بود عدد صحیحه دراون صورت مرتب سازی معمولی میرفتیم که میشو تتای nlogn.
شما اگه میخواستید همینکارا رو توی ارایه معمولی.انجام بدید، تتایn2 میشد. چون ارایه مرتب نبود و یا ارایه درهم ساز هم نبود.
ارسال: #۳
RE: دو سوال از آزمون نهم مدرسان شریف
(۲۶ فروردین ۱۳۹۶ ۱۰:۲۷ ق.ظ)*tarannom* نوشته شده توسط: هیپ یه درخت دودوییه کامله. درخت دودویی کامل ،از ۱ تا n/2 گره های داخلین و از کف n/2 به اضافه ۱، تا n برگ ها هستن. خب وقت میگه ۱۰ تا بزرگترین توی min heap ،یعنی میریم پایین این درخت، اونجاست که بزرگا نشستن.....پایین درخت برگاشه ،پس تو برگا دنبال اون ۱۰ تا میگردیم....که مرتبش تتای n میشه....
یه تابع درهم ساز در نظر بگیرید. یه عدد بهش میدیم یه جا به ما میده.هر عمل تتای یکه ، nتا عمل تتا n میشه. عملیاتی مثل این جستجو در حالت میانگین توی ارایه در هم ساز تتای n هست. اگه گفته بودبد ترین حالت،با درهم سازی میشد تتایn2 و درهم سازی اصلا خوب نبود. در این صورت به صورت سوال نگاه میکنیم اگه بازه عدد صحیح داده بود از روش دوستمون که گفتن میریم و و مرتب سازی شمارشی مرتب میکنیم و بقیه کارا که میشد تتای n . ولی اگه تو صورت سوال قید نکرده بود عدد صحیحه دراون صورت مرتب سازی معمولی میرفتیم که میشو تتای nlogn.
شما اگه میخواستید همینکارا رو توی ارایه معمولی.انجام بدید، تتایn2 میشد. چون ارایه مرتب نبود و یا ارایه درهم ساز هم نبود.
خیلی خیلی خیلی لطف کردید
ان شاالله موفق و پیروز باشید دوست گرامی
ارسال: #۴
RE: دو سوال از آزمون نهم مدرسان شریف
(۲۶ فروردین ۱۳۹۶ ۱۰:۲۷ ق.ظ)*tarannom* نوشته شده توسط: هیپ یه درخت دودوییه کامله. درخت دودویی کامل ،از ۱ تا n/2 گره های داخلین و از کف n/2 به اضافه ۱، تا n برگ ها هستن. خب وقت میگه ۱۰ تا بزرگترین توی min heap ،یعنی میریم پایین این درخت، اونجاست که بزرگا نشستن.....پایین درخت برگاشه ،پس تو برگا دنبال اون ۱۰ تا میگردیم....که مرتبش تتای n میشه....سلام دوست گرامی
یه تابع درهم ساز در نظر بگیرید. یه عدد بهش میدیم یه جا به ما میده.هر عمل تتای یکه ، nتا عمل تتا n میشه. عملیاتی مثل این جستجو در حالت میانگین توی ارایه در هم ساز تتای n هست. اگه گفته بودبد ترین حالت،با درهم سازی میشد تتایn2 و درهم سازی اصلا خوب نبود. در این صورت به صورت سوال نگاه میکنیم اگه بازه عدد صحیح داده بود از روش دوستمون که گفتن میریم و و مرتب سازی شمارشی مرتب میکنیم و بقیه کارا که میشد تتای n . ولی اگه تو صورت سوال قید نکرده بود عدد صحیحه دراون صورت مرتب سازی معمولی میرفتیم که میشو تتای nlogn.
شما اگه میخواستید همینکارا رو توی ارایه معمولی.انجام بدید، تتایn2 میشد. چون ارایه مرتب نبود و یا ارایه درهم ساز هم نبود.
نظر شما راجع به مرتب سازی سطلی چیه؟ به این صورت که چون n تا عدد حقیقی در بازه -۲۰۰ تا ۲۰۰ داریم می وتوانیم تقریبا ۴۰۰ بازه به طول یک بگیریم یعنی اعداد موجود در بازه -۲۰۰ تا -۱۹۹ و -۱۹۹ تا -۱۹۸ و .... و ۱۹۹ تا ۲۰۰
هر کدام از بازه ها رو با مرتب سازی سطلی مرتب کنیم چون گفته در حالت میانگین پس مرتب کردن هر بازه زمان [tex]\theta(n)[/tex] که ۴۰۰ تا ازاین بازه ها داریم ولی چون ثابت است در کل می شود [tex]\theta(n)[/tex]
نگران مصرف حافظه هم زیاد نباید باشیم چون هر بازه که تمام شد از حافظه ان برای مرتب کردن بازه دیگر استفاده می شود.
ارسال: #۵
RE: دو سوال از آزمون نهم مدرسان شریف
(۲۶ فروردین ۱۳۹۶ ۱۲:۲۳ ب.ظ)msour44 نوشته شده توسط:سلام.بله اینم هست.... من یه نمونه مرتب سازی غیر مقایسه ای مثل شمارشی مثال زدم که البته با سطلیم میشه....(26 فروردین ۱۳۹۶ ۱۰:۲۷ ق.ظ)*tarannom* نوشته شده توسط: هیپ یه درخت دودوییه کامله. درخت دودویی کامل ،از ۱ تا n/2 گره های داخلین و از کف n/2 به اضافه ۱، تا n برگ ها هستن. خب وقت میگه ۱۰ تا بزرگترین توی min heap ،یعنی میریم پایین این درخت، اونجاست که بزرگا نشستن.....پایین درخت برگاشه ،پس تو برگا دنبال اون ۱۰ تا میگردیم....که مرتبش تتای n میشه....سلام دوست گرامی
یه تابع درهم ساز در نظر بگیرید. یه عدد بهش میدیم یه جا به ما میده.هر عمل تتای یکه ، nتا عمل تتا n میشه. عملیاتی مثل این جستجو در حالت میانگین توی ارایه در هم ساز تتای n هست. اگه گفته بودبد ترین حالت،با درهم سازی میشد تتایn2 و درهم سازی اصلا خوب نبود. در این صورت به صورت سوال نگاه میکنیم اگه بازه عدد صحیح داده بود از روش دوستمون که گفتن میریم و و مرتب سازی شمارشی مرتب میکنیم و بقیه کارا که میشد تتای n . ولی اگه تو صورت سوال قید نکرده بود عدد صحیحه دراون صورت مرتب سازی معمولی میرفتیم که میشو تتای nlogn.
شما اگه میخواستید همینکارا رو توی ارایه معمولی.انجام بدید، تتایn2 میشد. چون ارایه مرتب نبود و یا ارایه درهم ساز هم نبود.
نظر شما راجع به مرتب سازی سطلی چیه؟ به این صورت که چون n تا عدد حقیقی در بازه -۲۰۰ تا ۲۰۰ داریم می وتوانیم تقریبا ۴۰۰ بازه به طول یک بگیریم یعنی اعداد موجود در بازه -۲۰۰ تا -۱۹۹ و -۱۹۹ تا -۱۹۸ و .... و ۱۹۹ تا ۲۰۰
هر کدام از بازه ها رو با مرتب سازی سطلی مرتب کنیم چون گفته در حالت میانگین پس مرتب کردن هر بازه زمان [tex]\theta(n)[/tex] که ۴۰۰ تا ازاین بازه ها داریم ولی چون ثابت است در کل می شود [tex]\theta(n)[/tex]
نگران مصرف حافظه هم زیاد نباید باشیم چون هر بازه که تمام شد از حافظه ان برای مرتب کردن بازه دیگر استفاده می شود.
۰
ارسال: #۶
RE: دو سوال از آزمون نهم مدرسان شریف
(۲۵ فروردین ۱۳۹۶ ۰۷:۴۵ ب.ظ)alimamala نوشته شده توسط: با عرض سلام
دوستان در مورد سوالات زیر راهنمایی می فرمایید لطفا؟
با تشکر
اگه میشه بگید کدوم گزینه میشه جواباشون
تو سوال اولی به نظرم این راه خوبه: چون گفته مرتبه زمانی میانگین : عناصر ارایه رو با در هم سازی در ارایه در هم ساز ذخیره میکنیم. متوسط این عمل میشه .تتای n
بعد" ۵۰ منهای هر کدوم از عناصر ارایه " رو جستجو میکنیم که اینم میشه تتای n
سوال دومم چون هرم کمینست ۱۰ عنصر کوچک جاشون معلومه که میشه تتای ۱
۱۰عنصر بزرگتر جاشون معلوم نیست، تو برگان که n/2 هستن باید بگردیم میشه تتای n
ارسال: #۷
RE: دو سوال از آزمون نهم مدرسان شریف
(۲۵ فروردین ۱۳۹۶ ۰۸:۰۹ ب.ظ)*tarannom* نوشته شده توسط:(25 فروردین ۱۳۹۶ ۰۷:۴۵ ب.ظ)alimamala نوشته شده توسط: با عرض سلام
دوستان در مورد سوالات زیر راهنمایی می فرمایید لطفا؟
با تشکر
اگه میشه بگید کدوم گزینه میشه جواباشون
تو سوال اولی به نظرم این راه خوبه: چون گفته مرتبه زمانی میانگین : عناصر ارایه رو با در هم سازی در ارایه در هم ساز ذخیره میکنیم. متوسط این عمل میشه .تتای n
بعد" ۵۰ منهای هر کدوم از عناصر ارایه " رو جستجو میکنیم که اینم میشه تتای n
سوال دومم چون هرم کمینست ۱۰ عنصر کوچک جاشون معلومه که میشه تتای ۱
۱۰عنصر بزرگتر جاشون معلوم نیست، تو برگان که n/2 هستن باید بگردیم میشه تتای n
سلام دوست عزیز
خیلی محبت کردید
فقط بی زحمت می فرمایید چرا درهم سازی کنیم اول ؟ مگه با آرایه ی داده شده نمی شه همین عملی که می فرمایید عدد ۵۰ رو از هرکدوم کم کنیم رو در آرایه ی معمولی انجام داد ؟ درهم سازی چه خاصیتی داره ؟
با تشکر
سوال ۵۲ گزینه ی ۲
سوال ۵۳ گزینه ی ۱
(۲۵ فروردین ۱۳۹۶ ۰۸:۱۷ ب.ظ)arash691 نوشته شده توسط:(25 فروردین ۱۳۹۶ ۰۷:۴۵ ب.ظ)alimamala نوشته شده توسط: با عرض سلام
دوستان در مورد سوالات زیر راهنمایی می فرمایید لطفا؟
با تشکر
سوال اول فکر کنم ابتدا با مرتب سازی شماری بشه اعداد رو مرتب کرد و با یه حلقه و با دو اشاره گر زوج هایی که جمعشان ۵۰ میشود و پیدا کرد که از مرتبه O(n) میشه .
سوال دوم هرم کمینه هست پس با مرتبه O(1) به اعداد کمینه اول تا کمینه k ام بطوری که k عددی ثابت باشد دسترسی داریم ولی مجموع بزرگترین عدد ها در برگ ها هستش یعنی تو بازه کف (n/2)+1 تا ...کف n که میشه مرتبه O(n)
مرسی آقا آرش
خیلی لطف کردی، موفق باشی
با سپاس مجدد از دوستان عزیز
لطف می کنید بفرمایید چرا از (n/2)+1 تا کف n جست و جو می کنیم ؟ ببخشید، شرمنده این قسمت رو متوجه نشدم
با تشکر
۰
ارسال: #۸
RE: دو سوال از آزمون نهم مدرسان شریف
(۲۵ فروردین ۱۳۹۶ ۰۷:۴۵ ب.ظ)alimamala نوشته شده توسط: با عرض سلام
دوستان در مورد سوالات زیر راهنمایی می فرمایید لطفا؟
با تشکر
سوال اول فکر کنم ابتدا با مرتب سازی شماری بشه اعداد رو مرتب کرد و با یه حلقه و با دو اشاره گر زوج هایی که جمعشان ۵۰ میشود و پیدا کرد که از مرتبه O(n) میشه .
سوال دوم هرم کمینه هست پس با مرتبه O(1) به اعداد کمینه اول تا کمینه k ام بطوری که k عددی ثابت باشد دسترسی داریم ولی مجموع بزرگترین عدد ها در برگ ها هستش یعنی تو بازه کف (n/2)+1 تا ...کف n که میشه مرتبه O(n)
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close