This assignment use java.

Part 3.You are holding a contest to determine the ultimate penny champion. Each participant in the contest has decided which side of the penny they like, heads or tails, and keeps that decision to themselves. We represent heads using the boolean value true and tails using false. The contest participants all get in a long line (array). They start by pairing up (the first two, second two, and so forth). After the two members reveal their pennies to each other, if both are the same, the first (left) person wins, otherwise, the second (right) person wins. The remaining members then battle it out the same way in the next round until only one winner emerges. If there are an odd number of people in any round, the last person gets a bye and automatically survives to the following round.

Solve the problem recursively by writing the following method: public static int champion(boolean[] a)

Return the index corresponding to the winner of the contest. You do not need to allocate any arrays for this problem and you should not modify the input array. Instead, adapt what we learned from binary search. You will probably need a helper method. You may assume that the array is at least length 1.

Note: After playing around with a number of examples, you discover that the above problem is equivalent to dividing up the line of participants into two parts (where each part is a contiguous piece of the line), performing a totally separate champion contest for each part, and having the winners of the two separate contests pairing up for a final match. The length of the first part is the largest power of two less than the number of participants, and the second part is the remaining participants. For example, if there are 11 participants, you would divide into a contest of the first 8 participants followed by a contest of the other 3. The 3 participants would have a pair battling with the other in a bye. The winner of the faceoff between the pair winner and the bye would survive until the final battle! See if you understand how this version of the problem results in the same sequence of battles that would occur in the earlier description.

The whole assignment can be referenced below:

For this assignment, you will implement a few recursive methods in a Java class called RecursionIntro. For this assignment, there are some rules spelled out below: You may not make use of any Java classes other than incidental use of Strings, calls to System.out.println, and accessing an existing array passed to your method. The tester program will verify that your program contains no imports, no use of "new", and the only uses of. (dot) are within calls to System.out.println, accessing array .length, or followed by a digit (double literals). You may not use for or while. Any looping must be accomplished using recursion. The tester program will check for no "for"s or "while"s and may be triggered by the word in a comment. You may not declare static or non-static member fields - only local or parameter variables allowed. You may implement additional helper methods to use the "recursive driver" technique as we did with the find method in class. Part 1. Even digits up, odd digits down (30 pts) Implement the method public static long eduodd(long n). eduodd(n) returns a value which increases each of the even decimal digits of n by one and decreases each of the odd digits of n by one. Leading one digits will disappear. The sign of eduodd(n) should be the same as n, unless n is negative and eduodd(n) is zero as seen in the last example below. Please review the written practice recursion problems as seen in class. Table of examples: In -11 0 1 27 36 987654321 896745230 -8443 -9552 1 1121113 3 0002 eduodd(n) 0 Part 2a. Recursive definition (20 pts) Implement the method public static int fibby(int n). fibby is mathematically defined for nonnegative values in the following way: fibby(0) = 1 fibby(n) = fibby([n/4]) + fibby([3n/4]) where n > 0 and [x] means the floor of x (round down). HINT: recall Java's integer division behavior. Table of examples: | In fibby(n) 1 2 2 3 3 4 4 6 5 6 6 8 7 8 8 11 9 11 10 11 20 24 100 111 Part 2b. Sparse table generation (20 pts) Notice that for many values i, fibby(i) = fibby(i+1). Implement the method public static void printsparsetable(int start, int end). Output using System.out.println all consecutive values of n and fibby(n) (just the two numeric values separated by a space) where n > start and n Send. However, skip a line of output if the previous row printed has the same fibby value. Page 1 of 2 For example, if you call printsparsetable(5, 10); you would print: 56 68 8 11 Note that even though fibby(4) == fibby(5), since we didn't print fibby(4), we still print fibby(5). But we skip fibby(7) because it equals the previously printed fibby value. A helper method will probably help with this. Part 3. There can be only one (30 pts) You are holding a contest to determine the ultimate penny champion. Each participant in the contest has decided which side of the penny they like, heads or tails, and keeps that decision to themselves. We represent heads using the boolean value true and tails using false. The contest participants all get in a long line (array). They start by pairing up the first two, second two, and so forth). After the two members reveal their pennies to each other, if both are the same, the first (left) person wins, otherwise, the second (right) person wins. The remaining members then battle it out the same way in the next round until only one winner emerges. If there are an odd number of people in any round, the last person gets a "bye" and automatically survives to the following round. Solve the problem recursively by writing the following method: public static int champion (boolean[] a) Return the index corresponding to the winner of the contest. You do not need to allocate any arrays for this problem and you should not modify the input array. Instead, adapt what we learned from binary search. You will probably need a helper method. You may assume that the array is at least length 1. Note: After playing around with a number of examples, you discover that the above problem is equivalent to dividing up the line of participants into two parts (where each part is a contiguous "piece" of the line), performing a totally separate champion contest for each part, and having the winners of the two separate contests pairing up for a final match. The length of the first part is the largest power of two less than the number of participants, and the second part is the remaining participants. For example, if there are 11 participants, you would divide into a contest of the first 8 participants followed by a contest of the other 3. The 3 participants would have a pair battling with the other in a bye. The winner of the faceoff between the pair winner and the bye would survive until the final battle! See if you understand how this version of the problem results in the same sequence of battles that would occur in the earlier description. Page 2 of 2 For this assignment, you will implement a few recursive methods in a Java class called RecursionIntro. For this assignment, there are some rules spelled out below: You may not make use of any Java classes other than incidental use of Strings, calls to System.out.println, and accessing an existing array passed to your method. The tester program will verify that your program contains no imports, no use of "new", and the only uses of. (dot) are within calls to System.out.println, accessing array .length, or followed by a digit (double literals). You may not use for or while. Any looping must be accomplished using recursion. The tester program will check for no "for"s or "while"s and may be triggered by the word in a comment. You may not declare static or non-static member fields - only local or parameter variables allowed. You may implement additional helper methods to use the "recursive driver" technique as we did with the find method in class. Part 1. Even digits up, odd digits down (30 pts) Implement the method public static long eduodd(long n). eduodd(n) returns a value which increases each of the even decimal digits of n by one and decreases each of the odd digits of n by one. Leading one digits will disappear. The sign of eduodd(n) should be the same as n, unless n is negative and eduodd(n) is zero as seen in the last example below. Please review the written practice recursion problems as seen in class. Table of examples: In -11 0 1 27 36 987654321 896745230 -8443 -9552 1 1121113 3 0002 eduodd(n) 0 Part 2a. Recursive definition (20 pts) Implement the method public static int fibby(int n). fibby is mathematically defined for nonnegative values in the following way: fibby(0) = 1 fibby(n) = fibby([n/4]) + fibby([3n/4]) where n > 0 and [x] means the floor of x (round down). HINT: recall Java's integer division behavior. Table of examples: | In fibby(n) 1 2 2 3 3 4 4 6 5 6 6 8 7 8 8 11 9 11 10 11 20 24 100 111 Part 2b. Sparse table generation (20 pts) Notice that for many values i, fibby(i) = fibby(i+1). Implement the method public static void printsparsetable(int start, int end). Output using System.out.println all consecutive values of n and fibby(n) (just the two numeric values separated by a space) where n > start and n Send. However, skip a line of output if the previous row printed has the same fibby value. Page 1 of 2 For example, if you call printsparsetable(5, 10); you would print: 56 68 8 11 Note that even though fibby(4) == fibby(5), since we didn't print fibby(4), we still print fibby(5). But we skip fibby(7) because it equals the previously printed fibby value. A helper method will probably help with this. Part 3. There can be only one (30 pts) You are holding a contest to determine the ultimate penny champion. Each participant in the contest has decided which side of the penny they like, heads or tails, and keeps that decision to themselves. We represent heads using the boolean value true and tails using false. The contest participants all get in a long line (array). They start by pairing up the first two, second two, and so forth). After the two members reveal their pennies to each other, if both are the same, the first (left) person wins, otherwise, the second (right) person wins. The remaining members then battle it out the same way in the next round until only one winner emerges. If there are an odd number of people in any round, the last person gets a "bye" and automatically survives to the following round. Solve the problem recursively by writing the following method: public static int champion (boolean[] a) Return the index corresponding to the winner of the contest. You do not need to allocate any arrays for this problem and you should not modify the input array. Instead, adapt what we learned from binary search. You will probably need a helper method. You may assume that the array is at least length 1. Note: After playing around with a number of examples, you discover that the above problem is equivalent to dividing up the line of participants into two parts (where each part is a contiguous "piece" of the line), performing a totally separate champion contest for each part, and having the winners of the two separate contests pairing up for a final match. The length of the first part is the largest power of two less than the number of participants, and the second part is the remaining participants. For example, if there are 11 participants, you would divide into a contest of the first 8 participants followed by a contest of the other 3. The 3 participants would have a pair battling with the other in a bye. The winner of the faceoff between the pair winner and the bye would survive until the final battle! See if you understand how this version of the problem results in the same sequence of battles that would occur in the earlier description. Page 2 of 2