۰
subtitle
سلام
فک کنم گزینه ۴ بشه!
برای اینکه یک نویسه طولش ۱ بشه! باید همه نویسه قبلی ها با هم دیگه خورد خورد زیر درخت ها رو بسازن و آخر از همه در درخت نهایی زیر درخت سمت چپ نویسه مورد نظر باشه و زیر درخت سمت راست بقیه نویسه ها! ( یا برعکس, نویسه سمت راست بقیه سمت چپ!)
حالا برای الف:
فرض کنید ۳ تا نویسه داریم با قراوانی های :
x1 = 0.4 , x2 = 0.5 , x3=0.3
خب حالا برای درخت هافمن اول x1 و x3 با هم ترکیب می شن و بعدش x2 باهاشون ترکیب میشه برای درخت نهایی پس x1 که فراوانیش ۲/۵ بود طول کدش ۱ نیست! پس الف غلطه!
برای ب:
فرض کنید نویسه ای که می خواد طول کدش ۱ بشه فراوانیش (1−ϵ)3 باشه و بقیه هم مثلا همه ۱/۳۰ باشه فراوانیشون! وقتی داریم درختو می سازیم اول اون ۱/۳۰ ها , دو تا دو تا به هم جمع میشن! و می شن ۱/۱۵ و یه دونه ۱/۳۰ هم میمونه! بعد ۱/۳۰ آخر و بقیه ۲/۱۵ ها با هم جمع میشن تا جایی که حاصل جمع ها از ۱/۳ بیشتر شه! ای حاصل جمع حتما کوچکتر از ۲/۳ هست ( چرا؟ چون اگه بخاد بشه ۲/۳ و از اون نویسه خاص ما که فراوانیش (1−ϵ)3 استفاده نشه شدنی نیس! )
پس الان ۳ تا زیر درخت میمونه ! اولی بین ۱/۳ و ۲/۳ اسمشو می زاریم x1
دومی کمتر از ۱/۳ x2
و سومی نویسه مد نظرمون! x3
حالا باید x2 و x3 رو انتخاب کنیم! و بعدش x1 رو پس حتما x3 طولش بیشتر از ۱ میشه! پس ب درسته!
ببخشید اگه خوب توضیح ندادم!
فک کنم گزینه ۴ بشه!
برای اینکه یک نویسه طولش ۱ بشه! باید همه نویسه قبلی ها با هم دیگه خورد خورد زیر درخت ها رو بسازن و آخر از همه در درخت نهایی زیر درخت سمت چپ نویسه مورد نظر باشه و زیر درخت سمت راست بقیه نویسه ها! ( یا برعکس, نویسه سمت راست بقیه سمت چپ!)
حالا برای الف:
فرض کنید ۳ تا نویسه داریم با قراوانی های :
x1 = 0.4 , x2 = 0.5 , x3=0.3
خب حالا برای درخت هافمن اول x1 و x3 با هم ترکیب می شن و بعدش x2 باهاشون ترکیب میشه برای درخت نهایی پس x1 که فراوانیش ۲/۵ بود طول کدش ۱ نیست! پس الف غلطه!
برای ب:
فرض کنید نویسه ای که می خواد طول کدش ۱ بشه فراوانیش (1−ϵ)3 باشه و بقیه هم مثلا همه ۱/۳۰ باشه فراوانیشون! وقتی داریم درختو می سازیم اول اون ۱/۳۰ ها , دو تا دو تا به هم جمع میشن! و می شن ۱/۱۵ و یه دونه ۱/۳۰ هم میمونه! بعد ۱/۳۰ آخر و بقیه ۲/۱۵ ها با هم جمع میشن تا جایی که حاصل جمع ها از ۱/۳ بیشتر شه! ای حاصل جمع حتما کوچکتر از ۲/۳ هست ( چرا؟ چون اگه بخاد بشه ۲/۳ و از اون نویسه خاص ما که فراوانیش (1−ϵ)3 استفاده نشه شدنی نیس! )
پس الان ۳ تا زیر درخت میمونه ! اولی بین ۱/۳ و ۲/۳ اسمشو می زاریم x1
دومی کمتر از ۱/۳ x2
و سومی نویسه مد نظرمون! x3
حالا باید x2 و x3 رو انتخاب کنیم! و بعدش x1 رو پس حتما x3 طولش بیشتر از ۱ میشه! پس ب درسته!
ببخشید اگه خوب توضیح ندادم!
