Question

算法分析里的漂亮打印问题，求C语言的源代码，不要C++的和JAVA的，网上的我基本都看过了，都是

或多或少的问题没解决就发上来了。希望有大神能够赐教。要切实可以运行的。定义的变量标注是什么即可
请用动态规划的办法

Answer 1

/**
 * 由给定的n个英文单词组成一篇文章，每个单词的长度(字符个数)依次为l1,l2...
 * 要在一台打印机上将这段文章漂亮的打印出来．打印机每行最多可打印M个字符．
 * 这里所说的漂亮打印定义如下：
 * 在打印机所打印的每一行中，行首和行尾可不留空格；
 * 行中每两个单词之间留一个空格，且不允许将单词打破。
 * 如果在一行中打印从单词i到单词j的字符，则按照打印规则，应该在一行中打印
 * sum(lk,i<=k<j)+j-i个字符,多余的空格数为M-j+i-sum(lk,i<=k<j);
 * 除文章的最后一行外，希望每行多余的空格数目尽可能少，
 * 以每行多余空格数的立方和达到最小作为漂亮的标准．
 * 分析与解答：
 * 最优子结构性质：
 * 在一个最优打印方案上，如果将单词1～k安排在第一行打印，则
 * 显然这个方案对后续的k+1～n个单词的打印安排是单词k+1~n的漂亮打印子问题的
 * 最优打印方案重叠的子问题：
 * 在第一行中安排单词1~k的所有打印方案都要考虑后续单词k+1~n的打印子问题．
 * 因此，在计算中有许多重叠子问题递归计算：
 * 由于在一行不允许将单词打破，故可设li<=M,1<=i<=n．
 * 为了处理边界情形，定义数组extras和lc如下：
 * extras[i][j]=M-j+i-sum(lk,i<=k<j)
 * 它是将单词i到j安排在一行中时行尾的多余空格数．
 * 注意extras[i][j]可能为负，即一行不够打印i~j，有可能将单词打破．
 * lc表示将单词i~j打印在一行上的费用：
 *          ┌∞    　　　　　　    if (extras[i][j]<0)
 * lc[i][j]=│0                     if (extras[i][j]>=0 && j=n)
 *          └(extras[i][j])^3    　else
 * 设c[i]是安排单词1～i时候的最小费用，则递归的计算如下：
 *      ┌0                                  i=0;
 * c[i]=│
 *      └min{c[j-1]+lc[j][i],1<=j<=i}       i>0;
 */

#include <stdio.h>
#include <stdlib.h>
#define N 100
#define INF 10000
void print(int *p, int n)
{
 int i,j;
 for (i=0;i<n;i++)
 {
  for (j=0;j<i;j++)
   printf("\t");
  for (j=i;j<n;j++)
   printf("%8d",*(p+i*N+j));
  printf("\n");
 }
}
int main()
{
 int i,j;
 int n,m;
 int min,tmp_min,tmp_idx;
 int l[N];
 int sum[N][N];
 int extras[N][N];
 int lc[N][N];
 int c[N+1],idx[N];
 printf("输入——文章中总共有多少个单词：");
 scanf("%d",&n);
 for (i=0;i<n;i++)
 {
  printf("输入——第%2d个单词的长度是多少：",i+1);
  scanf("%d",l+i);
 }
 printf("输入——每行可以打印多少个字符：");
 scanf("%d",&m);
 
 for (i=0;i<n;i++)
  sum[i][i] = l[i];
 for (i=1;i<n;i++)
  for (j=0;j<i;j++)
   sum[j][i] = sum[j][i-1]+l[i];
 print((int*)sum, n);
 for (i=0;i<n;i++)
  for (j=i;j<n;j++)
   extras[i][j] = m+i-j-sum[i][j];
 print((int*)extras, n);
 for (i=0;i<n;i++)
  for (j=i;j<n;j++)
   if (extras[i][j]<0)
    lc[i][j] = INF;
   else if (j==n-1)
    lc[i][j] = 0;
   else
    lc[i][j] = extras[i][j]*extras[i][j]*extras[i][j];
 print((int*)lc, n);

 c[n] = 0;
 for (i=n-1;i>=0;i--)
 {
  min = INF;
  for (j=i+1;j<=n;j++)
  {
   tmp_min = lc[i][j-1]+c[j];
   if (min>tmp_min)
   {
    min = tmp_min;
    tmp_idx = j-1;
   }
  }
  c[i] = min;
  idx[i] = tmp_idx;
 }
 printf("漂亮打印的空格立方和：%d\n", c[0]);
 printf("漂亮打印如下：\n");
 printf("|");
 for (i=0;i<m;i++)
  printf("-");
 printf("|\n|");
 tmp_idx = 0;
 for (i=0;i<n;i++)
 {
  for (j=0;j<l[i];j++)
   printf("*");
  if (idx[tmp_idx]==i)
  {
   for (int k=0;k<extras[tmp_idx][i];k++)
    printf(" ");
   printf("|\n|");
   tmp_idx = i+1;
  }
  else
   printf(" ");
 }
 for (i=0;i<m;i++)
  printf("-");
 printf("|\n");
 system("pause");
 return 0;
}

Answer 2

你没有说打印成什么样子，也没有事活打印什么数据，你问的太模糊了，代码就是现编也没有依照啊。

追问

算法里的经典问题漂亮打印，学过算法的都知道这个题目。问题很长，还有很多特殊字符不好打。需要学过这个的大神赐教

追答

你这样说就不需要我的帮助了，所谓的算法无非就是一些代码的累积，比如牛顿法，单纯性法，等等，但是你现在要的是一个打印输出格式，关算法毛事，只不过是一些代码组织输出而已，连算法你都会编写，这些格式控制就办不了，显得很高深的样子!!!

追问

你应该是没学过算法，不知道漂亮打印是什么意思，你可以去百度一下，看看什么叫漂亮打印，你再看看为什么属于算法的内容。

Answer 3

http://blog.csdn.net/code_pang/article/details/8851946

Answer 4

什么叫漂亮打印 ，彩色的打印的意思吗

追问

不是，是一个算法问题。你可以百度一下看看，题目有点长