#include<stdio.h> #include<string.h> #include<string.h> char str1[100],str2[100]; int len; int cal(char *str1,char *str2) { int ret=0,i; for(i=0;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==0) return 1; if(a%b==0) 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=1;i<len1;i++) { ret=max(ret,cal(str1+i,str2)); } for(j=1;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*=2; g=gcd(ans,len); ans/=g; len/=g; if(ans==0) printf("appx(%s,%s) = %d ",str1,str2,0); else if(len==1) printf("appx(%s,%s) = %d ",str1,str2,ans); else printf("appx(%s,%s) = %d/%d ",str1,str2,ans,len); } return 0; }
欧几里得算法，自己写的：
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 gcd(int a, int b) { if(a==0) return 1; if(a%b==0) 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 |