アルゴリズム

プリンストン大学アルゴリズム第3週：CollinearPoints共線パターン認識（99ポイント）-要約とコード



Princeton University Algorithm Week3



私のブログへようこそ

総括する

（コードには詳細なコメントがあります）
  1. このレッスンでは、マージと並べ替えについて説明します。求人応募は、同一線上のパターン認識のために並べ替えています。 java1.8のソートでは、マージソートと挿入ソートを組み合わせたtimソートを使用します。 安定した並べ替え：並べ替え後の同じ要素の相対位置は変更されません
  2. Point.javaには非常に重要なメソッドがあります。 compareTo（） 、それは定義します：縦座標が小さいほど、点は小さくなります。縦軸が同じ場合、横軸が小さいほど点が小さくなります。 （ジョブで横座標を順番に配置する必要がある場合、並べ替えられたポイントセットは2Dにマップされます。座標系には、減少しないポリラインがあります。このように、ループの1つのレイヤーのみを使用して検索できます。同一直線上にあります。残念ながら、ジョブにはxの制限がありません。
  3. サイズを比較して、最初にpoints [i-1] == point [i]を使用しましたが、座標は同じですが、points [i-1]はpoints [i]と等しくありません。
    points [i-1]とpoints [i]は参照を表すため、ヒープ内の2つの異なるアドレスを指し、サイズをpoints [i-1] .compareTo（points [i]）と比較します。
  4. FastCollinearPoints.javaでは、同一線上のポイント変数の数をいつ判断するかに注意を払うことが重要です。 2つのケースがあります。 1つは、隣接する要素の勾配が参照点と異なることです。もう1つは、最後の要素へのループです。状況はコードコメントで説明されています
  5. 唯一の失敗、1ポイント差し引かれ、体系的にJavaを学習せず、最初にスキップされました
Test 7: check for dependence on either compareTo() or compare() returning { -1, +1, 0 } instead of { negative integer, positive integer, zero } * filename = equidistant.txt - number of entries in student solution: 0 - number of entries in reference solution: 4 - 4 missing entries in student solution, including: '(30000, 0) -> (20000, 10000) -> (10000, 20000) -> (0, 30000)' ==> FAILED

  1. week3コースウェアでは、再帰呼び出しのアイコンは次のとおりです。
    これは、2回の再帰呼び出しによる再帰です（図は半分しかペイントされていません）




    9608551-c31de2c890e27f18.jpgMerge.jpg

コード

（提出する必要がある場合は、中国語のコメントを削除してください）

1つ：Point.java

import java.util.Comparator import edu.princeton.cs.algs4.StdDraw public class Point implements Comparable { // x-coordinate of this point private final int x // y-coordinate of this point private final int y // constructs the point (x, y) public Point(int x, int y) { this.x = x this.y = y } // draws this point public void draw() { StdDraw.point(x,y) } // draws the line segment from this point to that point public void drawTo(Point that) { StdDraw.line(this.x, this.y, that.x, that.y) } // string representation public String toString() { return '(' + x + ', ' + y + ')' } // compare two points by y-coordinates, breaking ties by x-coordinates public int compareTo(Point that) // the slope between this point and that point public double slopeTo(Point that) { if(x==that.x && y==that.y) return Double.NEGATIVE_INFINITY if(x==that.x && y!=that.y) return Double.POSITIVE_INFINITY if(y==that.y) return +0.0 return (double)(y-that.y)/(x-that.x) } // compare two points by slopes they make with this point public Comparator slopeOrder(){ return new SlopeOrder() } //nested class //sort rule private class SlopeOrder implements Comparator{ public int compare(Point p,Point q) { //p point slope is large if(slopeTo(p)slopeTo(q)) return 1 //p, q slope is equal else return 0 } } public static void main(String[] args) { Point p1 = new Point(0,0) Point p2 = new Point(1,1) Point p3 = new Point(2,2) Point p4 = new Point(2,1) Point p5 = new Point(4,1) System.out.println('p1.compareTo(p1) is '+p1.compareTo(p2)) System.out.println('p2.compareTo(p1) is '+p2.compareTo(p1)) System.out.println('p1.compareTo(p1) is '+p1.compareTo(p1)+' ') System.out.println('p1.slopeTo(p2) is ' +p1.slopeTo(p2)) System.out.println('p1.slopeTo(p4) is '+p1.slopeTo(p4)) System.out.println('p1.slopeTo(p1) is '+p1.slopeTo(p1)) System.out.println('p3.slopeTo(p4) is '+p3.slopeTo(p4)) System.out.println('p2.slopeTo(p5) is '+p2.slopeTo(p5)) } }

2：BruteCollinearPoints.java

import java.util.ArrayList import java.util.Arrays import edu.princeton.cs.algs4.In import edu.princeton.cs.algs4.Insertion import edu.princeton.cs.algs4.StdOut import edu.princeton.cs.algs4.StdDraw public class BruteCollinearPoints { //to store line segments private ArrayList LineSegmentList //to store the given points private Point[] points // Find the line segment consisting of 4 points in the constructor (job says: there are no 5 points and more points collinear) // finds all line segments containing 4 point public BruteCollinearPoints(Point[] pointsIn) { //Three exceptions //1: if the argument to the constructor is null System.out.println(' a ') if(pointsIn == null) throw new IllegalArgumentException('there is no point') //two: if any point in the array is null int N = pointsIn.length for(int i=0i

3：FastCollinearPoints.java

import java.util.ArrayList import java.util.Arrays import edu.princeton.cs.algs4.In import edu.princeton.cs.algs4.StdDraw import edu.princeton.cs.algs4.StdOut //much faster than the brute-force solution public class FastCollinearPoints { //to store line segments private ArrayList LineSegmentList //to store the given points private Point[] points // finds all line segments containing 4 or more points public FastCollinearPoints(Point[] pointsIn) { //Three exceptions //1: if the argument to the constructor is null if(pointsIn == null) throw new IllegalArgumentException('there is no point') //number of points int N=pointsIn.length //two: if any point in the array is null for(int i=0i=4 && currentCheck.compareTo(otherPoints[k-count+1])==-1) { Point start = currentCheck Point end = otherPoints[k-1] LineSegment linesegment = new LineSegment(start,end) LineSegmentList.add(linesegment) } count=2 } } } } // the number of line segments public int numberOfSegments() { return LineSegmentList.size() } // the line segments public LineSegment[] segments() { LineSegment[] segments = new LineSegment[LineSegmentList.size()] int index=0 for(LineSegment Line : LineSegmentList) { segments[index++] = Line } return segments } //main public static void main(String[] args) { In in = new In('src/week3/input9.txt') int n = in.readInt() StdOut.println('total '+n+' points') Point[] points = new Point[n] for (int i = 0 i