**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