eama183
دوشنبه 02 آذر 1388, 13:26 عصر
سلام دوستان
من تا چهرشنبه دوتا امتحان سخت دارم :افسرده:و متاسفانه این برنامه هم آخرین مهلتش چهارشنبه ست:گریه:،لطفا اگه کسی می تونه کمک کنه خواهش می کنم.
مسئله:
فرض کنید یک متن ورودی که شامل ان کلمه با طول های L1و....LN است داده شده است.طول هر کلمه بنا بر تعریف برابر با تعداد کاراکترهای به کار رفته در آن است.می خاهیم این متن را به گونه ای سطربندی کنیم که در هر سطر حداکثر ام کاراکتر قرار بگیرد.بین هر 2کلمهiو i+1 که در یک سطر قرار میگیزند یک کاراکتر خالی درج میکنیم.فضای اضافی باقی مانده در انتهای هر سطر را نیز با کاراکتر های خالی پر میکنیم. بنابراین اگر کلمات i تا j در یک سطر قرار گیرند تعداد کاراکتر های خالی اضافی در انتهای سطر برابر خواهد بود با :
m-j+i-∑L
راه های مختلفی برای تقسیم یک پاراگراف به چند سطر وجود دارد ولی سعی ما این است که سطرهای پاراگراف تا حد ممکن چشم نواز باشد یک روش مناسب این است که برای هر سطر یک هزینه در نظر بگیریم که برابر با مکعب تعداد فضاهای خالی در آن سطر است و سعی میکنیم مجموع این هزینه ها را به حداقل برسانیم .برای اینکه فضاهای خالی اضافی در آخرین سطر تاثیری در محاسبات نداشته باشند هزینه ی آخرین سطر را برابر 0 تعریف میکنیم. به عبارت دیگر اگر هزینه سطری که شامل کلمات آی تا جی است را :
LINECOST(i,j)=(m-j+i-∑L)^3
هزینه ی سطر بندی یک پاراگراف برابر خواهد بود با مجموع هزینه های مربوط به تمامی سطرهای آن پاراگراف .یک جواب بهینه عبارت است از تقسیم ان کلمه به چند سطر طوری که هزینه های سطر بندی کلمات کمترین مقدار ممکن را داشته باشند.
الف)فرض کنید c(j) برابر با هزینه ی سطربندی بهینه ی کلمات 1 تاj باشد.مقدار c(j) را به صورت بازگشتی (تابع لاین کست) تعریف کنید.
ب)با استفاده از برنامه سازی پویا یک الگوریتم کارا برای محاسبه مقدار جواب بهینه و خود جواب بهینه ارایه کنید.
فایل ورودی
در سطر اول از فایل ورودی مقدار ان(تعداد کلمات ) در سطر 2 مقدار ام (اندازه ی هر سطر) و در ان سطر بعدی عددهای ال1وال2و.....وال ان(طول کلمات ) می ایند.
فایل خروجی
در سطر اول از فایل خروجی مقدار جواب بهینه (هزینه سطر بندی بهینه کلمات ) می اید. در سطرهای بعدی و در هر سطر یک سه تایی (آی و جی و کا) می آید که نشان می دهد کلمات آی تا جی در سطر کا قرار گرفته اند.
من تا چهرشنبه دوتا امتحان سخت دارم :افسرده:و متاسفانه این برنامه هم آخرین مهلتش چهارشنبه ست:گریه:،لطفا اگه کسی می تونه کمک کنه خواهش می کنم.
مسئله:
فرض کنید یک متن ورودی که شامل ان کلمه با طول های L1و....LN است داده شده است.طول هر کلمه بنا بر تعریف برابر با تعداد کاراکترهای به کار رفته در آن است.می خاهیم این متن را به گونه ای سطربندی کنیم که در هر سطر حداکثر ام کاراکتر قرار بگیرد.بین هر 2کلمهiو i+1 که در یک سطر قرار میگیزند یک کاراکتر خالی درج میکنیم.فضای اضافی باقی مانده در انتهای هر سطر را نیز با کاراکتر های خالی پر میکنیم. بنابراین اگر کلمات i تا j در یک سطر قرار گیرند تعداد کاراکتر های خالی اضافی در انتهای سطر برابر خواهد بود با :
m-j+i-∑L
راه های مختلفی برای تقسیم یک پاراگراف به چند سطر وجود دارد ولی سعی ما این است که سطرهای پاراگراف تا حد ممکن چشم نواز باشد یک روش مناسب این است که برای هر سطر یک هزینه در نظر بگیریم که برابر با مکعب تعداد فضاهای خالی در آن سطر است و سعی میکنیم مجموع این هزینه ها را به حداقل برسانیم .برای اینکه فضاهای خالی اضافی در آخرین سطر تاثیری در محاسبات نداشته باشند هزینه ی آخرین سطر را برابر 0 تعریف میکنیم. به عبارت دیگر اگر هزینه سطری که شامل کلمات آی تا جی است را :
LINECOST(i,j)=(m-j+i-∑L)^3
هزینه ی سطر بندی یک پاراگراف برابر خواهد بود با مجموع هزینه های مربوط به تمامی سطرهای آن پاراگراف .یک جواب بهینه عبارت است از تقسیم ان کلمه به چند سطر طوری که هزینه های سطر بندی کلمات کمترین مقدار ممکن را داشته باشند.
الف)فرض کنید c(j) برابر با هزینه ی سطربندی بهینه ی کلمات 1 تاj باشد.مقدار c(j) را به صورت بازگشتی (تابع لاین کست) تعریف کنید.
ب)با استفاده از برنامه سازی پویا یک الگوریتم کارا برای محاسبه مقدار جواب بهینه و خود جواب بهینه ارایه کنید.
فایل ورودی
در سطر اول از فایل ورودی مقدار ان(تعداد کلمات ) در سطر 2 مقدار ام (اندازه ی هر سطر) و در ان سطر بعدی عددهای ال1وال2و.....وال ان(طول کلمات ) می ایند.
فایل خروجی
در سطر اول از فایل خروجی مقدار جواب بهینه (هزینه سطر بندی بهینه کلمات ) می اید. در سطرهای بعدی و در هر سطر یک سه تایی (آی و جی و کا) می آید که نشان می دهد کلمات آی تا جی در سطر کا قرار گرفته اند.