<>直线

<>1.题目

在平面直角坐标系中,两点可以确定一条直线。
如果有多点在一条直线上,那么这些点中任意两点确定的直线是同一条。
给定平面上2 × 3 个整点{(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z},
即横坐标是0 到1 (包含0 和1) 之间的整数、纵坐标是0 到2 (包含0 和2) 之间的整数的点。
这些点一共确定了11 条不同的直线。
给定平面上20 × 21 个整点{(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z},
即横坐标是0 到19 (包含0 和19) 之间的整数、纵坐标是0 到20 (包含0 和20) 之间的整数的点。
请问这些点一共确定了多少条不同的直线。(填空题)

答:本题遍历根据所有的点,计算出每两个点之间的斜率与截距,只要斜率与截距不同,就可以出确定直线不一样,但是还要考虑斜率不存在的情况,也就是直线垂直于x坐标轴的情况。

<>2.代码
public int requireDirectLine(int x,int y) { Test5 test5 = new Test5(); int arr[
][] =new int[x][y]; HashSet<String> set = new HashSet<>(); for(int i = 0; i <
arr.length; i++) { for(int j = 0; j < arr[0].length; j++) {
//取双重for循环为一个点,即(i,j),另外的双重for循环为另外一个点,即(p,q) for(int p = 0; p < arr.length; p++
) { for(int q = 0; q < arr[0].length; q++) { if( i == p && j ==q ) { //这一步判断可以不要
continue; } if( i != p) { //x1 == x2时直线斜率不存在,即当直线垂直于x轴时,直线斜率不存在。 String line =
""; int u = q - j; //y2-y1 int d = p - i; //x2-x1 int g = gcd(u,d); //u、d的最大公约数
line= line + u/g+ "/"+ d/g + "+"; //(y2-y1)/(x2-x1) k = u/g+ "/"+ d/g int b = j
* d - u *i; // y = kx +b -> b = y - kx 将点(i,j),k=(y2-y1)/x2-x1代入。 // 可得b=
(y0(x2-x1)- x0(y2-y1))/x2-x1 //即求除数与被除数的最大公约数就可以求出该直线的最简式,最简式一样即两条直线是同一条直线。 int
g2= gcd(b,d); //求 y0(x2-x1) - x0(y2-y1))/x2-x1 的最大公约数 line = line + b/g2 + "/" +
d/g2; // 直线 为 kx + b ,k、b不一致,将直线加入set。 set.add(line); } } } } } if( y == 1) {
//当y为1时,即只有一行,这时无需加上垂直的直线,即垂直与x坐标轴的值。 return set.size(); } return set.size() + x
; //加上斜率不存在的直线。即横坐标的值。 } //辗转相除法求最大公约数-->递归方式 public int gcd(int x,int y){ if( y
== 0){ return x; } return gcd(y,x%y); }
答案:40257

本题直接使用double计算k,b会出现除不尽的情况,因此会存在多于的直线,会使结果不准确。如下

错误解法示例:
public static void main(String[] args) { double x = requireDirectLine(20,21);
System.out.print(x); } public static double requireDirectLine(int x,int y) { int
arr[][] =new int[x][y]; HashSet<ArrayList<Double>> set = new HashSet<>(); for(
double i = 0; i < arr.length; i++) { for(double j = 0; j < arr[0].length; j++) {
for(double p = 0; p < arr.length; p++ ) { for( double q = 0; q < arr[0].length;
q++) { if( i == p && j ==q ) { continue; } if( i != p) { double k = (q-j)/(p-i);
if(k == -0.0) { k= 0.0; } double b = (-k)*i + j ; System.out.println("p1:("+i+
","+j+"),p2:("+p+","+q+")"+" "+"k:"+k+","+"b:"+b); ArrayList<Double> list = new
ArrayList<>(); list.add(k); list.add(b); set.add(new ArrayList<Double>(list)); }
} } } } Iterator<ArrayList<Double>> it = set.iterator(); if( y == 1) { return
set.size(); } return set.size() + x; }

可以看到结果比正确答案多出了很多。

上述错误为错误代码实例,只要数量足够大,就会出现除不尽的情况,因此难免会出现重复问题。因此,使用将直线化为最简式的方式。

<>3.求解最大公因数

<>3.1.辗转相除法

* 如果b等于0,计算结束,a就是最大公约数。
* 否则,计算a除以b的余数,让a等于b,而b等于那个余数;
* 回到第一步。 //迭代 public static int gcd2(int x,int y ){ while( y != 0 ){ int temp
= y; y = x % y; x = temp ; } return x; } //递归 public static int gcd3(int x,int y
){ if(y == 0 ){ return x; } return gcd3(y,x%y); }
<>3.2.定义法

根据定义从1开始遍历至两个元素的最小值,选取两者的公约数,即12能除的尽,18也能除尽的最大数,即为最大公约数。

public int gcd1(int x,int y){ int max = 1; for(int i = 2; i <= x && i<=y; i++ )
{ if(x % i==0 && y % i == 0){ max = i; } } return max; }

技术
今日推荐
阅读数 170189
阅读数 23
阅读数 5
阅读数 0
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信