©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>直线
<>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; }