#include<stdio.h>
#include<string.h>
#include<string.h>
char str1[],str2[];
int len;
int cal(char *str1,char *str2)
{
int ret=,i;
for(i=;str1[i]&&str2[i];i++)
{
if(str1[i]==str2[i])
ret++;
}
return ret;
} int max(int a, int b)
{
int z;
z=(a>b)?a:b;
return z;
} int gcd(int a, int b)
{
if(a==)
return ;
if(a%b==)
return b;
else
{
return gcd(b,(a%b));
}
}
/*
int gcd(int a, int b)
{
if(a==0)
return 1;
while(1)
{
int r=a%b;
if(r==0)
return b;
else
{
a=b;
b=r;
}
}
}*/
int findLargest(char *str1,char *str2)
{
int i,j;
int len1=strlen(str1);//len1 len2放在调用函数里，节省时间，不至于RE
int len2=strlen(str2);
len=len1+len2;
int ret=cal(str1,str2);
for(i=;i<len1;i++)
{
ret=max(ret,cal(str1+i,str2));
}
for(j=;j<len2;j++)
{
ret=max(ret,cal(str1,str2+j));
}
return ret;
} int main()
{
int ans;
while(scanf("%s",str1),strcmp(str1,"-1"))//输入-1,，存入数组的是两个字符
{
int g;
scanf("%s",str2);
ans=findLargest(str1,str2);
ans*=;
g=gcd(ans,len);
ans/=g;
len/=g;
if(ans==)
printf("appx(%s,%s) = %d\n",str1,str2,);
else if(len==)
printf("appx(%s,%s) = %d\n",str1,str2,ans);
else
printf("appx(%s,%s) = %d/%d\n",str1,str2,ans,len);
}
return ;
}
欧几里得算法，自己写的：
int gcd(int a, int b)
{
if(a==)
return ;
while()
{
int r=a%b;
if(r==)
return b;
else
{
a=b;
b=r;
}
}
}
递归方法写的：
int gcd(int a, int b)
{
if(a==)
return ;
if(a%b==)
return b;
else
{
return gcd(b,(a%b));
}
}
欧几里得算法又叫辗转相除法，用来求最大公约数，greatest common divisor最大公约数，gcd代表函数名
算法描述：1.设a%b=r，如果r==0，b即为最大公约数，返回b，2否则a<--b,b<--r,重复第一步
有可能gcd(int a ,int b)，分子为0，return 1，o和任何正数的最大公约数为1，分数约分后，判断如果分子为0，直接输出0
如果分母为1，表示，分子比分母大，输出分子就行，题目中只可能是用于fraction值为1的情况
有些欧几里得算法描述里要求如果a<b交换值，其实不然，在上面两种算法里，a=3,b=13
a%b=3 != 0,按照欧几里得算法描述，a<--b,b<--r，a=13，b=3。实际上不用换值，循环的第二次，或者递归的第二重
也会变成13%3，因此欧几里得算法适用于不论分子大还是分母大的情况
该算法结束的条件为a%b==0，返回b的值
RE了几次，之前将len1，len2弄成全局变量，RE，后来将len1，len2，放在findLargest函数里充当临时变量，留len一个全局
应该是节省了不少的空间，可见：全局变量的使用要慎重
除了这个算法之外，本题思路：
cal(char *str1, char *str2)从传入的地址开始字符串左对齐findLargest里面的第一个for循环：
| C | A | R | |||
| C | A | R | T |
| C | A | R | |||
| C | A | R | T |
| C | A | R | ||||
| C | A | R | T |
第二
| C | A | R | |||
| C | A | R | T |
| C | A | R | ||||
| C | A | R | T |