Một dãy từ được đưa ra, có giới hạn về số ký tự cho mỗi dòng. Bằng cách đặt dấu ngắt dòng, sao cho các dòng được in rõ ràng.
Các dòng phải cân đối, khi một số dòng có nhiều khoảng trắng thừa và một số dòng chứa một số khoảng thừa nhỏ, nó sẽ cân bằng chúng thành các dòng riêng biệt. Nó cố gắng sử dụng cùng một số khoảng trắng để làm cho chúng cân bằng.
Thuật toán này sẽ tạo ra bao nhiêu từ có thể được đặt trong một dòng và cần bao nhiêu dòng.
Đầu vào và Đầu ra
Input: The length of words for each line. {3, 2, 2, 5}. The max width is 6. Output: Line number 1: Word Number: 1 to 1 (only one word) Line number 2: Word Number: 2 to 3 (Second and 3rd word) Line number 3: Word Number: 4 to 4 (4th word)
Thuật toán
wordWrap(wordLenArr, size, maxWidth)
Đầu vào - Mảng độ dài từ, kích thước của mảng và chiều rộng tối đa của từ.
Đầu ra - Danh sách bao nhiêu từ sẽ đặt trên mỗi dòng.
Begin define two square matrix extraSpace and lineCost of order (size + 1) define two array totalCost and solution of size (size + 1) for i := 1 to size, do extraSpace[i, i] := maxWidth – wordLenArr[i - 1] for j := i+1 to size, do extraSpace[i, j] := extraSpace[i, j-1] – wordLenArr[j - 1] - 1 done done for i := 1 to size, do for j := i+1 to size, do if extraSpace[i, j] < 0, then lineCost[i, j] = ∞ else if j = size and extraSpace[i, j] >= 0, then lineCost[i, j] := 0 else linCost[i, j] := extraSpace[i, j]^2 done done totalCost[0] := 0 for j := 1 to size, do totalCost[j] := ∞ for i := 1 to j, do if totalCost[i-1] ≠∞ and linCost[i, j] ≠ ∞ and (totalCost[i-1] + lineCost[i,j] < totalCost[j]), then totalCost[i – 1] := totalCost[i – 1] + lineCost[i, j] solution[j] := i done done display the solution matrix End
Ví dụ
#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++) { //find extra space for all lines extraSpace[i][i] = maxWidth - wordLenArr[i-1]; for(int j = i+1; j<=size; j++) { //extra space when word i to j are in single line extraSpace[i][j] = extraSpace[i][j-1] - wordLenArr[j-1] - 1; } } for (int i = 1; i <= size; i++) { //find line cost for previously created extra spaces array 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++) { //find minimum cost for words 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); } main() { int wordLenArr[] = {3, 2, 2, 5}; int n = 4; int maxWidth = 6; wordWrap (wordLenArr, n, maxWidth); }
Đầu ra
Line number 1: Word Number: 1 to 1 Line number 2: Word Number: 2 to 3 Line number 3: Word Number: 4 to 4