CS代写/java代写/java作业代写/算法代写/数据结构代写:这是利用java进行递归知识的代写
Helpful Information:
● Getting Help
○ Lab and Office Hours (Always refer to this calendar before posting.)
● Academic Integrity: What You Can and Can’t Do in CSE 11
● Setting Up PAs
● How to Use Vim and Eclipse
● Code Style Guidelines
● Submitting on Vocareum and Grading Guidelines
Table of Contents:
Overview
Part 1: Warm up [60 points]
Warm up 1: Print in Binary [20 points]
Warm up 2: Random Mnemonic [20 points]
Warm up 3: Subset Sum [20 points]
Part 2: More interesting recursion problems [40 points] [+ 5 points in extra credit]
Problem 1: The Human Pyramid [20 points]
Problem 2: Generate Mnemonics [20 points]
Problem 3: Picking up coins (1 player 2D) [20 points]
Problem 4: Picking up Coins (2 Player 1-d) [20 points]
Extra credit: No problem left behind [5 points]
Submitting the Assignment
Overview
This assignment is autograded when you
submit: When you click Submit on Vocareum,
you’ll get a report telling your grade. That will be
your final grade (capped at 105). To see your
grade, check the grading report (or the
submission report) after submitting:
You may re-upload your files and re-submit as many times as you wish, with no
penalty to your grade. Your LAST submission is the one that counts for your
grade.
However, DO NOT hardcode ANY grader test case, or else you’ll get a 0 for
that problem.
Also, if you don’t use recursion you’ll get a 0 (unless stated otherwise.)
In this PA we will be focusing on Recursion. You will write several small recursion functions.
Learning to solve problems recursively can be challenging, especially at first. We think it’s best to
practice in isolation before adding the complexity of integrating recursion into a larger program. NOTE:
there is not a lot of code to write in any of these methods, so before you begin you should be 100%
sure what your base case(s) and recursive step(s) are. Though Recursive methods are often short, the
density and complexity that can be packed into such a small amount of code may surprise you. If you
are at all unclear about it, do not start coding. Rather seek help in the lab, in discussion, or in office
hours. You must use recursion to solve these problems.
NO LOOPS ALLOWED!! (unless explicitly stated otherwise)
If you use a loop or do not use recursion, you will get
0 points.
Help!
When implementing the functions in this PA you might come
across a StackOverflow error. This error is caused by an
infinite recursion. i.e. a recursion that never hits its base
case. Not sure why? This is a perfect time to practice some
of those debugging skills you learned above. 🙂 Ask a tutor
if you need help.
e.g. in the example below, infiniteRecursion will call itself over and over again until we run out of
memory for the method call stacks (StackOverflow error).
public void infiniteRecursion() {
infiniteRecursion();
}
Part 1: Warm up [60 points]
Implement ALL THREE of the following methods in the class WarmupRecursion (in the file
WarmupRecursion.java provided in the starter code) . We have provided a tester WarmupTester.java that
tests these methods. We’ve provided with a WarmupRecursionTester.java file that runs some local tests to
get you started; but these are not the same run by the grader.
Warm up 1: Print in Binary [20 points]
Write the following recursive method:
public static String binaryString(int n)
This method should return the binary representation of the non-negative decimal number n to as a String.
You can assume n will be non-negative (greater than or equal to 0).
For example, calling …
binaryString(6) returns “110”
binaryString(12) returns “1100”
binaryString(17) returns “10001”
Hints:
● The rightmost (least significant) digit of the binary representation of a decimal number can be
obtained by mod’ing that number by 2. E.g. 6%2 == 0; 17%2 == 1.
● The remaining digits to the left are the result of converting n/2 to binary. E.g. “11” is 6/2 (3) in
binary, and “1000” is 17/2 (8) in binary.
● A non-negative number less than 2 (that is, 1 or 0) is its own binary representation.
● Recall the first recursive function “foo” we looked at in class. The structure will be very useful here,
particularly if your binary strings are coming out reversed.
Warm up 2: Random Mnemonic [20 points]
On a telephone keypad, the digits are mapped onto the alphabet as shown
in the diagram aside:
In the past, in order to make their phone numbers more memorable, service
providers used to find numbers that spell out some word (called a
mnemonic) appropriate to their business that makes that phone number
easier to remember.
Implement the following method:
public static String generateRandomMnemonic(String digits)
This method takes as input a String containing 0 or more digits and returns a string which is a legal
mnemonic for that string of digits (though not necessarily an actual word), chosen at random.
If the String digits is empty or null, this function should return an empty string.
For example, calling generateRandomMnemonic(“723”) might return any of “PAD”, “QBF”, “QAE”, or
any of the other 36 possible Strings that can be generated by the letters associated with the numbers 7, 2
and 3 in that order.
Please use the following function as a helper method:
private static String getCode(char A) {
switch (A) {
case ‘2’:
return “ABC”;
case ‘3’:
return “DEF”;
case ‘4’:
return “GHI”;
case ‘5’:
return “JKL”;
case ‘6’:
return “MNO”;
case ‘7’:
return “PQRS”;
case ‘8’:
return “TUV”;
case ‘9’:
return “WXYZ”;
default:
return “”;
}
}
Hints:
● You will find the String’s charAt and substring() methods very useful here. In particular,
s.substring(1) returns a new String with all the characters in s except for the very first.
● The base case is the simplest version of the problem, for which you know the answer immediately.
Since we are asking you to handle Strings of length 0, you might consider using that as your base
case.
Warm up 3: Subset Sum [20 points]
Write the following recursive method:
public static boolean isSubSetSum(ArrayList
This method takes an ArrayList of integers, and a targetNumber and determines if there is a subset of
those integers that sum to that targetNumber.
For example, given the numbers {3, 7, 1, 8, -3} and the target sum 4, the result is true because subset {3,
1} sums to 4 . On the other hand, if the target sum were 2, the result is false since there is no subset that
sums to 2.
Hints:
● If the set is empty, then it clearly has no elements that can add to the targetNumber, unless
targetNumber is 0. If targetNumber is 0 answer is always true.
● The subset of elements that are used in the sum will either contain the first number in the set, or it
will not. Either way, once you have chosen to use the number or throw it away, it will need to be
removed from the set you pass into your recursive call. You will need to have two recursive cases
here: one where the first number is in the subset, and one where the first number is not in the
subset. Whether you use the first element or not will affect what you pass in for targetNumber in
your recursive call. Then after you have done both recursive calls, consider how to combine them
to give you your final answer. (It might make things faster to do only one, and only do the second if
you need to).
Part 2: More interesting recursion problems [40 points]
[+ 5 points in extra credit]
Choose TWO of the following four problems to implement. Implement this in a file called
Recursion.java. Do not remove the method signature for the ones you choose not to implement.
We’ve provided with RecursionTester.java file that runs some local tests to get you started; but these are
not the same run by the grader.
Problem 1: The Human Pyramid [20 points]
Imagine that you have a human pyramid where each person in a row is balanced on the two
people below them, as in the following diagram:
Each row has one fewer person than the row above them, and each person carries the weight
of themselves plus half the weight carried by the two people standing on them. For example,
if you have a pyramid of people with the following weights:
111.3
140.3 125.3
134.2 180.9 175.6
The person on the top carries only their own weight (111.3). The people in the next row
carry their weights (140.3 and 125.3, respectively) and half of the weight of the person on
the top (111.3/2 = 55.65), so the total weight carried by the people in the second row is
195.95 and 180.95, respectively. Finally the people in the bottom row carry their own
weight, plus half the weight carried by the people standing on them. So the total weights at
the bottom row are: 134.2 + (195.95/2) = 232.175, 180 + (195.95/2 + 180.95/2) =
369.35, and 175.6 + (180.95/2) = 266.075.
Implement the method:
public static double humanPyramidWeight(
ArrayList
That takes a nested ArrayList containing the weights of the people in the pyramid, a level
where the top person in the pyramid is at level 0 and each level increases by 1, and an
offset, which is the number of people in from the left in a given level.
This function returns the total weight carried (as described above) by the person in
the specified level of the pyramid at the given offset.
If the level/offset passed is outside the bounds of the ArrayList, return 0.
For example, the numerical example above
The arrayList is created as follows
ArrayList
ArrayList
weights.add(new ArrayList
weights.add(new ArrayList
weights.add(new ArrayList
weights.get(0).add(111.3);
weights.get(1).add(140.3);
weights.get(1).add(125.3);
weights.get(2).add(134.2);
weights.get(2).add(180.9);
weights.get(2).add(175.6);
// The method
humanPyramidWeight(weights,0,0) must return 111.3 ,
humanPyramidWeight(weights,2,0) must return 232.175 ,
humanPyramidWeight(weights,2,1) must return 369.35 ,
humanPyramidWeight(weights,2,2) must return 266.075 ,
humanPyramidWeight(weights,2,3) must return 0
Problem 2: Generate Mnemonics [20 points]
NOTE: For only this problem you may use a loop in addition to recursion. You must use recursion to
solve a significant part of the problem (or you’ll get a 0), but you can use a loop that works with a
recursive call. (Of course, the problem is also possible to solve without a loop if
you want a real challenge.)
On a telephone keypad, the digits are mapped onto the alphabet as shown in the
diagram aside. In the past, in order to make their phone numbers more
memorable, service providers used to find numbers that spell out some word
(called a mnemonic) appropriate to their business that makes that phone number
easier to remember.
Imagine that you have just been hired by a local telephone company to write a recursive function
public static ArrayList
that will generate all possible letter combinations that correspond to a given number, represented as
a string of digits.
For example, the call generateMnemonics(“723”) should return an ArrayList that has the following 36
possible Strings that correspond to that prefix:
PAD , PBD, PCD, QAD, QBD,QCD, RAD, RBD, RCD , SAD , SBD, SCD, PAE, PBE, PCE,
QAE, QBE, QCE , RAE, RBE, RCE, SAE, SBE, SCE ,PAF, PBF , PCF, QAF, QBF, QCF,
RAF, RBF, RCF, SAF, SBF, SCF
(The order of the above Strings might be different in your solution’s returned ArrayList)
As another example, generateMnemonics(“121”) , generateMnemonics(“21”) and
generateMnemonics(“12”) would all return an ArrayList that has the Strings “A” , “B” and “C”. In other words
the codes for 0 , 1 and any non-numeric character is just the empty String.
Problem 3: Picking up coins (1 player 2D) [20 points]
Some coins are spread in the cells of an m x n board, one coin per cell. A robot, located in the upper left
cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell.
On each step, the robot can move either one cell to the right or one cell down from its current location.
When the robot visits a cell with a coin, it picks up that coin.
Write a recursive function
public static int collectCoins2D(int[][] board, int row, int col)
that takes a row and a col of the board as an argument and returns the the maximum number of coins
the robot can collect by moving from that cell to the bottom right cell (row = m-1 and col = n-1) In the
example shown below if the robot starts at the upper left cell of the board (row = col = 0) it can collect 27
coins. (Can you see How?) . You may assume that the board is always rectangular or square. If the
row/col passed is outside the bounds of the board, return -1.
1 9 8
0 6 1
2 8 3
For the above board,
collectCoins2d(board, 0, 0) must return 27
collectCoins2d(board, 2, 0)) must return 13
collectCoins2d(board, 1, 1)) must return 17
collectCoins2d(board, 2, 2)) must return 3
collectCoins2d(board, 4, 2)) must return -1
Problem 4: Picking up Coins (2 Player 1-d) [20 points]
Some coins are again spread on a board this time of dimensions 1 x m board, one coin per cell. (You
may assume that m is always even and the board is represented as an ArrayList of Integers). Two Robots
play a game alternating turns. In its turn, the Robot selects either the first or last coin from the row,
removes it from the row permanently, and receives the value of the coin.
Write a recursive function to determine the maximum possible value that the robot playing first can
definitely collect.
Note: The opponent is as clever as the user.
Let us understand the problem with few examples:
1. 5, 3, 7, 10 : The robot collects maximum value as 15(10 + 5)
2. 8, 15, 3, 7 : The robot collects maximum value as 22(7 + 15)
Does choosing the best at each move give an optimal solution? No In the second example, had the first
player picked 8 first he would have at the max won 15. ( Do you see why? )
The signature of the method you’re asked to implement is:
public static int collectCoins1D(int[] m)
Hint:- You may find it useful to write a private recursive helper method
private static int collectMaxCoinsHelp(int[] m, int start, int end)
Where start and end represent the current positions of the first and the last coin in the ArrayList. This
helper method will be recursive and computes the maximum value that the first user can collect from the
start coin to the end coin. Your collectCoins1D must make an appropriate call to the recursive
collectMaxCoinsHelp method and simply return that value.
collectCoins1D(new int[] { 5, 3, 7, 10} must return 15
collectCoins1D(new int[] { 8,15,3,7} must return 22
collectCoins1D(new int[] {2,1,6,3,9} must return 13
collectCoins1D(new int[] {1,1,1,1,1,1,1} must return 4
Extra credit: No problem left behind [5 points]
Implement ONE of the two remaining methods, i.e. implement either of the two methods you didn’t
choose.
That’s all.
Submitting the Assignment
This assignment is autograded when you
submit: Every time you Submit on Vocareum,
your submission will be graded. That will be
your final grade (capped at 105).
You may re-upload your files and re-submit as
many times as you wish, with no penalty to
your grade. Your LAST submission is the one
that counts for your grade.
However, DO NOT hardcode ANY grader test case, or else you’ll get a 0 for
that problem. Also, if you don’t use recursion you’ll get a 0. (unless stated otherwise.)
How to Submit on Vocareum
Submission Files (Make sure your submission contains all of the files and that they work on the
ieng6 lab machines!)
● WarmupRecursion.java
● Recursion.java
You don’t have to submit the tester files. Those are for your own use.
No style this time! 🎉
🚨 DO NOT REMOVE ANY METHOD SIGNATURES FROM THE STARTER
CODE THAT YOU CHOOSE TO NOT IMPLEMENT.
OTHERWISE, THE SCRIPTS WILL NOT COMPILE.
Maximum Score Possible: 100 out of 100 Points + 5 points for extra credit