A-A+

《挑战程序设计竞赛》读书笔记(四)格点问题的证明

2014年05月03日 算法 评论 2 条 阅读 5,073 次
摘要:

《挑战程序设计竞赛》2.6节第一道题中讲解了求线段上格点个数的问题,该解答给出了结果,但中间过程省略了不少内容。本文补充了相关的证明和解释。
问题描述如下:
格点是指平面坐标系中,横纵坐标都是整数的点。给定平面上两个格点,P1(x1,y1),P2(x2,y2),则线段P1P2上除了P1和P2外,有几个格点?事实上,该问题答案为|x2-x1|和|y2-y1|的最大公约数减1,并给出了一个图示。本文对该结论给出了证明。

《挑战程序设计竞赛》2.6节第一道题中讲解了求线段上格点个数的问题,该解答给出了结果,但中间过程省略了不少内容。本文补充了相关的证明和解释。

问题描述如下:

格点是指平面坐标系中,横纵坐标都是整数的点。给定平面上两个格点,P1(x1,y1),P2(x2,y2),则线段P1P2上除了P1和P2外,有几个格点?

例如:P1=(1,11),P2=(5,3),则格点有(2,9), (3,7), (4,5)三个。

一种朴素的想法是枚举满足 min(x1,x2)<= x <= max(x1,x2), min(y1,y2)<= y <= max(y1,y2)的所有x,y,判断是否在线段上,其复杂度为O(|x2-x1|*|y2-y1|)。

书中说,事实上,该问题答案为|x2-x1|和|y2-y1|的最大公约数减1,并给出了一个图示如图1。

gp_1

图1

图1中画的最下面的一个三角形正好以P2结尾,说明该问题答案为|x2-x1|和|y2-y1|的最大公约数减1。书中并未给出这个证明。本文将说明,最下面的一个三角形确实是正好以P2结尾。我们用反证法来证明。假设最下面的一个三角形不是正好以P2结尾,则可能是如下的情况,如图2。

gp_2

图2

如图2,假设A1,…An是P1P2上的所有格点,且A1是离P1最近的格点。如果最后一个三角形AnCnP3不是正好以P2结束,则我们可以将三角形AnBnP2平移至三角形P1B1A1中,如图3。则E1也是格点,与A1是离P1最近的格点矛盾。得证。

gp-3

图3

得到了这个结论,剩下的就可以用辗转相除法求得最终的结果。

2.6节其他题目涉及到数论。没学过数论真是硬伤啊,等以后补充了相关知识之后再补充本章节其他内容。

 

 

2 条留言  访客:1 条  博主:1 条

  1. 火星王子

    楼主写的不错啊

    • LoopJump

      谢谢!:)

给我留言