辗转相除法求H.C.F小结

辗转相除法

大纲：

问题
原理
反思

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.若是我尝试用模做，是否也能做出这题，所以它给我的教训是？

　　　　　　　　- 有一定可能。遇题先广搜一波，然后对每个可能的点（方向）进行部分深搜

秒客网

辗转相除法求H.C.F小结

相关文章