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