واسه ۵۱ کافیه تو اینترنت سرچ کنید.
گزینه ۳ درسته.
در مورد سوال ۵۳ من فکر کنم چون یکی مربوط به شاخه راست درخته و یکی چپ ماکزیممشون میشه.
psps1368 چرا دارید دو شاخه چپ و راست را به صورت مجزا در نظر میگیرید ؟ مگه این دو شاخه با هم به پایین نمی‌آیند ؟
(۳۰ بهمن ۱۳۸۹ ۰۸:۵۰ ب.ظ)hatami84 نوشته شده توسط: در مورد سوال ۵۳ به نظر من گزینه ۴ درسته بستگی داره که k , n چند در نظر گرفته بشه ماکزیمم اینها فکر کنم جواب درست تری بدهد.
دقیقا" درست میگین، حداکثر ارتفاع درخ را در سوال داده که چون k,n را نمی دونیم باید max بگیریم
(۳۰ بهمن ۱۳۸۹ ۰۹:۰۱ ب.ظ)Masoud05 نوشته شده توسط:(30 بهمن ۱۳۸۹ ۰۸:۴۷ ب.ظ)afagh1389 نوشته شده توسط: 52 منم ۴ زدم.
در مورد سوال ۵۵ هم که یکی از دوستان گفتند که counting الگوریتمه نه ساختار داده بگم که منم نگفتم ساختار داده است ساختار داده ما آرایه است که با counting مرتب میکنیم اعداد رو و در O(1 هم جستجو،درج و حذف میکنیم.
مرتب سازی شمارشی فقط برا حالاتی هست که بازه مشخص باشه و نه یه مقدار مثل n که به بینهایت میل میکنه. پس این تحلیل غلطه.
کاملا" موافقم، فقط یک آرایه میخواهیم به اندازه رادیکال n که مقدار هر درایه، تعداد عناصر تکرار شده آن اندیس(که همان مقدار آن درایه است-counting sort) در آن ذخیره می شود
پس همه عملیت در O(1)
(۰۱ اسفند ۱۳۸۹ ۱۲:۳۹ ق.ظ)۸۷۸۵۵۶۱۱ نوشته شده توسط:فرض کنید یه عنصر رو میخواید حذف کنید، اگه لطف کنید به من بگید چطوری توی زمان خطی اینکار رو میکنید ممنون میشم؟!!! حتی آرایه مرتب هم به زمان لگاریتمی نیاز داره، اگه الگوریتم جدیدی ابداء کردید بگید(30 بهمن ۱۳۸۹ ۰۸:۵۰ ب.ظ)hatami84 نوشته شده توسط: در مورد سوال ۵۳ به نظر من گزینه ۴ درسته بستگی داره که k , n چند در نظر گرفته بشه ماکزیمم اینها فکر کنم جواب درست تری بدهد.
دقیقا" درست میگین، حداکثر ارتفاع درخ را در سوال داده که چون k,n را نمی دونیم باید max بگیریم
(۳۰ بهمن ۱۳۸۹ ۰۹:۰۱ ب.ظ)Masoud05 نوشته شده توسط:(30 بهمن ۱۳۸۹ ۰۸:۴۷ ب.ظ)afagh1389 نوشته شده توسط: 52 منم ۴ زدم.
در مورد سوال ۵۵ هم که یکی از دوستان گفتند که counting الگوریتمه نه ساختار داده بگم که منم نگفتم ساختار داده است ساختار داده ما آرایه است که با counting مرتب میکنیم اعداد رو و در O(1 هم جستجو،درج و حذف میکنیم.
مرتب سازی شمارشی فقط برا حالاتی هست که بازه مشخص باشه و نه یه مقدار مثل n که به بینهایت میل میکنه. پس این تحلیل غلطه.
کاملا" موافقم، فقط یک آرایه میخواهیم به اندازه رادیکال n که مقدار هر درایه، تعداد عناصر تکرار شده آن اندیس(که همان مقدار آن درایه است-counting sort) در آن ذخیره می شود
پس همه عملیت در O(1)
آفاق خانم اگه میتونید دلیل بیارید من اشتباه میکنم( اگه اینطور باشه یه چیز خوب به من یاد دادین)
یه مدل الگوریتم شمارشی بر مبنای فراوانی نسبی است یعنی مثلا اگه شما ۵ تا یک دارید خونه با اندیس یک آرایه ۵ است پس وقتی میخواهید یک رو حذف کنید فقط کافیه محتوای آرایه رو یک واحد کاهش بدین برای جستجو هم کافیه چک کنید محتوا صفر نباشه.
الگوریتم counting به این خاطر کاربرد نداره که فضای حافظه زیادی اشغال میکنه ولی بقیه گزینه‌ها فضای حافظه n است پس اینجا counting که رادیکال n است خیلی بهتره مخصوصا که بازه اعداد مشخصه!
(۰۱ اسفند ۱۳۸۹ ۱۲:۵۸ ق.ظ)afagh1389 نوشته شده توسط: یه مدل الگوریتم شمارشی بر مبنای فراوانی نسبی است یعنی مثلا اگه شما ۵ تا یک دارید خونه با اندیس یک آرایه ۵ است پس وقتی میخواهید یک رو حذف کنید فقط کافیه محتوای آرایه رو یک واحد کاهش بدین برای جستجو هم کافیه چک کنید محتوا صفر نباشه.اینایی که میگید درست، اما من قصد دارم عدد تغریباً وسط آرایه رو حذف کنم، خوب چطوری بفهمم که کجا هست که در زمان خطی پیداش کنم و بعدش هم حذفش کنم .
الگوریتم counting به این خاطر کاربرد نداره که فضای حافظه زیادی اشغال میکنه ولی بقیه گزینه‌ها فضای حافظه n است پس اینجا counting که رادیکال n است خیلی بهتره مخصوصا که بازه اعداد مشخصه!
در ضمن شما برای مرتب سازی شمارشی نیاز به n حافظه دارید چراکه باید خانه های خالی رو هم داشته باشید پس این روش از نظر حافظه بهینه نیست هر چند که جستجو در آن لگاریتمی هست و طبق راهکار شما باید هر جا داده داریم توی آرایه دیگه که تعداد هست ۱ واحد اضافه کنیم که اینم وابسته به جستجو هست و میشه لگاریتمی.
(۳۰ بهمن ۱۳۸۹ ۱۰:۴۴ ب.ظ)psps1368 نوشته شده توسط: سوال ۵۳: گزینه ۳، اگر منظور سوال از ارتفاع، طولانی ترین مسیر از ریشه تا برگ باشه، این جوری میشه: توی از ریشه به سمت پایین سعی کنید فقط n رو به دو تقسیم کنید. وقتی که به k و ۱ رسیدیم تا این جا log2 n رو داریم. حالا از این جا به پایین k رو تقسیم کنید تا به ۱ و ۱ برسید. تا این جا هم log4 k اومدیم پایین و در مجموع log2 n + log4 k
سلام
مگه اینکه نوشته [tex]T(1,*)=T(*,1)=a[/tex]
منظورش این نیست که هرکدوم ۱ شد جواب بر میگرده؟ حتما باید به ۱و۱ برسیم؟
(۰۱ اسفند ۱۳۸۹ ۰۱:۰۷ ق.ظ)Masoud05 نوشته شده توسط: اینایی که میگید درست، اما من قصد دارم عدد تغریباً وسط آرایه رو حذف کنم، خوب چطوری بفهمم که کجا هست که در زمان خطی پیداش کنم و بعدش هم حذفش کنم .تو سوال نوشته فرقی بین آنها نیست. پس وسط و اول و آخر نداریم
در ضمن شما برای مرتب سازی شمارشی نیاز به n حافظه دارید چراکه باید خانه های خالی رو هم داشته باشید پس این روش از نظر حافظه بهینه نیست هر چند که جستجو در آن لگاریتمی هست و طبق راهکار شما باید هر جا داده داریم توی آرایه دیگه که تعداد هست ۱ واحد اضافه کنیم که اینم وابسته به جستجو هست و میشه لگاریتمی.
همون آرایه که داره تعداد رو نشون میده شامل خود داده بطور ضمنی هستش
نباید که حتما خود عدد ذخیره بشه
برای درج a
[tex]array[a] ;[/tex]
و برای حذف a
[tex]array[a]--;[/tex]
خوب حالا اگه برمبنای فراوانی مطلق هم باشه فرقی نداره بازم درج و حذف با یه تفریق حل میشه عدد وسط آرایه هم مشخصه.
امکان نداره سوال ۵۵ ۱ بشه چون اگه خودتون میگید لیستتون آرایه ای هست پس چجوری جستجوش توی o(1) میشه من هنوزم با ۳ موافقم با هیپ به ۳ میرسیم از bst هم نمیتونیم استفاده کنیم چون لیست عنصر تکراری داره ...
من که توضیح دادم چرا نمیخونید!!!
من گفتم تو شمارشی اگه بخواهیم ببینیم ۱ توی آرایه هست یا نه کافیه ببینیم خونه ۱ آرایه صفر نباشه.
اگر بر مبنای فراوانی مطلق هم باشه کافیه مثلا اگه میخواهیم ببینیم ۳۰ توی آرایه هست یا نه [A[31 -A[30 میکنیم اگر ۰ شد یعنی ۳۰ نداریم یعنی تعداد ۳۰ها رو به ما میده حتی جای ۳۰ هم مشخصه از روی A[30
قرار دادن این شروط در صورتی که با هیپ به گزینه ۳ میرسم به نظرتون عادلانه است بگذریم آفاق جون درمورد سوال ۵۱ نظری ندارید به نظرتون این سوالات برای سخت افزار چه طور بود منصفانه بود ؟ ساختمان رو عرض میکنم ///
اینها شرط نیست الگوریتمه به هر حال این سوال کاملا به نظر طراح بستگی داره.
۵۱ رو من ۴ زدم اما میگن ۳ میشه یعنی اشتباه زدم
چرا بر چه اساسی اشتراک ۲ تا لیست n نمشه در حالت میانگین من ۲ زدم ؟
(۰۱ اسفند ۱۳۸۹ ۱۰:۳۴ ق.ظ)afagh1389 نوشته شده توسط: خوب حالا اگه برمبنای فراوانی مطلق هم باشه فرقی نداره بازم درج و حذف با یه تفریق حل میشه عدد وسط آرایه هم مشخصه.من گفتم تغریباً وسط آرایه، علتش هم اینه که میخواستم ذهنتون روی جستجوی دودویی نره که با ۱ عمل جستجو وسط رو پیدا میکنه .