CIS 3020 Part 6 - Revision history

Jka: /* Code to track the moves */

2007-04-25T17:26:37Z

Code to track the moves

2007-04-25T17:26:05Z

Code to track the moves

2007-04-25T17:24:58Z

Code to track the moves

2007-04-25T17:23:51Z

Code to track the moves

2007-04-25T17:22:31Z

Code to Count Moves

2007-04-25T17:10:32Z

Solution

2007-04-25T17:06:56Z

Tower of Hanoi Problem

2007-04-25T16:58:18Z

Doing these calculations faster

2007-04-25T16:41:08Z

Design

2007-04-25T16:21:08Z

Convert to an iterative process (tail recursive)

@@ Line 252: / Line 252: @@
 p3 = destination pole
 </pre>
 ==[[CIS 3020 Part 7]]==

@@ Line 232: / Line 232: @@
 ** Move the n-1 disks from pole two to pole three
 {|
+|
 <pre>
@@ Line 244: / Line 245: @@
+}
 </pre>
-|| valign=top
+||
 <pre>
 n = number of disks to move

@@ Line 231: / Line 231: @@
 ** Move the n<sup>th</sup> disk from pole one to pole three
 ** Move the n-1 disks from pole two to pole three
 <pre>
 void hanoiMoves(int n, int p1, int p2, int p3) {
@@ Line 241: / Line 243: @@
+   }
+}
 </pre>

@@ Line 223: / Line 223: @@
+   }
    return result;
+}
 </pre>

← Older revision		Revision as of 17:10, 25 April 2007
Line 208:		Line 208:
	# Move the n<sup>th</sup> disk from pole 1 to pole 3		# Move the n<sup>th</sup> disk from pole 1 to pole 3
	# Move the n-1 disks from pole 2 to pole 3		# Move the n-1 disks from pole 2 to pole 3
		+	===Code to Count Moves===
		+	* If there is one disk to move, then result is one
		+	* If there are two or more disks to move, then result is:
		+	** Move n-1 disks from pole one to pole two
		+	** Move the n<sup>th</sup> disk from pole one to pole three
		+	** Move the n-1 disks from pole two to pole three
		+	<pre>
		+	int hanoiCount(int n) {
		+	int result;
		+	if (n==1) {
		+	result = 1;
		+	} else {
		+	result = hanoiCount(n-1) + 1 + hanoiCount(n-1);
		+	}
		+	return result;
		+	}
		+	</pre>

← Older revision		Revision as of 17:06, 25 April 2007
Line 203:		Line 203:
	* Moving one disk at a time you are to move all disks from the first pole to the third pole.		* Moving one disk at a time you are to move all disks from the first pole to the third pole.
	* Contraint: No disk can be placed on a smaller disk.		* Contraint: No disk can be placed on a smaller disk.
		+	===Solution===
		+	Break the problem into a set of smaller/simpler problems:
		+	# Move n-1 disks from pole 1 to pole 2
		+	# Move the n<sup>th</sup> disk from pole 1 to pole 3
		+	# Move the n-1 disks from pole 2 to pole 3

← Older revision		Revision as of 16:58, 25 April 2007
Line 198:		Line 198:
	</pre>		</pre>
	NOTE: Double the size of the problem (the exponent n), the number of steps only increases by 1.		NOTE: Double the size of the problem (the exponent n), the number of steps only increases by 1.
		+	* Because doubling the size of the problem (the exponent n) only causes the number of steps to increase by one, we identify the run time as logarithmic. This makes the O() of the algorithm O(log n).
		+	==Tower of Hanoi Problem==
		+	* There are 57 disks of graduated size stacked on the first pole of a set of three poles.
		+	* Moving one disk at a time you are to move all disks from the first pole to the third pole.
		+	* Contraint: No disk can be placed on a smaller disk.

← Older revision		Revision as of 16:41, 25 April 2007
Line 170:		Line 170:
	}		}
	</pre>		</pre>
		+	==Doing these calculations faster==
		+	Consider the case of b<sup>16</sup>. The calculations can be done in just four multiplications rather than fifteen as the preceding methods use. Implementation requires working backwards.
		+	<pre>
		+	public int expt(int b, int n) {
		+	return (fastExpt(b,n));
		+	}
		+
		+	private int fastExpt(int b, int n) {
		+	int result;
		+	if (n<=0) {
		+	result = 1;
		+	} else if (even(n)) {
		+	result = square(fastExpt(b, n/2));
		+	} else {
		+	result = b * fastExpt(b, n-1);
		+	}
		+	return result;
		+	}
		+
		+	private int square (int x) {
		+	return (x*x);
		+	}
		+
		+	private boolean even (int x) {
		+	return (x%2 == 0);
		+	}
		+	</pre>
		+	NOTE: Double the size of the problem (the exponent n), the number of steps only increases by 1.

← Older revision		Revision as of 16:21, 25 April 2007
Line 140:		Line 140:
	** Assumptions: none		** Assumptions: none
	** Relationships: none		** Relationships: none
		+	===Alternative===
		+	* In this approach we keep track of the computed value (product) as we run a counter from n to 0
		+	* Each time we decrement the counter, we multiply the product by the current value of b until the counter reaches 0
		+	* The counter tells us if we have reached the stopping point
		+	====Design====
		+	* If counter <= 0 then
		+	** Result is product we have been computing
		+	* If counter is any other value
		+	** Product is our product so far times b
		+	** Decrement the counter
		+	** Try again
		+
		+	What must our product start at? 1
		+
		+	What must our counter start at? n
		+	<pre>
		+	public int expt(int b, int n) {
		+	return (doExpt(b, n, 1);
		+	}
		+
		+	public int doExpt(int b, int count, int prod) {
		+	int result;
		+	if (count <= 0) {
		+	result = prod;
		+	} else {
		+	result = doExpt(b, count - 1, b * prod);
		+	}
		+	return result;
		+	}
		+	</pre>