PDA

View Full Version : سوال: تست الگوریتم هافمن



bahar1370
سه شنبه 14 شهریور 1391, 02:56 صبح
حد اکثر طول یک کد درخت هافمن با n گره چند بیت است؟
n-1 یا n/2
تو کتاب تست n-1 .فکر می کنم این جواب برای وقتی که با n برگ چند تا بیت.
من فکر می کنم n/2 درسته .
همین ؟؟؟؟؟

مسعود اقدسی فام
سه شنبه 14 شهریور 1391, 08:23 صبح
وقتی بحث حداکثر می‌شه، یعنی در هر سطح فقط یه برگ داشته باشیم. یعنی یه جورایی درخت به صورت اریب پیش رفته. در این حالت وقتی n تا برگ داریم، دو تا که سطح آخر هستن و n - 2 تا می‌مونه سطوح بالاتر. پس n - 2 سطح بالایی بعلاوه‌ی سطح آخر، یعنی n - 1 سطح درست می‌شه.

فرض کنید n = 4، و همچین درختی رو ترسیم کنید.