تست ۹۴ طرلحی الگوریتم ۱۳۹۰
فرض کنید یک رشته کاراکتری دارای حرفی با تکرار معین مطابق جدول زیر باشد اگر این رشته به روش هافمن کدگذاری شود اندازه کد کدام حروف یکسان است؟(فرض کنید m>3)
E D C B A حرف
M+2 M-1 M+1 M M+3 تعدا تکرار
جواب: B,D
من روش هافمن رو خوب خوندم ولی اصلا نمیتونم به این سوال پاسخ بدم
اگه کسی بلده کمک کنه چون احتمالان این تست تو کنکور امسال هم مشابهش میاد
مرسی
مطمئنی فقط B,D کد یکسانی دارن؟ من حساب کردم A,C,E هم کد یکسان (بطول ۲) دارن و البته کد B,D هم طول ۳ دارن.
(اشتباه حل کردم جواب رو برداشتم پایین شرح داده شده)
(۳۰ فروردین ۱۳۹۱ ۰۳:۳۵ ب.ظ)yaser_ilam_com نوشته شده توسط: دوست من یادت نره سوال چی خواسته " اندازه کدام دو کد " یکسان است .
ابتدا کوچکترین دو کد را پیدا می کنیم D که همان M-1 و B که همان M می باشد کوچکترین هستند (به M مقدار میدهیم تا بدست اید)
حال این دو را در پایین ترین سطح(برگها) قرار می دهیم جمع اینها معادل ۲M-1 می شود . C کوچکتر از ۲M-1 لذا سمت چپ قرار می گیر جمع این دو معادل ۳M می باشد .E کوچکتر از ۳M لذا سمت چپ قرار می گیرد جمع این دو معادل ۴M+2 .
A کوچکتر از ۴M+2 لذا سمت چپ قرار می گیرد و جمع این دو معادل ۵M+5 که همان ریشه است می باشد .
دوباره از ریشه به پایین ادامه م دهیم :
ریشه معادل ۵M+5 و فرزند چپ و راست به ترتیب به صورت A و ۴M+2 قرار می گیرد A برگ است و گره ۴M+2 فرزند چپ و راست به ترتیب به صورت E و ۳M است .
E برگ است و گره ۳M فرزند چپ و راست به ترتیب به صورت C و ۲M-1 قرار می گیرد C برگ است و گره ۲M-1 دارای فرزند چپ و راست به صورت M-1 و M یعنی همان B و D .
کد A بصورت ۰ .
کد B بصورت ۱۱۱۱ .
کد C بصورت ۱۱۰/
کد D بصورت ۱۱۱۰ .
کد E بصورت ۱۰/
لذا B , D دارای اندازه یکسان معادل ۴ هستند .
فکر کنم یه جای کار اشتباه میکنی ، بعد از اینکه B,D رو انتخاب میکنی و جمعشون میشه ۲M-1 دوباره باید جدول رو Update کنی و دو حرفی که کمترین تکرار رو دارن رو انتخاب کنی .
یعنی اگه مثلا M = 4 در نظر بگیری داریم :
A=7 , B^D=7 , C=5 , E=6
که در اینصورت C , E رو انتخاب میکنیم و به عنوان برگ های درخت جداگانه از B^D قرار میدهیم.تا اینجا یک جنگل از دو درخت C^E , B^D داریم و دوباره جدول رو Update میکنیم و الا آخر... درسته؟
(۳۰ فروردین ۱۳۹۱ ۰۳:۵۵ ب.ظ)sd_javadi نوشته شده توسط:حق با شماست .ممنون از دقتتون .(30 فروردین ۱۳۹۱ ۰۳:۳۵ ب.ظ)yaser_ilam_com نوشته شده توسط: دوست من یادت نره سوال چی خواسته " اندازه کدام دو کد " یکسان است .
لذا B , D دارای اندازه یکسان معادل ۴ هستند .
فکر کنم یه جای کار اشتباه میکنی ، بعد از اینکه B,D رو انتخاب میکنی و جمعشون میشه ۲M-1 دوباره باید جدول رو Update کنی و دو حرفی که کمترین تکرار رو دارن رو انتخاب کنی .
یعنی اگه مثلا M = 4 در نظر بگیری داریم :
A=7 , B^D=7 , C=5 , E=6
که در اینصورت C , E رو انتخاب میکنیم و به عنوان برگ های درخت جداگانه از B^D قرار میدهیم.تا اینجا یک جنگل از دو درخت C^E , B^D داریم و دوباره جدول رو Update میکنیم و الا آخر... درسته؟
من تنها راه حل ممکن برای رسیدن به جوابی که دوستمون قرار داده بود رو بررسی کرده بودم.
جواب آخر من .
هم اندازه :
B,D
A,C,E
باید تو گزینه ها دید کدام درسته شاید همون گزینه B,D رو تو گزینه ها قرار داده باشند
درسته با دادن مقدار به M موارد B , D به طول ۳ و A, E, C به طول ۲ دارای اندازه‌ی یکسان هستند.
با تشکر از جواب خوب دوستان
ایشالا که اگه شما هم مشکلی داشتین من بتونم کمک کنم
ولی صورت سوال یه جاش مشکل داره اگه M=1 یا دو باشه اوضاع فرق می کنه و باید بررسی بشه در این صورت M+1 , M+2 بزرگتر از ۲M-1 هستند
در این صورت تنها B,D یکسان خواهند بود