Programming Assignment 2
You will implement and test 4 short recursive methods. With the proper
use of recursion, none of these methods should require more than a dozen
lines of code. Non-recursive methods receives 0 credit!!!
Purposes:
Ensure that you can write and test small recursive methods.
Your program file name must be AssignmentTwo.java. This program should
contain 4 recursive methods and your main method to test the four recursive
methods.
You may ask general questions from other students, tutors and your instructor, and
those students may answer questions with pencil and paper. But do not look at
program files or other students’ solutions to any homework problems. Do not write
any code in Canvas discussion threads.
1. Triangle Pattern
public void triangle(int m, int n)
/* Precondition: m <= n * Postcondition: The method should print a pattern of 2*(n-m+1) lines * to the standard output. The first line contains m asterisks, the next * line contains m+1 asterisks, and so on up to a line with n asterisks. * Then the pattern is repeated backwards, going n back down to m. * Example output: triangle(3, 5) will print this: *** **** ***** ***** **** *** */ Hint: Only one of the arguments changes in the recursive call. Which one? Test your program with following inputs: triangle(4, 8) triangle(5,5) triangle(3,6) triangle(6, 8) 2. Section Numbers public void numbers(String prefix, int levels) The method prints output consisting of the String prefix followed by "section numbers" of the form 1.1., 1.2., 1.3., and so on. The levels argument determines how may levels the section numbers have. For example, if levels is 2, then the section numbers have the form x.y. If levels is 3, then section numbers have the form x.y.z. The digits permitted in each level are always '1' through '9'. As an example, if prefix is the string "THERBLIG" and levels is 2, then the method would start by printing: THERBLIG1.1. THERBLIG1.2. THERBLIG1.3. and end by printing: THERBLIG9.7. THERBLIG9.8. THERBLIG9.9. The stopping case occurs when levels reaches zero (in which case the prefix is printed once by itself followed by nothing else). The Java String class has many manipulation methods, but you'll need only the ability to make a new string which consists of prefix followed by another character (such as '1') and a period ('.'). If s is the String that you want to create and c is the digit character (such as '1'), then the following statement will correctly form s: s = prefix + c + '.'; This new String s can be passed as a parameter to recursive calls of the method. Test your method with following inputs: numbers(“EPISODE” , 3) numbers(“ERA”, 4) numbers(“Passage”, 1) 3. A Teddy Bear Picnic This question involves a game with teddy bears. The game starts when I give you some bears. You can then give back some bears, but you must follow these rules (where n is the number of bears that you have): 1. If n is even, then you may give back exactly n/2 bears. 2. If n is divisible by 3 or 4, then you may multiply the last two digits of n and give back this many bears. (By the way, the last digit of n is n%10, and the next-to-last digit is ((n%100)/10). 3. If n is divisible by 5, then you may give back exactly 42 bears. The goal of the game is to end up with EXACTLY 42 bears. For example, suppose that you start with 250 bears. Then you could make these moves: · --Start with 250 bears. · --Since 250 is divisible by 5, you may return 42 of the bears, leaving you with 208 bears. · --Since 208 is even, you may return half of the bears, leaving you with 104 bears. · --Since 104 is even, you may return half of the bears, leaving you with 52 bears. · --Since 52 is divisible by 4, you may multiply the last two digits (resulting in 10) and return these 10 bears. This leaves you with 42 bears. · --You have reached the goal! Write a recursive method to meet this specification: public boolean bears(int n) // Precondition: n>0
// Postcondition: A true return value means that it is possible to win // the bear
game by starting with n bears. A false return value means that
// it is not possible to win the bear game by starting with n bears. // Examples:
// bear(250) is true (as shown above)
// bear(42) is true
// bear(84) is true
// bear(53) is false
// bear(41) is false
// bear(854) is ?
// bear( 1011) is ?
Hint: To test whether n is even, use the expression ((n % 2) == 0).
4. Find Longest Repeated Pattern
public int findLongest(char c, String s, int length)
Given a String, find the longest sequence of matching characters in that String and
return that int length. For instance, “aaabbccccccdde” has 6 c’s so the method would
return 6
Call this method passing it the first character in the String, the rest of the String and
1, as in
findLongest(‘a’, s, 1)
length represents the longest matching sequence found so far, which is 1 because
we found ‘a’
Base case: if length==0 or length==1 return the length of s
Recursive cases: if c matches the 0th character of s, then we extend the sequence,
return the value of the recursive call with c, the rest of s after the 0th character, and
length+1
else no match, return whichever is larger, length (the length we found of char c up to
this point in s), or the value returned by recursively calling the method with the 0th
character of s, the rest of s, and 1 as we are starting over
Example: “aaabbccccccdde”
Call the method with ‘a’, “aabbccccccdde”, 1
First character matches, so call with ‘a’, “abbccccccdde”, 2
First character matches, so call with ‘a’, “bbccccccdde, 3
No match, so return max(3, call with ‘b’, “bccccccdde”, 1)
First character matches, so call with ‘b’, “ccccccdde, 2
No match, so return max(2, call with ‘c’, “cccccdde”, 1)
First character matches, so call with ‘c’, “ccccdde”, 2
…
Eventually these calls return 6 (6 c’s found)
Return max(2, 6)
Return max(3, 6)
Run your program on the following inputs.
“aabbbcddddddeefffghiii”, “19855aa00000cc24443bbb” ,
“33335557i322k555554p”,
“2oo88rrrrr55ttyuuuuuuuuuuuuuuu44uuuuuuuuu4u444uuuuuuuuuuuuuuu”
Turn in the following
Cover page (page 1): Your name, assignment number, assignment title, and due
date.
One page abstract (page 2): Describe the four problems in your own words
(descriptions are given in the lab document), explain your recursive algorithm
design, and observations. Make sure to check spellings and grammar. The
abstract should be typed in Times New Roman style font with single spacing and
the font size of 12.
Source Program(s): Turn in Java source code AssignmentTwo.java. Your
program should be properly indented and commented with each method with
JavaDoc pre/post conditions.
Outputs: Outputs of all test cases in a PDF. Test cases are given to you in the
lab document. All outputs should be properly labeled identifying different
methods and their inputs.
File #1
