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

辗转相除法

大纲:

  1. 问题
  2. 原理
  3. 反思

 1.     问题

一个试题,请完成以下填空

下列程序是利用辗转相除法求H.C.F(最大公约数)

 include <stdio.h>
 
  
             
            scanf(“%d%d”,&m,& 
            r=[? 
             
            m=[?];n=r;r=[? 
            printf(“h.c.f  
  
 }

应试时未想出解

为什么想不出?

首先是不知道什么是辗转相除法,辗转?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怎么变呢?辗转相除???

总结失败原因

                   根本原因, ?b:gcd(b,a% }

解读,拿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.     反思

  1. 以后我是否还会碰到这种——实现不难,可不知其原理,就无法解题,的题目

-          打算抽空刷经典算法(math)题

2.我的同学是怎么在不懂原理的情况下解题的

-          方向对了,用了模,r!=0神猜测,后面调试把m=n试出来了

3.若是我尝试用模做,是否也能做出这题,所以它给我的教训是?

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

更多相关文章
  • 信息安全系统设计基础exp_5
    北京电子科技学院(BESTI) 实验报告 课程:信息安全系统设计基础 班级:1353 姓名:郑伟.吴子怡 学号:20135322.20135313 指导教师: 娄嘉鹏 实验日期:2015年11月17日 必修/选修:必修 实验序号:exp5 实验时间:15:30-18:00 实验名称:  exp5_通 ...
  • 题意: f(x) = K, x = 1 f(x) = (a*f(x-1) + b)%m , x > 1 求出( A^(f(1)) + A^(f(2)) + A^(f(3)) + ...... + A^(f(n)) ) modular P. 1 <= n <= 10^6 0 < ...
  • 安装apachetop工具实时监测apache运行情况
    apachetop这个工具非常有用,在apache下,通过apachetop可以动态的查看apache的日志文件,直观的看到访问的每个地址的请求数速度及流量等信息.我们经常会需要知道服务器的实时监测服务器的运行状况,比如哪些 URL 的访问量最大,服务器每秒的请求数,哪个搜索引擎正在抓取我们网站?面 ...
  • CKEditor Link插件实现手动输入变为自动下拉框
    CKEditor Link插件,支持超链接地址,页面锚点和电子邮箱类型链接地址又包括http://,https://,ftp://,news://,其他但是有一个问题,这里的URL 地址都需要手动输入为了数据的完整性,如果只允许用户选择一个列表,那么就需要稍微改动一下.效果如下 下面来修改ckedi ...
  • Fabric 是一个 Python 库和命令行工具,用于连接到 SSH 服务器并执行命令,知名的移动应用 Instagram就使用Fabric来管理他们上百台服务器的事情.这两天,偶尔再次看了遍这篇文章,并且对Fabric感兴趣,或许我管理一些服务器时也许还能用得上,所以花了点时间简单了解了一下Fa ...
  • 本文章先来给大家介绍一个不错的文件备份实现,就是每天定时给mysql数据库进行备份了,同时也可以对其它文件进行备份哦,同时也可以把本地文件备份到远程服务器中.普通的本地备份 代码如下 net stop mysqlxcopy D:/xx/data/bbb/*.* E:/cache/test/%date ...
  • 下面来给各位同学介绍一篇关于Centos6.5安装Cloudstack 4.3-管理节点和计算节点安装例子,有兴趣的朋友可参考一下.安装过程中也遇到不少问题,特别感谢 兆松兄 @itnihao 的帮忙,想起那天半夜还在帮忙解决二级存储无法正常启动的问题,那是我逝去的青春.1. 先决条件 至少一个支持 ...
  • RHCSA 系列十四: 在 RHEL 7 中设置基于 LDAP 的认证
    在这篇文章中,我们将首先罗列一些 LDAP 的基础知识(它是什么,它被用于何处以及为什么会被这样使用),然后向你展示如何使用 RHEL 7 系统来设置一个 LDAP 服务器以及配置一个客户端来使用它达到认证的目的.RHCSA 系列:设置 LDAP 服务器及客户端认证 – Part 14正如你将看到的 ...
  • Apple Safari For Windows 'window.open()' URI欺骗漏洞
    发布日期:2012-03-28更新日期:2012-03-29受影响系统:Apple Safari 5.1.5 for Windows描述:--------------------------------------------------------------------------------B ...
一周排行