最长公共序列.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <stdio.h>
#include <stdlib.h>

//求最长公共子序列
//两种做法：递归、状态数组表

/*
测试数据如下
输入: 
7 5
1 3 4 4 7 8 9
3 4 4 8 10
输出: 
4
*/
int cal(int *a,int *b,int ca,int cb)
{
	int tempa,tempb;
	if(ca==-1||cb==-1) return 0;
	else if(a[ca]==b[cb]) return cal(a,b,ca-1,cb-1)+1;
	else 
	{
		tempa=cal(a,b,ca-1,cb);
		tempb=cal(a,b,ca,cb-1);
		if(tempa<tempb) return tempb;
		else return tempa;
	}
}

int main()
{
	int counta,countb,a[10],b[10],i;
	scanf("%d %d",&counta,&countb);
	for(i=0;i<counta;i++) scanf("%d",&a[i]);
	for(i=0;i<countb;i++) scanf("%d",&b[i]);
	printf("%d\n",cal(a,b,counta-1,countb-1));
	return 0;
}

===========================================

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <string.h>
using namespace std;

//求最长公共子序列 NOJ 1022
#define NMAX 1005
int f[NMAX][NMAX];//使用数组存放状态，以空间换时间
char s1[NMAX];
char s2[NMAX];

void cal(char *s1,char *s2,int len1,int len2)
{
    int i,j;
	memset(f,0,sizeof(f));
    for(i=1;i<=len1;i++)
    {
        for(j=1;j<=len2;j++)
        {	//该位置字符相同，上一状态加1即可得
            if(s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]+1;
            else
            {	//若字符不相同，则为上一状态的最大值
                if(f[i][j-1]<f[i-1][j]) f[i][j]=f[i-1][j];
                else f[i][j]=f[i][j-1];
            }
        }
    }
}


int main()
{
    int i,j;
    while(scanf("%s%s",&s1,&s2)!=EOF)
    {
        i=strlen(s1);
        j=strlen(s2);
        cal(s1,s2,i,j);
        printf("%d\n",f[i][j]);
    }
    return 0;
}