17 اسفند 1392, 04:33 ب.ظ
17 اسفند 1392, 05:24 ب.ظ
(17 اسفند 1392 04:13 ب.ظ)fallah_o68 نوشته شده توسط: [ -> ]سلام
لطفا یکی از دوستان توضیح بده که چرا سوال ۵ جوابش گزینه ۲ یا گزینه ۴ میشه. به نظر من گزینه ۱ میشه. چون شما میتونید عنصر با اندیس ۱۰ را در زیر ریشه قرار بدید سپس آخرین برگ که گره ۱۰۰ باشد جایگزین آن میشود. حال مقایسه باید انجام شده تا عدد ۱۰۰ به آخرین سطح برود. این مقایسه ابتدا بین ۲ بچه انجام شده و سپس یک مقایسه با عدد ۱۰۰ انجام میشود. یعنی برای پایین آمدن هر سطح ۲ مقایسه لازم است. چون ۵ سطح داریم ۱۰ مقایسه میشود. البته شاید در آخرین سطح ۱ مقایسه نیز کافی باشد بنابراین به نظرم جواب ۹ میشود. البته تاکید میکنم چون در صورت سوال گفته شده بدترین حالت، سناریوی فوق بدترین حالت را میگوید.
در مورد سوال ۱۴ بین گزینه دوم و اول (طبق نظرات قبلی) شک وجود دارد که لطفا یک نفر دقیقا توضیح دهد.
در مورد سوال ۱۸ نیز بین گزینه اول و دوم شک وجود دارد. دوستانی که میگویند گزینه دوم میشود لطفا مثال نقضی بزنند و یکی از موارد را رد کنند یا دوستانی که میگویند گزینه ۱ میشود لطفا استدلالی بگویند.
در مورد سوال ۱۵ هم اکثرا گزینه ۴ را میگویند اما یکی از دوستان گزینه ۲ را بیان کرد. اگر کسی مثالی دارد که گزینه اول تا سوم را نقض میکند ارائه دهد.
با تشکر
به نام خدا
شما برای مقایسه بین دوتا بچه نیازی به مقایسه با هر دوتاشون ندارید.
زبان ریاضی: به بیان ساده تر برای heapify کردن درخت با N گره، به (Log(N مقایسه نیازه، حالا درختی که عنصر 10 توش root باشه (زیر درختی از درخت اصلی که 10 توش root هستش) شامل 15 گره (یک Heap کامل و پر با ریشه 10) و دارای 3 سطح هستش. پس با Log (15)] +1] مقایسه عمل Heapify انجام میشه.
موفق باشید
17 اسفند 1392, 06:07 ب.ظ
(17 اسفند 1392 05:24 ب.ظ)mrmasoud نوشته شده توسط: [ -> ]زبان ریاضی: به بیان ساده تر برای heapify کردن درخت با N گره، به (Log(N مقایسه نیازه، حالا درختی که عنصر ۱۰ توش root باشه (زیر درختی از درخت اصلی که ۱۰ توش root هستش) شامل ۱۵ گره (یک Heap کامل و پر با ریشه ۱۰) و دارای ۳ سطح هستش. پس با Log (15)] +1] مقایسه عمل Heapify انجام میشه.
ببینید دوست بزرگوار، من توصیه میکنم به کتاب clrs سری بزنید. شرایط کاملا مشابه حذف کمترین عنصر از ریشه درختی با عضو ۱۰ بوده که مثلا گره ۱۰۰ جایگزین آن میشود. خب در این شرایط مقایسه ها نباید به سمت ریشه انجام شود بلکه باید به سمت برگها برود. در بدترین حالت گره ۱۰ دقیقا سمت چپ گره ۱ است (یعنی سطح اول گراف) و تا آخرین سطح گراف ۵ سطح وجود دارد. درضمن مجبوریم که ابتدا دو بچه خود را با هم مقایسه کنیم تا کمترین بدست آید سپس کمترین بچه با گره ۱۰۰ مقایسه شده تا مطمین شویم که ۱۰۰ بزرگتر است (که قطعا اینطور است) این کار غیر ممکن است با ۱ مقایسه انجام شود یعنی حتما ۲ مقایسه میخاهیم. بنابراین در بدترین شرایط طبق سناریو فوق در کل ۹ یا شاید ۱۰ مقایسه لازم باشد.
در مورد سوالات ۱۴، ۱۵ و ۱۸ هم هرکسی توضیح دقیق یا مثال نقض دارد لطفا بگوید
با تشکر
17 اسفند 1392, 06:29 ب.ظ
(17 اسفند 1392 06:07 ب.ظ)fallah_o68 نوشته شده توسط: [ -> ]به نام خدا(17 اسفند 1392 05:24 ب.ظ)mrmasoud نوشته شده توسط: [ -> ]زبان ریاضی: به بیان ساده تر برای heapify کردن درخت با N گره، به (Log(N مقایسه نیازه، حالا درختی که عنصر ۱۰ توش root باشه (زیر درختی از درخت اصلی که ۱۰ توش root هستش) شامل ۱۵ گره (یک Heap کامل و پر با ریشه ۱۰) و دارای ۳ سطح هستش. پس با Log (15)] +1] مقایسه عمل Heapify انجام میشه.
ببینید دوست بزرگوار، من توصیه میکنم به کتاب clrs سری بزنید. شرایط کاملا مشابه حذف کمترین عنصر از ریشه درختی با عضو ۱۰ بوده که مثلا گره ۱۰۰ جایگزین آن میشود. خب در این شرایط مقایسه ها نباید به سمت ریشه انجام شود بلکه باید به سمت برگها برود. در بدترین حالت گره ۱۰ دقیقا سمت چپ گره ۱ است (یعنی سطح اول گراف) و تا آخرین سطح گراف ۵ سطح وجود دارد. درضمن مجبوریم که ابتدا دو بچه خود را با هم مقایسه کنیم تا کمترین بدست آید سپس کمترین بچه با گره ۱۰۰ مقایسه شده تا مطمین شویم که ۱۰۰ بزرگتر است (که قطعا اینطور است) این کار غیر ممکن است با ۱ مقایسه انجام شود یعنی حتما ۲ مقایسه میخاهیم. بنابراین در بدترین شرایط طبق سناریو فوق در کل ۹ یا شاید ۱۰ مقایسه لازم باشد.
در مورد سوالات ۱۴، ۱۵ و ۱۸ هم هرکسی توضیح دقیق یا مثال نقض دارد لطفا بگوید
با تشکر
دوست عزیز و گرامی ِ بنده.
شما با توجه به مطالعات خودتون در CLRS به بنده توضیح بدید: (توضیح راه حل در نکته 4 می باشد)
1) عمل Heapify چه کار میکه؟
(با توجه به جایگزینی عنصر با ایندکس 100 به جای ایندکس 10)
2) عمل Heapify در گراف MinHeap با 15 گره (گراف MinHeap که 15 گره دارد) چه تعداد مقایسه نیاز دارد؟
3) عناصر موجود در سطر آخر یک MinHeap چه ویژگی هایی دارند (راهنمایی: از نظر مقدار این عناصر بزرگترین عناصر در درخت می باشند، و در CLRS گفته شده برای یافتن عنصر ماکزیمم کافیه عناصر برگ را جستجو کنیم (n/2).)
4) درخت نیمه مرتب (Heap) یعنی چه؟ و چه تفاوتی با درخت مرتب BST دارد؟ (راهنمایی: در Heap ترتیب برگ ها اهمیتی ندارد! پس نیازی به اینکه در سمت چپ قرار بگیره یا راست مهم نیست)
نکته راه گشا: بنابراین با یک مقایسه بین عناصر 2i , 2i+1 عنصر کمینه به دست می آید و با عنصر i تعویض می گردد.
با توجه به این اطلاعات ناقص بنده، فکر میکنم گزینه مربوطه گزینه 4 و با 3 مقایسه بین عناصر می توان درخت را دوباره به Heap تبدیل نمود.
البته این حرفا با توجه به اطلاعات ناقص بنده هست، خوشحال می شم اگر راه حل بنده غلطه بفرمایید...
با سپاس
17 اسفند 1392, 06:33 ب.ظ
(17 اسفند 1392 06:07 ب.ظ)fallah_o68 نوشته شده توسط: [ -> ](17 اسفند 1392 05:24 ب.ظ)mrmasoud نوشته شده توسط: [ -> ]زبان ریاضی: به بیان ساده تر برای heapify کردن درخت با N گره، به (Log(N مقایسه نیازه، حالا درختی که عنصر ۱۰ توش root باشه (زیر درختی از درخت اصلی که ۱۰ توش root هستش) شامل ۱۵ گره (یک Heap کامل و پر با ریشه ۱۰) و دارای ۳ سطح هستش. پس با Log (15)] +1] مقایسه عمل Heapify انجام میشه.
ببینید دوست بزرگوار، من توصیه میکنم به کتاب clrs سری بزنید. شرایط کاملا مشابه حذف کمترین عنصر از ریشه درختی با عضو ۱۰ بوده که مثلا گره ۱۰۰ جایگزین آن میشود. خب در این شرایط مقایسه ها نباید به سمت ریشه انجام شود بلکه باید به سمت برگها برود. در بدترین حالت گره ۱۰ دقیقا سمت چپ گره ۱ است (یعنی سطح اول گراف) و تا آخرین سطح گراف ۵ سطح وجود دارد. درضمن مجبوریم که ابتدا دو بچه خود را با هم مقایسه کنیم تا کمترین بدست آید سپس کمترین بچه با گره ۱۰۰ مقایسه شده تا مطمین شویم که ۱۰۰ بزرگتر است (که قطعا اینطور است) این کار غیر ممکن است با ۱ مقایسه انجام شود یعنی حتما ۲ مقایسه میخاهیم. بنابراین در بدترین شرایط طبق سناریو فوق در کل ۹ یا شاید ۱۰ مقایسه لازم باشد.
در مورد سوالات ۱۴، ۱۵ و ۱۸ هم هرکسی توضیح دقیق یا مثال نقض دارد لطفا بگوید
با تشکر
لازم نیست عنصر 10 با ریشه جابه‌جا بشه و بعد حذف و هیپیفای کنیم
کافیه از سطح 10 پایین بیایم و بچه‌ها رو با هم مقایسه کنیم، هربار هر کدوم کوچکتر بود میره بالا و از اونجا به بعد بررسی انجام میشه
17 اسفند 1392, 07:43 ب.ظ
سلام
فکر کنم سوال 20 گزینه 2 بشه.
به عنوان نمونه:
A=| 5 |4 |3 |2 |1
----------------------
1-| 4 |5 |2 |3 |0 |1 |
2-| 4 |2 |5 |0 |3 |1 |
3-| 2 |4 |0 |5 |1 |3 |
4-| 2 |0 |4 |1 |5 |3 |
5-| 0 |2 |1 |4 |3 |5 |
6-| 0 |1 |2 |3 |4 |5 |
یعنی در بدترین حالت می شود n
ببخشید چرا ۲۰ رو زدید ۳؟
1=1
2=1+2
3=1+2+3
۴=1+2+3+4
و الی آخر...
فکر کنم سوال 20 گزینه 2 بشه.
به عنوان نمونه:
A=| 5 |4 |3 |2 |1
----------------------
1-| 4 |5 |2 |3 |0 |1 |
2-| 4 |2 |5 |0 |3 |1 |
3-| 2 |4 |0 |5 |1 |3 |
4-| 2 |0 |4 |1 |5 |3 |
5-| 0 |2 |1 |4 |3 |5 |
6-| 0 |1 |2 |3 |4 |5 |
یعنی در بدترین حالت می شود n
(16 اسفند 1392 08:23 ب.ظ)hamid_tehran نوشته شده توسط: [ -> ]به نظر من برخی از جواب ها اینا هست (طبق دفترچه F )
سوال : پاسخ
۱ - ۴
۲ - ۴
۳ - ۳
۴ - ۲
۵ - ۳
۸ - ۱
۹ - ۲
۱۰ - ۳
۱۱ - ۲
۱۲ - ۴
۱۵ - ۳
۱۶ - ۲
۲۰ - ۳
۲۲ - ۲
۲۵ - ۴
۳۵ - ۳
۳۷ - ۲
۴۳ - ۲
ببخشید چرا ۲۰ رو زدید ۳؟
(16 اسفند 1392 11:22 ب.ظ)ashkan_d13 نوشته شده توسط: [ -> ]منم طبق سوالاتی که حل کردم و جوابای شما که دیدم، گزینه‌های زیر فکر میکنم درسته (سبزا تقریباً قطعی!)
1- 4
2- 2
۳- ۳
۴- ۴
5- 4
۶- ؟
۷- ۲
8- 1
۹- ۲
10- 3
۱۱- ۴
12- 4
۱۳- ۳
۱۴- ۲
۱۵- ۴
۱۶- ۲
۱۷- ؟
۱۸- ۱
19- 1
۲۰- ۳
1=1
2=1+2
3=1+2+3
۴=1+2+3+4
و الی آخر...
(17 اسفند 1392 10:45 ق.ظ)sharareh_moradi نوشته شده توسط: [ -> ]خیلی از دوستان سوال ۱۰ رو میگن گزینه ۳ !!!!
میشه دلایلتون رو هم بگین؟؟؟
چرا من این سوال رو متوجه نمیشم!!
آخه وقتی اندازه معطلی i برابر i میشه
پس اندازه معطلی کل میشه مجموع i از ۱ تا ۱۰ دیگه
که میشه n*(n+1)/2
که برای n=10 میشه ۵۵
17 اسفند 1392, 08:51 ب.ظ
(17 اسفند 1392 06:33 ب.ظ)ashkan_d13 نوشته شده توسط: [ -> ]لازم نیست عنصر ۱۰ با ریشه جابه‌جا بشه و بعد حذف و هیپیفای کنیم
کافیه از سطح ۱۰ پایین بیایم و بچه‌ها رو با هم مقایسه کنیم، هربار هر کدوم کوچکتر بود میره بالا و از اونجا به بعد بررسی انجام میشه
من دقیقا منظورم این شکل ضمیمه هست که بدترین شرایط را برای درخت رقم میزند. با توجه به شکل، وقتی آخرین گره (گره ۱۰۰ یا هر عدد دیگر منتها عدد ۱۰۰ میتواند بدترین شرایط باشد) جایگزین ۱۰ شود طبق heapify عمل میکنیم. یعنی ابتدا ۱۱ و ۱۲ (طبق شکل بنده) با هم مقایسه میشوند که ۱۱ کوچکتر است سپس ۱۱ با ۱۰۰ مقایسه میشود که ۱۱ کوچکتر است و جایگزین میشود. سپس ۱۰۰ به همین روال تا پایین درخت و رسیدن به برگها به پیش میرود. چون ۵ سطح تا پایین درخت داریم بنابراین ۱۰ یا ۹ مقایسه لازم است. اگر هر کدام از دوستان با این استدلال مشکل دارند لطفا با توجه به شکل بنده یا شکلی از خودشان توضیح لازم را به سایرین بدهند
در مورد سوال ۱۴، ۱۵ و ۱۸ هیچکس نیست که مثال نقض یا دلیل محکمی ارائه بده و جواب قطعی را بگه.
17 اسفند 1392, 09:00 ب.ظ
[attachment=15592]دوستان
من هم گیچ شدم در مورد سوال ۵
یک چیز مطمئنم : که حداکثر مقایسه و تحت هر شرایطی تو یه هیپ واسه هیپیفای حداکثر با logn برابره پس در log 100 میشه ۷ پس گزینه ۱ عمراً نمیشه
حالا تو سوال گفته بدترین حالت ممکن
من یه درخت پیوست کردم و به نظرم بدترین حالته :
یه درخت که برگ سمت چپش برچسب ۱۰ و سمت راستش ۹۹ تا گره داره
حالا این چند مقایسه می خواد ؟
لطفاً به این لینک هم برین
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
در مورد سوالهای یادگیری امسال هستش
من هم گیچ شدم در مورد سوال ۵
یک چیز مطمئنم : که حداکثر مقایسه و تحت هر شرایطی تو یه هیپ واسه هیپیفای حداکثر با logn برابره پس در log 100 میشه ۷ پس گزینه ۱ عمراً نمیشه
حالا تو سوال گفته بدترین حالت ممکن
من یه درخت پیوست کردم و به نظرم بدترین حالته :
یه درخت که برگ سمت چپش برچسب ۱۰ و سمت راستش ۹۹ تا گره داره
حالا این چند مقایسه می خواد ؟
لطفاً به این لینک هم برین
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
در مورد سوالهای یادگیری امسال هستش
17 اسفند 1392, 11:47 ب.ظ
(17 اسفند 1392 10:45 ق.ظ)sharareh_moradi نوشته شده توسط: [ -> ]خیلی از دوستان سوال ۱۰ رو میگن گزینه ۳ !!!!
میشه دلایلتون رو هم بگین؟؟؟
چرا من این سوال رو متوجه نمیشم!!
آخه وقتی اندازه معطلی i برابر i میشه
پس اندازه معطلی کل میشه مجموع i از ۱ تا ۱۰ دیگه
که میشه n*(n+1)/2
که برای n=10 میشه ۵۵
به نام خدا
سلام.
برای راحتی این طوری بخونید سوال رو: ۱۰ پردازش داریم که در زمان صفر امدن، هر پردازش i به میزان i دقیقه طول میکشه.
زمان معطلی = زمان پاسخ (از اول تا انتهای پاسخ دهی بهش)
می خواهیم زمان معطلی کمینه بشه، چه کار میشه کرد؟
جواب: از الگوریتم SJF (کمترین زمان، اول) باید استفاده کنیم.
و ....
(17 اسفند 1392 09:00 ب.ظ)mhghna نوشته شده توسط: [ -> ]دوستان
من هم گیچ شدم در مورد سوال ۵
یک چیز مطمئنم : که حداکثر مقایسه و تحت هر شرایطی تو یه هیپ واسه هیپیفای حداکثر با logn برابره پس در log 100 میشه ۷ پس گزینه ۱ عمراً نمیشه
حالا تو سوال گفته بدترین حالت ممکن
من یه درخت پیوست کردم و به نظرم بدترین حالته :
یه درخت که برگ سمت چپش برچسب ۱۰ و سمت راستش ۹۹ تا گره داره
حالا این چند مقایسه می خواد ؟
لطفاً به این لینک هم برین
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
در مورد سوالهای یادگیری امسال هستش
به نام خدا
دوست عزیز
در صورت سوال گفته شده، MinHeap.
خاصیت MinHeap :
۱) درخت کامل است. (درخت کامل درختی هستش که همه برگهای اون بجز احتمالا سطر آخر، تکمیل شده است، درختی که شما کشیدید Heap نیست.)
۲) نیمه مرتب است
۳) عناصر ریشه، از برگ های خود کوچکتر هستند
(17 اسفند 1392 08:51 ب.ظ)fallah_o68 نوشته شده توسط: [ -> ]به نام خدا.(17 اسفند 1392 06:33 ب.ظ)ashkan_d13 نوشته شده توسط: [ -> ]لازم نیست عنصر ۱۰ با ریشه جابه‌جا بشه و بعد حذف و هیپیفای کنیم
کافیه از سطح ۱۰ پایین بیایم و بچه‌ها رو با هم مقایسه کنیم، هربار هر کدوم کوچکتر بود میره بالا و از اونجا به بعد بررسی انجام میشه
من دقیقا منظورم این شکل ضمیمه هست که بدترین شرایط را برای درخت رقم میزند. با توجه به شکل، وقتی آخرین گره (گره ۱۰۰ یا هر عدد دیگر منتها عدد ۱۰۰ میتواند بدترین شرایط باشد) جایگزین ۱۰ شود طبق heapify عمل میکنیم. یعنی ابتدا ۱۱ و ۱۲ (طبق شکل بنده) با هم مقایسه میشوند که ۱۱ کوچکتر است سپس ۱۱ با ۱۰۰ مقایسه میشود که ۱۱ کوچکتر است و جایگزین میشود. سپس ۱۰۰ به همین روال تا پایین درخت و رسیدن به برگها به پیش میرود. چون ۵ سطح تا پایین درخت داریم بنابراین ۱۰ یا ۹ مقایسه لازم است. اگر هر کدام از دوستان با این استدلال مشکل دارند لطفا با توجه به شکل بنده یا شکلی از خودشان توضیح لازم را به سایرین بدهند
در مورد سوال ۱۴، ۱۵ و ۱۸ هیچکس نیست که مثال نقض یا دلیل محکمی ارائه بده و جواب قطعی را بگه.
سلام.
دوست عزیز و بزرگوار، قصد اذیت کردن شما رو ندارم، فقط برای اینکه گیرتون پیدا بشه، مطلب زیر رو دارم میگم:
این مثال شما، عنصر با اندیس ۳ رو دارید حذف میکنید!
به صورت سوال دقت کنید:
عنصر با اندیس ۱۰، نه عدد ۱۰!
اگر Heap رو با ارایه پیاده سازی کنیم طبق صورت مساله، عنصر با index 10، لزوما عدد ۱۰ نیست! اصلا برامون هم مهم نیست چه عددی هست!
وظیفه ما اینه
عنصر با اندیس ۱۰۰ (که هر چی میخواد باشه! باشه!) رو میذاریم جای عنصر با اندیس ۱۰/ (از این به بعد بهش میگم X)
عنصر ۲۰ و ۲۱ (بچه هاش) رو با هم مقایسه می کنیم، یکی از این عناصر بزرگتر از دیگری هستش، حالا عنصر کوچکتر رو با X جابه جا میکنیم.---> تا اینجا یک مقایسه
حالا بسته به اینکه با اندیس ۲۰ یا ۲۱ جابه جا شده، یا عناصر (۴۰ و ۴۱) یا (۴۲ و ۴۳) رو با هم مقایسه میکنیم!
مثل روش بالا با یه مقایسه این عنصر میره سر جاش! --> تا اینجا دو مقایسه
و در مرحله سوم هم یکی از جفت های زیر رو باید مقایسه کنیم (۸۰ و ۸۱) یا (۸۲ و ۸۳) یا (۸۳ و ۸۴) یا (۸۴ و ۸۵).
---> سه مقایسه.
تمت.
(البته خدا رو چه دیدید، شاید سنجش گزینه 1! رو اعلام کنه)
18 اسفند 1392, 01:16 ق.ظ
(17 اسفند 1392 11:47 ب.ظ)mrmasoud نوشته شده توسط: [ -> ]به صورت سوال دقت کنید:
عنصر با اندیس ۱۰، نه عدد ۱۰!
اگر Heap رو با ارایه پیاده سازی کنیم طبق صورت مساله، عنصر با index 10، لزوما عدد ۱۰ نیست! اصلا برامون هم مهم نیست چه عددی هست!
وظیفه ما اینه
عنصر با اندیس ۱۰۰ (که هر چی میخواد باشه! باشه!) رو میذاریم جای عنصر با اندیس ۱۰/ (از این به بعد بهش میگم X)
عنصر ۲۰ و ۲۱ (بچه هاش) رو با هم مقایسه می کنیم، یکی از این عناصر بزرگتر از دیگری هستش، حالا عنصر کوچکتر رو با X جابه جا میکنیم.---> تا اینجا یک مقایسه
حالا بسته به اینکه با اندیس ۲۰ یا ۲۱ جابه جا شده، یا عناصر (۴۰ و ۴۱) یا (۴۲ و ۴۳) رو با هم مقایسه میکنیم!
مثل روش بالا با یه مقایسه این عنصر میره سر جاش! --> تا اینجا دو مقایسه
و در مرحله سوم هم یکی از جفت های زیر رو باید مقایسه کنیم (۸۰ و ۸۱) یا (۸۲ و ۸۳) یا (۸۳ و ۸۴) یا (۸۴ و ۸۵).
---> سه مقایسه.
تمت.
(البته خدا رو چه دیدید، شاید سنجش گزینه ۱! رو اعلام کنه)
سلام و تشکر بابت استدلال و توضیحتان
بله بنده قبول دارم که اشتباه کردم و عنصر با اندیس ۱۰ را باید در نظر گرفت. اما میخام بگم که من در روز کنکور میخاستم این سوال را پاسخ ندهم چون به نظرم تعداد مقایسه ها باید زوج باشد و هیچکدام از گزینه ها زوج نیست. مثلا در جمله زیر مربوط به استدلال جنابعالی:
عنصر ۲۰ و ۲۱ (بچه هاش) رو با هم مقایسه می کنیم، یکی از این عناصر بزرگتر از دیگری هستش، حالا عنصر کوچکتر رو با X جابه جا میکنیم.---> تا اینجا یک مقایسه
وقتی عنصر ۲۰ و ۲۱ باهم مقایسه میشوند، یکی از عناصر کوچکتر است. شما طبق روال min-heapify حق ندارید عنصر کوچکتر را با عنصر جایگزین شده در اندیس ۱۰ (X) بدون انجام مقایسه تعویض کنید. از کجا میدانید که این عنصر قطعا کوچکتر بوده است. بنابراین نیاز به مقایسه بین عنصر کوچکتر با عنصر جایگزین شده در اندیس ۱۰ (X) هم باید انجام شود ---> بنابراین تا اینجا ۲ مقایسه (مطابق متد max-heapify کتاب clrs هربار ۲ مقایسه بین عناصر انجام میشود لطفا به شبه کد آن رجوع کنید و اگر حرف مرا قبول ندارید توجیه کنید)
در کل ۳ بار عملیات انجام شده و هربار ۲ مقایسه لازم است یعنی در کل ۶ مقایسه لازم است که در هیچ گزینه ای وجود ندارد!!!
شما یا سایر دوستان جواب یا مثال نقض یا اثباتی برای سوالات ۱۴، ۱۵ و ۱۸ سراغ دارید چون هنوز جواب قطعی و محکمی برای این سوالات را کسی نگفته
18 اسفند 1392, 02:06 ق.ظ
سلام
دوستان چرا اکثرا سوال ۱۱ رو زدن گزینه ۴ ؟؟؟؟
میشه لطفا کسی مثال نقض برای گزینه ۲ بیاره؟؟
ضمنا چرا دوستان اصلا در مورد سوالات ماشین لرنینگ و پترن حرف نمی زنن؟خیلی راحت بود که همه مطمین هستند یا هیچکس نزده؟!!
برای زبان و هوش چی؟ خبری نیست؟کسی چیزی نمیگه؟ کلیدی چیزی؟!!
دوستان چرا اکثرا سوال ۱۱ رو زدن گزینه ۴ ؟؟؟؟
میشه لطفا کسی مثال نقض برای گزینه ۲ بیاره؟؟
ضمنا چرا دوستان اصلا در مورد سوالات ماشین لرنینگ و پترن حرف نمی زنن؟خیلی راحت بود که همه مطمین هستند یا هیچکس نزده؟!!
برای زبان و هوش چی؟ خبری نیست؟کسی چیزی نمیگه؟ کلیدی چیزی؟!!
18 اسفند 1392, 02:25 ق.ظ
(18 اسفند 1392 02:06 ق.ظ)hamid_tehran نوشته شده توسط: [ -> ]سلام
دوستان چرا اکثرا سوال ۱۱ رو زدن گزینه ۴ ؟؟؟؟
میشه لطفا کسی مثال نقض برای گزینه ۲ بیاره؟؟
ضمنا چرا دوستان اصلا در مورد سوالات ماشین لرنینگ و پترن حرف نمی زنن؟خیلی راحت بود که همه مطمین هستند یا هیچکس نزده؟!!
برای زبان و هوش چی؟ خبری نیست؟کسی چیزی نمیگه؟ کلیدی چیزی؟!!
برای این مساله، باید از راه حل برنامه نویسی پویا استفاده کرد. ابتدا و انتها و طول تعیین کننده نمی توانند باشند (جواب خوبی ممکنه بدهند اما بهترین جواب نیست
و همواره درست کار نمیکنه.مثلا طول بازه: فرض کنید
---- ************---------------------------------------------------------
----------------------------**--------------------------------------------------
(* به معنی بازه خالی هستش)
فرض کنید چهار تا بازه بالا داده شده اند
الگوریتم اگر براساس طول بازه انتخاب کنه چی رو میگیره؟
اولین انتخاب سمت چپ بالا هستش.
بعدش تنها انتخاب ممکنه سمت راست بالا هستش
.پر واضح هستش که دو انتخاب پایین پوشش بیشتری داشتن.
مثلا شروع بازه: فرض کنید.
---- ************---------------------------------------------------------
**----------------------------**--------------------------------------------------
بر اساس اولین شروع (حریصانه)
انتخاب سمت راست بالا به عنوان اولین.
بعد از اون تنها انتخاب ممکنه اول سمت چپ می تونه باشه!
برای خاتمه هم مثل همین مثال ها
موفق باشید
18 اسفند 1392, 09:33 ق.ظ
ضمنا چرا دوستان اصلا در مورد سوالات ماشین لرنینگ و پترن حرف نمی زنن؟خیلی راحت بود که همه مطمین هستند یا هیچکس نزده؟!!
سلام
واسه سوالهای یادگیری ماشین یه سری به این یه این موضوع بزن
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام
واسه سوالهای یادگیری ماشین یه سری به این یه این موضوع بزن
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
18 اسفند 1392, 10:45 ق.ظ
(18 اسفند 1392 02:06 ق.ظ)hamid_tehran نوشته شده توسط: [ -> ]سلام
دوستان چرا اکثرا سوال ۱۱ رو زدن گزینه ۴ ؟؟؟؟
میشه لطفا کسی مثال نقض برای گزینه ۲ بیاره؟؟
ضمنا چرا دوستان اصلا در مورد سوالات ماشین لرنینگ و پترن حرف نمی زنن؟خیلی راحت بود که همه مطمین هستند یا هیچکس نزده؟!!
برای زبان و هوش چی؟ خبری نیست؟کسی چیزی نمیگه؟ کلیدی چیزی؟!!
برای استعداد تحصیلی میتونید به لینک زیر مراجعه کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
18 اسفند 1392, 10:58 ق.ظ
(16 اسفند 1392 08:24 ب.ظ)it866 نوشته شده توسط: [ -> ]سوال ۴ میشه یک درخت مورب در صورتی که برچسب نداشته باشیم. ولی با n بر چسب متفاوت از اعداد ۱ تا n پس میشه n!
۵ رو زدم ۷
۶ نزدم
۹ هم میشه nlogn
دوست عزیز کافیه درختشو بکشید متوجه می شید که جواب سه تا جابجایی است