Java/Collections Data Structure/Algorithms
Содержание
- 1 Anagrams
- 2 Compute prime numbers
- 3 Compute the area of a triangle using Heron"s Formula
- 4 Fibonacci
- 5 Find connections using a depth-first search
- 6 Find connections using hill climbing.
- 7 Find optimal solution using least-cost
- 8 Find the lost keys
- 9 Hanoi puzzle
- 10 Print a table of fahrenheit and celsius temperatures 1
- 11 Print a table of fahrenheit and celsius temperatures 2
- 12 Print a table of Fahrenheit and Celsius temperatures 3
- 13 Sieve
- 14 Soundex - the Soundex Algorithm, as described by Knuth
Anagrams
import java.io.IOException;
public class AnagramApp {
static int size;
static int count;
static char[] charArray;
public static void main(String[] args) throws IOException {
String input = "Java Source and Support";
size = input.length();
count = 0;
charArray = new char[size];
for (int j = 0; j < size; j++)
charArray[j] = input.charAt(j);
doAnagram(size);
}
public static void doAnagram(int newSize) {
int limit;
if (newSize == 1) // if too small, return;
return;
// for each position,
for (int i = 0; i < newSize; i++) {
doAnagram(newSize - 1); // anagram remaining
if (newSize == 2) // if innermost,
display();
rotate(newSize); // rotate word
}
}
// rotate left all chars from position to end
public static void rotate(int newSize) {
int i;
int position = size - newSize;
// save first letter
char temp = charArray[position];
//shift others left
for (i = position + 1; i < size; i++)
charArray[i - 1] = charArray[i];
//put first on right
charArray[i - 1] = temp;
}
public static void display() {
System.out.print(++count + " ");
for (int i = 0; i < size; i++)
System.out.print(charArray[i]);
System.out.println();
}
}
Compute prime numbers
/* Compute prime numbers, after Knuth, Vol 1, Sec 1.3.2, Alg. "P".
* Unlike Knuth, I don"t build table formatting into
* computational programs; output is one per line.
* <p>
* Note that there may be more efficient algorithms for finding primes.
* Consult a good book on numerical algorithms.
* @author Ian Darwin
*/
public class Primes {
/** The default stopping point for primes */
public static final long DEFAULT_STOP = 4294967295L;
/** The first prime number */
public static final int FP = 2;
static int MAX = 10000;
public static void main(String[] args) {
long[] prime = new long[MAX];
long stop = DEFAULT_STOP;
if (args.length == 1) {
stop = Long.parseLong(args[0]);
}
prime[1] = FP; // P1 (ignore prime[0])
long n = FP+1; // odd candidates
int j = 1; // numberFound
boolean isPrime = true; // for 3
do {
if (isPrime) {
if (j == MAX-1) {
// Grow array dynamically if needed
long[] np = new long[MAX * 2];
System.arraycopy(prime, 0, np, 0, MAX);
MAX *= 2;
prime = np;
}
prime[++j] = n; // P2
isPrime = false;
}
n += 2; // P4
for (int k = 2; k <= j && k < MAX; k++) { // P5, P6, P8
long q = n / prime[k];
long r = n % prime[k];
if (r == 0) {
break;
}
if (q <= prime[k]) { // P7
isPrime = true;
break;
}
}
} while (n < stop); // P3
for (int i=1; i<=j; i++)
System.out.println(prime[i]);
}
}
Compute the area of a triangle using Heron"s Formula
/** Compute the area of a triangle using Heron"s Formula.
* Code and values from Prof W. Kahan and Joseph D. Darcy.
* See http://www.cs.berkeley.edu/~wkahan/JAVAhurt.pdf.
* Derived from listing in Rick Grehan"s Java Pro article (October 1999).
* Simplified and reformatted by Ian Darwin.
*/
public class Heron {
public static void main(String[] args) {
// Sides for triangle in float
float af, bf, cf;
float sf, areaf;
// Ditto in double
double ad, bd, cd;
double sd, aread;
// Area of triangle in float
af = 12345679.0f;
bf = 12345678.0f;
cf = 1.01233995f;
sf = (af+bf+cf)/2.0f;
areaf = (float)Math.sqrt(sf * (sf - af) * (sf - bf) * (sf - cf));
System.out.println("Single precision: " + areaf);
// Area of triangle in double
ad = 12345679.0;
bd = 12345678.0;
cd = 1.01233995;
sd = (ad+bd+cd)/2.0d;
aread = Math.sqrt(sd * (sd - ad) * (sd - bd) * (sd - cd));
System.out.println("Double precision: " + aread);
}
}
Fibonacci
/*
* Copyright (c) 2000 David Flanagan. All rights reserved.
* This code is from the book Java Examples in a Nutshell, 2nd Edition.
* It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
* You may study, use, and modify it for any non-commercial purpose.
* You may distribute it non-commercially as long as you retain this notice.
* For a commercial use license, or to purchase the book (recommended),
* visit http://www.davidflanagan.ru/javaexamples2.
*/
/**
* This program prints out the first 20 numbers in the Fibonacci sequence. Each
* term is formed by adding together the previous two terms in the sequence,
* starting with the terms 1 and 1.
*/
public class Fibonacci {
public static void main(String[] args) {
int n0 = 1, n1 = 1, n2; // Initialize variables
System.out.print(n0 + " " + // Print first and second terms
n1 + " "); // of the series
for (int i = 0; i < 18; i++) { // Loop for the next 18 terms
n2 = n1 + n0; // Next term is sum of previous two
System.out.print(n2 + " "); // Print it out
n0 = n1; // First previous becomes 2nd previous
n1 = n2; // And current number becomes previous
}
System.out.println(); // Terminate the line
}
}
Find connections using a depth-first search
/*
* Chapter 10 - AI-Based Problem Solving The Art of Java by Herbert Schildt and
* James Holmes McGraw-Hill/Osborne 2003
*
*/
//The entire depth-first search program follows:
//Find connections using a depth-first search.
import java.util.*;
import java.io.*;
//Flight information.
class FlightInfo {
String from;
String to;
int distance;
boolean skip; // used in backtracking
FlightInfo(String f, String t, int d) {
from = f;
to = t;
distance = d;
skip = false;
}
}
public class Depth {
final int MAX = 100; // maximum number of connections
// This array holds the flight information.
FlightInfo flights[] = new FlightInfo[MAX];
int numFlights = 0; // number of entries in flight array
Stack btStack = new Stack(); // backtrack stack
public static void main(String args[]) {
String to, from;
Depth ob = new Depth();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ob.setup();
try {
System.out.print("From? ");
from = br.readLine();
System.out.print("To? ");
to = br.readLine();
ob.isflight(from, to);
if (ob.btStack.size() != 0)
ob.route(to);
} catch (IOException exc) {
System.out.println("Error on input.");
}
}
//Initialize the flight database.
void setup() {
addFlight("New York", "Chicago", 900);
addFlight("Chicago", "Denver", 1000);
addFlight("New York", "Toronto", 500);
addFlight("New York", "Denver", 1800);
addFlight("Toronto", "Calgary", 1700);
addFlight("Toronto", "Los Angeles", 2500);
addFlight("Toronto", "Chicago", 500);
addFlight("Denver", "Urbana", 1000);
addFlight("Denver", "Houston", 1000);
addFlight("Houston", "Los Angeles", 1500);
addFlight("Denver", "Los Angeles", 1000);
}
//Put flights into the database.
void addFlight(String from, String to, int dist) {
if (numFlights < MAX) {
flights[numFlights] = new FlightInfo(from, to, dist);
numFlights++;
} else
System.out.println("Flight database full.\n");
}
// Show the route and total distance.
void route(String to) {
Stack rev = new Stack();
int dist = 0;
FlightInfo f;
int num = btStack.size();
// Reverse the stack to display route.
for (int i = 0; i < num; i++)
rev.push(btStack.pop());
for (int i = 0; i < num; i++) {
f = (FlightInfo) rev.pop();
System.out.print(f.from + " to ");
dist += f.distance;
}
System.out.println(to);
System.out.println("Distance is " + dist);
}
/*
* If there is a flight between from and to, return the distance of flight;
* otherwise, return 0.
*/
int match(String from, String to) {
for (int i = numFlights - 1; i > -1; i--) {
if (flights[i].from.equals(from) && flights[i].to.equals(to)
&& !flights[i].skip) {
flights[i].skip = true; // prevent reuse
return flights[i].distance;
}
}
return 0; // not found
}
// Given from, find any connection.
FlightInfo find(String from) {
for (int i = 0; i < numFlights; i++) {
if (flights[i].from.equals(from) && !flights[i].skip) {
FlightInfo f = new FlightInfo(flights[i].from, flights[i].to,
flights[i].distance);
flights[i].skip = true; // prevent reuse
return f;
}
}
return null;
}
// Determine if there is a route between from and to.
void isflight(String from, String to) {
int dist;
FlightInfo f;
// See if at destination.
dist = match(from, to);
if (dist != 0) {
btStack.push(new FlightInfo(from, to, dist));
return;
}
// Try another connection.
f = find(from);
if (f != null) {
btStack.push(new FlightInfo(from, to, f.distance));
isflight(f.to, to);
} else if (btStack.size() > 0) {
// Backtrack and try another connection.
f = (FlightInfo) btStack.pop();
isflight(f.from, f.to);
}
}
}
Find connections using hill climbing.
/*
The Art of Java
by Herbert Schildt and James Holmes
McGraw-Hill/Osborne ? 2003
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
//Flight information.
class FlightInfo {
String from;
String to;
int distance;
boolean skip; // used in backtracking
FlightInfo(String f, String t, int d) {
from = f;
to = t;
distance = d;
skip = false;
}
}
public class Hill {
final int MAX = 100;
// This array holds the flight information.
FlightInfo flights[] = new FlightInfo[MAX];
int numFlights = 0; // number of entries in flight array
Stack btStack = new Stack(); // backtrack stack
public static void main(String args[]) {
String to, from;
Hill ob = new Hill();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ob.setup();
try {
System.out.print("From? ");
from = br.readLine();
System.out.print("To? ");
to = br.readLine();
ob.isflight(from, to);
if (ob.btStack.size() != 0)
ob.route(to);
} catch (IOException exc) {
System.out.println("Error on input.");
}
}
// Initialize the flight database.
void setup() {
addFlight("New York", "Chicago", 900);
addFlight("Chicago", "Denver", 1000);
addFlight("New York", "Toronto", 500);
addFlight("New York", "Denver", 1800);
addFlight("Toronto", "Calgary", 1700);
addFlight("Toronto", "Los Angeles", 2500);
addFlight("Toronto", "Chicago", 500);
addFlight("Denver", "Urbana", 1000);
addFlight("Denver", "Houston", 1000);
addFlight("Houston", "Los Angeles", 1500);
addFlight("Denver", "Los Angeles", 1000);
}
// Put flights into the database.
void addFlight(String from, String to, int dist) {
if (numFlights < MAX) {
flights[numFlights] = new FlightInfo(from, to, dist);
numFlights++;
} else
System.out.println("Flight database full.\n");
}
// Show the route and total distance.
void route(String to) {
Stack rev = new Stack();
int dist = 0;
FlightInfo f;
int num = btStack.size();
// Reverse the stack to display route.
for (int i = 0; i < num; i++)
rev.push(btStack.pop());
for (int i = 0; i < num; i++) {
f = (FlightInfo) rev.pop();
System.out.print(f.from + " to ");
dist += f.distance;
}
System.out.println(to);
System.out.println("Distance is " + dist);
}
/*
* If there is a flight between from and to, return the distance of flight;
* otherwise, return 0.
*/
int match(String from, String to) {
for (int i = numFlights - 1; i > -1; i--) {
if (flights[i].from.equals(from) && flights[i].to.equals(to)
&& !flights[i].skip) {
flights[i].skip = true; // prevent reuse
return flights[i].distance;
}
}
return 0; // not found
}
// Given from, find the farthest away connection.
FlightInfo find(String from) {
int pos = -1;
int dist = 0;
for (int i = 0; i < numFlights; i++) {
if (flights[i].from.equals(from) && !flights[i].skip) {
// Use the longest flight.
if (flights[i].distance > dist) {
pos = i;
dist = flights[i].distance;
}
}
}
if (pos != -1) {
flights[pos].skip = true; // prevent reuse
FlightInfo f = new FlightInfo(flights[pos].from, flights[pos].to,
flights[pos].distance);
return f;
}
return null;
}
// Determine if there is a route between from and to.
void isflight(String from, String to) {
int dist;
FlightInfo f = null;
// See if at destination.
dist = match(from, to);
if (dist != 0) {
btStack.push(new FlightInfo(from, to, dist));
return;
}
// Try another connection. f = find(from);
if (f != null) {
btStack.push(new FlightInfo(from, to, f.distance));
isflight(f.to, to);
} else if (btStack.size() > 0) {
// Backtrack and try another connection.
f = (FlightInfo) btStack.pop();
isflight(f.from, f.to);
}
}
}
Find optimal solution using least-cost
/*
* Chapter 10 - AI-Based Problem Solving The Art of Java by Herbert Schildt and
* James Holmes McGraw-Hill/Osborne ? 2003
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
// Flight information.
class FlightInfo {
String from;
String to;
int distance;
boolean skip; // used in backtracking
FlightInfo(String f, String t, int d) {
from = f;
to = t;
distance = d;
skip = false;
}
}
public class Optimal {
final int MAX = 100;
// This array holds the flight information.
FlightInfo flights[] = new FlightInfo[MAX];
int numFlights = 0; // number of entries in flight array
Stack btStack = new Stack(); // backtrack stack
Stack optimal; // holds optimal solution
int minDist = 10000;
public static void main(String args[]) {
String to, from;
Optimal ob = new Optimal();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
boolean done = false;
FlightInfo f;
ob.setup();
try {
System.out.print("From? ");
from = br.readLine();
System.out.print("To? ");
to = br.readLine();
do {
ob.isflight(from, to);
if (ob.btStack.size() == 0)
done = true;
else {
ob.route(to);
ob.btStack = new Stack();
}
} while (!done);
// Display optimal solution.
if (ob.optimal != null) {
System.out.println("Optimal solution is: ");
int num = ob.optimal.size();
for (int i = 0; i < num; i++) {
f = (FlightInfo) ob.optimal.pop();
System.out.print(f.from + " to ");
}
System.out.println(to);
System.out.println("Distance is " + ob.minDist);
}
} catch (IOException exc) {
System.out.println("Error on input.");
}
}
// Initialize the flight database.
void setup() {
addFlight("New York", "Chicago", 900);
addFlight("Chicago", "Denver", 1000);
addFlight("New York", "Toronto", 500);
addFlight("New York", "Denver", 1800);
addFlight("Toronto", "Calgary", 1700);
addFlight("Toronto", "Los Angeles", 2500);
addFlight("Toronto", "Chicago", 500);
addFlight("Denver", "Urbana", 1000);
addFlight("Denver", "Houston", 1000);
addFlight("Houston", "Los Angeles", 1500);
addFlight("Denver", "Los Angeles", 1000);
}
// Put flights into the database.
void addFlight(String from, String to, int dist) {
if (numFlights < MAX) {
flights[numFlights] = new FlightInfo(from, to, dist);
numFlights++;
} else
System.out.println("Flight database full.\n");
}
// Save shortest route.
void route(String to) {
int dist = 0;
FlightInfo f;
int num = btStack.size();
Stack optTemp = new Stack();
for (int i = 0; i < num; i++) {
f = (FlightInfo) btStack.pop();
optTemp.push(f); // save route
dist += f.distance;
}
// If shorter, keep this route
if (minDist > dist) {
optimal = optTemp;
minDist = dist;
}
}
/*
* If there is a flight between from and to, return the distance of flight;
* otherwise, return 0.
*/
int match(String from, String to) {
for (int i = numFlights - 1; i > -1; i--) {
if (flights[i].from.equals(from) && flights[i].to.equals(to)
&& !flights[i].skip) {
flights[i].skip = true; // prevent reuse
return flights[i].distance;
}
}
return 0; // not found
}
// Given from, find any connection using least-cost.
FlightInfo find(String from) {
int pos = -1;
int dist = 10000; // longer than longest route
for (int i = 0; i < numFlights; i++) {
if (flights[i].from.equals(from) && !flights[i].skip) {
// Use the shortest flight.
if (flights[i].distance < dist) {
pos = i;
dist = flights[i].distance;
}
}
}
if (pos != -1) {
flights[pos].skip = true; // prevent reuse
FlightInfo f = new FlightInfo(flights[pos].from, flights[pos].to,
flights[pos].distance);
return f;
}
return null;
}
// Determine if there is a route between from and to.
void isflight(String from, String to) {
int dist;
FlightInfo f;
// See if at destination.
dist = match(from, to);
if (dist != 0) {
btStack.push(new FlightInfo(from, to, dist));
return;
}
// Try another connection.
f = find(from);
if (f != null) {
btStack.push(new FlightInfo(from, to, f.distance));
isflight(f.to, to);
} else if (btStack.size() > 0) {
// Backtrack and try another connection.
f = (FlightInfo) btStack.pop();
isflight(f.from, f.to);
}
}
}
Find the lost keys
/*
*
* Chapter 10 - AI-Based Problem Solving The Art of Java by Herbert Schildt and
* James Holmes McGraw-Hill/Osborne 2003
*/
import java.util.Stack;
//Room information.
class RoomInfo {
String from;
String to;
boolean skip;
RoomInfo(String f, String t) {
from = f;
to = t;
skip = false;
}
}
public class Keys {
final int MAX = 100;
// This array holds the room information.
RoomInfo room[] = new RoomInfo[MAX];
int numRooms = 0; // number of rooms
Stack btStack = new Stack(); // backtrack stack
public static void main(String args[]) {
String to, from;
Keys ob = new Keys();
ob.setup();
from = "front_door";
to = "keys";
ob.iskeys(from, to);
if (ob.btStack.size() != 0)
ob.route(to);
}
// Initialize the room database.
void setup() {
addRoom("front_door", "lr");
addRoom("lr", "bath");
addRoom("lr", "hall");
addRoom("hall", "bd1");
addRoom("hall", "bd2");
addRoom("hall", "mb");
addRoom("lr", "kitchen");
addRoom("kitchen", "keys");
}
// Put rooms into the database.
void addRoom(String from, String to) {
if (numRooms < MAX) {
room[numRooms] = new RoomInfo(from, to);
numRooms++;
} else
System.out.println("Room database full.\n");
}
// Show the route.
void route(String to) {
Stack rev = new Stack();
RoomInfo r;
int num = btStack.size();
// Reverse the stack to display path.
for (int i = 0; i < num; i++)
rev.push(btStack.pop());
for (int i = 0; i < num; i++) {
r = (RoomInfo) rev.pop();
System.out.print(r.from + " to ");
}
System.out.println(to);
}
/*
* If there is a path between from and to, return true, otherwise return
* false.
*/
boolean match(String from, String to) {
for (int i = numRooms - 1; i > -1; i--) {
if (room[i].from.equals(from) && room[i].to.equals(to)
&& !room[i].skip) {
room[i].skip = true; // prevent reuse
return true;
}
}
return false; // not found
}
// Given from, find any path.
RoomInfo find(String from) {
for (int i = 0; i < numRooms; i++) {
if (room[i].from.equals(from) && !room[i].skip) {
RoomInfo r = new RoomInfo(room[i].from, room[i].to);
room[i].skip = true; // prevent reuse
return r;
}
}
return null;
}
// Determine if there is a path between from and to.
void iskeys(String from, String to) {
int dist;
RoomInfo r;
// See if at destination.
if (match(from, to)) {
btStack.push(new RoomInfo(from, to));
return;
}
// Try another connection.
r = find(from);
if (r != null) {
btStack.push(new RoomInfo(from, to));
iskeys(r.to, to);
} else if (btStack.size() > 0) {
// Backtrack and try another connection.
r = (RoomInfo) btStack.pop();
iskeys(r.from, r.to);
}
}
}
Hanoi puzzle
public class HanoiTower {
static int nDisks = 3;
public static void main(String[] args) {
hanoiTower(nDisks, "A", "B", "C");
}
public static void hanoiTower(int topN, char src, char inter, char dest) {
if (topN == 1)
System.out.println("Disk 1 from " + src + " to " + dest);
else {
// src to inter
hanoiTower(topN - 1, src, dest, inter);
// move bottom
System.out.println("Disk " + topN + " from " + src + " to " + dest);
//inter to dest
hanoiTower(topN - 1, inter, src, dest);
}
}
}
Print a table of fahrenheit and celsius temperatures 1
/* Print a table of Fahrenheit and Celsius temperatures
* @author Ian F. Darwin, http://www.darwinsys.ru/
* @version $Id: TempConverter.java,v 1.10 2004/03/16 01:43:31 ian Exp $
*/
public class TempConverter {
public static void main(String[] args) {
TempConverter t = new TempConverter();
t.start();
t.data();
t.end();
}
protected void start() {
}
protected void data() {
for (int i=-40; i<=120; i+=10) {
float c = (i-32)*(5f/9);
print(i, c);
}
}
protected void print(float f, float c) {
System.out.println(f + " " + c);
}
protected void end() {
}
}
Print a table of fahrenheit and celsius temperatures 2
import java.text.*;
/* Print a table of fahrenheit and celsius temperatures, a bit more neatly.
* @author Ian F. Darwin, http://www.darwinsys.ru/
* @version $Id: TempConverter2.java,v 1.6 2004/03/07 02:50:49 ian Exp $
*/
public class TempConverter2 extends TempConverter {
protected DecimalFormat df;
public static void main(String[] args) {
TempConverter t = new TempConverter2();
t.start();
t.data();
t.end();
}
// Constructor
public TempConverter2() {
df = new DecimalFormat("#0.00");
}
protected void print(float f, float c) {
System.out.println(df.format(f) + " " + df.format(c));
}
protected void start() {
System.out.println("Fahr Centigrade.");
}
protected void end() {
System.out.println("-------------------");
}
}
class TempConverter {
public static void main(String[] args) {
TempConverter t = new TempConverter();
t.start();
t.data();
t.end();
}
protected void start() {
}
protected void data() {
for (int i=-40; i<=120; i+=10) {
float c = (i-32)*(5f/9);
print(i, c);
}
}
protected void print(float f, float c) {
System.out.println(f + " " + c);
}
protected void end() {
}
}
Print a table of Fahrenheit and Celsius temperatures 3
import java.text.*;
/* Print a table of Fahrenheit and Celsius temperatures, with decimal
* points lined up.
* @author Ian F. Darwin, http://www.darwinsys.ru/
* @version $Id: TempConverter3.java,v 1.4 2004/03/07 02:50:49 ian Exp $
*/
public class TempConverter3 extends TempConverter2 {
protected FieldPosition fp;
protected DecimalFormat dff;
public static void main(String[] args) {
TempConverter t = new TempConverter3();
t.start();
t.data();
t.end();
}
// Constructor
public TempConverter3() {
super();
dff = new DecimalFormat("#0.0");
fp = new FieldPosition(NumberFormat.INTEGER_FIELD);
}
protected void print(float f, float c) {
String fs = dff.format(f, new StringBuffer(), fp).toString();
fs = prependSpaces(4 - fp.getEndIndex(), fs);
String cs = df.format(c, new StringBuffer(), fp).toString();
cs = prependSpaces(4 - fp.getEndIndex(), cs);
System.out.println(fs + " " + cs);
}
protected String prependSpaces(int n, String s) {
String[] res = {
"", " ", " ", " ", " ", " "
};
if (n<res.length)
return res[n] + s;
throw new IllegalStateException("Rebuild with bigger \"res\" array.");
}
}
class TempConverter2 extends TempConverter {
protected DecimalFormat df;
public static void main(String[] args) {
TempConverter t = new TempConverter2();
t.start();
t.data();
t.end();
}
// Constructor
public TempConverter2() {
df = new DecimalFormat("#0.00");
}
protected void print(float f, float c) {
System.out.println(df.format(f) + " " + df.format(c));
}
protected void start() {
System.out.println("Fahr Centigrade.");
}
protected void end() {
System.out.println("-------------------");
}
}
class TempConverter {
public static void main(String[] args) {
TempConverter t = new TempConverter();
t.start();
t.data();
t.end();
}
protected void start() {
}
protected void data() {
for (int i=-40; i<=120; i+=10) {
float c = (i-32)*(5f/9);
print(i, c);
}
}
protected void print(float f, float c) {
System.out.println(f + " " + c);
}
protected void end() {
}
}
Sieve
/*
* Copyright (c) 2000 David Flanagan. All rights reserved.
* This code is from the book Java Examples in a Nutshell, 2nd Edition.
* It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
* You may study, use, and modify it for any non-commercial purpose.
* You may distribute it non-commercially as long as you retain this notice.
* For a commercial use license, or to purchase the book (recommended),
* visit http://www.davidflanagan.ru/javaexamples2.
*/
/**
* This program computes prime numbers using the Sieve of Eratosthenes
* algorithm: rule out multiples of all lower prime numbers, and anything
* remaining is a prime. It prints out the largest prime number less than or
* equal to the supplied command-line argument.
*/
public class Sieve {
public static void main(String[] args) {
// We will compute all primes less than the value specified on the
// command line, or, if no argument, all primes less than 100.
int max = 100; // Assign a default value
try {
max = Integer.parseInt(args[0]);
} // Parse user-supplied arg
catch (Exception e) {
} // Silently ignore exceptions.
// Create an array that specifies whether each number is prime or not.
boolean[] isprime = new boolean[max + 1];
// Assume that all numbers are primes, until proven otherwise.
for (int i = 0; i <= max; i++)
isprime[i] = true;
// However, we know that 0 and 1 are not primes. Make a note of it.
isprime[0] = isprime[1] = false;
// To compute all primes less than max, we need to rule out
// multiples of all integers less than the square root of max.
int n = (int) Math.ceil(Math.sqrt(max)); // See java.lang.Math class
// Now, for each integer i from 0 to n:
// If i is a prime, then none of its multiples are primes,
// so indicate this in the array. If i is not a prime, then
// its multiples have already been ruled out by one of the
// prime factors of i, so we can skip this case.
for (int i = 0; i <= n; i++) {
if (isprime[i]) // If i is a prime,
for (int j = 2 * i; j <= max; j = j + i)
// loop through multiples
isprime[j] = false; // they are not prime.
}
// Now go look for the largest prime:
int largest;
for (largest = max; !isprime[largest]; largest--)
; // empty loop body
// Output the result
System.out.println("The largest prime less than or equal to " + max
+ " is " + largest);
}
}
Soundex - the Soundex Algorithm, as described by Knuth
/*
* Copyright (c) Ian F. Darwin, http://www.darwinsys.ru/, 1996-2002.
* All rights reserved. Software written by Ian F. Darwin and others.
* $Id: LICENSE,v 1.8 2004/02/09 03:33:38 ian Exp $
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS""
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
* Java, the Duke mascot, and all variants of Sun"s Java "steaming coffee
* cup" logo are trademarks of Sun Microsystems. Sun"s, and James Gosling"s,
* pioneering role in inventing and promulgating (and standardizing) the Java
* language and environment is gratefully acknowledged.
*
* The pioneering role of Dennis Ritchie and Bjarne Stroustrup, of AT&T, for
* inventing predecessor languages C and C++ is also gratefully acknowledged.
*/
/**
* Soundex - the Soundex Algorithm, as described by Knuth
* <p>
* This class implements the soundex algorithm as described by Donald
* Knuth in Volume 3 of <I>The Art of Computer Programming</I>. The
* algorithm is intended to hash words (in particular surnames) into
* a small space using a simple model which approximates the sound of
* the word when spoken by an English speaker. Each word is reduced
* to a four character string, the first character being an upper case
* letter and the remaining three being digits. Double letters are
* collapsed to a single digit.
*
* <h2>EXAMPLES</h2>
* Knuth"s examples of various names and the soundex codes they map
* to are:
* <b>Euler, Ellery -> E460
* <b>Gauss, Ghosh -> G200
* <b>Hilbert, Heilbronn -> H416
* <b>Knuth, Kant -> K530
* <b>Lloyd, Ladd -> L300
* <b>Lukasiewicz, Lissajous -> L222
*
* <h2>LIMITATIONS</h2>
* As the soundex algorithm was originally used a <B>long</B> time ago
* in the United States of America, it uses only the English alphabet
* and pronunciation.
* <p>
* As it is mapping a large space (arbitrary length strings) onto a
* small space (single letter plus 3 digits) no inference can be made
* about the similarity of two strings which end up with the same
* soundex code. For example, both "Hilbert" and "Heilbronn" end up
* with a soundex code of "H416".
* <p>
* The soundex() method is static, as it maintains no per-instance
* state; this means you never need to instantiate this class.
*
* @author Perl implementation by Mike Stok (<stok@cybercom.net>) from
* the description given by Knuth. Ian Phillips (<ian@pipex.net>) and
* Rich Pinder (<rpinder@hsc.usc.edu>) supplied ideas and spotted
* mistakes.
* @author Ian Darwin, http://www.darwinsys.ru/ (Java Version)
* @version $Id: Soundex.java,v 1.9 2004/02/23 00:30:49 ian Exp $
*/
public class Soundex {
/* Implements the mapping
* from: AEHIOUWYBFPVCGJKQSXZDTLMNR
* to: 00000000111122222222334556
*/
public static final char[] MAP = {
//A B C D E F G H I J K L M
"0","1","2","3","0","1","2","0","0","2","2","4","5",
//N O P W R S T U V W X Y Z
"5","0","1","2","6","2","3","0","1","0","2","0","2"
};
/** Convert the given String to its Soundex code.
* @return null If the given string can"t be mapped to Soundex.
*/
public static String soundex(String s) {
// Algorithm works on uppercase (mainframe era).
String t = s.toUpperCase();
StringBuffer res = new StringBuffer();
char c, prev = "?";
// Main loop: find up to 4 chars that map.
for (int i=0; i<t.length() && res.length() < 4 &&
(c = t.charAt(i)) != ","; i++) {
// Check to see if the given character is alphabetic.
// Text is already converted to uppercase. Algorithm
// only handles ASCII letters, do NOT use Character.isLetter()!
// Also, skip double letters.
if (c>="A" && c<="Z" && c != prev) {
prev = c;
// First char is installed unchanged, for sorting.
if (i==0)
res.append(c);
else {
char m = MAP[c-"A"];
if (m != "0")
res.append(m);
}
}
}
if (res.length() == 0)
return null;
for (int i=res.length(); i<4; i++)
res.append("0");
return res.toString();
}
/** main */
public static void main(String[] args) {
String[] names = {
"Darwin, Ian",
"Davidson, Greg",
"Darwent, William",
"Derwin, Daemon"
};
for (int i = 0; i< names.length; i++)
System.out.println(Soundex.soundex(names[i]) + " " + names[i]);
}
}
