سلام. سوال اول باید N نفر رو بر اساس سرعتشون مرتب کنیم. کل هزینه همینه. بعد در هر مرحله kسریعترین نفر باقی مونده به اون سمت میرن و سریعترین نفرشون برمیگرده.

سوال دوم قسمت اول باید با شرط های پشت سر هم چک کنیم که کدوم بانه. مسئله مانند درختیه که سمت چپش فقط یک ود و سمت راستش یک زیر درخت مشابه درخت اوله. یعنی یک درخت دودویی که فقط فرزندان سمت راستش بسط داده شدن. مجموع هزینه رو میگیریم احتمال انتخاب یک زبان ضربدر سوالات اون زبان. یعنی ۴۰×۱+۱۷×۲+۱۱×۳+۹×۴+... این حاصل رو تقسیم بر ۱۰۰ کنید (چون اعداد مثل ۴۰ و ۱۷ و درصد هستن.) این مقدار میه A1. برای A2 هم باید درخت هافمن رو تشکیل بدید و مثل سوال قبل وزن هر یال رو ضربدر شماره سطر یال کنید. بعد نسبتش رو محاسبه کنید.

واسه سوال دوم مطمئنید؟!!
واسه بدست آوردن A1 فکر کنم این درست نباشه
چون راه حلی که واسش گفتید خود هافمن هستش
من سعی کردم این رو مثل مثال clrs واسه هافمن حل کنم
که تعداد کاراکتر ها رو داده بود ۱۰۰۰۰۰ تا و اینکه این ها رو میشه ۳بیتی حل کرد (همه با هر تعداد فراوانی با سه بیت) بوده و بعد با هافمن اومد اونی رو که فراوانیش بیشتره با بیت کمتر بیان کرد
اینجا ملاک رو ۱۰۰ گرفتم
گفتم ۸تا هستن (۸تا زبان) و در ابتدا وزن هریال رو اگه ۳بگیریم میشه ۳۰۰ بعد با هافمن حل کردم شد ۲۵۶ بعدشم نسبت
فقط شک داشتم گفتم بپرسم نکنه درست نباشه .
واسه سوال الف هم توضیحاتتون درسته.مرسی کمکم کردین
اینم یه جوریایی هافمن میشه
فقط با سوال و مبحث بازی شده تا دانشجو بیشتر به مبحث فکر کنه
پس مرتبه اش میشه همون مرتبه هافمن که O(n)هستش.
در مورد سوال دوم میشه در مورد جواب من نظرتون رو بگید ببینم درست بود یا نه؟
بازم مرسی

راهی که گفتم هافمن نیست. گفتم اول انگلیسی چک میشه. اگه نبود آلمانی، اگه نبود فرانسوی و ... برای انگلیسی یه مقایسه داریم. برای المان دوتا و برای فرانسه ۳ تا. درخت مورب ایجاد میشه. به هیچ وجه توازن هافمن رو نداره. اینی که میگید ۳ زبان داریم و یه درخت با ارتفاع ۳ میسازیم اشتباهه. توی هر سوال فقط یک زبان تایید یا رد میشه. شما توی هر نود از درختتون مجموعه رو دارید نصف میکنید. درحالی که باید یه عضو از مجموعه جدابشه و چک بشه که این عنصر هست یا نه. یعنی یه مرور و جستجوی خطی. با این تفاوت که اونهایی که احتمال اومدنشون بالاتره زودتر چک میشن.