کسی میتونه این سوالو برام توضبح بده ک چجوری میشه ب جواب رسید؟
[attachment=17886]
سلام
فک کنم گزینه ۴ بشه!
برای اینکه یک نویسه طولش ۱ بشه! باید همه نویسه قبلی ها با هم دیگه خورد خورد زیر درخت ها رو بسازن و آخر از همه در درخت نهایی زیر درخت سمت چپ نویسه مورد نظر باشه و زیر درخت سمت راست بقیه نویسه ها! ( یا برعکس, نویسه سمت راست بقیه سمت چپ!)
حالا برای الف:
فرض کنید ۳ تا نویسه داریم با قراوانی های :
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 طولش بیشتر از ۱ میشه! پس ب درسته!
ببخشید اگه خوب توضیح ندادم!
با عدد گذاری حل میشه
راحت تقریبا
اما یکم گیره [GRINNING FACE WITH SMILING EYES]
اههه چ سوال چرتی بوده هاااا...
نمیدونم چرا من یجور دیگ برداشت کردم!
مرسی
من این سوالو اشکال دارم جوابی که دوستمون توضیح دادنو نمیفهمم
به نظر منم گزینه یک همیشه درست نیست هر چند که میتونه گاهی درست باشه
در مورد گزینه ۲ نظری ندارم
اما جواب آقای سید جوادی تو کتابشون رو ببینید
[attachment=17894]