普林斯顿大学算法Week3:CollinearPoints共线模式识别(99分)--总结及代码

2023-10-16 07:30
文章标签 算法 代码 总结 99 模式识别 week3 共线 collinearpoints 普林斯顿大学

本文主要是介绍普林斯顿大学算法Week3:CollinearPoints共线模式识别(99分)--总结及代码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

总结

(代码有详细注释)
  1. 本课讲了归并排序,作业应用是排序进行共线的模式识别,java1.8中的排序用的是tim排序,结合了归并排序与插入排序,属于稳定排序:排序之后相同元素的相对位置会不会改变
  2. Point.java中有个非常重要的方法,compareTo(),它定义:纵坐标越小则点越小,如果纵坐标相同,那么横坐标越小则点越小.(如果作业中要求横坐标也是按顺序排列,那么排序后的点集映射到二维坐标系中是非递减的折线, 这样找共线只用一层循环即可,可惜作业没加上对x的限制)
  3. 比较大小,一开始我用的是points[i-1] == point[i],尽管坐标相同但是points[i-1]不等于points[i]
    因为points[i-1]和points[i]表示引用,在堆中指向两个不同的地址,比较大小得用points[i-1].compareTo(points[i])
  4. 在FastCollinearPoints.java中,一定要注意什么时候对共线点数变量count进行判断,有两种情况,一个是,相邻元素与参考点的斜率不同;另一个是循环到最后一个元素.这两种情况在代码注释中有解释
  5. 唯一一处FAILED,扣了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课件中,递归调用的图示:
    这是包含两个递归调用的递归 (图示只画了一半)
    Merge.jpg

代码

(如需提交,请删除中文注释)

一:Point.java

import java.util.Comparator;
import edu.princeton.cs.algs4.StdDraw;
public class Point implements Comparable<Point> {// x-coordinate of this pointprivate final int x;// y-coordinate of this pointprivate final int y;// constructs the point (x, y)public Point(int x, int y) {this.x = x;this.y = y;} // draws this pointpublic   void draw() {StdDraw.point(x,y);}// draws the line segment from this point to that pointpublic   void drawTo(Point that) {StdDraw.line(this.x, this.y, that.x, that.y);}// string representationpublic String toString() {return "(" + x + ", " + y + ")";}// compare two points by y-coordinates, breaking ties by x-coordinates  public  int compareTo(Point that) {if(y<that.y || (y==that.y && x<that.x)) return -1;else if(y==that.y && x==that.x) return 0;else return +1;}   // the slope between this point and that pointpublic  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 pointpublic Comparator<Point> slopeOrder(){return new SlopeOrder();}//nested class//sort ruleprivate class SlopeOrder implements Comparator<Point>{public int compare(Point p,Point q) {//p点斜率大if(slopeTo(p)<slopeTo(q)) return -1;//p点斜率小else if(slopeTo(p)>slopeTo(q)) return 1;//p,q斜率相等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)+"\n");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));}
}

二: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 segmentsprivate ArrayList<LineSegment> LineSegmentList;//to store the given pointsprivate Point[] points;//在构造函数中找出由4点构成的线段(作业说了:没有5点及更多点共线的情况)// finds all line segments containing 4 pointpublic BruteCollinearPoints(Point[] pointsIn) { //三种异常//一:if the argument to the constructor is nullSystem.out.println(" a ");if(pointsIn == null) throw new IllegalArgumentException("there is no point");//二:if any point in the array is nullint N = pointsIn.length;for(int i=0;i<N;i++) if(pointsIn[i]==null) throw new IllegalArgumentException("exist null point");//三:if the argument to the constructor contains a repeated point//检查是否有重复的点,先排序,再查重会方便,作业允许这样: For example, you may use Arrays.sort()points = new Point[N];for(int i=0;i<N;i++) points[i] = pointsIn[i];Arrays.sort(points);for(int i=1;i<N;i++) if(points[i-1].compareTo(points[i])==0) throw new IllegalArgumentException("exist repeated point"); //to save every required line segmentLineSegmentList = new ArrayList<LineSegment>();//find line segmentfor(int dot1=0;dot1<=N-4;dot1++) {for(int dot2=dot1+1;dot2<=N-3;dot2++) {//k12:the slope between point[dot2] and point[dot1]double k12 = points[dot2].slopeTo(points[dot1]);for(int dot3=dot2+1;dot3<=N-2;dot3++) {//k13:the slope between point[dot3] and point[dot1]double k13 = points[dot3].slopeTo(points[dot1]);if(k13 != k12) continue;for(int dot4=dot3+1;dot4<=N-1;dot4++) {//k14:the slope between point[dot4] and point[dot1]double k14 = points[dot4].slopeTo(points[dot1]);if(k14 != k12) continue;//find a line segmentLineSegment linesegment = new LineSegment(points[dot1],points[dot4]);LineSegmentList.add(linesegment);}}}}}// the number of line segmentspublic int numberOfSegments() {return LineSegmentList.size();}// the line segmentspublic LineSegment[] segments() {LineSegment[] segments = new LineSegment[LineSegmentList.size()];int index=0;for(LineSegment Line : LineSegmentList) {segments[index++] = Line;}return segments;}    //mainpublic static void main(String[] args) {In in = new In("src/week3/input8.txt"); int n = in.readInt();StdOut.println("total "+n+" points");Point[] points = new Point[n];for (int i = 0; i < n; i++) {int x = in.readInt();int y = in.readInt();StdOut.println("("+x+","+y+")"); points[i] = new Point(x,y);}       //draw the pointsStdDraw.enableDoubleBuffering();StdDraw.setXscale(0, 32768);StdDraw.setYscale(0, 32768);StdDraw.setPenColor(StdDraw.RED);StdDraw.setPenRadius(0.01);for (Point p : points) {p.draw();}StdDraw.show();              // print and draw the line segmentsBruteCollinearPoints collinear = new BruteCollinearPoints(points);StdOut.println(collinear.numberOfSegments());for (LineSegment segment : collinear.segments()) {StdOut.println(segment);segment.draw();}StdDraw.show();          }
}

三: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 segmentsprivate ArrayList<LineSegment> LineSegmentList;//to store the given pointsprivate Point[] points;// finds all line segments containing 4 or more pointspublic FastCollinearPoints(Point[] pointsIn) {//三种异常//一:if the argument to the constructor is nullif(pointsIn == null) throw new IllegalArgumentException("there is no point");//number of pointsint N=pointsIn.length;//二:if any point in the array is nullfor(int i=0;i<N;i++) if(pointsIn[i]==null) throw new IllegalArgumentException("exist null point");//三:if the argument to the constructor contains a repeated point//检查是否有重复的点,先排序,再查重会方便,作业允许这样: For example, you may use        Arrays.sort()//同时有利于后面排除重复线段points = new Point[N];for(int i=0;i<N;i++) points[i] = pointsIn[i];//用的是结合了归并和插入的tim排序,稳定排序Arrays.sort(points);for(int i=1;i<N;i++) if(points[i-1].compareTo(points[i])==0) throw new IllegalArgumentException("exist repeated point");//to save every required line segmentLineSegmentList = new ArrayList<LineSegment>();//当前的参考点Point currentCheck;//对照点重新存储,不包括参考点,共N-1个Point[] otherPoints = new Point[N-1];//开始比较斜率,一个一个来for (int i=0;i<N;i++) {currentCheck = points[i];// copy points without Point currentCheck to otherPointsfor(int j=0;j<N;j++) {if(j<i) otherPoints[j] = points[j];if(j>i) otherPoints[j-1] = points[j];}//根据斜率对点排序//用的是结合了归并和插入的tim排序,稳定排序Arrays.sort(otherPoints,currentCheck.slopeOrder());//遍历已经排序的otherPoints找线段//注意,归并和插入排序都是稳定的,所以tim排序是稳定的,这非常重要//配合Point的compareTo方法,可以直接过滤掉重复线段//一开始没太注意compareTo方法,后来发现这个方法能固定住点之间的相对位置,所以可以过滤重复线段//两点共线int count=2;for(int k=1;k<N-1;k++) {double k1 = otherPoints[k-1].slopeTo(currentCheck);double k2 = otherPoints[k].slopeTo(currentCheck);if(k1==k2) {count++;//当循环到最后一个点,同时这个点和前面的点共线if(k==N-2) {//如果4点及以上共线,并且otherPoints中与参考点共线且排在最左边的点比参考点大的话,注意此处是遍历到头,所以索引是k-count+2if(count>=4 && currentCheck.compareTo(otherPoints[k-count+2])==-1) { //线段起点Point start = currentCheck;//线段终点Point end = otherPoints[k];LineSegment linesegment = new LineSegment(start,end);LineSegmentList.add(linesegment);}}}else{//如果4点及以上共线,并且otherPoints中与参考点共线且排在最左边的点比参考点大的话,索引是k-count+1if(count>=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 segmentspublic  int numberOfSegments() {return LineSegmentList.size();}// the line segmentspublic LineSegment[] segments() {LineSegment[] segments = new LineSegment[LineSegmentList.size()];int index=0;for(LineSegment Line : LineSegmentList) {segments[index++] = Line;}return segments;}//mainpublic 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 < n; i++) {int x = in.readInt();int y = in.readInt();StdOut.println("("+x+","+y+")"); points[i] = new Point(x,y);}//draw the pointsStdDraw.enableDoubleBuffering();StdDraw.setXscale(0, 32768);StdDraw.setYscale(0, 32768);StdDraw.setPenColor(StdDraw.RED);StdDraw.setPenRadius(0.01);for (Point p : points) {p.draw();}StdDraw.show();//print and draw the line segmentsFastCollinearPoints collinear = new FastCollinearPoints(points);StdOut.println(collinear.numberOfSegments());for (LineSegment segment : collinear.segments()) {StdOut.println(segment);segment.draw();}StdDraw.show();          }
}

WelcomeToMyBlog

这篇关于普林斯顿大学算法Week3:CollinearPoints共线模式识别(99分)--总结及代码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/219997。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2