چند min heapبا ۷عنصرکه حاوی کلید های متمایز۱تا۷ است میشه ساخت؟جوابش ۸۰ ولی چطور محاسبه میشه؟
سلام خسته نباشید.ببینید میخوایم مین هیپ درست کنیم درست؟؟؟مین هیپ قاعدش اینه که ریشه مقدارش از فرزنداش کمتره
حالا ما کلیدامون ایناس:۱،۲،۳،۴،۵،۶،۷
خب قبول داری توی مین هیپ ریشه کوچکترین مقدار از بین مقدارهای موجود رو داره؟؟؟
پس الان ریشه میشه ۱ مقدار دیگه ای برای ریشه قابل قبول نیست.پس ریشه فقط ۱ حالت داره.
خب الان ۶ تا کلید مونده.ببین مین هیپ یه خاصیت داره اونم این که درخت کامل هستش یعنی تا سطح یکی مونده به اخر پر و تو سطح اخر نودها از چپ به راست چیده میشن.حالا اگه شکل این مین هیپ رو رسم میکنی میبینی که ۳ تا نود سمت چپ ریشه و ۳ تا نود سمت راست ریشه هستش
نحوه کار به این شکله:
ریشه که یکی از نودها رو مصرف کرد و یه حالت هم داشت
حالا از بین ۶ تا نود ۳ تاشو برای زیر درخت سمت چپ انتخاب میکنیم یعنی [tex]\binom{6}{3}[/tex] و حالا قبول داری فرزندان ریشه سمت چپ چون دو تا هستن میتونن با هم جا به جا شن و مشکلی نیست پس اینم ۲ حالت.
حالا ۳ عنصر باقیمونده رو سمت راست میذاریم(دقت کن دیگه انتخاب نداریم.چ.ن ۳ تا نود لازم داریم و فقط ۳ تا نود هم باقیمونده پس به یه حالت میتونیم انتخاب کنیم) و فرزندهای ریشه سمت راست هم به ۲ حالت جابه جا میشن
پس کلا داریم:
[tex]\binom{6}{3}\ast2\ast2=20\ast2\ast2=80[/tex]
یه کوچولو درباره جا به جا شدن برات توضیح بدم:
نود با مقدار ۱ که ریشه بود.حالا فرض کن سمت چپ ریشش ۲ و فرزندهاش هم ۳ و ۴ هستن
حالا قبول داری یه حالت اینه که ریشه زیردرخت چپ ۲ باشه و فرزند چپش ۳ و فرزند راستش ۴ و یه حالتم اینه ریشه زیردرخت چپ ۲ باشه و فرزند چپش ۴ و فرزند راستش ۳ .پس دیدی ۲ حالت شد .برای همین ما اومدیم در ۲ ضرب کردیم و برای زیر درخت سمت راست هم این قضیه صادقه
ببخشید اگه بد توضیح دادم
(۰۱ دى ۱۳۹۳ ۰۹:۴۷ ب.ظ)miladcr7 نوشته شده توسط: سلام خسته نباشید.ببینید میخوایم مین هیپ درست کنیم درست؟؟؟مین هیپ قاعدش اینه که ریشه مقدارش از فرزنداش کمتره
حالا ما کلیدامون ایناس:۱،۲،۳،۴،۵،۶،۷
خب قبول داری توی مین هیپ ریشه کوچکترین مقدار از بین مقدارهای موجود رو داره؟؟؟
پس الان ریشه میشه ۱/ مقدار دیگه ای برای ریشه قابل قبول نیست.پس ریشه فقط ۱ حالت داره.
خب الان ۶ تا کلید مونده.ببین مین هیپ یه خاصیت داره اونم این که درخت کامل هستش یعنی تا سطح یکی مونده به اخر پر و تو سطح اخر نودها از چپ به راست چیده میشن.حالا اگه شکل این مین هیپ رو رسم میکنی میبینی که ۳ تا نود سمت چپ ریشه و ۳ تا نود سمت راست ریشه هستش
نحوه کار به این شکله:
ریشه که یکی از نودها رو مصرف کرد و یه حالت هم داشت
حالا از بین ۶ تا نود ۳ تاشو برای زیر درخت سمت چپ انتخاب میکنیم یعنی [tex]\binom{6}{3}[/tex] و حالا قبول داری فرزندان ریشه سمت چپ چون دو تا هستن میتونن با هم جا به جا شن و مشکلی نیست پس اینم ۲ حالت.
حالا ۳ عنصر باقیمونده رو سمت راست میذاریم(دقت کن دیگه انتخاب نداریم.چ.ن ۳ تا نود لازم داریم و فقط ۳ تا نود هم باقیمونده پس به یه حالت میتونیم انتخاب کنیم) و فرزندهای ریشه سمت راست هم به ۲ حالت جابه جا میشن
پس کلا داریم:
[tex]\binom{6}{3}\ast2\ast2=20\ast2\ast2=80[/tex]
یه کوچولو درباره جا به جا شدن برات توضیح بدم:
نود با مقدار ۱ که ریشه بود.حالا فرض کن سمت چپ ریشش ۲ و فرزندهاش هم ۳ و ۴ هستن
حالا قبول داری یه حالت اینه که ریشه زیردرخت چپ ۲ باشه و فرزند چپش ۳ و فرزند راستش ۴ و یه حالتم اینه ریشه زیردرخت چپ ۲ باشه و فرزند چپش ۴ و فرزند راستش ۳/پس دیدی ۲ حالت شد .برای همین ما اومدیم در ۲ ضرب کردیم و برای زیر درخت سمت راست هم این قضیه صادقه
ببخشید اگه بد توضیح دادم
خیلی خیلی ممنون.اتفاقا خیلی خوب توضیح دادید.تشکر
(۰۱ دى ۱۳۹۳ ۰۹:۴۷ ب.ظ)miladcr7 نوشته شده توسط: سلام خسته نباشید.ببینید میخوایم مین هیپ درست کنیم درست؟؟؟مین هیپ قاعدش اینه که ریشه مقدارش از فرزنداش کمتره
حالا ما کلیدامون ایناس:۱،۲،۳،۴،۵،۶،۷
خب قبول داری توی مین هیپ ریشه کوچکترین مقدار از بین مقدارهای موجود رو داره؟؟؟
پس الان ریشه میشه ۱/ مقدار دیگه ای برای ریشه قابل قبول نیست.پس ریشه فقط ۱ حالت داره.
خب الان ۶ تا کلید مونده.ببین مین هیپ یه خاصیت داره اونم این که درخت کامل هستش یعنی تا سطح یکی مونده به اخر پر و تو سطح اخر نودها از چپ به راست چیده میشن.حالا اگه شکل این مین هیپ رو رسم میکنی میبینی که ۳ تا نود سمت چپ ریشه و ۳ تا نود سمت راست ریشه هستش
نحوه کار به این شکله:
ریشه که یکی از نودها رو مصرف کرد و یه حالت هم داشت
حالا از بین ۶ تا نود ۳ تاشو برای زیر درخت سمت چپ انتخاب میکنیم یعنی [tex]\binom{6}{3}[/tex] و حالا قبول داری فرزندان ریشه سمت چپ چون دو تا هستن میتونن با هم جا به جا شن و مشکلی نیست پس اینم ۲ حالت.
حالا ۳ عنصر باقیمونده رو سمت راست میذاریم(دقت کن دیگه انتخاب نداریم.چ.ن ۳ تا نود لازم داریم و فقط ۳ تا نود هم باقیمونده پس به یه حالت میتونیم انتخاب کنیم) و فرزندهای ریشه سمت راست هم به ۲ حالت جابه جا میشن
پس کلا داریم:
[tex]\binom{6}{3}\ast2\ast2=20\ast2\ast2=80[/tex]
یه کوچولو درباره جا به جا شدن برات توضیح بدم:
نود با مقدار ۱ که ریشه بود.حالا فرض کن سمت چپ ریشش ۲ و فرزندهاش هم ۳ و ۴ هستن
حالا قبول داری یه حالت اینه که ریشه زیردرخت چپ ۲ باشه و فرزند چپش ۳ و فرزند راستش ۴ و یه حالتم اینه ریشه زیردرخت چپ ۲ باشه و فرزند چپش ۴ و فرزند راستش ۳/پس دیدی ۲ حالت شد .برای همین ما اومدیم در ۲ ضرب کردیم و برای زیر درخت سمت راست هم این قضیه صادقه
ببخشید اگه بد توضیح دادم
درمورد این سوالا میشه توضیح بدید ببخشیدا
چشم حتما.فقط لطف کنید یه تاپیک دیگه دست کنید و اینا رو اونجا بذارید.چون میگن چند سوالو یه جا حل نکنیم
مرسی
(۰۱ دى ۱۳۹۳ ۱۱:۲۲ ب.ظ)miladcr7 نوشته شده توسط: چشم حتما.فقط لطف کنید یه تاپیک دیگه دست کنید و اینا رو اونجا بذارید.چون میگن چند سوالو یه جا حل نکنیم
مرسی
تویه لینک دیگه که به اشتبا ۲بارم ارسال کردم منتظر جوابتونم.پیشاپیش ممنون