Algorithm for neatly printing a paragraph on a printer

Question

First of all, this is not homework, so please don't tag it as homewrok

I did not understand this problem. Can anybody explain it to me? It is not the english that I do not understand, but rather the general gist of the problem.

Answer 1

• The algorithm is supposed to print the paragraph "neatly"
• Padding space at the end of lines (except at the end) is not "neat"
• Thus, the algorithm should minimize such padding
• The exact measure of "neatness" is the sum of the squares of the padding on each line (a very common measure of compound errors, that basically implies that it's more acceptable to have many small errors than a few large ones).

Answer 2

My method for solving this problem ?...Sure babe....Here ya go..served up on a silver platter.

[1] Google search for say: Consider the problem of neatly printing a paragraph on a printer

[2] Pick say ~10 sites that are not obvious chaff.

[3] Have a quick look at the source code on the site...pick some code that is well structured and has plenty of comments.

[4] Pop it into visual studio..write some quciky code that excises the algorithm.

[5] Follow the flow of the code and compare it with the stated problem.

[6] Check a few of the results by hand. If they fail goto step 3.

[7] Run through the code until you understand how it works.

And there you go..How learn just about anything in 7 pain free steps.

Drinks all around...

Can I get you another cocktail ?

It's you lucky day... I'm in a good mood...So, here is a little pseudo code for you....from the first Google hit...even has line numbers so you can ask questions about specific lines...glory days...grrrr.

Lets assume that for all k s where 1 <= k <= n lk < M. PRINT_NEATLY is a bottom-up dynamic-proramming algorithm for the above recursive equation.
Lets create another array lineend[n] to record the end of line word number.


PRINT_NEATLY(n, M, l)
1   for i  <-- n to 1
2       p <-- i
3       CharsLeft <-- M - lp
4       while (CharsLeft - lp+1 -1) > 0 and p < n
5           do  CharsLeft <-- CharsLeft - lp+1 - 1
6                   p <-- p + 1
7       if p = n
8           then c[i] <-- 0
9                   lineend[i] <-- n
10          else
11              c[i] <-- a big number, probably the Maximum nuber for this type.
12              sum_lk <-- 0
13              for j <-- i to p
14                  sum_lk <-- sum_lk + lj 
15                  cost <-- ( M -j + i - sumlk )3 + c[j+1]
16                   if  cost < c[i]
17                       then c[i] <-- cost
18                               lineend[i] <-- j 

19    // Print paragraph
20    start <-- 1
21    while start <= n
22        do
23            for word <-- start to lineend[start]
24                print  ln
25            print newline
26            start <-- lineend[start] + 1