C++程序設(shè)計例解(04)

2019-11-17 05:42:44

字體：大中小

供稿：網(wǎng)友

04. 試從含有n個int型數(shù)的數(shù)組中刪去若干個成分，使剩下的全部成分構(gòu)成一個不減的子序列。設(shè)計算法和編寫程序求出數(shù)組的不減子序列的長。
解：
從數(shù)組的第一個元素開始，順序考察數(shù)組的每個元素，當(dāng)數(shù)組的全部元素都被考察后才能求出數(shù)組的最長不減子序列的長。設(shè)數(shù)組為b[]，已考察了b[0]至b[i-1]的全部元素，求得當(dāng)前最長的不減子序列長為k。當(dāng)前正要考察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的不減子序列的終元素值。
但當(dāng)b[i]小于那個長度為k的不減子序列最小的終元素的值時，假如在b[0]至b[i-1]中有長度為k-1的不減子序列，且該子序列的值不大于b[i]，這時因長度為k-1的不減子序列的終元素值小于等于b[i]，就得到一個終元素更小的長度為k的不減子序列。為能發(fā)現(xiàn)上述可能，就得保留長度為k-1的不減子序列的終元素。依此類推，為保留長為k-2,k-3等的不減子序列，相應(yīng)地也要為它們保留終元素的值。為此要引入一個數(shù)組變量，設(shè)為數(shù)組a[]，其第j個元素a[j]存放長為j的不減子序列的終元素的值。顯然，數(shù)組a[]中的元素也是不減的序列。利用這個性質(zhì)，在考察b[i]時，就能知道a[]中哪個元素需要改變。從最長子序列至最短子序列順序?qū)ふ医K元素小于等于b[i]的長為j的子序列，因b[i]大于等于長為j的不減子序列的終元素，找到了一個終元素更小的長為j+1的不減子序列，用b[i]作長為j+1的子序列的終止元素。當(dāng)j的值為k 時，已為長為k+1的子序列設(shè)定了終元素，這時最長不減子序列長k應(yīng)增1。通過以上分析，得到求最長不減子序列長的算法如下：
算法---求數(shù)組b[]的最長不減子序列長
{
置最長不減子序列長k為1；
用b[0]設(shè)置長為1的子序列的終止元素；
for(i=1;i<n;i++) /*順序至b[1]考察至b[n-1]*/
{
以子序列長為k至1的順序?qū)ふ移浣K元素小于等于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*/
}
}

程序運行結(jié)果如下：
k = 5
------------------
若把本問題改為求從數(shù)組中刪去部分元素后的最長不減子序列，就要在求最長不減子序列長的過程中，不僅要保留各種長度不減子序列的終元素，同時要保留不減子序列的全部元素。為此，上述程序中的數(shù)組a[]應(yīng)改為兩維數(shù)組a[][]，其中a[][]的j行存儲長為不減子序列的元素，該子序列的終元素為a[j][j-1]。在找到一個終元素更小的長為j+1的不減子序列時，除用b[i]作為j+1的子序旬的終止元素外，應(yīng)同時將長為j的子序列元素全部復(fù)制到長為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的子序列復(fù)制到長為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");
}
程序運行結(jié)果如下：
k=5
2 3 4 5 9