Week 23
Source Code
import java.util.*;
public class Week23 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("Welcome to Week 23");
System.out.println("E1 - Example 1");
System.out.println("Q - Quit");
System.out.print("Choice: ");
String choice = in.nextLine();
switch (choice) {
case "E1":
System.out.println("Example 1");
// example1();
break;
case "E2":
System.out.println("Example 2");
// example2(3);
break;
case "E3":
System.out.println("Example 3");
// System.out.println(factorial(5));
break;
case "E4":
System.out.println("Example 4");
// System.out.println(fibonacci(5));
break;
case "E5":
System.out.println("Example 5");
int target = 1;
int[] arr1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int foundIndex = recursiveBinarySearch(arr1, target, 0, arr1.length - 1);
System.out.println(target + " was found at index " + foundIndex);
break;
case "E6":
System.out.println("Example 6");
int[] arrMerge = {86, 3, 43, 5};
System.out.println(Arrays.toString(arrMerge));
mergeSort(arrMerge);
System.out.println(Arrays.toString(arrMerge));
break;
case "E7":
System.out.println("Example 7");
// 3 discs
// Hanoi towersofHanoi = new Hanoi(3);
break;
case "E8":
System.out.println("Example 8");
// 64 discs
// Hanoi towersofHanoi = new Hanoi(64);
break;
// quit and default cases
case "Q":
break;
default:
System.out.println("Invalid Choice");
break;
}
}
// example1() method
// example2() method
// factorial method
// fibonacci method
// recursive binary search method
public static int recursiveBinarySearch(int[] array, int target, int start, int end) {
int middle = (start + end) / 2;
// base case: check middle element
if (target == array[middle]) {
return middle;
}
// base case: check if we've run out of elements
if (end < start) {
return -1; // not found
}
// recursive call: search start to middle
if (target < array[middle]) {
return recursiveBinarySearch(array, target, start, middle - 1);
}
// recursive call: search middle to end
if (target > array[middle]) {
return recursiveBinarySearch(array, target, middle + 1, end);
}
return -1;
}
// merge sort
public static void mergeSort(int[] a) {
// Base case: if the array is of length 0 or 1, it's already sorted
if (a.length <= 1) {
return;
}
// Creating two arrays to hold the two halves of the input array
int[] first = new int[a.length / 2];
int[] second = new int[a.length - first.length];
// Copying the first half of the array 'a' into 'first'
for (int i = 0; i < first.length; i++) {
first[i] = a[i];
}
// Copying the second half of the array 'a' into 'second'
for (int i = 0; i < second.length; i++) {
second[i] = a[first.length + i];
}
// Recursively sort the first half
mergeSort(first);
// Recursively sort the second half
mergeSort(second);
// Merge the sorted halves back into the original array
merge(first, second, a);
}
// Private helper method to merge two sorted arrays into a single sorted array
private static void merge(int[] first, int[] second, int[] a) {
int iFirst = 0; // Index into the first array
int iSecond = 0; // Index into the second array
int j = 0; // Index into the merged array
// While both arrays have elements yet to be merged
while (iFirst < first.length && iSecond < second.length) {
// Determine which element from the two halves is smaller
// and add it to the merged array
if (first[iFirst] < second[iSecond]) {
a[j] = first[iFirst];
iFirst++;
} else {
a[j] = second[iSecond];
iSecond++;
}
j++;
}
// If there are remaining elements in 'first', add them to 'a'
while (iFirst < first.length) {
a[j] = first[iFirst];
iFirst++;
j++;
}
// If there are remaining elements in 'second', add them to 'a'
while (iSecond < second.length) {
a[j] = second[iSecond];
iSecond++;
j++;
}
}
}
W23Problem1.java
public class W23Problem1 {
public static void mystery1(int n) {
if (n <= 0) {
System.out.println("End");
} else {
System.out.println(n);
mystery1(n - 2);
}
}
public static void main(String[] args) {
mystery1(5);
}
}W23Problem2.java
public class W23Problem2 {
public static void mystery2(String str) {
if (str.length() == 0) {
System.out.println("End");
} else {
mystery2(str.substring(1));
System.out.println(str.charAt(0));
}
}
public static void main(String[] args) {
mystery2("CAT");
}
}RecursiveBinarySearchActivity.java
public class RecursiveBinarySearchActivity {
// The recursive binary search method
public static int recursiveBinarySearch(int[] array, int target, int start, int end) {
if (end < start) {
return -1; // Base case: not found
}
int middle = (start + end) / 2;
if (target == array[middle]) {
return middle; // Base case: found
}
if (target < array[middle]) {
return recursiveBinarySearch(array, target, start, middle - 1);
} else { // target > array[middle]
return recursiveBinarySearch(array, target, middle + 1, end);
}
}
// Problem 1
public static void problem1() {
int result1 = -1;
System.out.println("Problem 1 Result: " + result1);
}
// Problem 2
public static void problem2() {
int result2 = -1;
System.out.println("Problem 2 Result: " + result2);
}
// Problem 3
public static void problem3() {
int callCount = -1;
System.out.println("Problem 3: Total recursive calls = " + callCount);
}
// Problem 4
public static void problem4() {
int callCount = -1;
System.out.println("Problem 4: Total recursive calls = " + callCount);
}
// Helper method to count recursive calls for Problem 3
public static int countRecursiveCalls(int[] array, int target) {
return countCallsHelper(array, target, 0, array.length - 1, 0);
}
public static int countCallsHelper(int[] array, int target, int start, int end, int count) {
count++;
if (end < start) {
return count;
}
int middle = (start + end) / 2;
if (target == array[middle]) {
return count;
}
if (target < array[middle]) {
return countCallsHelper(array, target, start, middle - 1, count);
} else {
return countCallsHelper(array, target, middle + 1, end, count);
}
}
// main method
public static void main(String[] args) {
// call each problem
}
}Hanoi.java
public class Hanoi {
private int numDiscs; // Number of discs
public Hanoi(int n) {
// Assign the number of discs.
numDiscs = n;
// Move the number of discs from peg 1 to peg 3
// using peg 2 as a temporary storage location.
moveDiscs(numDiscs, 1, 3, 2);
}
/**
* The moveDiscs method accepts the number of
* discs to move, the peg to move from, the peg
* to move to, and the temporary peg as arguments.
* It uses recursion to display the necessary
* disc moves.
*/
private void moveDiscs(int num, int fromPeg, int toPeg, int tempPeg) {
if (num > 0) {
moveDiscs(num - 1, fromPeg, tempPeg, toPeg);
System.out.println("Move a disc from peg " + fromPeg + " to peg " + toPeg);
moveDiscs(num - 1, tempPeg, toPeg, fromPeg);
}
}
}Last updated
Was this helpful?