[Instructions] [Search] [Current] [Changes] [Syllabus] [Handouts] [Outlines] [Labs] [Assignments] [Examples] [Bailey Docs] [SamR Docs] [Tutorial] [API]
Held: Tuesday, March 3, 1998
/** 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[])
Vector
-like object, so we don't explicity refer
to the vector.
/** * Sort all the elements in the subvector between lb and ub. * pre: 0 <= lb <= ub < size() * pre: the elements in the vector are comparable using * a lessEqual method * post: elementAt(lb) <= elementAt(lb+1) <= ... elementAt(ub) * post: no element is added to or removed from the vector */ public void selectionSort(int lb, int ub) { // Variables int index_of_largest; // ... element in subrange // The preconditions will be checked in the following // function call, so we don't check them here // Base case: one element, so it's sorted if (lb == ub) { return; } // Find the index of the largest element in the subrange index_of_largest = indexOfLargest(lb,ub); // Swap that element and the last element swap(index_of_largest, ub); // Sort the rest of the subvector (if there is any) // Note that we don't have to compare ub-1 to lb, since // the preconditions and the base case take care of it. selection_sort(lb,ub-1); } // selectionSort /** * Find the index of the largest element in a subvector * pre: 0 <= lb <= ub < size() * pre: the elements in the vector are comparable using * a lessEqual method * post: returns I s.t. for all i, lb <= i <= ub, * elementAt(I) >= elementAt(i) */ public int indexOfLargest(int lb, int ub) { // Variables int guess; // Current guess as to index of largest // Check the preconditions Assert.pre(lb <= ub, "nonempty subrange"); Assert.pre(0 <= lb, "reasonable starting point"); Assert.pre(ub < size(), "reasonable ending point"); // Make initial guesses guess = lb; // Repeatedly improve our guesses until we've looked at // all the elements for(int i = lb+1; i <= lb; ++i) { if (elementAt(guess).lessEqual(elementAt(i))) { guess = i; } // if } // for // That's it return guess; } // index_of_largest
On to More Sorting Techniques
Back to Recursion Repeated
Outlines:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
Current position in syllabus
[Instructions] [Search] [Current] [Changes] [Syllabus] [Handouts] [Outlines] [Labs] [Assignments] [Examples] [Bailey Docs] [SamR Docs] [Tutorial] [API]
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.
This page may be found at http://www.math.grin.edu/~rebelsky/Courses/CS152/98S/home/rebelsky/public_html/Courses/CS152/98S/Outlines/outline.24.html
Source text last modified Tue Jan 12 11:52:24 1999.
This page generated on Mon Jan 25 09:49:21 1999 by SiteWeaver. Validate this page.
Contact our webmaster at rebelsky@math.grin.edu