自动换行问题 -888棋牌游戏

给出了一个单词序列，每行的字符数有限制。通过放置换行符，以使打印线清晰可见。

这些行必须平衡，当某些行具有很多额外的空间并且某些行包含少量额外的空间时，它将平衡它们到单独的行。它尝试使用相同数量的额外空间来使它们平衡。

该算法将产生一行中可以放置多少个单词，以及需要多少行。

输入输出

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
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: " <= 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