辗转相除法
大纲：
- 问题
- 原理
- 反思
1. 问题
一个试题，请完成以下填空
下列程序是利用辗转相除法求H.C.F(最大公约数)
include <stdio.h>
int main(){
int m,n,r;
scanf(“%d%d”,&m,&n);
r=[?];
while([?]){
m=[?];n=r;r=[?];
printf(“h.c.f is %d”,n);
return ;
}应试时未想出解
为什么想不出?
首先是不知道什么是辗转相除法,辗转？m除一下,n除一下？翻来?覆去?
然后在想r是不是m*n
开始在纸上演算,发现几对数字中大数模小数可以得到h.c.f,不过又觉得这题用不到模,所以这种方法被我否定了,后面则是尝试用r=m*n,m=r/2,r=n/m;这种交换,不通,空一的初始化与空二的边界值难以确定
空一:相乘？
空二:输出与r对应，可r到哪为止呢?
空三:m走来被改写？？？wtf???? M? r/n??
空四:r给n了，r要做次改变，r怎么变呢?辗转相除???
总结失败原因
根本原因，不懂辗转相除法的数学原理
数学知识面窄了
次要原因，问了几个同学，其中一个人用试的给试出来了，另一个数学好，知道怎么做，试出来人的说:
空2是看到输出的是r，所以空2写的r!=0(wtf??),还说这题肯定用模做(wtf???为什么能猜这么准)
求其思考过程，说是先填了几个公试，再调试尝试(wtf??)
没搞懂他是怎么试出来的，到下笔时还是不懂他为什么能成功试出来
2. 原理
设这是一个求a,b两数的H.C.F的函数 gcd(a,b);
gcd(a,b);
如果a>b &&a%b!=0
gcd(a,b)===gcd(b,a%b)
请看到这里的同学拿出笔演算一下,用短除法什么的
拓展阅读:其数学证明
下面给出c代码
int gcd(int a,int b){
return a%b==?b:gcd(b,a%b);
}解读,拿a,b中那个大的数，模小的数，看结果是不是零，是零就输出小的
10 与 5的H.C.F就是5
不是零
10 与 8
10%8=2
到此,用余数去替换大数，然后继续//本文重点
递归 gcd(8,2)
得到2
- 特别注意的点 -
用了模的性质巧妙的碰开了先输大的，再输小的，的问题
5 %10=5,10=5,gcd(10,5)
现在，你可以完成大纲一中的问题了吗?
3. 反思
- 以后我是否还会碰到这种——实现不难，可不知其原理，就无法解题，的题目
- 打算抽空刷经典算法(math)题
2.我的同学是怎么在不懂原理的情况下解题的
- 方向对了，用了模，r!=0神猜测，后面调试把m=n试出来了
3.若是我尝试用模做，是否也能做出这题，所以它给我的教训是？
- 有一定可能。遇题先广搜一波，然后对每个可能的点（方向）进行部分深搜