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
- 15 EXAMPLES
- 16 LIMITATIONS
Anagrams
<source lang="java">
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(); }
}
</source>
Compute prime numbers
<source lang="java">
/* 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.*
* 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]); } } </source>
Compute the area of a triangle using Heron"s Formula
<source lang="java">
/** 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); }
}
</source>
Fibonacci
<source lang="java">
/*
* 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 }
}
</source>
Find connections using a depth-first search
<source lang="java">
/*
* 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); } }
}
</source>
Find connections using hill climbing.
<source lang="java">
/* 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); } }
}
</source>
Find optimal solution using least-cost
<source lang="java">
/*
* 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); } }
}
</source>
Find the lost keys
<source lang="java">
/*
* * 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); } }
}
</source>
Hanoi puzzle
<source lang="java">
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); } }
}
</source>
Print a table of fahrenheit and celsius temperatures 1
<source lang="java">
/* 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() { }
}
</source>
Print a table of fahrenheit and celsius temperatures 2
<source lang="java">
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() { }
}
</source>
Print a table of Fahrenheit and Celsius temperatures 3
<source lang="java">
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() { }
}
</source>
Sieve
<source lang="java">
/*
* 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); }
}
</source>
Soundex - the Soundex Algorithm, as described by Knuth
<source lang="java">
/*
* 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 The Art of Computer Programming. 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. **
EXAMPLES
* Knuth"s examples of various names and the soundex codes they map * to are: * Euler, Ellery -> E460 * <b>Gauss, Ghosh -> G200 * <b>Hilbert, Heilbronn -> H416 * <b>Knuth, Kant -> K530 * <b>Lloyd, Ladd -> L300 * <b>Lukasiewicz, Lissajous -> L222 **
LIMITATIONS
* As the soundex algorithm was originally used a <B>long 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]); }
}
</source>