算法 第四版 习题 答案1.2
/*
* 1.2.1 编写一个Point2D的用例，从命令行接受一个整数N。在单位正方形内生成N个随机点，然后计算两点之间的最近距离
*/
public class testPoint2D {
public testPoint2D() {
// TODO Auto-generated constructor stub
}
public static void drawbox(double bw, double bh)
{
StdDraw.setPenRadius(0.005);
StdDraw.setPenColor(StdDraw.RED);
Interval1D xinterval = new Interval1D(0, bw);
Interval1D yinterval = new Interval1D(0, bh);
Interval2D box = new Interval2D(xinterval, yinterval);
box.draw();
}
public static Point2D[] drawpoint(int N)
{
Point2D[] p=new Point2D[N];
for(int i=0;i
{
double x=Math.random();
double y=Math.random();
p[i]=new Point2D(x, y) ;
p[i].draw();
}
return p;
}
public static double findmindist(Point2D[] p)
{
Point2D p1=p[0];
Point2D p2=p[1];
double mindist =p[0].distanceTo(p[1]);
StdDraw.setPenRadius(0.002);
StdDraw.setPenColor(StdDraw.RED);
int n=p.length ;
for(int i=1;i
for(int j=i+1;j
{
double temp=p[i].distanceTo(p[j]);
if(temp
{ mindist=temp;
p1=p[i];
p2=p[j];
}
}
p1.drawTo(p2);
StdOut.print("min dist="+mindist +p1.toString()+p2.toString());
return mindist;
}
public static void main(String[] args) {
int N=StdIn.readInt();//读取画点的数量
//StdDraw.setXscale(0,1 );
//StdDraw.setYscale(0,1);
drawbox(1,1);//画出一个单位大小的正方形
StdDraw.setPenRadius(0.01);
StdDraw.setPenColor(StdDraw.BLACK);
//drawpoint(N);//画出N个点
double min=findmindist(drawpoint(N));
}
}
/*
* 编写一个Interval1D的用例，从命令行接受一个整数N。从标准输入中读取N个间隔（每个间隔由一对double值定义）并打印出所有相交的间隔对
*/
public class testInterval1D {
public testInterval1D() {
// TODO Auto-generated constructor stub
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int N = StdIn.readInt();
Interval1D[] interval = new Interval1D[N];
int T = N;
while (N > 0) {
double lo = N;
double hi = N + N;
interval[T - N] = new Interval1D(lo, hi);
StdOut.println(interval[T - N].toString());
N--;
}
StdOut.println(" OUT:");
for (int i = 0; i < T - 1; i++)
for (int j = i + 1; j < T; j++) {
if (interval[i].intersects(interval[j]) == true) {
StdOut.println(interval[i].toString()
+ interval[j].toString());
} else {
StdOut.println(interval[i].toString()
+ interval[j].toString() + "none");
}
}
}
}
/**
* 1.2.3
*/
/**
* @author Administrator
*
*/
public class TestInterval2D {
public static void main(String[] args) {
// TODO Auto-generated method stub
StdOut.println("enter N:");
int N = 10;
StdOut.println("enter min and max:");
double min = 0.1;
double max = 0.9;
StdDraw.setXscale(0, 1);
StdDraw.setYscale(0, 1);
StdDraw.setPenRadius(0.001);
StdDraw.setPenColor(StdDraw.RED);
Interval2D[] box = new Interval2D[N];
Interval1D[] xinterval = new Interval1D[N];
Interval1D[] yinterval = new Interval1D[N];
double average = (max - min);
Point2D[][] p = new Point2D[N][2];
/*
* Point2D[][] p 使用数组保存点二位平面的对角顶点，用来计算是否包含。 Interval2D[] box
* 建立数组对象，保存每个平面的信息。
*/
for (int i = 0; i < N; i++) {
double x = Math.random();
double y = Math.random();
double x1 = x + average * Math.random();
double y1 = y + average * Math.random();
if (x1 > 1) {
x1 = 1;
}
if (y1 > 1) {
y1 = 1;
}
p[i][0] = new Point2D(x, y);
p[i][1] = new Point2D(x1, y1);
xinterval[i] = new Interval1D(x, x1);
yinterval[i] = new Interval1D(y, y1);
box[i] = new Interval2D(xinterval[i], yinterval[i]);
box[i].draw();
}
/*
* 检测时候相交
*/
for (int i = 0; i < N - 1; i++)
for (int j = i + 1; j < N; j++) {
if (box[i].intersects(box[j])) {
StdDraw.setPenColor(StdDraw.BLACK);
box[i].draw();
box[j].draw();
// StdOut.println(box[i].toString()+box[j].toString());
}
}
/*
* 是否包含
*/
for (int i = 0; i < N - 1; i++)
for (int j = i + 1; j < N; j++) {
if (box[i].contains(p[j][0]) && box[i].contains(p[j][1])) {
StdDraw.setPenRadius(0.005);
StdDraw.setPenColor(StdDraw.BLUE);
box[i].draw();
StdDraw.setPenColor(StdDraw.GREEN);
box[j].draw();
StdOut.println("i=" + i + "j=" + j + " "
+ box[i].toString() + box[j].toString());
}
}
}
}
/*
* 1.2.6 回环变位检测
* 1.2.7 递归返回值
*/
public class CircularRotation {
public CircularRotation() {
// TODO Auto-generated constructor stub
}
public static String mystery(String s)
{
int N=s.length();
if(N<=1) return s;
String a=s.substring(0, N/2);
String b=s.substring(N/2, N);
StdOut.println(a+b);
return mystery(b)+ mystery(a);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String s1 = "ACTGACG";
String s2 = "TGACGAC";
String ss;
ss = s1.concat(s1);
// int p=ss.indexOf(s2);
if (s1.length() == s2.length() && ss.indexOf(s2) > 0) {
StdOut.println("Yes!");
} else {
StdOut.println("NO!");
StdOut.println(ss.indexOf(s2, ss.indexOf(s2)) + " "
+ ss.indexOf(s2));
}
//测试mystery(s)
ss="0123456789";
String a =mystery(ss);
StdOut.println("a="+a);
}
}
/*************************************************************************
* 1.2.9
*
*
* Compilation: javac BinarySearch.java
* Execution: java BinarySearch whitelist.txt < input.txt
* Data files: http://algs4.cs.princeton.edu/11model/tinyW.txt
* http://algs4.cs.princeton.edu/11model/tinyT.txt
* http://algs4.cs.princeton.edu/11model/largeW.txt
* http://algs4.cs.princeton.edu/11model/largeT.txt
*
* % java BinarySearch tinyW.txt < tinyT.txt
* 50
* 99
* 13
*
* % java BinarySearch largeW.txt < largeT.txt | more
* 499569
* 984875
* 295754
* 207807
* 140925
* 161828
* [367,966 total values]
*
*************************************************************************/
import java.util.s;
/**
* The BinarySearch class provides a static method for binary searching
* for an integer in a sorted array of integers.
*
* The rank operations takes logarithmic time in the worst case.
*
* For additional documentation, see
* href="http://algs4.cs.princeton.edu/11model">Section 1.1 of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class BinarySearch3 {
/**
* This class should not be instantiated.
*/
/**
* Searches for the integer key in the sorted array a[].
*
* @param key
* the search key
* @param a
* the array of integers, must be sorted in ascending order
* @return index of key in array a[] if present; -1 if not present
*/
public static int rank(int key, int[] a, Counter counter) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) {
hi = mid - 1;
counter.increment();
StdOut.println("
} else if (key > a[mid]) {
lo = mid + 1;
counter.increment();
StdOut.println(">c="+counter.tally());
} else {
StdOut.println("c="+counter.tally());
return mid;
}
}
return -1;
}
/**
* Reads in a sequence of integers from the whitelist file, specified as a
* command-line argument. Reads in integers from standard input and prints
* to standard output those integers that do *not* appear in the file.
*/
public static void main(String[] args) {
// read the integers from a file
In in = new In("LargeW");
int[] whitelist = in.readAllInts();
Counter counter = new Counter("counter");
// sort the array
s.sort(whitelist);
StdOut.println(whitelist.length);
// read integer key from standard input; print if not in whitelist
while (!StdIn.isEmpty()) {
int key = StdIn.readInt();
if (rank(key, whitelist, counter) == -1)
StdOut.println(key);
}
}
}
/*
* 1.2.10 编写一个VisualCounter类，支持加一和减一操作。它的构造函数接受两个参数N和max，
* 其中N指定了操作的最大次数，max指定了计数器的最大绝对值。作为副作用，用图像显示每次计数器变化后的值。
*/
public class VisualCounter {
private int count;
private int maxOperation;
private int val;// Record value of the Counter
private int maxVal;
private int x = 0;
public VisualCounter(int N, int max) {
maxOperation = N;
maxVal = max;
StdDraw.setXscale(0, N);
StdDraw.setYscale(-max, max);
StdDraw.setPenRadius(0.005);
// TODO Auto-generated constructor stub
}
// current value
/**
* Initializes a new counter starting at 0, with the given id.
*
* @param id
* the name of the counter
*/
/**
* Increments the counter by 1.
*/
public void increment() {
if (count < maxOperation && val < maxVal) {
count++;
val++;
x++;
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.point(x, val);
}
}
/**
* decrement the counter by 1.
*/
public void decrement() {
if (count < maxOperation && val > -maxVal) {
count++;
val--;
x++;
StdDraw.setPenColor(StdDraw.RED);
StdDraw.point(x, val);
}
}
/**
* Returns the current count.
*/
public int tally() {
return count;
}
/**
* Returns a string representation of this counter
*/
public String toString() {
return count + " ";
}
public static void main(String[] args) {
VisualCounter VC = new VisualCounter(2000, 1000);
for (int i = 0; i < 2000; i++) {
if (i / 1000 == 1)
VC.decrement();
else
VC.increment();
}
StdOut.println(VC.tally());
}
}
/*
* 1.2.11根据Date的API实现SmartDate类型在日期非法时抛出一个异常
* 1.2.12为SmartDate添加一个方法dayofWeek()，为日期返回一个星期。
* 1.2.19字符串解析。
*/
public class SmartDate implements Datable {
private final int month;
private final int day;
private final int year;
public int month() {
return month;
}
public int day() {
return day;
}
public int year() {
return year;
}
/*
* 原理：蔡勒公式: W={[C/4]-2C+y+[y/4]+[26(m+1)/10]+d-1}%7 （其中[ ]为取整符号）
* 其中,W是所求日期的星期数.如果求得的数大于7,可以减去7的倍数,直到余数小于7为止.c是公元年份
* 的前两位数字,y是已知公元年份的后两位数字;m是月数,d是日数.方括[ ]表示只截取该数的整数部分。
*/
public String dayofWeek() {
int w = (year / 100 / 4 - 2 * (year / 100) + year % 100 + year % 100
/ 4 + 26 * (month + 1) / 10 + day - 1) % 7;
switch (w) {
case 1:
return "Monday";
case 2:
return "Tuseday";
case 3:
return "Wednesday";
case 4:
return "Thursday";
case 5:
return "Friday";
case 6:
return "Saturday";
default:
return "Sunday";
}
}
private static boolean isLeapYear(int y) {
return ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0);
}
private boolean isIllegal(int m, int d, int y) {
if (y < 0 || d < 1 || d > 31)
return false;
if (m > 12 || m < 0)
return false;
int[] monthofday = { 0, 31, -1, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
if (isLeapYear(y)) {
monthofday[2] = 29;
} else {
monthofday[2] = 28;
}
if (d > monthofday[m])
return false;
else
return true;
}
public SmartDate(int m, int d, int y) {
if (!isIllegal(m, d, y)) {
throw new IllegalArgumentException("Illegal date");
} else {
month = m;
day = d;
year = y;
}
}
public String toString() {
return (month() + "/" + day() + "/" + year());
}
/*
* 大于返回1，等于返回0，小于返回-1；
*/
public int comparaTo(SmartDate that){
if(this.year()==that.year()&&this.month()==that.month()&&this.day()==that.day()) return 0;
if(this.year()>that.year()) return 1;
if(this.month()>that.month()) return 1;
if(this.day()>that.day()) return 1;
return -1;
}
public boolean equals(Object x) {
if (this == x)
return true;
if (x == null)
return false;
if (this.getClass() != x.getClass())
return false;
SmartDate that = (SmartDate) x;
if (this.day != that.day)
return false;
if (this.month != that.month)
return false;
if (this.year != that.year)
return false;
return true;
}
}
/*
* 1.2.13 实现Transaction模版
* 1.2.14 实现Transaction模版equals()方法
* 1.2.19 字符串解析。
*/
public class Transaction {
private String who;
private SmartDate when;
private double amount;
public Transaction(String who, SmartDate when, double amount) {
// TODO Auto-generated constructor stub
if (who == null)
throw new IllegalArgumentException("Illegal date");
this.who = who;
this.when = when;
this.amount = amount;
}
public String toString() {
return (who + " " + when.toString() + " " + amount);
}
public String getWho() {
return who;
}
public void setWho(String who) {
this.who = who;
}
public SmartDate getWhen() {
return when;
}
public void setWhen(SmartDate when) {
this.when = when;
}
public double getAmount() {
return amount;
}
public void setAmount(double amount) {
this.amount = amount;
}
public boolean equals(Object x) {
if (this == x)
return true;
if (x == null)
return false;
if (this.getClass() != x.getClass())
return false;
Transaction that = (Transaction) x;
if (this.who !=that.who)
return false;
if (this.when != that.when)
return false;
if (this.amount != that.amount)
return false;
return true;
}
public int compareTo(Transaction that)
{
return this.when.comparaTo(that.when);
}
public int hashCode(){
return this.toString().hashCode();
}
}
/*
* 1.2.16 有理数，实现有理数的加减乘除。
* 1.2.17 有理数的健壮性，使用断言来防止溢出
*
*/
public class Rational implements Comparable
private int num;// 分子
private int den;// 分母
private int INT_max = 2147483647;
private int INT_min = -2147483647;
private static Rational zero = new Rational(0, 1);
public Rational(int numerator, int denominator) {
// TODO Auto-generated constructor stub
if (denominator == 0) {
throw new RuntimeException("Denominator is zero");
}
int g = gcd(numerator, denominator);
num = numerator / g;
den = denominator / g;
if (den < 0) {
den = -den;
num = -num;
}
}
public int numerator() {
return num;
}
public int denominator() {
return den;
}
private int gcd(int numerator, int denominator) {
if (numerator < 0)
numerator = -numerator;
if (denominator < 0)
denominator = -denominator;
if (denominator == 0)
return numerator;
return gcd(denominator, numerator % denominator);
}
/*
* 计算最小公倍数
*/
private int lcm(int m, int n) {
if (m < 0)
m = -m;
if (n < 0)
n = -n;
if (n == 0)
return m;
else {
int g = gcd(m, n);
assert is_overflow_times(m,n/g):"lcm times overflow";
return m * (n / g);
}
}
public double todouble() {
return (double) num / den;
}
public String toString() {
if (den == 1)
return num + "";
return num + "/" + den;
}
/*
* (non-Javadoc)
*
* @see java.lang.Comparable#compareTo(java.lang.Object) 大于返回1，小于返回-1，等于返回0；
*/
public int compareTo(Rational that) {
// TODO Auto-generated method stub
int lhs = this.num * that.den;
int rhs = this.den * that.num;
if (lhs < rhs)
return -1;
if (lhs > rhs)
return 1;
return 0;
}
public boolean equals(Object Y) {
if (Y == null)
return false;
if (Y.getClass() != this.getClass())
return false;
Rational b = (Rational) Y;
return this.compareTo(b) == 0;
}
/*
* 判断加法溢出,如果溢出返回ture,不溢出返回flase;
*/
private boolean is_overflow_plus(int a, int b) {
return a >= 0 ? INT_max - a > b : INT_min - a < b;
}
/*
* 判断乘法溢出,如果溢出返回ture,不溢出返回flase;
* *
*/
private boolean is_overflow_times(int a, int b) {
if(a<0) a=-a;
if(b<0) b=-b;
if (a == 0||b==0)
return false;
else
return INT_max / a > b;
}
public Rational times(Rational that) {
Rational c = new Rational(this.num, that.den);
Rational d = new Rational(that.num, this.den);
assert is_overflow_times(c.num , d.num):"times overflow";
assert is_overflow_times(c.den , d.den):"times overflow";
return new Rational(c.num * d.num, c.den * d.den);
}
public Rational plus(Rational that) {
if (this.compareTo(zero) == 0) {
return that;
}
if (that.compareTo(zero) == 0) {
return this;
}
int f = gcd(this.num, that.num);
int g = gcd(this.den, that.den);
assert is_overflow_plus((this.num / f) * (that.den / g), (that.num / f)
* (this.den / g)) : "plus overflow";
Rational s = new Rational((this.num / f) * (that.den / g)
+ (that.num / f) * (this.den / g), lcm(this.den, that.den));
s.num = s.num * f;
return s;
}
public Rational minus(Rational that) {
Rational temp = new Rational(-that.num, that.den);
return this.plus(temp);
}
public Rational divides(Rational that) {
Rational temp = new Rational(that.den, that.num);
return this.times(temp);
}
/*
* eclipse中开启断言选择菜单：Run ---> Run... ---> 选择 Arguments 选项卡
* 在 VM arguments 文本框中输入： -ea 注意 中间没有空格，如果输入 -da 表示禁止断言。
* 然后关闭该窗口，提示保存，然后保存就开启了断言。
*/
public static void main(String[] args) {
// boolean isOk = 1<2;
// assert isOk:"nos";
// System.out.println("程序正常");
Rational a=new Rational(3,214748);
StdOut.println("a="+a.toString());
Rational b=new Rational(4,214748);
StdOut.println("b="+b.toString());
StdOut.println(a.compareTo(b));
StdOut.println("a等于b?"+a.equals(b));
StdOut.println("a*b="+a.times(b).toString());
StdOut.println("a+b="+a.plus(b).toString());
StdOut.println("a-b="+a.minus(b).toString());
StdOut.println("a/b="+a.divides(b).toString());
}
}
本文来源：https://www.2haoxitong.net/k/doc/65101041f78a6529657d5330.html
文档为doc格式