讨论 / 17 过河 压缩的值怎么算的啊?
zhongjiaxin 2010-10-05 06:05:00
点我顶贴 收藏 删除
为什么要压缩成100?

请说详细点,谢谢

#1 jiangminyang@2010-10-05 06:05:00
回复 删除
没为什么

应为两点间大于100 你总可以通过某种办法跳到所以可以缩

下面是证明

首先证明一个数学定理。如果两个数a,b互质

那么a,b不能构成的最大数小于a*b。

[证明]

要求的这个数可以表示成ax+by=c(即求此时c的最大值)。

问题转化为最小必然能构成的数为多少?

如果c存在,可以得到一个解(x0,y0),ax0+by0=c,方程的通解可以表示成

x=x0+bt y=y0-at

我们需要求正整数解,那么必须满足

x>0,y>0

所以y0/a>t>-x0/b

要保证至少存在一个整数t

所以y0/a+x0/b>=1 所以by0+ax0>=a*b

换句话说,也就是当数是a*b时,必然能构成

所以最大不能构成的数必然小于a*b

[证毕]

因为相领两个数必然互质。

[证明]

假设这两个数不互质,那么他们必然存在一个公因数p

那么一个数为a另一个数为b(a=b+1),那么a=pk b=pk’

所以a-b=pk-pk’=p(k-k’)=1

因为p为整数,所以p=1,所以相邻两个数必然互质。

[证毕]

通过上述两个定理我们可以知道当存在两个数时,不妨记这两个数为a,b那么当步数大于a*b的时候,我们必然可以走到,又因为最大的两个数的乘积小于100 ,所以我们可以把大于100的步长直接缩小为100步,因为大于100步的部分必然能跳到,所以再跳是没有意义的。

查看更多回复
提交回复