資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C #
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律學單詞拼合問題
給定一個單詞序列，每行字元數有限。透過換行符使行清晰列印。
某些行有很多額外空格，某些行的額外空格較少時，這些行必須保持平衡，才能分隔各行。此演算法會盡可能使用相同數量的額外空格使其保持平衡。
此演算法會生成可以放置在一行中的單詞數，以及需要的行數。
輸入和輸出
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)演算法
wordWrap(wordLenArr, size, maxWidth)
輸入 − 單詞長度陣列、陣列大小和單詞的最大寬度。
輸出 − 按行放置單詞數的列表。
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
示例
#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);
}輸出
Line number 1: Word Number: 1 to 1 Line number 2: Word Number: 2 to 3 Line number 3: Word Number: 4 to 4
更新日期: 17-Jun-2020
1K+ 瀏覽量
廣告