حل تشریحی سوال شماره 13 طراحی الگوریتم

تعدادی فایل با اندازه های مشخص را میخواهیم روی نوار ذخیره کنیم. فرض کنید $f_1,\dots ,f_n$ به ترتیب (از راست به چپ) روی نوار ذخیره شده باشند، هزینه خواندن فایل $f_i$ برابر ${\sum }_{k-1}^i\left|f_i\right|$ خواهد بود که $\left|f_k\right|$ برابر طول فایل $f_k$ می‌باشد. فرض کنید قرار است هر فایل تنها یکبار خوانده شود میخواهیم مجموع هزینه را کمینه کنیم. بدین منظور از الگوریتم حریصانه زیر استفاده می‌کنیم فایل‌ها را به ترتیب اندازه از کوچک به بزرگ روی نوار ذخیره می‌کنیم. اگر n تعداد فایل‌ها ،باشد کم‌ترین n که به ازای آن الگوریتم فوق لزوماً درست کار نمی‌کند، کدام است؟