没有合适的资源?快使用搜索试试~ 我知道了~
青蛙约会 c语言源代码
5星 · 超过95%的资源 需积分: 50 17 下载量 131 浏览量
2010-06-20
14:55:10
上传
评论 1
收藏 25KB DOC 举报
温馨提示
试读
5页
青蛙约会 此题其实就是扩展欧几里德算法-求解不定方程,线性同余方程。 设过s步后两青蛙相遇,则必满足以下等式: (x+m*s)-(y+n*s)=k*l(k=0,1,2....) 稍微变一下形得: (n-m)*s+k*l=x-y 令n-m=a,k=b,x-y=c,即 a*s+b*l=c 只要上式存在整数解,则两青蛙能相遇,否则不能。
资源推荐
资源详情
资源评论
此题其实就是扩展欧几里德算法-求解不定方程,线性同余方程。
设过 s 步后两青蛙相遇,则必满足以下等式:
(x+m*s)-(y+n*s)=k*l(k=0,1,2....)
稍微变一下形得:
(n-m)*s+k*l=x-y
令 n-m=a,k=b,x-y=c,即
a*s+b*l=c
只要上式存在整数解,则两青蛙能相遇,否则不能。
首先想到的一个方法是用两次 for 循环来枚举 s,l 的值,看是否存在 s,l 的
整数解,若存在则输入最小的 s,
但显然这种方法是不可取的,谁也不知道最小的 s 是多大,如果最小的 s 很大
的话,超时是明显的。
其实这题用欧几里德扩展原理可以很快的解决,先来看下什么是欧几里德
扩展原理:
欧几里德算法又称辗转相除法,用于计算两个整数 a,b 的最大公约数。其
计算原理依赖于下面的定理:
定理:gcd(a,b) = gcd(b,a mod b)
证明:a 可以表示成 a = kb + r,则 r = a mod b
假设 d 是 a,b 的一个公约数,则有
d|a, d|b,而 r = a - kb,因此 d|r
因此 d 是(b,a mod b)的公约数
假设 d 是(b,a mod b)的公约数,则
d | b , d |r ,但是 a = kb +r
因此 d 也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,
得证
资源评论
- E_delta2014-06-05太有用了,很受启发
OPEICE
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功