问题10: GCD*两个正整数a和b的最大公因子是最大整数,它均分两个数(没有余数)。公元前300年的希腊数学家欧几里得认识到,a和b的最大公因子是以下之一:如果a和b均分较大的值,则值越小,或较小值的最大公共除数和除以较小值的最大公因子,换句话说,如果a大于b,a不可被b除,那么gcd(a, b) == gcd(b, a % b)使用欧几里德算法递归地编写gcd函数。
如果是,则返回最小公共因子的长度:因此,对于"abababab“和"abab",返回2 as s可被t除,最小公共因子是长度为2的"ab”。我的思路是:定义这两个字符串的长度,找出这两个字符串的最大公因子。如果t除以s,那么最小公共因子就是t的最小除数,然后可以使用以下算法:。
有没有更简单的解决办法?