C程序设计例解(05)

 

04. 试从含有n个int型数的数组中删去若干个成分，使剩下的全部成分构成一个不减的子序列。设计算法和编写程序求出数组的不减子序列的长。
解：
    从数组的第一个元素开始，顺序考察数组的每个元素，当数组的全部元素都被考察后才能求出数组的最长不减子序列的长。设数组为b[]，已考察了b[0]至b[i-1]的全部元素，求得当前最长的不减子序列长为k。当前正要考察b[i]是否会引起k值增大，依赖于b[i]是否会大于或等于b[0]至b[i-1]中某个最长不减子序列的终元素.b[0]至b[i-1]中可能有多个长为k的不减子序列。很显然，在同样长度的不减子序列中，只要保留那个子序列终元素最小的一个就足够了。如有一变量保存有在b[0]至b[i-1]中长度为k的不减子序列最小的终元素，这样在b[0]至b[i-1]中，是否有长度为k+1的不减子序列，依赖于b[i]是否大于等于那个长度为k的不减子序列的终元素值。
    但当b[i]小于那个长度为k的不减子序列最小的终元素的值时，如果在b[0]至b[i-1]中有长度为k-1的不减子序列，且该子序列的值不大于b[i]，这时因长度为k-1的不减子序列的终元素值小于等于b[i]，就得到一个终元素更小的长度为k的不减子序列。为能发现上述可能，就得保留长度为k-1的不减子序列的终元素。依此类推，为保留长为k-2,k-3等的不减子序列，相应地也要为它们保留终元素的值。为此要引入一个数组变量，设为数组a[]，其第j个元素a[j]存放长为j的不减子序列的终元素的值。显然，数组a[]中的元素也是不减的序列。利用这个性质，在考察b[i]时，就能知道a[]中哪个元素需要改变。从最长子序列至最短子序列顺序寻找终元素小于等于b[i]的长为j的子序列，因b[i]大于等于长为j的不减子序列的终元素，找到了一个终元素更小的长为j+1的不减子序列，用b[i]作长为j+1的子序列的终止元素。当j的值为k 时，已为长为k+1的子序列设定了终元素，这时最长不减子序列长k应增1。通过以上分析，得到求最长不减子序列长的算法如下：
算法---求数组b[]的最长不减子序列长
{
    置最长不减子序列长k为1；
    用b[0]设置长为1的子序列的终止元素；
    for(i=1;i<n;i++)        /*顺序至b[1]考察至b[n-1]*/
    {
        以子序列长为k至1的顺序寻找其终元素小于等于b[i]的长为j的子序列；
        用b[i]作为长为j+1的子序列的终元素；
        if(j==k)k++;        /*最长不减子序列长k增1*/
    }
}
程序代码如下：
#include<stdio.h>
#define N 100
int b[]={9,8,5,4,3,2,7,6,8,7,5,3,4,5,9,1};
int a[N];
#define n sizeof b/sizeof b[0]
void main()
{
    int k,i,j;
    a[1]=b[0];
    k=1;
    for(i=1;i<n;i++)
    {
        for(j=k;j>=1&&a[j]>b[i];j--);
        a[j+1]=b[i];        /*长为j+1的子序列的终元素存贮在a[j+1]*/
        if(j==k) k++;        /*最长不减子序列长k增1*/
    }
    printf("K = %d\n",k);
}

程序运行结果如下：
k = 5
------------------
    若把本问题改为求从数组中删去部分元素后的最长不减子序列，就要在求最长不减子序列长的过程中，不仅要保留各种长度不减子序列的终元素，同时要保留不减子序列的全部元素。为此，上述程序中的数组a[]应改为两维数组a[][]，其中a[][]的j行存储长为不减子序列的元素，该子序列的终元素为a[j][j-1]。在找到一个终元素更小的长为j+1的不减子序列时，除用b[i]作为j+1的子序旬的终止元素外，应同时将长为j的子序列元素全部复制到长为j+1的子序列中。直接写出程序如下：
#include<stdio.h>
#define N 100
int b[] = {9,8,5,4,3,2,7,6,8,7,5,3,4,5,9,1};
int a[N][N];
#define n sizeof b/sizeof b[0]
void main()
{
    int k,i,j,m;
    a[1][0]=b[0];
    k=1;
    for(i=1;i<n;i++)
    {
        for(j=k;j>=1&&a[j][j-1]>b[i];j--);
        for(m=0;m<j;m++)        /*长为j的子序列复制到长为j+1的子序列*/
            a[j+1][m]=a[j][m];
        a[j+1][j]=b[i];        /*长为j+1的终元素存贮在a[j+1][j]*/
        if(j==k) k++;        /*最长不减子序列长k增1*/
    }
    printf("K = %d\n",k);
    for(j=0;j<k;j++)
        printf("%4d",a[k][j]);
    printf("\n");
}
程序运行结果如下：
    k=5
    2  3  4  5  9