数学问题的解题窍门——辗转相除法
辗转相除法
求最大公约数
问题:线上格点的个数
给定平面上两个格点(格点是指纵横坐标都为整数的点) ,线段 上,除了还有多少个格点??
限制条件:
输入样例:
p1= 1 11
p2= 5 3
输出样例:
(2,9) (3,7) (4,5)
3个格点
这道题目解答并不困难,首先我们立马就能想到寻找之间的整数、间的整数。然后检查所有的点是否在直线上。虽然可以求出答案,但是时间复杂度较大,并不是一个好办法。
这个题目其实可以利用最大公约数求解。
求a,b最大公约数的辗转相除法:
- x=max(a,b) y=min(a,b)
- y=x%y ,x=y
- 如果y!=0 ,则重复步骤2否则最大公约数为x
编写函数:
//求最大公约数的递归算法
int gcd(x,y){ //x>=y
if(y==0)return x;
return gcd(y,x%y);
}
本题中所求的格点个数=
为啥最大公约数-1就是格点的个数呢??
以本题的示例输入为例,可以这样考虑:
8,4的最大公约数是4,说明8%4=0,4%4=0;
所以8和4都可以均分为4份,如下图所示:
将横纵坐标都4等分,发现在线段内正好有三个点,而且每个点的横纵坐标都是整数,所以就有三个格点。
在本例中|x_1-x_2|=4与|y_1-y_2|=8,最大公约数为4,所以有3个格点。
代码如下;
#include <iostream>
using namespace std;
//最大公约数
int gcd(int x, int y) {
if (y == 0) {
return x;
}
return gcd(y, x % y);
}
//输出格点
string printGridPoint(int x, int y) {
return "(" + to_string(x) + "," + to_string(y) + ")";
}
int main() {
int x1, y1, x2, y2;
cout << "P1=";
cin >> x1 >> y1;
cout << "P2=";
cin >> x2 >> y2;
int x = max(abs(x1 - x2), abs(y1 - y2));
int y = min(abs(x1 - x2), abs(y1 - y2));
int num = gcd(x, y);
int stepX = (x1 - x2) / num;
int stepY = (y1 - y2) / num;
for (int i = 1; i < num; i++) {
cout << printGridPoint(x2 + stepX * i, y2 + stepY * i) << " ";
}
cout << endl;
cout << (num - 1) << "个格点";
}