/u2/rebelsky/bin/html2ps. The command I used
to print this was (approximately) % html2ps -D url | psnup -2 | lp
% chgrp my_group directory% chmod 770 directory
sum(1/length(C(char[i]))) is 1
(by the structure of binary trees).
public int minimum_stamps(int price, int[] counts) {
int min = -1; // The minimum
int submin; // The minimum for a smaller price
int[] subcounts = new int[stamp_values.length];
// Counts for smaller price
// Sanity check
if (price == 0) {
for(int i = 0; i < stamp_values.length; ++i) {
counts[i] = 0;
} //for
return 0;
}
// Try each stamp value
for(int i = 0; i < stamp_values.length; ++i) {
if (price >= stamp_values[i]) {
submin = minimum_stamps(price-stamp_values[i],subcounts);
// If it's a valid number of stamps, and "better" than our
// previous best, update our best
if ( (submin > -1) &&
( (submin+1 < min) || (min == -1) ) ) {
min = submin+1;
for(int j = 0; j < stamp_values.length; ++j) {
counts[j] = subcounts[j];
} // for
counts[i] += 1;
} // A better value
} // if the value is smaller than the price
} // for
// That's it, we're done
return min;
} // minimum_stamps
/**
Compute the nth Fibonacci number.
pre: n >= 0
pre: fib(n) <= maximum integer
post: returns the nth fibonacci number
*/
public static int fib(int n) {
// Base case
if ((n == 0) || (n == 1)) {
return 1;
} // base case
// Recursive case
else {
return fib(n-1) + fib(n-2);
} // recursive case
} // fib(n)
/**
Compute the nth Fibonacci number.
pre: n >= 0
pre: fib(n) <= maximum integer
post: returns the nth fibonacci number
*/
public static int newfib(int n) {
int[] solutions = new int[n+1];
// Fill in the intial solutions
solutions[0] = 1;
solutions[1] = 1;
// Fill in the remaining solutions
for(int i = 2; i <=n; ++i) {
solutions[i] = solutions[i-1] + solutions[i-2]
} // for
// That's it
return solutions[n];
} // newfib
/**
Compute the nth Fibonacci number.
pre: n >= 0
pre: fib(n) <= maximum integer
post: returns the nth fibonacci number
*/
public static int newerfib(int n) {
int[] solutions = new int[n+1];
// We'll use 0 to indicate "no solution yet"
for(int i = 0; i <= n; ++i) {
solutions[i] = 0;
}
// Compute the fibonacci using this helper array
return newerfib(n,solutions);
} // newerfib(int)
/**
Compute the nth Fibonacci number.
pre: n >= 0
pre: fib(n) <= maximum integer
pre: solutions.length >= n+1
post: returns the nth fibonacci number
*/
public static int newerfib(int n, int[] solutions) {
// Deal with precomputed solutions. Note that return
// immediately exits the routine, so I don't need an
// else clause.
if (solutions[n] != 0) {
return solutions[n];
}
// Base case
if ((n == 0) || (n == 1)) {
solutions[n] = 1;
} // base case
// Recursive case
else {
solutions[n] = newerfib(n-1,solutions) + newerfib(n-2,solutions);
} // recursive case
return solutions[n];
} // newerfib(int,int[])
Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.
Source text last modified Wed Oct 8 12:40:28 1997.
This page generated on Tue Nov 4 14:21:46 1997 by SiteWeaver.
Contact our webmaster at rebelsky@math.grin.edu