06 بهمن 1393, 10:19 ب.ظ
06 بهمن 1393, 10:47 ب.ظ
سلام
فک کنم گزینه ۴ بشه!
برای اینکه یک نویسه طولش ۱ بشه! باید همه نویسه قبلی ها با هم دیگه خورد خورد زیر درخت ها رو بسازن و آخر از همه در درخت نهایی زیر درخت سمت چپ نویسه مورد نظر باشه و زیر درخت سمت راست بقیه نویسه ها! ( یا برعکس, نویسه سمت راست بقیه سمت چپ!)
حالا برای الف:
فرض کنید ۳ تا نویسه داریم با قراوانی های :
x1 = 0.4 , x2 = 0.5 , x3=0.3
خب حالا برای درخت هافمن اول x1 و x3 با هم ترکیب می شن و بعدش x2 باهاشون ترکیب میشه برای درخت نهایی پس x1 که فراوانیش ۲/۵ بود طول کدش ۱ نیست! پس الف غلطه!
برای ب:
فرض کنید نویسه ای که می خواد طول کدش ۱ بشه فراوانیش [tex]\frac{(1-\epsilon)}{3}[/tex] باشه و بقیه هم مثلا همه ۱/۳۰ باشه فراوانیشون! وقتی داریم درختو می سازیم اول اون ۱/۳۰ ها , دو تا دو تا به هم جمع میشن! و می شن ۱/۱۵ و یه دونه ۱/۳۰ هم میمونه! بعد ۱/۳۰ آخر و بقیه ۲/۱۵ ها با هم جمع میشن تا جایی که حاصل جمع ها از ۱/۳ بیشتر شه! ای حاصل جمع حتما کوچکتر از ۲/۳ هست ( چرا؟ چون اگه بخاد بشه ۲/۳ و از اون نویسه خاص ما که فراوانیش [tex]\frac{(1-\epsilon)}{3}[/tex] استفاده نشه شدنی نیس! )
پس الان ۳ تا زیر درخت میمونه ! اولی بین ۱/۳ و ۲/۳ اسمشو می زاریم x1
دومی کمتر از ۱/۳ x2
و سومی نویسه مد نظرمون! x3
حالا باید x2 و x3 رو انتخاب کنیم! و بعدش x1 رو پس حتما x3 طولش بیشتر از ۱ میشه! پس ب درسته!
ببخشید اگه خوب توضیح ندادم!
فک کنم گزینه ۴ بشه!
برای اینکه یک نویسه طولش ۱ بشه! باید همه نویسه قبلی ها با هم دیگه خورد خورد زیر درخت ها رو بسازن و آخر از همه در درخت نهایی زیر درخت سمت چپ نویسه مورد نظر باشه و زیر درخت سمت راست بقیه نویسه ها! ( یا برعکس, نویسه سمت راست بقیه سمت چپ!)
حالا برای الف:
فرض کنید ۳ تا نویسه داریم با قراوانی های :
x1 = 0.4 , x2 = 0.5 , x3=0.3
خب حالا برای درخت هافمن اول x1 و x3 با هم ترکیب می شن و بعدش x2 باهاشون ترکیب میشه برای درخت نهایی پس x1 که فراوانیش ۲/۵ بود طول کدش ۱ نیست! پس الف غلطه!
برای ب:
فرض کنید نویسه ای که می خواد طول کدش ۱ بشه فراوانیش [tex]\frac{(1-\epsilon)}{3}[/tex] باشه و بقیه هم مثلا همه ۱/۳۰ باشه فراوانیشون! وقتی داریم درختو می سازیم اول اون ۱/۳۰ ها , دو تا دو تا به هم جمع میشن! و می شن ۱/۱۵ و یه دونه ۱/۳۰ هم میمونه! بعد ۱/۳۰ آخر و بقیه ۲/۱۵ ها با هم جمع میشن تا جایی که حاصل جمع ها از ۱/۳ بیشتر شه! ای حاصل جمع حتما کوچکتر از ۲/۳ هست ( چرا؟ چون اگه بخاد بشه ۲/۳ و از اون نویسه خاص ما که فراوانیش [tex]\frac{(1-\epsilon)}{3}[/tex] استفاده نشه شدنی نیس! )
پس الان ۳ تا زیر درخت میمونه ! اولی بین ۱/۳ و ۲/۳ اسمشو می زاریم x1
دومی کمتر از ۱/۳ x2
و سومی نویسه مد نظرمون! x3
حالا باید x2 و x3 رو انتخاب کنیم! و بعدش x1 رو پس حتما x3 طولش بیشتر از ۱ میشه! پس ب درسته!
ببخشید اگه خوب توضیح ندادم!
06 بهمن 1393, 11:43 ب.ظ
با عدد گذاری حل میشه
راحت تقریبا
اما یکم گیره [GRINNING FACE WITH SMILING EYES]
راحت تقریبا
اما یکم گیره [GRINNING FACE WITH SMILING EYES]
06 بهمن 1393, 11:56 ب.ظ
اههه چ سوال چرتی بوده هاااا...
نمیدونم چرا من یجور دیگ برداشت کردم!
مرسی
نمیدونم چرا من یجور دیگ برداشت کردم!
مرسی
07 بهمن 1393, 12:08 ب.ظ
من این سوالو اشکال دارم جوابی که دوستمون توضیح دادنو نمیفهمم
07 بهمن 1393, 04:09 ب.ظ
به نظر منم گزینه یک همیشه درست نیست هر چند که میتونه گاهی درست باشه
در مورد گزینه ۲ نظری ندارم
اما جواب آقای سید جوادی تو کتابشون رو ببینید
[attachment=17894]
در مورد گزینه ۲ نظری ندارم
اما جواب آقای سید جوادی تو کتابشون رو ببینید
[attachment=17894]