শব্দগুলোর একটি সিকোয়েন্স দেওয়া আছে, প্রতিটি লাইনের জন্য ক্যারেক্টার সংখ্যার একটি সীমা রয়েছে। লাইন ব্রেক ব্যবহার করে এমনভাবে লাইনগুলো প্রিন্ট করা হয় যাতে সেগুলো স্পষ্ট দেখা যায়।
লাইনগুলো সাদৃশ্যাবহ (balanced) হতে হবে। যখন কিছু লাইনে অনেক অতিরিক্ত স্পেস থাকে এবং কিছু লাইনে কম অতিরিক্ত স্পেস থাকে, তবে সেগুলো আলাদা লাইনে বিতরণ করে সাদৃশ্য তৈরি করা হয়। এটি একই সংখ্যক অতিরিক্ত স্পেস ব্যবহার করে সাদৃশ্য তৈরি করার চেষ্টা করে।
এই অ্যালগরিদমটি নির্দেশ করবে প্রতি লাইনে কতগুলো শব্দ রাখা যাবে এবং মোট কতগুলো লাইন দরকার।
ইনপুট এবং আউটপুট
ইনপুট: প্রতিটি লাইনের শব্দ দৈর্ঘ্য। {3, 2, 2, 5}। সর্বোচ্চ প্রস্থ ৬।
আউটপুট:
Line number 1: Word Number: 1 to 1 (केवल একটি শব্দ)
Line number 2: Word Number: 2 to 3 (দ্বিতীয় এবং তৃতীয় শব্দ)
Line number 3: Word Number: 4 to 4 (চতুর্থ শব্দ)
অ্যালগরিদম
wordWrap(wordLenArr, size, maxWidth)
ইনপুট: শব্দ দৈর্ঘ্য অ্যারে, অ্যারের আকার এবং শব্দের সর্বোচ্চ প্রস্থ।
আউটপুট: প্রতি লাইনে কতগুলো শব্দ রাখা হবে তার তালিকা।
শুরু
(size + 1) ক্রমের extraSpace এবং lineCost নামে দুটি স্কোয়ার ম্যাট্রিক্স সংজ্ঞায়িত করুন
(size + 1) আকারের totalCost এবং solution নামে দুটি অ্যারে সংজ্ঞায়িত করুন
i := 1 থেকে size পর্যন্ত, করুন
extraSpace[i, i] := maxWidth - wordLenArr[i - 1]
j := i+1 থেকে size পর্যন্ত, করুন
extraSpace[i, j] := extraSpace[i, j-1] - wordLenArr[j - 1] - 1
끝난
끝난
i := 1 থেকে size পর্যন্ত, করুন
j := i+1 থেকে size পর্যন্ত, করুন
যদি extraSpace[i, j] < 0 হয়, তবে
lineCost[i, j] = ∞
অন্যথায় যদি j = size এবং extraSpace[i, j] >= 0 হয়, তবে
lineCost[i, j] := 0
অন্যথায়
lineCost[i, j] := extraSpace[i, j]²
끝난
끝난
totalCost[0] := 0
j := 1 থেকে size পর্যন্ত, করুন
totalCost[j] := ∞
i := 1 থেকে j পর্যন্ত, করুন
যদি totalCost[i-1] ≠ ∞ এবং lineCost[i, j] ≠ ∞ এবং
(totalCost[i-1] + lineCost[i,j] < totalCost[j]) হয়, তবে
totalCost[i - 1] := totalCost[i - 1] + lineCost[i, j]
solution[j] := i
끝난
끝난
solution ম্যাট্রিক্স প্রদর্শন করুন
শেষ
উদাহরণ (C++)
#include <iostream>
using namespace std;
int dispSolution(int solution[], int size) {
int k;
if (solution[size] == 1)
k = 1;
else
k = dispSolution(solution, solution[size]-1) + 1;
cout << "Line number " << k << ": Word Number: " << solution[size] << " to " << size << endl;
return k;
}
void wordWrap(int wordLenArr[], int size, int maxWidth) {
int extraSpace[size+1][size+1];
int lineCost[size+1][size+1];
int totalCost[size+1];
int solution[size+1];
for(int i = 1; i<=size; i++) {
extraSpace[i][i] = maxWidth - wordLenArr[i-1];
for(int j = i+1; j<=size; j++)
extraSpace[i][j] = extraSpace[i][j-1] - wordLenArr[j-1] - 1;
}
for (int i = 1; i <= size; i++) {
for (int j = i; j <= size; j++) {
if (extraSpace[i][j] < 0)
lineCost[i][j] = INT_MAX;
else if (j == size && extraSpace[i][j] >= 0)
lineCost[i][j] = 0;
else
lineCost[i][j] = extraSpace[i][j] * extraSpace[i][j];
}
}
totalCost[0] = 0;
for (int j = 1; j <= size; j++) {
totalCost[j] = INT_MAX;
for (int i = 1; i <= j; i++) {
if (totalCost[i-1] != INT_MAX && lineCost[i][j] != INT_MAX &&
(totalCost[i-1] + lineCost[i][j] < totalCost[j])) {
totalCost[j] = totalCost[i-1] + lineCost[i][j];
solution[j] = i;
}
}
}
dispSolution(solution, size);
}
int main() {
int wordLenArr[] = {3, 2, 2, 5};
int n = 4;
int maxWidth = 6;
wordWrap(wordLenArr, n, maxWidth);
}
আউটপুট
Line number 1: Word Number: 1 to 1 Line number 2: Word Number: 2 to 3 Line number 3: Word Number: 4 to 4
