زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۴:۲۶ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

یک تست از الگوریتم هافمن

ارسال:
۳۰ فروردین ۱۳۹۱, ۱۰:۲۵ ق.ظ
یک تست از الگوریتم هافمن
تست ۹۴ طرلحی الگوریتم ۱۳۹۰

فرض کنید یک رشته کاراکتری دارای حرفی با تکرار معین مطابق جدول زیر باشد اگر این رشته به روش هافمن کدگذاری شود اندازه کد کدام حروف یکسان است؟(فرض کنید m>3)

E D C B A حرف
M+2 M-1 M+1 M M+3 تعدا تکرار

جواب: B,D

من روش هافمن رو خوب خوندم ولی اصلا نمیتونم به این سوال پاسخ بدم

اگه کسی بلده کمک کنه چون احتمالان این تست تو کنکور امسال هم مشابهش میاد

مرسی
یافتن تمامی ارسال‌های این کاربر
 سپاس‌گزاری شده توسط: zeinab
ارسال:
۳۰ فروردین ۱۳۹۱, ۰۳:۱۹ ب.ظ
یک تست از الگوریتم هافمن
مطمئنی فقط B,D کد یکسانی دارن؟ من حساب کردم A,C,E هم کد یکسان (بطول ۲) دارن و البته کد B,D هم طول ۳ دارن.

هیچ تمدنی توسط بیگانگان از برون فتح نمی‌شود مگر آنکه ابتدا از درون خود را تخریب کرده باشد.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(شاید به دردتون خورد)
یافتن تمامی ارسال‌های این کاربر
ارسال:
۳۰ فروردین ۱۳۹۱, ۰۳:۳۵ ب.ظ (آخرین ویرایش در این ارسال: ۳۰ فروردین ۱۳۹۱ ۰۴:۵۰ ب.ظ، توسط yaser_ilam_com.)
یک تست از الگوریتم هافمن
(اشتباه حل کردم جواب رو برداشتم پایین شرح داده شده)

درد من حصار برکه نیست ، درد من زیستن با ماهیانیست که فکر دریا به ذهنشان خطور نکرده
یافتن تمامی ارسال‌های این کاربر
ارسال:
۳۰ فروردین ۱۳۹۱, ۰۳:۵۵ ب.ظ
یک تست از الگوریتم هافمن
(۳۰ فروردین ۱۳۹۱ ۰۳:۳۵ ب.ظ)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 میکنیم و الا آخر... درسته؟

هیچ تمدنی توسط بیگانگان از برون فتح نمی‌شود مگر آنکه ابتدا از درون خود را تخریب کرده باشد.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(شاید به دردتون خورد)
یافتن تمامی ارسال‌های این کاربر
ارسال:
۳۰ فروردین ۱۳۹۱, ۰۴:۴۸ ب.ظ (آخرین ویرایش در این ارسال: ۳۰ فروردین ۱۳۹۱ ۰۴:۵۱ ب.ظ، توسط yaser_ilam_com.)
RE: یک تست از الگوریتم هافمن
(۳۰ فروردین ۱۳۹۱ ۰۳:۵۵ ب.ظ)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 به طول ۲ دارای اندازه‌ی یکسان هستند.

Yesterday is History, Tomorrow is a Mystery but Today is a Gift
That is why it's called the Present
یافتن تمامی ارسال‌های این کاربر
ارسال:
۳۰ فروردین ۱۳۹۱, ۱۰:۰۲ ب.ظ
یک تست از الگوریتم هافمن
با تشکر از جواب خوب دوستان
ایشالا که اگه شما هم مشکلی داشتین من بتونم کمک کنم
یافتن تمامی ارسال‌های این کاربر
ارسال:
۲۸ دى ۱۳۹۱, ۰۶:۳۷ ب.ظ (آخرین ویرایش در این ارسال: ۲۸ دى ۱۳۹۱ ۰۶:۴۱ ب.ظ، توسط mahdiii.)
RE: یک تست از الگوریتم هافمن
ولی صورت سوال یه جاش مشکل داره اگه M=1 یا دو باشه اوضاع فرق می کنه و باید بررسی بشه در این صورت M+1 , M+2 بزرگتر از ۲M-1 هستند

در این صورت تنها B,D یکسان خواهند بود
یافتن تمامی ارسال‌های این کاربر


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  کد هافمن Sanazzz ۲ ۲,۵۱۵ ۰۴ اردیبهشت ۱۳۹۸ ۰۳:۴۷ ب.ظ
آخرین ارسال: Sanazzz
  بهترین کتاب (ها) آموزش و تست ساختمان داده و طراحی الگوریتم برای کنکور ارشد AreF95 ۶ ۱۲,۴۱۹ ۰۵ تیر ۱۳۹۷ ۱۱:۴۱ ق.ظ
آخرین ارسال: shahbaz222
  محاسبه طول کلمه در هافمن Mr.R3ZA ۳ ۳,۷۷۵ ۱۰ خرداد ۱۳۹۷ ۰۲:۲۳ ق.ظ
آخرین ارسال: saeed_vahidi
  علوم کامپیوتر - کدینگ هافمن ali.majed.ha ۳ ۲,۳۹۶ ۰۸ اسفند ۱۳۹۵ ۱۱:۱۶ ق.ظ
آخرین ارسال: ali.majed.ha
  حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)(۱) Saman ۲۳ ۲۵,۲۷۳ ۱۲ مهر ۱۳۹۵ ۰۱:۳۱ ق.ظ
آخرین ارسال: Saman
  حل سوالات ساختمان داده و طراحی الگوریتم(۶۰۰ مساله،و تست های مهم)(۲) Saman ۱ ۲,۳۱۷ ۱۲ مهر ۱۳۹۵ ۱۲:۲۴ ق.ظ
آخرین ارسال: Saman
  ۱۷۱ نرم افزار و ۱۹۸ الگوریتم - شبانه الگوریتم دانشگاه تهران axarsu ۱ ۲,۴۵۶ ۰۸ شهریور ۱۳۹۵ ۰۸:۳۶ ب.ظ
آخرین ارسال: majidgeek
  ۲۴۲ الگوریتم ،۳۷۱ نرم. الگوریتم برم یا نرم افزار؟ azamcheraghi ۱۱ ۷,۲۱۸ ۰۳ تیر ۱۳۹۵ ۱۱:۳۸ ق.ظ
آخرین ارسال: azamcheraghi
  مشکل در الگوریتم جایگزینی (الگوریتم ساعت ) araz22 ۶ ۴,۷۲۱ ۱۹ مهر ۱۳۹۴ ۱۰:۲۴ ب.ظ
آخرین ارسال: so@
  ۸ الگوریتم ۱۲ نرم افزار ۱۵ علوم -- نرم افزار شریف گرایش الگوریتم ahrmb ۲ ۱,۸۴۱ ۰۸ مهر ۱۳۹۴ ۰۶:۴۳ ب.ظ
آخرین ارسال: ahrmb

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close