| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2622 人关注过本帖
标题:求出最长子序列长度后怎样显示最长子序列元素值
只看楼主 加入收藏
canhui87
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2008-10-2
收藏
 问题点数:0 回复次数:10 
求出最长子序列长度后怎样显示最长子序列元素值
对以下2个求最长子序列的程序
在最长子序列长度时,怎样显示最长子序列的元素值
或这用一个数组来存储最长子序列中结尾元素最小的一组

一个为 O(n^2)的

#include <stdio.h>

int a[10]={1,4,7,20,2,11,5,13,6,10};
int b[10]={0};          //b[i]存以a[i]为结尾元素的最长子序列长度
int c[10]={0};          //c[n]存a[n]最长子序列元素
int LISdyna()
{
    int maxL(int n);
    int i,j,k,n=10;

    for(i=1,b[0]=1;i <n;i++)
    {
        for(j=0,k=0;j <i;j++)
            if(a[j] <=a[i]&&k <b[j]) k=b[j];
        b[i]=k+1;
    }
    return maxL(n);
}

int maxL(int n)            //max(b[i])为a[n]最长子序列长度
{
    int i,temp;
    for(i=0,temp=0;i <n;i++)
        if(b[i]>temp) temp=b[i];
    return temp;
}

int main()
{
    int i,j,k=LISdyna();
    printf("%d\n",k);      //k为a[n]最长子序列长度
   
    return 0;
}
搜索更多相关主题的帖子: 序列 长子 元素 长度 
2008-11-21 11:46
canhui87
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2008-10-2
收藏
得分:0 
一个为 O(nlbn)的
#include <stdio.h>

int a[10]={1,4,22,20,11,2,5,13,6,4};
int b[10]={0};

int LIS()
{
    int binary(int i,int k);
    int i,j,k,n=10;
    b[1]=a[0];
    for(i=1,k=1;i <n;i++)
    {
        if(a[i]>=b[k]) b[++k]=a[i];
        else b[binary(i,k)]=a[i];
    }
    return k;
}

int binary(int i,int k)
{
    int h,j;
    if(a[i] <b[1])return 1;
    for(h=1,j=k;h!=j-1;)
    {
        if(b[k=(h+j)/2] <=a[i]) h=k;
        else j=k;
    }
    return j;
}

int main()
{
    printf("%d\n",LIS());

    return 0;
}
2008-11-21 11:46
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
加一个记录转移方式的数组

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2008-11-21 12:23
canhui87
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2008-10-2
收藏
得分:0 
记录转移方式?
小弟不懂
希望能讲具体点
当作多学一个知识
2008-11-22 01:07
风居住的街道
Rank: 1
等 级:新手上路
帖 子:374
专家分:0
注 册:2008-10-24
收藏
得分:0 
刚刚研究了一下。我有个问题……

就是改良版本的LIS,我的资料说它求出来的D并不是题目要求的子序列。但是我产生的例子里面,它恰恰是一个满足要求的子序列啊……这是巧合,还是说D的结果可以当作一个满足要求的子序列?

如果是巧合,那在改良版本的LIS中,如何求得满足要求的子序列?

程序代码:
/*

 * LIS - Longest Increasing Subsequence

 */

#include <stdlib.h>

/*

 * O(n^2) 方法

 * a内存输入的数字

 * 返回最长上升子序列的长度

 * b用来返回最长递增子序列的值。

 */
int lis_dp(const int *a, int *b, size_t len)
{
    int i, j, dmax, bmax;
    int *d = (int*)malloc(len * sizeof(int));

    /*
     * 从0开始分析,则对于a[0]来说,最长的上升子序列长度就是
     * 1,即a[0]本身。那么对于a[0]和 a[1]来说,则分析如下:
     *  - 如果a[0] <= a[1] 则最长子序列长度为 a[0]的长度+1
     *  - 如果a[0] > a[1] 则最长子序列的长度为 a[0]和a[1]中
     *    比较长的那个。
     *
     * 我们用d[n] (0<n<=len)来保存a[n]的最长子序列的值。那么
     * 很轻易就可以得到d[n]的状态转移式:
     *  - d[0] = 1
     *  - d[n] = max{1, d[i]+1}, 其中i=n+1,n+2,...,len-1
     *
     *  不过,下面的代码采取了逆推的方式,因为这样可以马上得
     *  到最长递增序列的第一个值,从而很轻松就可以顺推得到整
     *  个序列,而如果顺推的话,那得到整个序列就需要开另外一
     *  个数组来逆推。这样很麻烦。
     */

    bmax = b[len-1] = len - 1;
    dmax = d[len-1] = 1;

    for (i = len - 2; i >= 0; i--)
    {
        b[i] = i;
        d[i] = 0;

        for (j = i; j < len; j++)
        {
            if (a[i] < a[j] && d[i] < d[j] + 1)
            {
                b[i] = j;
                d[i] = d[j] + 1;
            }
        }

        if (d[i] > dmax)
        {
            bmax = i;
            dmax = d[i];
        }
    }

    free(d);

    for (i = 0; bmax != b[bmax]; i++)
    {
        j = bmax;
        bmax = b[bmax];
        b[i] = a[j];
    }

    b[i] = a[bmax];

    return dmax;
}

/*

 * O(nlgn)方法

 * 参数同上

 */
int lis_improve(const int *a, int *b, size_t len)
{
    int i, blast;

    /*
     * 首先我们考虑经典的计算LIS的方法。
     * 对于每个a[i],我们可以求出一个相应的f[i](即上面的
     * d[i]),这个f[i]取决于i之前的每个f[n](0<=n<i)的最大值
     * 。那么我们考虑一下这种情况,如果在i之前有x和y,满足:
     *  - x < y < i; a[x] < a[y] < a[i]; f[x] = f[y]且最大
     * 那么,因为f[x] = f[y],我们应该选择x还是y作为f[i]的选
     * 取值呢?显然选择x比y要好。因为a[x]要大于a[y],这样选
     * 择了x,使得x和i的距离最大化了,如果这段距离中,有
     * a[z] 满足a[x] < a[z] < a[y],那么与选择a[y]相比,将会
     * 得到更长的上升子序列(当然这种情况下,a[z]本身的 f[z]
     * 会大于a[x]和a[y],但是这是在单独扫描的情况下,下面我
     * 们会看到另一种完全不需要求F[i]的方法)。
     *
     * 那么,我们其实可以对于每个f[i]进行分类。我们只需要保
     * 留满足f[i]=k的所有A[i]总的最小的那个值就够了。假设
     * D[j]记录这个最小值,则D[j]=min{A[i]}(F[i]=k)。
     *
     * 因为f[i]是一直上升的。所以其D[j]也应该是一直上升的。
     * 从而D是一个有序的序列。利用这个序列,我们可以得到另外
     * 一种计算最长递增子序列的方法。同样设当前要判断的节点
     * 为A[i],假设这时D序列的长度为len。则直接判断A[i]和
     * D[len-1]。如果A[i]比较大,证明A[i]至少比我们之前找到
     * 的所有有可能出现在最长递增子序列里面的值要大。显然这
     * 时候最长子序列的长度应该被扩展一个。因此将A[i]加在D的
     * 后面,同时len加一。然而。如果A[i]比D[len-1]要小。则很
     * 显然,这个A[i]无法为扩展子序列提供任何“帮助”。但它本
     * 身仍然可能成为新的最长子序列中的一员。怎么办呢?我们
     * 在D中寻找这样一个位置x,使得D[x] < A[i] <= D[x+1],显
     * 然,因为A小于D[x+1],根据上面的分析,相对于D[x+1],使
     * 用A[i]能帮助我们得到更长的递增子序列。所以我们用A[i]
     * 来代替D[x+1]的位置。
     *
     * 一直重复这个过程,直到到最后的A[len-1],这样,len就是
     * 我们的最长递增子序列的长度了。
     *
     * 对于这个方法。如果查找的时候使用顺序查找。显然复杂度
     * 仍然为O(n^2)不变。但是考虑到D为单调上升序列。那么只需
     * 要在D上使用二分查找。则复杂度会提高到O(nlgn),这是一
     * 个相当大的提高。但前提是二分查找的设计合理高效。
     *
     * 下面的实现中。使用的是b的最后一个元素的位置blast,而
     * 不是b序列的长度,只是效率上的考虑,本身没什么关系的。
     */

    b[0] = a[0];
    blast = 0;

    for (i = 1; i < len; i++)
    {
        if (a[i] < b[blast])
        {
            size_t begin = 0, end = blast;

            while (begin < end)
            {
                size_t middle = (begin + end) >> 1;

                if (b[middle] < a[i])
                    begin = middle + 1;
                else
                    end = middle - 1;
            }

            b[end + (b[end] < a[i])] = a[i];
        }
        else
            b[++blast] = a[i];
    }

    return blast + 1;
}

#include <stdio.h>

int main(void)
{
    int i, res;
    int a[] = {1, 4, 7, 20, 2, 11, 5, 13, 6, 10}, b[10];

    printf("lis_dp: %d\n", res = lis_dp(a, b, 10));
    for (i = 0; i < res; i++)
        printf("%d ", b[i]);

    printf("\nlis_improve: %d\n", res = lis_improve(a, b, 10));
    for (i = 0; i < res; i++)
        printf("%d ", b[i]);
    printf("\n");
    return 0;
}

2008-11-22 03:38
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
风居住的街道 在 2008-11-22 03:38 的发言:

刚刚研究了一下。我有个问题……

就是改良版本的LIS,我的资料说它求出来的D并不是题目要求的子序列。但是我产生的例子里面,它恰恰是一个满足要求的子序列啊……这是巧合,还是说D的结果可以当作一个满足要求的子 ...



如果你对dp实质理解的深刻些,其实我在上面说的记录转移就是答案。
你把转移方式记录了就可以了.

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2008-11-23 15:45
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
我明白了……

其实对于第一个DP的,我已经计算出结果了。就是第二个优化版本的原理我不太清楚……感觉那已经不像是DP了……

专心编程………
飞燕算法初级群:3996098
我的Blog
2008-11-23 15:50
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
麻烦孔明给一个改良版的LIS的D不是题目要求的需要的反例可以么?有点儿糊涂,想找个反例分析一下~~

专心编程………
飞燕算法初级群:3996098
我的Blog
2008-11-23 15:52
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
收藏
得分:0 
StarWing83 在 2008-11-23 15:50 的发言:

我明白了……

其实对于第一个DP的,我已经计算出结果了。就是第二个优化版本的原理我不太清楚……感觉那已经不像是DP了……


第二个其实就是把已经处理过的数据有序化了,类似一个优先队列。
其实利用二分思想优化dp复杂度的方法有许多的(经典题目是stars(天上的星星),fyoj那里还有一个香蕉和猴子)。

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2008-11-23 15:53
中学者
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:3554
专家分:80
注 册:2007-9-14
收藏
得分:0 
归纳假设法便可设计出O(nlgn)的算法..

樱花大战,  有爱.
2008-11-23 17:36
快速回复:求出最长子序列长度后怎样显示最长子序列元素值
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016275 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved