IT大道IT大道

首页 >  技术 > 求直线上的整数点算法

求直线上的整数点算法

原文 http://blog.csdn.net/mylinchi/article/details/53714796 2016-12-17 22:31:55 0 评论

问题描述:

求直线itdadao上有多少个整数点(x,y)满足itdadao

问题分析:

把直线方程进行移项,得到itdadao

假设已经得到直线上一个点的坐标itdadao,假设直线存在另外一个点坐标为itdadao,那么把两点代入直线得到方程itdadao,整理得到 itdadao

假设itdadao,上上式两边同除g,可以得到itdadao,其中itdadao。把等式再变形得到itdadao,此时的itdadaoitdadao互素,itdadao必定是itdadao的整数倍,即k可以为任意整数。整理得到itdadaoitdadao

由上面的分析知道,只需要就出方程itdadao的任意一组解,就可以求出其他解。

扩展欧几里德算法:

找出一对整数itdadao,使得itdadao

对应的算法程序如下:

void gcd(int a,int b, int& d, int& x, int& y){

      if (!b){ d = a; x = 1; y = 0; }

      else{ gcd(b, a%b, d, y, x); y -= x*(a /b); }

}//d为gcd(a,b),x和y为解

对于a和b最大公约数的求解在欧几里德算法中就介绍过,唯一需要记忆的就是x和y的初始条件x=1,y=0,x和y的递归关系y -= x*(a /b);。

假设itdadao,的一组解是itdadao。如果-c是g的整数倍,则itdadao的一组解是itdadao;当c不是g的整数倍是无整数解。

综上,先求itdadao的解,再求itdadao的解,最后求itdadao的其他解,分三步走。程序实现如下:

#include<iostream>
#include<cstdio>
using namespace std;

void gcd(int a, int b, int& g, int& x, int& y){
	if (!b){ g = a; x = 1; y = 0; }
	else{ gcd(b, a%b, g, y, x); y -= x*(a / b); }
}

int main()
{
	int a, b, c, x1, x2, y1, y2, g, x, y;
	cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2;
	gcd(a, b, g, x, y);//ax+by=gcd(x,y)
	if (c%g == 0){
		int x0 = -x*(c / g), y0 = -y*(c / g);//ax+by=-c
		printf("(%d,%d)\n",x0,y0);
		bool kup = true, kdown = true;
		for (int k = 1;; k++){
			int xn = x0 - k*(b / g), yn = y0 + k*(a / g);
			if (kup&&xn >= x1&&xn <= x2&&yn >= y1&&yn <= y2){
				printf("(%d,%d)\n",xn,yn);
			}
			else kup = false;
			xn = x0 + k*(b / g);
			yn = y0 - k*(a / g);
			if (kdown&&xn >= x1&&xn <= x2&&yn >= y1&&yn <= y2){
				printf("(%d,%d)\n", xn, yn);
			}
			else kdown = false;
			if (!(kup || kdown))break;
		}
	}
	else printf("No point.\n"); 
	system("pause");
	return 0;
}


Tags:c/c   算法  

标签列表