public class Analysis
1: import java.util.Scanner;
3: /**
4: * A program to count the operations in two different algorithms for printing
5: * from 1 to N, and use those counts to find a formula for the amount of work
6: * those algorithms do.
7: *
8: * @author Mark Young (A00000000)
9: */
10: public class Analysis {
12: // Maximum number to print to
13: private static final int MAX = 10;
15: public static void main(String[] args) {
16: // create variables
17: Scanner kbd = new Scanner(System.in);
18: int[] vec1 = new int[MAX + 1];
19: int[] opCountStupid = new int[MAX + 1];
20: int[] opCountBetter = new int[MAX + 1];
22: // introduce yourself
23: System.out.print("\n\n"
24: + "This program compares two methods for filling an array "
25: + "with the numbers\nfrom 1 to N. "
26: + "It counts the number of operations required "
27: + "for each method\nfor N running from 0 to " + MAX
28: + ", and then calculates a formula "
29: + "for the amount\nof work required.\n\n");
30: pause(kbd);
32: // get data for the stupid method
33: System.out.print("Filling a array using the Stupid method:\n");
34: for (int i = 0; i <= MAX; ++i) {
35: opCountStupid[i] = fillStupidly(i, vec1);
36: printPositives(vec1);
37: System.out.print("\tTo fill the array stupidly from 1 to " + i
38: + " takes " + opCountStupid[i] + " steps.\n");
39: vec1 = new int[MAX + 1];
40: }
41: pause(kbd);
43: // get data for the intelligent method
44: System.out.print("Filling a array using the Better method:\n");
45: for (int i = 0; i <= MAX; ++i) {
46: opCountBetter[i] = fillIntelligently(i, vec1);
47: printPositives(vec1);
48: System.out.print("\tTo fill the array intelligently from 1 to " + i
49: + " takes " + opCountBetter[i] + " steps.\n");
50: vec1 = new int[MAX + 1];
51: }
52: pause(kbd);
54: // find and report the equation for the stupid method
55: System.out.print("\n\nFinding equation for Stupid:\n");
56: findEquation(opCountStupid);
57: System.out.print("\n\n");
58: pause(kbd);
60: // find and report the equation for the better method
61: System.out.print("\n\nFinding equation for Better:\n");
62: findEquation(opCountBetter);
63: System.out.print("\n\n");
64: pause(kbd);
65: }
67: /**
68: * Stupid algorithm for filling v up with the numbers from 1 to n. Requires
69: * that:
70: * <ul>
71: * <li> n >= 0
72: * <li> v.length >= n
73: * <li> v[0..n-1] all equal zero
74: * </ul>
75: * Given those preconditions, after the method has completed
76: * <ul>
77: * <li> v[0..n-1] set to 1, 2, 3, 4, ..., n (in sequence)
78: * <li> the return value is the number of steps the algorithm took to
79: * achieve that state.
80: * </ul>
81: *
82: * @param upTo the number to fill up to
83: * @param array the array to fill with the numbers
84: * @return number of steps taken to complete the filling
85: */
86: private static int fillStupidly(int upTo, int[] array) {
87: int opCount = 0;
88: int stepANumber, stepCNumber;
90: // Prevent infinite loop!
91: if (upTo < 1) {
92: return 0;
93: }
95: // step 1: print the number 1
96: ++opCount; // "print" (assignment)
97: array[0] = 1;
99: // step 2: repeat
100: do {
101: // step 2a: count how many numbers we've already printed
102: stepANumber = 0;
103: while (stepANumber < array.length) {
104: // comparison
105: if (array[stepANumber] == 0) {
106: break;
107: }
108: ++opCount; // AFTER on THIS OCCASION
109: // because we want to simulate counting
110: // the numbers, and 0 represents that
111: // there is no number there,
112: // so it doesn't get counted
113: ++stepANumber;
114: }
116: // step 2b: if it's N, stop (we're done)
117: ++opCount; // comparison
118: if (stepANumber == upTo) {
119: return opCount;
120: }
122: // step 2c: add 1 to the number from step a
123: ++opCount; // assignment
124: stepCNumber = stepANumber + 1;
126: // step 2d: find the end of the list
127: stepANumber = 0;
128: while (stepANumber < array.length) {
129: // comparison
130: if (array[stepANumber] == 0) {
131: break;
132: }
133: ++opCount; // AFTER on THIS OCCASION
134: // for same reasons as above
135: ++stepANumber;
136: }
138: // step 2e: print the number you got in step c
139: ++opCount; // assignment
140: array[stepANumber] = stepCNumber;
141: } while (true);
142: }
144: /**
145: * Better algorithm for filling v up with the numbers from 1 to n. Requires
146: * that:
147: * <ul>
148: * <li> n >= 0
149: * <li> v.length >= n
150: * </ul>
151: * Given those preconditions, after the method has completed
152: * <ul>
153: * <li> v[0..n-1] set to 1, 2, 3, 4, ..., n (in sequence)
154: * <li> the return value is the number of steps the algorithm took to
155: * achieve that state.
156: * </ul>
157: *
158: * @param upTo the number to fill up to
159: * @param array the array to fill with the numbers
160: * @return number of steps taken to complete the filling
161: */
162: private static int fillIntelligently(int upTo, int[] array) {
163: int opCount = 0;
164: int numToPrint;
166: // step 1: set k to 1
167: ++opCount; // assignment
168: numToPrint = 1;
170: while (true) {
171: // step 2: while k <= n
172: ++opCount; // comparison
173: if (numToPrint > upTo) {
174: return opCount;
175: }
177: // step 2a: print k
178: ++opCount; // assignment
179: array[numToPrint - 1] = numToPrint;
181: // step 2b: add one to k
182: ++opCount; // increment
183: ++numToPrint;
184: }
185: }
187: /**
188: * Print out the non-zero values at the front of an array.
189: *
190: * @param array the array to print numbers from
191: */
192: private static void printPositives(int[] array) {
193: for (int n : array) {
194: if (n > 0) {
195: System.out.print(n + " ");
196: } else {
197: break;
198: }
199: }
200: System.out.println();
201: }
203: /**
204: * Find and print an equation describing the function stored in an array.
205: * The array must be filled in with the values of an integer function such
206: * that values[i] = f(i), and that function must be either constant, linear
207: * or quadratic.
208: *
209: * The method tries to find a formula for the function, and prints out the
210: * actual and predicted values in a table. If they match, it reports the
211: * formula it found. Otherwise it prints a message saying it's none of
212: * those.
213: *
214: * @param values an array holding the values of an int function
215: */
216: public static void findEquation(int[] values) {
217: // try to find a, b and c using:
218: // v[1] = a + b + c
219: // v[2] = 4a + 2b + c
220: // v[3] = 9a + 3b + c
221: // SO, LET
222: // v1 = v[1] == a + b + c
223: // v2 = v[2] - 4 * v1 == -2b + -3c
224: // v3 = v[3] - 9 * v1 == -6b + -8c
225: // v3 -= 3 * v2 == c
226: // v2 += 3 * v3 == -2b
227: // v2 /= -2 == b
228: // v1 -= v2 + v3 == a
230: double v1 = values[1];
231: double v2 = values[2] - 4 * v1;
232: double v3 = values[3] - 9 * v1;
233: v3 -= 3 * v2;
234: v2 += 3 * v3;
235: v2 /= -2;
236: v1 -= v2 + v3;
238: // check if that works!
239: for (int i = 1; i < values.length; ++i) {
240: double value = v3 + i * (v2 + i * v1);
241: System.out.println("\t\tCheck: " + values[i] + " =?= " + value);
242: if (values[i] != value) {
243: System.out.print("\tThe formula is not constant, "
244: + "linear or quadratic!\n");
245: return;
246: }
247: }
248: if (v1 == 0) {
249: if (v2 == 0) {
250: System.out.print("\tThe formula is constant: "
251: + v3 + ".\n");
252: } else {
253: System.out.print("\tThe formula is linear: "
254: + v2 + "N + " + v3 + ".\n");
255: }
256: } else {
257: System.out.print("\tThe formula is quadratic: "
258: + v1 + "N^2 + " + v2 + "N + " + v3 + ".\n");
259: }
260: }
262: /**
263: * Prompt and wait for the user to press the enter key. Uses a Scanner
264: * parameter so that we don't run into the problems that arise from having
265: * multiple Scanners attached to System.in, and also to avoid having a
266: * static Scanner, which might get created when some other program tries to
267: * use findEquation.
268: *
269: * @param kbd the Scanner(System.in) to wait for the enter key on
270: */
271: private static void pause(Scanner kbd) {
272: System.out.print("\nPress enter...");
273: kbd.nextLine();
274: System.out.println();
275: }
277: }