| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3031 人关注过本帖
标题:最长不下降子序列,要求输出的是最长的那个序列数 和长度
只看楼主 加入收藏
多多少少忖测
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2015-7-12
结帖率:0
收藏
已结贴  问题点数:20 回复次数:17 
最长不下降子序列,要求输出的是最长的那个序列数 和长度
长度我会 但是序列数怎么弄弄不出来啊 求助啊
2015-07-12 22:05
多多少少忖测
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2015-7-12
收藏
得分:0 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int longest_increasing(int num[],int n)
{
     int lis[100000],j,maxn=0,i,b[10000],w=0;
     for(i=0;i<n;i++)
     {
         if(num[i]==0)continue;
         lis[i]=1;
         for(j=0;j<i;j++)
             if(num[i]>num[j]&&lis[j]+1>lis[i])
               {lis[i]=lis[j]+1;  
               
     
     }}
         for(i=0;i<n;i++)
        if(maxn<lis[i])
        {  maxn=lis[i];
        
        }
    return maxn;
}

int main()
{    printf("此程序用来计算最长不下降序列\n什么是最长不下降序列?\n设由n个不相同的整数组成的数列,a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j)");
     printf("\n例如3,18,7,14,10,12,23,41,16,24。\n若存在i1<i2<i3< … < ie 且有a(i1)<a(i2)< … <a(ie)则称为长度为e的不下降序列。");
     printf("如上例中3,18,23,24就是一个长度为4的不下降序列,同时也有3,7,10,12,16,24长度为6的不下降序列。");
     int num[100000],n,i,max,j,m,p;
     printf("\n请输入数列数n,然后按回车键,将会为您自动生成n个数:");
     scanf("%d",&n);//输入数据数量
     srand((unsigned) time(NULL)); //用时间做种,每次产生随机数不一样
 //用时间做种,每次产生随机数不一样
     printf("产生的随机数为:");
     for (j=0; j<n;j++)
  {
     p=rand();
     for(m=0;m<j;m++)
   if( p==num[m]) //检查是否重复
break;
if(m>=j)
num[j]=p;
else
{
j--;
continue;
}
}

for (j=0; j<n;j++)

 printf("%d ", num[j]);
     system("pause");
   
     printf("最长不下降序列长为 : %d  \n",max);//打印最大值
   
     return 0;
 }


这个是我做的程序,  就差不知道怎么能输出最长的那个序列的 这些序列数呢
2015-07-12 22:06
多多少少忖测
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2015-7-12
收藏
得分:0 
真是想破脑筋也没有想出来,各种方法试过都是失败了,哎,求大神帮忙用c语言看看啊
2015-07-12 22:08
多多少少忖测
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2015-7-12
收藏
得分:0 
2015-07-12 22:16
多多少少忖测
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2015-7-12
收藏
得分:0 
2015-07-13 10:06
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:5 
最长不下降序我觉得对全序列做个排序就可以了,剔除相邻的相等数即可。

能编个毛线衣吗?
2015-07-13 11:46
lianyicq
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:26
帖 子:737
专家分:3488
注 册:2013-1-26
收藏
得分:5 
回复 楼主 多多少少忖测
程序代码:
#include <stdio.h>
#include <conio.h>
#include <process.h>
int a[]={0,3,18,7,14,10,12,23,41,16,24};

int len,output[10]={0};

void find(int x,int y)
  { int i,j;
    if (x>10)
    {return;}

    for(i=x+1;i<=10;i++)
    { if (a[i]>a[x])
      { output[y]=a[i];
     find(i,y+1);}
    else if (i==10) y=y-1;    

         if (i==10)
       {
         for(j=0;j<=y;j++)
             printf ("%d ",output[j]);
         printf("  ");
    
     }
      }
  }

void main()
  {  
    system("cls");
    find(0,0);
    getch();
  }


[ 本帖最后由 lianyicq 于 2015-7-14 09:30 编辑 ]

大开眼界
2015-07-13 12:16
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 6楼 wmf2014
突然觉得没仔细研究题意,这个问题还是有些深度的,需要仔细考虑下。


能编个毛线衣吗?
2015-07-13 12:54
jklqwe111
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:35
帖 子:336
专家分:1135
注 册:2014-4-13
收藏
得分:5 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int lisid[10000];//存储最长序列下标
int longest_increasing(int num[],int n,int id*)//用指针id传入lisid[]
{
     //int lis[100000],j,maxn=0,i,b[10000],w=0;//maxn=0改为maxn=1
     int lis[100000],j,maxn=1,i,b[10000],w=0;
     for(i=0;i<n;i++)
     {
        // if(num[i]==0)continue;此句何意?
         lis[i]=1;
        b[i]=i;//用b数组记录链长为lis[i]的序列的前一个元素的下标,此处初始化为自身的位置
         for(j=0;j<i;j++)
             if(num[i]>num[j]&&lis[j]+1>lis[i])
               {lis[i]=lis[j]+1;  
                b[i]=j;//记录下标
           }
            if(maxn<lis[i]) maxn=lis[i];
            w=i;//记录最长链末端下标
          }
         //for(i=0;i<n;i++)没有必要再次循环
        //if(maxn<lis[i])
        //{  maxn=lis[i];
        
       // }
//以下获得最长序列下标,顺序是逆序,可根据需要修改顺序
       id[0]=w;
      i=0;
      while(b[w]!=w)
       {
         i++;
         id[i]=b[w];
         w=b[w];
       }

   
    return maxn;
}


以上修改没有测试,提供一种思路,供参考。
2015-07-13 16:05
lianyicq
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:26
帖 子:737
专家分:3488
注 册:2013-1-26
收藏
得分:0 
原七楼代码改成了VC++下测试通过
显示最长字串及其长度。只显示了第一个最长字串,若要全部显示,自己想办法解决。
程序代码:
#include <stdio.h>
#include <conio.h>
#include <process.h>
int a[]={0,3,18,7,14,10,12,23,41,16,24};

int len,output[10]={0},outcome[10];
int max;
void find(int x,int y)
  { int i,j;
    if (x>10)
    {return;}

    for(i=x+1;i<=10;i++)
    { if (a[i]>a[x])
      { output[y]=a[i];
     find(i,y+1);}
    else if (i==10) y=y-1;    

         if (i==10)
       { if (max<y)
         {  max=y;
            for(j=0;j<=y;j++) outcome[j]=output[j];


         }
         for(j=0;j<=y;j++)
             printf ("%d ",output[j]);
         printf("  ");
    
     }
      }
  }

void main()
  {  
    int i;
    system("cls");
    max=0;
    find(0,0);
    printf("\n\n");
    printf("最长字串的长度是%d。\n",max+1);
    for(i=0;i<=max;i++)
        printf("%d ",outcome[i]);
    getch();
  }



[ 本帖最后由 lianyicq 于 2015-7-14 10:01 编辑 ]

大开眼界
2015-07-14 09:30
快速回复:最长不下降子序列,要求输出的是最长的那个序列数 和长度
数据加载中...
 
   



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

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