一道数据结构的题，求一个算法

只看该作者 · 2011-9-7 10:33

本帖最后由 alicedodo 于 2011-9-7 10:38 编辑

一道数据结构的题，求一个算法

有一种这样的数据对象：
1）每个对象含有两个可用无符号整型表示的属性，分别为u16Quick(敏捷)和u16Strong(力量)
2）敏捷和力量之间没有任何关系，互不影响

现在我们随机创建一些对象实体，每个实体的属性值也是随机赋值的，创建若干个之后，我们便得到了一
个对象集合。

题目的要求是：从这个集合中找出一个满足以下条件的最大有序子集：

1）子集表示为{O1,O2,O3, ······，On},如果有1<=i<j<=n,那么Oj的敏捷值不低于Oi的敏捷值且
Oj的力量值不低于Oi的力量值。
2）在所有能满足条件1）的子集中，我们要找到包含对象数量最多的那个子集，如果这样的子集有多个
，只找出一个即可。
3）找到目标子集后，我们要能按{O1,O2,O3, ······，On}的顺序将对象挨个输出。

例如对象集合包含A[1,7]、B[4,9]、C[3,3]、D[5,7]、E[3,5]共5个对象(敏捷值在前),那么符合要求的最

大有序子集就是{C[3,3]，E[3,5]，B[4,9]}和{C[3,3],E[3,5],D[5,7]} ,我们只找出其中一个来就可以了。

这个问题想了很久了，一直没思路，求一个能解决上述问题的算法。

只看该作者 · 2011-9-7 10:35

吐槽一下，二姨家的发帖编辑器太难用了，拉一下鼠标就花屏。

只看该作者 · 2011-9-7 11:55

我认为这个题目比电子竞赛更能考验人的思维能力，顶一个。

只看该作者 · 2011-9-7 12:47

本帖最后由 liang7143 于 2011-9-7 12:52 编辑

按要求，排序应该是不可避免的
1、对象集合进行递增排序
   以敏捷值进行排序，如果敏捷值相同，则力量值值小的排前面。
2、敏捷值排序完成以后，对力量值组成的序列  寻找最长连续单调递增子序列
   这样的算法网上应该有很多

只看该作者 · 2011-9-7 13:10

本帖最后由 alicedodo 于 2011-9-7 13:14 编辑

4# liang7143
你说的第1步很容易想到，我也是这么做的。

最难的就是第2步，在一个按敏捷属性升序排序的序列里找出同时满足力量值升序排列的最长序列。

其实这个题目完全可以简化为这样的说法：

给一个杂乱排列的数列，如 2,4,1,7,8,5,4,6,2,9,10 。
在不改动各个数值相对位置的前提下找出最长的升序数列。

一开始的时候我想用递归从后往前找，也就是先找到后面n个序列中符合条件的最长序列，然后再把前面的一个数值放进来，看看能不能使这个序列变得更长，不过我总能找出不符合这个思路的反例来，所以一直没找到好的方法。

只看该作者 · 2011-9-7 13:29

给一个杂乱排列的数列，如 2,4,1,7,8,5,4,6,2,9,10 。
在不改动各个数值相对位置的前提下找出最长的升序数列。

这就是寻找最长连续单调递增子序列
有现成的算法可以上网搜索
比如
http://hi.baidu.com/silverxinger ... 6d1c02632798ad.html

只看该作者 · 2011-9-7 13:50

有点小复杂

1万 · 2011-9-7 15:11

动态规划俺还是不行,要向6楼学习

只看该作者 · 2011-9-7 18:06

本帖最后由 alicedodo 于 2011-9-7 18:19 编辑

6# liang7143
感谢6楼给出的链接！！困扰我N久得问题终于解决了。参考链接中的方法，我根据我的理解把我这个问题

的解决思路说一说。

大体分两步：

1、以u16Quick为基准对序列进行升序排序，得到新的序列A 。
2、以u16Strong为基准，在新序列A中查找最长升序子序列。

步骤1很好理解，也很好实现。现在我们主要来讨论步骤2，即如何在序列A中查找最长升序子序列。
步骤2是一个动态规划的具体应用。

假设上文序列A中各个元素的u16Strong项依次为

2  4  1  7  8  5  4  6  2  9  10

（1）先看第1个元素，组成的序列为{2}，最长升序子序列为{2}，长度为1 。
（2）再看前2个元素，组成的序列为{2，4}，如果我要求某升序子序列中必须包含最后一个元素，那么符

合条件的最长升序子序列为{2,4}，长度为2=1+1，这个子序列是从（1）的基础上得来的。
（3）再看前3个元素，组成的序列为{2，4，1}，要求同（2），最长升序子序列为{1}，长度为1=0+1 。
（4）再看前4个元素，组成的序列为{2，4，1，7}，要求同（2），最长升序子序列为{2,4,7}，长度为

3=2+1，这个子序列是从（2）的基础上得来的。

依此类推

如果在前i个元素中，以A[i-1](序列下标从0开始)为末尾元素的最长升序子序列长度为u8Len[i-1]，
那么序列A元素下标i和u8Len[i-1]就构成了一组映射。
同理，在前i+1个元素中，以 A 为末尾元素的最长升序子序列长度为u8Len，u8Len的值可能有两种：
（1） A[0]~A[i-1]中所有的u16Strong项均大于A的u16Strong项，则u8Len的值为1 。
（2） A[0]~A[i-1]中存在某些元素，这些元素的u16Strong项均不大于A的u16Strong项，若这些元素对应的u8Len[]集合中最大值为u8Len[k]，则u8Len=u8Len[k]+1 。
递推式如下：

         u8Len=max(1,max(u8Len(k))+1), (A[k].u16Strong<=A.u16Strong && k<=i)

这样，当我们把A中所有元素遍历完毕之后，我们会得到一个序列u8Len，里面的最大值max(u8Len)就是序列A最长升序子序列的长度。
查找结果如下：

0  1  2  3  4  5  6  7  8  9  10          (i)
-----------------------------------------------------------
2  4  1  7  8  5  4  6  2  9  10          (A.u16Strong )
------------------------------------------------------
1  2  1  3  4  3  3  4  2  5  6             (A.u8Len)
----------------------------------------------------------
X  0  X  1  3  1  1  5  0  4  9             ( A.u8PreIdx )

maxlen = 6
倒序输出： A[10]-->A[9]-->A[4]-->A[3]-->A[1]-->A[0]
               10       9       8       7       4       2
所以最长升序子序列
         2 4 7 8 9 10

下面是这个算法的C代码。

复制
typedef struct _obj { INT16U u16Quick; /*敏捷*/ INT16U u16Strong; /*力量*/ INT8U  u8Len;    /*参考含义前文*/ INT8U  u8PreIdx; /*在含有本元素的最长序列中，u8PreIdx记录最长序列前面元素的下标*/ } OBJ ; void max_child_que(OBJ* pA, INT8U u8N) { INT8U u8I = 0; INT8U u8K = 0; INT8U u8MaxLen = 0; inc_sort(pA,n);          /*以u16Quick为基准对序列进行升序排序*/ pA[0].u8Len = 1; PA[0].u8PreIdx = 255;    /*255为非法值*/ for(u8I=1; u8I<u8N ; u8I++)  /*遍历序列，填充各个元素的u8Len和u8PreIdx*/ { pA[u8I].u8Len = 0; for(u8K=0; u8K<u8I; u8K++) { if(pA[u8K].u16Strong <= pA[u8I].u16Strong) { if(pA[u8K].u8Len+1 > pA[u8I].u8Len) { pA[u8I].u8Len = pA[u8K].u8Len+1; pA[u8I].u8PreIdx = u8K; } } } if(pA[u8I].u8Len == 0)    /*很不幸，本元素很孤单*/ { pA[u8I].u8Len = 1;       /*最长序列长度为1*/ PA[u8I].u8PreIdx = 255;    /*赋非法值*/ } } for(u8I=1,u8MaxLen=pA[0].u8Len,u8K=0; u8I<u8N; u8I++)/*查找最大u8Len*/ { if(u8MaxLen < pA[u8I].u8Len) { u8MaxLen = pA[u8I].u8Len; u8K = u8I; } } printf("Max Len = %d\n", u8MaxLen);       /*最长升序子序列长度输出*/ for(; u8K != 255; u8K = pA[u8K].u8PreIdx)  /*最长升序子序列倒序输出*/ { printf("  %d  ", pA[u8K].u16Strong); } }

最后，再次感谢6楼！

一道数据结构的题，求一个算法

相关下载

相关帖子

社区建设奖章

技术奇才奖章

欢快之小溪

七世轮回

无冕之王奖章

沉静之湖泊

缘定三生

技术领袖奖章

技术高手奖章

经常做客

涓涓之细流

荣誉元老奖章

坚毅之洋流

十世金身