۰
subtitle
ارسال: #۱
اثبات نکته ای از درخت هیپ
دوستان من قبلا سوالی رو در یه تاپیک پرسیدم با این که جواب سوالم رو نگرفتم و اصلا متوجه توضیحات دوستان نشدم مجددا سوالم رو در این تاپیک ایجاد کردم:
سوالی از فصل درخت های ویژه ی کتاب پوران
ص۲۱۸ کتاب یوسفی
درخت های ویژه
==
توی کتاب پوران به آدرس صفحه ای که گفتم(کتاب چاپ ۸۹) اومده :
ثابت می شود که در ارتفاع h هیپ حداکثر به تعداد [tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil[/tex]گره وجود دارد.
====
اما من قبول ندارم پون میگم وقتی n رو تغییر بدم این فرمول ممکنه غلط باشه حتی اگه واژه حداکثر رو به کار ببریم.
برای اثبات لطفا درختی کامل با ۴ گره رسم کنید. اولا بگید شماره گذاری سطوح را باید از ۱ بگیریم یا ۰ ؟(من می گم ۱،شما اگه بگید صفر هم قبول می کنم با این قسمت مشکلی ندارم)
دوستان گفتن ارتفاع از پایین به بالا شروع میشه و از صفر گفتم چشم.
حالا شما بگید در ارتفاع ۱ از درخت کاملی که ۴ گره داره چطوری میشه حداکثر [tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil[/tex]گره وجود داشته باشه ؟ (در حالی که اینجا n برابر ۴ هست و اگه تقسیم کنیم به(۲ به توان (۱+۱)) ، جواب میشه:
۴/۴ =۱
==
اینم شکل:
![[تصویر: 148855_1_1379087161.gif]](https://img.manesht.ir/148855_1_1379087161.gif)
اگه شکلم درسته بگید اگه غلطه هم بگید.
من می گم شکلم درسته فرمول غلطه
اگه قبول دارید سپاس رو بزنید وگرنه اگه واقعا سوالمو متوجه شدید و مطمئنین می تونید با دلیل قانع کننده ثابت کنید هادی یوسفی راست می گه بیاید پاسخ بدید.
؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
اگه موافقید با من،سپاس رو بزنید
ضمنا من هم ارتفاع رو درک می کنم و هم سطح رو(به هر سوالی هم گیر ۳پیچ نمیدم مگه اینگه شبهه زیاد داشته باشه برام)
؟
از دوست گرامی اجازه گرفتم در مورد این سوال گفتگوهامونو اینجا میذارم. اگه شما هم حرفمو قبول دارید سپاس رو بزنید یا بحث کنید لطفا
====
من: ارتفاع از پایین به بالا شماره گذاری میشه
من: ولی سطح ار بالا به پایین
User2: alan in derkht kamel nist?
من: ببین
من: من اصلا به کامل بودنش کار ندارم
من: کامل بخون
من: به نظر شما من اشتباه می کنم یا جناب یوسفی؟
User2: vali in alan to ertefah 1 ke 4 ta gereh nadare
User2: clrs ham esbatesh hamino migeh
User2: dorosteh dg
من: ببین دوست من
من: n یعنی چی؟
من: مگه n تعداد کل گره های درخت نیست؟
User2: tedad gereh
من: خوب
من: مگه n=4 نیست توی این درخت ما
User2: man manzoreh soal ro fek kona gereh ta on ertefast
من: اصلا تا همون ارتفاع
من: تعداد گره تا ارتفاع ۱ شما میگید چن تاست ؟
User2: 3ta
من: خوب بازم پوران اشتباه کرده دیگه عزیز
User2: akhe clrs pas chi?
من: یه مثال قانع کننده بزنید نگید CLRS
من: من دارم جوابو رد می کنم و هیچ دلیل قانع کننده ای پیدا نشده تا نقض کنه حرفمو.
من: میخوام مطمئن شم اشتباه نمی کنم
User2: نه من میگم تو ارتفاع ۱ ما دو تا گره داریم
من: پس قبول کردید تو ارتفاع ۱ حداکثر ۲ گره داریم
User2: منم که همینو اول گفتم اره
من: خوب n یا تعداد کل گره های ما چنده ؟
User2: 3تا
من: h یا ارتفاع هم ۱ هست قبول ؟
User2: خوب
من: ۲ به توان ۱+۱
من: میشه ۴
من: قبول؟
User2: بله
من: پس چطوری ۳/۴ میشه ۲ ؟
من: هاااان؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
من: یوسفی اشتباه کرده ۱۰۰ درصد
User2: اخه نمیشه ردش کرد شاید ما یه جا اشتباه میکنیم
من: حاضرید چت من و شما رو بذارم توی تاپیک ؟ تا بقیه بخونن؟ دیگه اون همه حرف تکراری نزنن ؟
User2: اگه ارتفاع از ۱ شروع چه ؟
من: بشه. بد تر میشه. حتی اگه از ۱ شروع بشه بازم غلط میاد
User2: اره
من: h=2 میشه
من: پس ۲ به توان ۳ میشه ۸
من: چطوری ۳ یا ۴ تقسیم بر ۸ میشه ۲ ؟
من: هرگز درست نیست
من: هیچکس منو قانع نکرده
من: همه میخوان به زور جواب یوسفی رو قبول کنن
من: چون استاد بزرگی هست
من: من راضی نیستم تا ثابت نشه کی اشتب میزنه
من: اگه کسی واقعا منو قانع کنه و منطقی ثابت کنه حاظرم بگم اشتباه می کنم
سوالی از فصل درخت های ویژه ی کتاب پوران
ص۲۱۸ کتاب یوسفی
درخت های ویژه
==
توی کتاب پوران به آدرس صفحه ای که گفتم(کتاب چاپ ۸۹) اومده :
ثابت می شود که در ارتفاع h هیپ حداکثر به تعداد [tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil[/tex]گره وجود دارد.
====
اما من قبول ندارم پون میگم وقتی n رو تغییر بدم این فرمول ممکنه غلط باشه حتی اگه واژه حداکثر رو به کار ببریم.
برای اثبات لطفا درختی کامل با ۴ گره رسم کنید. اولا بگید شماره گذاری سطوح را باید از ۱ بگیریم یا ۰ ؟(من می گم ۱،شما اگه بگید صفر هم قبول می کنم با این قسمت مشکلی ندارم)
دوستان گفتن ارتفاع از پایین به بالا شروع میشه و از صفر گفتم چشم.
حالا شما بگید در ارتفاع ۱ از درخت کاملی که ۴ گره داره چطوری میشه حداکثر [tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil[/tex]گره وجود داشته باشه ؟ (در حالی که اینجا n برابر ۴ هست و اگه تقسیم کنیم به(۲ به توان (۱+۱)) ، جواب میشه:
۴/۴ =۱
==
اینم شکل:
اگه شکلم درسته بگید اگه غلطه هم بگید.
من می گم شکلم درسته فرمول غلطه
اگه قبول دارید سپاس رو بزنید وگرنه اگه واقعا سوالمو متوجه شدید و مطمئنین می تونید با دلیل قانع کننده ثابت کنید هادی یوسفی راست می گه بیاید پاسخ بدید.
؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
اگه موافقید با من،سپاس رو بزنید
ضمنا من هم ارتفاع رو درک می کنم و هم سطح رو(به هر سوالی هم گیر ۳پیچ نمیدم مگه اینگه شبهه زیاد داشته باشه برام)
؟
از دوست گرامی اجازه گرفتم در مورد این سوال گفتگوهامونو اینجا میذارم. اگه شما هم حرفمو قبول دارید سپاس رو بزنید یا بحث کنید لطفا
====
من: ارتفاع از پایین به بالا شماره گذاری میشه
من: ولی سطح ار بالا به پایین
User2: alan in derkht kamel nist?
من: ببین
من: من اصلا به کامل بودنش کار ندارم
من: کامل بخون
من: به نظر شما من اشتباه می کنم یا جناب یوسفی؟
User2: vali in alan to ertefah 1 ke 4 ta gereh nadare
User2: clrs ham esbatesh hamino migeh
User2: dorosteh dg
من: ببین دوست من
من: n یعنی چی؟
من: مگه n تعداد کل گره های درخت نیست؟
User2: tedad gereh
من: خوب
من: مگه n=4 نیست توی این درخت ما
User2: man manzoreh soal ro fek kona gereh ta on ertefast
من: اصلا تا همون ارتفاع
من: تعداد گره تا ارتفاع ۱ شما میگید چن تاست ؟
User2: 3ta
من: خوب بازم پوران اشتباه کرده دیگه عزیز
User2: akhe clrs pas chi?
من: یه مثال قانع کننده بزنید نگید CLRS
من: من دارم جوابو رد می کنم و هیچ دلیل قانع کننده ای پیدا نشده تا نقض کنه حرفمو.
من: میخوام مطمئن شم اشتباه نمی کنم
User2: نه من میگم تو ارتفاع ۱ ما دو تا گره داریم
من: پس قبول کردید تو ارتفاع ۱ حداکثر ۲ گره داریم
User2: منم که همینو اول گفتم اره
من: خوب n یا تعداد کل گره های ما چنده ؟
User2: 3تا
من: h یا ارتفاع هم ۱ هست قبول ؟
User2: خوب
من: ۲ به توان ۱+۱
من: میشه ۴
من: قبول؟
User2: بله
من: پس چطوری ۳/۴ میشه ۲ ؟
من: هاااان؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
من: یوسفی اشتباه کرده ۱۰۰ درصد
User2: اخه نمیشه ردش کرد شاید ما یه جا اشتباه میکنیم
من: حاضرید چت من و شما رو بذارم توی تاپیک ؟ تا بقیه بخونن؟ دیگه اون همه حرف تکراری نزنن ؟
User2: اگه ارتفاع از ۱ شروع چه ؟
من: بشه. بد تر میشه. حتی اگه از ۱ شروع بشه بازم غلط میاد
User2: اره
من: h=2 میشه
من: پس ۲ به توان ۳ میشه ۸
من: چطوری ۳ یا ۴ تقسیم بر ۸ میشه ۲ ؟
من: هرگز درست نیست
من: هیچکس منو قانع نکرده
من: همه میخوان به زور جواب یوسفی رو قبول کنن
من: چون استاد بزرگی هست
من: من راضی نیستم تا ثابت نشه کی اشتب میزنه
من: اگه کسی واقعا منو قانع کنه و منطقی ثابت کنه حاظرم بگم اشتباه می کنم
۲
ارسال: #۲
RE: اثبات نکته ای از درخت هیپ
سلام .
ببینید اولا که ارتفاع درخت رو به ازای فرزند سمت راست ریشه اشتباه نوشتید چون ارتفاع اونم [tex]0[/tex] هستش.
ارتفاع گره: طولانی ترین فاصله از آن گره تا یک گره برگ
حالا واسه ی تک تک گره ها اگه بخوایم حساب کنیم
تعداد گره های با ارتفاع ۲ :
[tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil \Rightarrow \left \lceil \frac{4}{2^{2 1}} \right \rceil = 1[/tex] ، با توجه به درخت فقط گره ی ریشه ارتفاع ۲ دارد (a)
تعداد گره های با ارتفاع ۱ :
[tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil \Rightarrow \left \lceil \frac{4}{2^{1 1}} \right \rceil = 1[/tex] ، با توجه به درخت فقط فرزند چپ ریشه ارتفاع ۱ دارد (b)
تعداد گره های با ارتفاع ۰ :
[tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil \Rightarrow \left \lceil \frac{4}{2^{0 1}} \right \rceil = 2[/tex] ، با توجه به درخت فقط فرزند راست ریشه © و گره ی برگ زیر درخت چپ ریشه (d) ارتفاع ۰ دارد
*** آزمون ۲۵ درصد دوم پارسه همچین سوالی اومده بود من صورت سوال رو با جواب که از طریق این فرمول حل میشه مینویسم خودتون هم میتونید به راحتی با کشیدن درخت به جواب برسید .
سوال : تعداد گره های با ارتفاع [tex]1[/tex] در یک درخت دودویی کامل با [tex]1000[/tex] نود چند تا است ؟
[tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil \Rightarrow \left \lceil \frac{1000}{2^{1 1}} \right \rceil = 250[/tex]
اثبات این فرمول دیگه واسه ی خودتون، توی حل تمرین لاتین CLRS هستش میتونید اونجا ببینید فقط این فرمول حواستون باشه که قید حداکثر رو هم داره .
ببینید اولا که ارتفاع درخت رو به ازای فرزند سمت راست ریشه اشتباه نوشتید چون ارتفاع اونم [tex]0[/tex] هستش.
ارتفاع گره: طولانی ترین فاصله از آن گره تا یک گره برگ
حالا واسه ی تک تک گره ها اگه بخوایم حساب کنیم
تعداد گره های با ارتفاع ۲ :
[tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil \Rightarrow \left \lceil \frac{4}{2^{2 1}} \right \rceil = 1[/tex] ، با توجه به درخت فقط گره ی ریشه ارتفاع ۲ دارد (a)
تعداد گره های با ارتفاع ۱ :
[tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil \Rightarrow \left \lceil \frac{4}{2^{1 1}} \right \rceil = 1[/tex] ، با توجه به درخت فقط فرزند چپ ریشه ارتفاع ۱ دارد (b)
تعداد گره های با ارتفاع ۰ :
[tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil \Rightarrow \left \lceil \frac{4}{2^{0 1}} \right \rceil = 2[/tex] ، با توجه به درخت فقط فرزند راست ریشه © و گره ی برگ زیر درخت چپ ریشه (d) ارتفاع ۰ دارد
*** آزمون ۲۵ درصد دوم پارسه همچین سوالی اومده بود من صورت سوال رو با جواب که از طریق این فرمول حل میشه مینویسم خودتون هم میتونید به راحتی با کشیدن درخت به جواب برسید .
سوال : تعداد گره های با ارتفاع [tex]1[/tex] در یک درخت دودویی کامل با [tex]1000[/tex] نود چند تا است ؟
[tex]\left \lceil \frac{n}{2^{h 1}} \right \rceil \Rightarrow \left \lceil \frac{1000}{2^{1 1}} \right \rceil = 250[/tex]
اثبات این فرمول دیگه واسه ی خودتون، توی حل تمرین لاتین CLRS هستش میتونید اونجا ببینید فقط این فرمول حواستون باشه که قید حداکثر رو هم داره .
۰
ارسال: #۳
اثبات نکته ای از درخت هیپ
متاسفانه آقای csharpisatechnology به جوابهایی که در همون پست داده شد دقت کافی نداشتن. ولی به هر حال با جوابی که در پست شماره ۲ همین تاپیک داده شده فکر می‌کنم دیگه قانع شده باشید. دیگه از این روشنتر نمیشه توضیح داد.
۰
ارسال: #۴
اثبات نکته ای از درخت هیپ
دوست گرامی شاید از نگاه شما اشتباه کردن تاسف باشه
اما به نظرم کامل نکردن توضیح یک مطلب ممکنه بعضی اوقات فاجعه بار باشه اونم تو این زمان اندکی که واسه کنکور داریم.
به هر حال امیدوارم هر استادی هرچیزی که تو کتاب خونده رو نیاره و مثلا ۱۰ تا کتاب رو بخونه و نتیجه گیری خلاصه و کامل و مفیدشو بیاره طوری که همه درک کنن و شبهه ای در کار نباشه.
==
حلال کنید و به بزرگواری خودتون عفو بفرمایید.
=
اینم نتیجه گیری کلی خودم که میذارم شاید بدرد دیگران بخوره و یه عکس خلاصه و کامل باشه که بیشتر شبهه ها رو رفع می کنه:
![[تصویر: 148960_1_1379087161.gif]](https://img.manesht.ir/148960_1_1379087161.gif)
آقا مدیر ببند این پستو جوابو یافتیم بالاخره
مرسی از همه خصوصا mp1368،
==
اگر در پشت کنکوریم غم نیست/وگر از قله ها دوریم غم نیست/مهم اینه که با هم ما رفیقیم/چو عاشق بهر دستوریم غم نیست
اما به نظرم کامل نکردن توضیح یک مطلب ممکنه بعضی اوقات فاجعه بار باشه اونم تو این زمان اندکی که واسه کنکور داریم.
به هر حال امیدوارم هر استادی هرچیزی که تو کتاب خونده رو نیاره و مثلا ۱۰ تا کتاب رو بخونه و نتیجه گیری خلاصه و کامل و مفیدشو بیاره طوری که همه درک کنن و شبهه ای در کار نباشه.
==
حلال کنید و به بزرگواری خودتون عفو بفرمایید.
=
اینم نتیجه گیری کلی خودم که میذارم شاید بدرد دیگران بخوره و یه عکس خلاصه و کامل باشه که بیشتر شبهه ها رو رفع می کنه:
آقا مدیر ببند این پستو جوابو یافتیم بالاخره
مرسی از همه خصوصا mp1368،
==
اگر در پشت کنکوریم غم نیست/وگر از قله ها دوریم غم نیست/مهم اینه که با هم ما رفیقیم/چو عاشق بهر دستوریم غم نیست
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close