Analyzing Printing neatly again Recursive formula 断句点 个如是的众来 断句点确定后留下两类问题 的不优美度,假 类问题的不优美度要考虑最后一行数值:另 类问题的不优美度不考虑最后一行的数值 ■D(1,n)!递归 ■说明上述选择方法、证明上述选择方法的正确 a D(j)=min ek D(k+1.j)1 ■初始值? ■递归公式准备工作如何做?【见下页】 初始值( Initial values) 最优子结构 当k)一计+所有词的字符数≤行字符数时【词与词 ■原问题的解是最优的 之间空格数为】 ■C(uj)=行字符数一K(〕]3 ■如何说明原问题的解是由子问题的最优解构成 ■D(uj)户=0 的,这是分析问题的关键 ■如果编程:请问最严重的异常情况是什么? ■思考:如果字符宽度不同,上述方法有效否? ■进一步:如果字符宽度不同,其宽度可以无级缩放, 每行两头完全对齐,如何定义优美度 清华太学未证想 优美打印问题变种 编辑距离 ■字符宽度不同 ■从一个字符串到另一个字符串可以由若干变换构成 ■可以调整某些字符的宽度,如空格,但调整要 计算在优美度内 可以调整所有字符的宽度 ■其它语言如汉语的优美度问题 n Twiddle ■图文混排问题等等 ■x=oy,其中o是一连串的变换=t2…tn5 清华大学 宋斌恒 25 Analyzing Printing neatly again n 断句点 n 断句点确定后留下两类问题 n 一类问题的不优美度要考虑最后一行数值；另 一类问题的不优美度不考虑最后一行的数值； n 说明上述选择方法、证明上述选择方法的正确 性。 n 递归公式准备工作如何做？【见下页】 清华大学 宋斌恒 26 Recursive Formula n 请问：如果C(i,j)表示从第i个词开始到第j个词结束段落 包括最后一行的不优美度，如果D(i,j)表示从第i个词开 始到第j个词结束段落不包括最后一行的不优美度，假 设有n个词，原问题的不优美度为 n D(1,n)！递归公式？ n C(i,j)=mini<k<j {C(i,k)+ C(k+1,j)} n D(i,j)=mini<k<j {C(i,k)+ D(k+1,j)} n 初始值？ 清华大学 宋斌恒 27 初始值（Initial values） n 当k(i,j)=j－i＋所有词的字符数≤行字符数时【词与词 之间空格数为1】 n C(i,j)=[行字符数－k(i,j)]3 n D(i,j)=0 n 如果编程：请问最严重的异常情况是什么？ n 思考：如果字符宽度不同，上述方法有效否？ n 进一步：如果字符宽度不同，其宽度可以无级缩放， 每行两头完全对齐，如何定义优美度？ 清华大学 宋斌恒 28 最优子结构 n 原问题的解是最优的 n 如何说明原问题的解是由子问题的最优解构成 的，这是分析问题的关键 清华大学 宋斌恒 29 优美打印问题变种 n 字符宽度不同 n 可以调整某些字符的宽度，如空格，但调整要 计算在优美度内。 n 可以调整所有字符的宽度。 n 其它语言如汉语的优美度问题 n 图文混排问题等等 清华大学 宋斌恒 30 编辑距离 n 从一个字符串到另一个字符串可以由若干变换构成： n Copy n Replace n Delete n Insert n Twiddle n Kill n x=s(y), 其中s是一连串的变换s＝t1 t2… tn