سلام !
میتونید جواب این سوال رو به من بگید یا حداقل راهنماییم کنید؟
چار فایل مرتب شده ی f اندیس ۱ و fاندیس ۲ و fاندیس ۳وf اندیس ۴به ترتیب با اندازه های ۵۰و۱۰۰و۲۰۰و۳۰۰ در اختیار داریم.
ترتیب ادغام دو به دوی آن ها چگونه باشد که کمترین مقدار مقایسه ها صورت بگیرد!؟
استاد میگف یه جورایی ربط داره به مبحث "هافمن" از درس طراحی الگوریتم!
نمیشه دقیقا گفت مربوط به مبحث هافمنه راه حلش شبیه به الگوریتم هافمنه !
جوابش اینجوری میشه که اول ۵۰ با ۱۰۰ ادغام میشه که تعداد ۱۵۰ مقایسه لازم داره . ۲۰۰ با ۱۵۰ ادغام میشه که ۳۵۰ مقایسه لازم داره . ۳۰۰ با ۳۵۰ ادغام میشه که ۶۵۰ مقایسه لازم داره و در نهایت تعداد کل مقایسه ها برابر با ۱۱۵۰=۱۵۰+۳۵۰+۶۵۰ میشه .
شبیه بودنش به الگوریتم هافمن اینجاست که می تونی برای حل کردنش از درخت دودویی استفاده کنی که پیاده سازی این درخت دقیقا مثل درخت هافمنه (دو مقدار کوچکتر رو از لیست برداشته و با هم ادغام می کنیم ) اسمش هم درخت دودویی ادغامه. به این صورت که گره های خارجی (برگ ها) معرف فایل ها هستند و گره های داخلی معرف فایلی است که از ادغام دو فایل نشان داده شده توسط فرزندانش حاصل شده است و عدد داخل هر گره اندازه فایل نمایش داده شده توسط آن گره است .
برای محاسبه ی تعداد مقایسه ها در حالت کلی هم اگر [tex]d_{i}[/tex] برابر مسافت فایل [tex]F_{i}[/tex] در درخت دودویی ادغام باشد(فاصله از ریشه ) و [tex]q_{i}[/tex] اندازه فایل [tex]F_{i}[/tex] (تعداد رکورد هاش) باشد ، تعداد کل رکورد های جابجا شده از این رابطه بدست میاد
[tex]\sum _{i=0}^{n} d_{i} q_{i}[/tex]
که اگه توی این سوال درخت دودویی ادغام رو رسم بکنی جواب اینجوری بدست میاد
[attachment=8072]
(۳*۵۰)+(۳*۱۰۰)+(۲*۲۰۰)+(۱*۳۰۰)=۱۱۵۰
(۰۷ آذر ۱۳۹۱ ۰۲:۴۶ ب.ظ)javadem نوشته شده توسط: جسارته ولی راه حلی که فرمودین یه مشکل کوچیک داره!
اون عددی که شما بدست آوردید مینیمم نیست!
اگر اول ۱۰۰ و ۵۰ رو ادغام کنید به ۱۵۰ مقایسه نیاز است!
سپس اگر ۱۵۰ و ۲۰۰ را ادغام کنید ۳۵۰ مقایسه نیاز است !
و بعد از آن اگر ۳۵۰ با ۳۰۰ ادغام شود به ۶۵۰ مقایسه نیاز است که در کل میشه:
۱۵۰+۳۵۰+۶۵۰ =۱۱۵۰ که کمتر از ۱۳۰۰ است!
به نظر من راهش همون الگوریتم هافمن هست که در هر مرحله کوچکترینها با هم ادغام بشن و به همین ترتیب تا آخرین فایل!
چون نتیجه هر عمل ادغام قراره در اعمال بعدی هم محاسبه بشه باید در هر مرحله سعی بشه که تعداد مقایسه هر ادغام کمترین باشه!
راه حل درسته اما من توی محاسبه اشتباه کرده بودم ! مرسی که گفتید
درستش کردم .
یه دنیا ممنونم ازتون!