最大公约数(greatest common divisor)
欧几里得辗转相除法:
gcd(x,y)表示x和y的最大公约数
进入运算时:x!=0,y!=0,本质上就是不断转换成求等价更小数的最大公约数。如果x%y=0,返回y,即最大公约数。
gcd(x,y)=gcd(y,x%y)
证明:
设k=x/y,b=x%y 则:x=ky+b
如果n能够同时整除x和y,则(y%n)=0,(ky+b)%n=0,则b%n=0,即n也同时能够整除y和b。
由上得出:同时能够整除y和(b=x%y)的数,也必然能够同时整除x和y。故而gcd(x,y)=gcd(y,x%y)。当(b=x%y)=0,即y可以整除x,这时的y也就是所求的最大公约数了。
附上两条重要性质:gcd(a,b)=gcd(b,a),gcd(-a,b)=gcd(a,b)
最小公倍数(least common multiple)
公式解法:
最小公倍数=两数之积/最大公约数
package main import ( "fmt" ) /* *穷举法:最大公约数 */ func gcdNormal(x, y int) int { var n int if x > y { n = y } else { n = x } for i := n; i >= 1; i-- { if x%i == 0 && y%i == 0 { return i } } return 1 } /* *辗转相除法:最大公约数 *递归写法,进入运算是x和y都不为0 */ func gcd(x, y int) int { tmp := x % y if tmp > 0 { return gcd(y, tmp) } else { return y } } /* *辗转相除法:最大公约数 *非递归写法 */ func gcdx(x, y int) int { var tmp int for { tmp = (x % y) if tmp > 0 { x = y y = tmp } else { return y } } } /* *穷举写法:最小公倍数 */ func lcmNormal(x, y int) int { var top int = x * y var i = x if x < y { i = y } for ; i <= top; i++ { if i%x == 0 && i%y == 0 { return i } } return top } /* *公式解法:最小公倍数=两数之积/最大公约数 */ func lcm(x, y int) int { return x * y / gcd(x, y) } func main() { x, y := 12, 15 fmt.Println("gcdNormal=", gcdNormal(x, y)) fmt.Println("gcd=", gcd(x, y)) fmt.Println("gcdx=", gcdx(x, y)) fmt.Println("\nlcmNormal=", lcmNormal(x, y)) fmt.Println("lcm=", lcm(x, y)) }
猜生日问题:
不过小明是个神秘的人,不会轻易告诉你他的生日,现在他想到一个办法,让你去猜他的生日是哪一天。
小明会告诉你如下三个信息:
1. 出生月份和出生日子的最大公约数;
2. 出生月份和出生日子的最小公倍数;
3. 出生年份;
现在要求你猜出小明的生日。
对于每组数据依次输入三个数x,y,z,
x表示出生月份和出生日子的最大公约数(1<= x <=1000);
y表示出生月份和出生日子的最小公倍数(1<= y <=1000);
z表示出生年份(1900 <= z <= 2013)。
每组输入数据占一行。
如果答案不存在 ,输出“-1”;
如果答案存在但不唯一 ,输出“1”;
如果答案唯一,输出生日,日期格式为YYYY/MM/DD;
package main import ( "fmt" ) /*检查如期是否合法*/ func checkDate(y, m, d int) int { var arr [13]int = [13]int{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} //闰年 if (y%4 == 0 && y%100 != 0) || y%400 == 0 { arr[2] = 29 } if arr[m] < d { return 0 } return 1 } /* *已知x和y的最小公倍数min和最大公约数max,求x和y *由最小公倍数性质:min=x*y/max,所以x*y=max*min *由最大公约数性质:x和y都可以写成max*n */ func rgcd(min, max, y int, m, d *int) int { var mMax, dMax, res, count, tmp int = 12 / max, 31 / max, min * max, 0, 0 for i := 1; i <= mMax; i++ { for j := 1; j <= dMax; j++ { tmp = max * i * max * j if tmp > res { break } else if tmp == res { //计算得到的日期的合法,才加上 tmpM := max * i tmpD := max * j if checkDate(y, tmpM, tmpD) == 1 { *m = tmpM *d = tmpD //fmt.Println(*m, *d) count++ } } } } if count > 1 { return 1 } else if count == 1 { return 0 } else { return -1 } } func main() { min, max, y, m, d := 24, 3, 1999, 0, 0 fr := rgcd(min, max, y, &m, &d) if fr == 0 { fmt.Printf("%d/%02d/%02d", y, m, d) } else { fmt.Println(fr) } }
有疑问加站长微信联系(非本文作者)