分享
 
 
 

C程序设计例解(05)

王朝c/c++·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有