C程序設計例解(05)

2019-11-17 05:40:46

字體：大中小

來源：轉載

供稿：網友

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*/
    }
    }

程序運行結果如下：
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