序列小游戏 - 编程论坛

#2

HJin2007-06-26 08:52

Are these two problems or just one?

[QUOTE]任意给定5个数字，其中必定存在3个数字已经有序（或者升序，或者降序），找出这5个数字中最长的升序或降序序列。
例如：1，7，5，3，9。则{1，7，9}，{1，5，9}，{1，3，9}都是最长的升序序列；
而{7，5，3}是最长的降序序列。
再如：1，3，2，5，7。最长的升序序列为{1，3，5，7}和{1，2，5，7}。[/QUOTE]
This can be done by first copy your sequence a to another sequence b,
sort b, and then find the larget common subsequence of a and b.

You should be able to write your own algorithm for LCS.

[QUOTE]
自动生成各种可能的序列，对于5个数字所有可能的序列为：
{0,1,2,3}、{0,1,2,4}、{0,1,3,4}、{0,2,3,4}、{1,2,3,4}
{0,1,2}、{0,1,3}、{0,2,3}、{1,2,3}
{0,1,4}、{0,2,4}、{1,2,4}
{1,3,4}
{2,3,4}、{0,3,4}
考察各种可能的序列是否升序或是降序，若是则打印；[/QUOTE]
This can be done by using some recursive algorithm to permute the numbers. You may first want to try to generate all the n! permutations for 1..n.

#3

住爱里2007-06-26 09:15

呵呵。。。一个问题啦

“任意给定5个数字，其中必定存在3个数字已经有序（或者升序，或者降序），找出这5个数字中最长的升序或降序序列。”

#4

林风2007-06-26 11:47

发点实际的，比如答案什么的啊？！！

#5

aipb20072007-06-26 12:08

[CODE]#include <iostream>
using namespace std;
int main(){
int a[] = {1,2,3,4,5};
for (int i = 0;i < 5;++i)
for (int j = i+1;j < 5;++j)
for (int k = j+1;k < 5;++k){
cout << a[i] << a[j] << a[k] << "\t";
for (int l = k+1;l < 5;++l)
cout << a[i] << a[j] << a[k] << a[l] << "\t";
}
system("pause");
}[/CODE]

实际的来了，可以输出5个数排列的15种可能，当然还有一种是本身。
吃饭去啦！

#6

aipb20072007-06-26 14:47

[CODE]#include <iostream>
using namespace std;
bool is_ordered(int a,int b,int c,int d = 0){
if (d)
return (a>b && b>c && c>d) || (a<b && b<c && c<d);
else
return (a>b && b>c) || (a<b && b<c);
}

int main(){
int a[] = {1,3,2,5,7};

for (int i = 0;i < 5;++i)
for (int j = i+1;j < 5;++j)
for (int k = j+1;k < 5;++k){
if (is_ordered(a[i],a[j],a[k]))
cout << a[i] << a[j] << a[k] << "\n";
for (int l = k+1;l < 5;++l)
if (is_ordered(a[i],a[j],a[k],a[l]))
cout << a[i] << a[j] << a[k] << a[l] << "\n";
}
system("pause");
}[/CODE]

复习真累，写点代码，好了，再去复习啦！

#7

住爱里2007-06-27 08:31

谢谢呀！偶自己弄一下！

#8

jcao2007-06-27 15:18

回复：（住爱里）序列小游戏

到期末考试了，现在全是求助的了。还有没有别的编程方法,比如用结构体类型处理。

#9

野比2007-06-27 20:57

aipb2007...我还是觉得你太包办了... 这样人家失去了自己思考的机会.. 只能限于"理解程序"...

#10

aipb20072007-06-27 22:36

哦，我错了，我是那哈没事干，就写了。
还有我有的代码一般也会贴。

以后注意！

嘿嘿~~~~~~~~

#11

住爱里2007-07-12 23:06

#include <iostream>
using namespace std;
int is_ordered5(int a, int b,int c,int d,int f);
int is_ordered4(int a, int b,int c,int d);
int is_ordered3(int a, int b,int c);
void main()
{
int a[5] ;
int flag1=1,flag2=1;
cout<<"请输入五个不相等的整数：";
for(int m=0;m<5;m++)
cin>>a[m];
int *p;
p=&a[0];
cout<<endl<<"输入的数字中最长升序和降序序列为:"<<endl;
if(is_ordered5(p[0],p[1],p[2],p[3],p[4]))

{
for(int i=0;i<5;i++)
cout<<p[i]<<"\t";

flag1=0;
}
if(flag1==1)
{
for (int i = 0;i < 5;++i)
for (int j = i+1;j < 5;++j)
for (int k = j+1;k < 5;++k)
for(int l=k+1;l<5;l++)
{
if (is_ordered4(a[i],a[j],a[k],a[l]))
{
cout << a[i] <<"\t"<< a[j] <<"\t"<<a[k] <<"\t"<< a[l]<<"\n";
flag2=0;
}
}
if(flag2==1)

{
for (int p = 0;p < 5;++p)
for (int q = p+1;q < 5;++q)
for (int h = q+1;h < 5;++h)
if(is_ordered3(a[p],a[q],a[h]))
cout<<a[p]<<"\t"<<a[q]<<"\t"<<a[h]<<"\n";
}
}
}

int is_ordered5(int a, int b,int c,int d,int f)
{
return(a>b && b>c && c>d && d>f||a<b && b<c && c<d && d<f);
}
int is_ordered4(int a, int b,int c,int d)
{
return(a>b && b>c && c>d ||a<b && b<c && c<d );
}
int is_ordered3(int a, int b,int c)
{
return(a>b && b>c ||a<b && b<c);
}

#12

leeco2007-07-12 23:53

以下是引用HJin在2007-6-26 8:52:16的发言：
Are these two problems or just one?

任意给定5个数字，其中必定存在3个数字已经有序（或者升序，或者降序），找出这5个数字中最长的升序或降序序列。
例如：1，7，5，3，9。则{1，7，9}，{1，5，9}，{1，3，9}都是最长的升序序列；
而{7，5，3}是最长的降序序列。
再如：1，3，2，5，7。最长的升序序列为{1，3，5，7}和{1，2，5，7}。

This can be done by first copy your sequence a to another sequence b,
sort b, and then find the larget common subsequence of a and b.

You should be able to write your own algorithm for LCS.

自动生成各种可能的序列，对于5个数字所有可能的序列为：
{0,1,2,3}、{0,1,2,4}、{0,1,3,4}、{0,2,3,4}、{1,2,3,4}
{0,1,2}、{0,1,3}、{0,2,3}、{1,2,3}
{0,1,4}、{0,2,4}、{1,2,4}
{1,3,4}
{2,3,4}、{0,3,4}
考察各种可能的序列是否升序或是降序，若是则打印；

This can be done by using some recursive algorithm to permute the numbers. You may first want to try to generate all the n! permutations for 1..n.

他已经说的很好了，就是这样，原来最长递增子序列问题可以规约到最长公共子序列问题，我以前到没想过，一直是直接用动态规划求解的。

#13

HJin2007-07-13 02:58

回复：（leeco）以下是引用HJin在2007-6-26 8:52:16的...

double post --- due to the problem of the forum. deleted.

[此贴子已经被作者于2007-7-13 3:02:31编辑过]

#14

HJin2007-07-13 03:00

回复：（leeco）以下是引用HJin在2007-6-26 8:52:16的...

The LCS (longest common subsequence) algorithm is often an O(n^2) algorithm, as implemented by a dynamic programming technique.

The LMIS (or LIS, or LMS, short for Longest Monotonically Increasing Subsequence) algoritm based on LCS is O(n^2) since LCS itself is. If you use dynamic programming to write the LMIS algorithm, you can achieve O(n lgn) time complexity, by using some binary search technique in the process. That means your hard work is rewarded.