138
poj 1580 String Matching【gcd辗转相除法】
开始想用类似“错车”的思路去解决，但是发现不是太好着手，还是选用首字母定位的方法去解决的
题意：现定义两个仅由大写字母组成的字符串的匹配程度如下：将某一字符串的首字符与另一字符串的某一字符对齐，然后后面的字符也一一对齐，直至某一字符串的串尾为止。对于每一组对齐的两个字符，若这两个字符相等，则计数。最后计算这个计数的2倍，与两串总长度的最大比值。
如果说这题最大的收获就是，两种方法的辗转相除法求gcd
AC的代码：
#include <stdio.h>
#include <string.h>
/*//辗转相除法的递归写法
int gcd(int a,int b)
{
if(!b) return a;
return gcd(b,a%b);
}
*/
int gcd(int a, int b)
{//辗转相除法
while (b%a)
{
int t=a;
a=b%a;
b=t;
}
return a;
}
void appx(char * wo1,char * wo2)
{
if(!strcmp(wo1,wo2))
{
printf("appx(%s,%s) = 1\n",wo1,wo2);
return;
}
//值已经传进来了
int len1=strlen(wo1),len2=strlen(wo2);
int count=0;
int i,j,max,common=0;
//枚举word1和word2的首字母
for(i=0;i<len1;i++)
{
for(j=0;j<len2;j++)
{
max=0;
for (int i1=i,j1=j;i1<len1 && j1<len2;++i1,++j1)
if (wo1[i1]==wo2[j1])
++max;
if (common<max)
common=max;
}
}
if(common==0)
{
printf("appx(%s,%s) = 0\n",wo1,wo2);
return;
}
int molecular=common*2;//分子
int denominator=len1+len2;//分母
int g=gcd(molecular,denominator);
printf("appx(%s,%s) = %d/%d\n",wo1,wo2,molecular/g,denominator/g);
}
int main()
{
char word1[105],word2[105];
while(scanf("%s",word1))
{
if(!strcmp(word1,"-1"))
return 0;
scanf("%s",word2);
appx(word1,word2);
}
return 0;
}
最后更新：2017-04-03 12:56:21