Problem 1: Pool pH Maintenance
Problem 2: Builder's Friend
Problem 3: Summing Up Lengths
Problem 4: Reverse Polish Notation
Problem 5: Message Decoder
Problem 6: Maximum Segment Sum
In each problem description, given is a "sample program execution" showing a dialog between the user and a program that solves the problem correctly. In each such dialog, text that is underlined corresponds to input provided by the user. Text that is not underlined corresponds to output produced by the program.
Problem 1: Pool pH Maintenance
In order to maintain a pool properly, it is necessary to keep the pH level as close to 7.4 as possible. Every morning, the pool owner should check the pH level, and he/she should add, as necessary, either "pH Plus" or "pH Minus" (which come in the form of measurable powders). (If the level is already equal to 7.4 then no pH adjusters should be added.) One ounce of the "pH Minus" that we are using will decrease the pool's pH by .1 per 5,000 gallons of water. One ounce of our "pH Plus" will increase the pool's pH by .2 per 5,000 gallons of water.
Develop a program that will determine the amount and type of pH adjuster that should be added to a pool, based on the current pH level and the size of the pool. It may be helpful to know that there are 7.48 gallons per cubic foot.
The program should accept input and provide output in the format shown below, repeating until a "Pool length" value of 0 (zero) is given. You may assume that the value entered by the user for "Current PH level" will not be 7.4.
Sample Program Execution:
Pool length (feet): 24.0
Pool width (feet): 12.5
Average pool depth (feet): 5.25
Current pH level: 7.2
Pool size is 11781.00 gallons.
Add 2.36 ounces of pH Plus.
Pool length (feet): 12.5
Pool width (feet): 24.0
Average pool depth (feet): 5.25
Current pH level: 7.5
Pool size is 11781.00 gallons.
Add 2.36 ounces of pH Minus.
Pool length (feet): 0.0
A wall facing company needs a program to estimate how many bricks--and pallets of bricks--are needed to face a wall so that they can make more accurate bids and save money. The company uses bricks of only one size: 8 inches long, 2 inches high. The bricks come on pallets of 384. Workers place a half inch of grout between adjacent bricks. In order to add strength to the wall, it is required that every other row of bricks begins with a half brick (4 inches wide). (See illustration for an example.)
+-------+-------+-------+-------+-------+
| | | | | |
+---+---+---+---+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+---+---+---+---+
Develop a program that takes as input the length and height of up to six wall sections and that produces as output the number of bricks and pallets of bricks that are needed for the job. For our purposes, each section of wall should be considered separate from the others. Also, all cut scraps will be thrown out. In some cases this may be wasteful, but it saves the builders time.
The program should accept input and provide output in the format shown below (repeating until a value of 0 (zero) is entered for the number of wall sections).
Sample Program Exeuction:
Number of wall sections: 2
Length of section 1 (inches): 24
Height of section 1 (inches): 24
Length of section 2 (inches): 1200
Height of section 2 (inches): 24
The number of bricks needed for this job is 1455.
The number of pallets needed for this job is 4.
Number of wall sections: 0
An expression of the form P Yards, Q Feet, R Inches is said to be in normal form if P>0, 0<Q<3, and 0<R<12. For example, each of the following is in normal form:
Notice how we omit mention of any unit of measure that is not needed (because the corresponding number of units is zero). In the last expression above, for instance, we mention neither Yards nor Inches.
In contrast to the above, none of the following expressions is in normal form, the first because the number of Feet exceeds 3, the second because the number of Inches exceeds 12, and the third because Yards is mentioned when it need not be.
You are to construct a program that takes as input a sequence of lengths and produces as output the sum of those lengths, expressed in normal form. Each input length is entered on a separate line in the form of three integers, representing a number of yards, feet, and inches, respectively. (The only restriction on the inputs is that they be nonnegative. In particular, this means that the lengths given as input need not be in normal form.) End of input is signaled by a length of zero.
The program should accept input and provide output in the format shown below.
Sample Program Execution:
Enter Length: 7 0 4
Enter Length: 0 5 25
Enter Length: 2 2 5
Enter Length: 0 0 0
The sum of the lengths is 12 Yards, 10 Inches
Problem 4: Reverse Polish Notation
Early in this century, the Polish logician Jan Lucasiewicz introduced a notation for logical and mathematical expression that eliminated the need for parentheses and rules of operator precedence and operator associativity for evaluation of such expressions. This so-called Polish Notation calls for the operators to precede their operands. A variation, called Reverse Polish Notation, calls for the operators to follow their operands. For example, to evaluate the (normal) arithmetic expression
the evaluator would need to know which rules of precedence and associativity were in force.
In order to indicate explicitly an expression's structure (which determines how it may be evaluated), we place parentheses around its subexpressions. The expression given above has two possible structures, which are given below together with how they would be written in Reverse Polish Notation.
Construct a program that will accept as input a properly formed Reverse Polish expression, evaluate it, and report the result. Only positive, single digit numbers will be used in the expression, although the result may be negative and/or have more than one digit. Only the operators +, -, *, and / will be used. (The "/" operator denotes integer division.) No spaces or other punctuation will be used, and all input can be assumed to be valid.
The program should accept input and provide output in the format shown below, repeating until a value of 0 (zero) is entered for an expression.
Sample Program Execution:
Reverse Polish Expression: 85-3
Result: 6
Reverse Polish Expression: 853+-
Result: 0
Reverse Polish Expression: 72/38+*
Result: 33
Reverse Polish Expression: 2
Result: 2
Reverse Polish Expression: 0
Develop a program that accepts as input two strings, the first of which is ciphertext (i.e., an encoded message) and the second of which is a key that can be used to decode it, and that produces as output the plaintext (i.e., the original message).
The key is a string of four uppercase letters. To decode the first letter of ciphertext, "add" it (see explanation below) to the first letter of the key. Similarly, to decode the second, third, and fourth letters of ciphertext, "add" them to the second, third, and fourth, respectively, letters of the key. Beginning with the fifth letter of ciphertext, use the four letters of the key once more, in the same way. (Thus, the first letter of the key is used for decoding the 1st, 5th, 9th, etc., letters of ciphertext, the second letter of the key is used for decoding the 2nd, 6th, 10th, etc., letters of ciphertext, and similarly for the third and fourth letters of the key.)
To "add" two letters together, add their numeric values together (using A=1, B=2, C=3, ..., Z=26), subtract 26 if the result is greater than 26, and then find the letter having the corresponding numeric value. For example, E + C = H (corresponding to 5 + 3 = 8) and E + X = C (corresponding to 5 + 24 - 26 = 3).
Ciphertext given as input will not include lower case letters. It may, however, include spaces and punctuation marks (e.g., periods, commas, etc.). Upper case letters are to be decoded as described above. Any other characters are assumed to be their own codes. (E.g., The result of decoding a comma is a comma.)
The program should accept input and provide output in the format shown below, repeating until a null string is entered for a message.
Sample Program Execution:
Enter Ciphertext: EN UC ENDVCQG!
Enter Key: BALL
Plaintext: GO GO GOPHERS!
Enter Ciphertext:
Problem 6: Maximum Segment Sum
Develop a program that accepts as input a sequence of integers and that produces as output the maximum among the sums of all the nonempty contiguous subsequences of that sequence.
Consider, for example, the sequence
S has length 14. Thus, for every i and j satisfying 1 <= i <= j <= 14, there is a nonempty contiguous subsequence Si.. j beginning with the i-th element of S and ending with the j-th element of S. For example, S3..9 = <-1, -7, 12, 5, 3, -10, 5>. The sum of the elements in S3..9 is 7. Some nonempty contiguous subsequences of S have smaller sums and others have larger sums. Your program is to find the sum that is largest. For S, the answer is 30, because the sum of the elements in S5..12 is 30 (12 + 5 + 3 + -10 + 5 + -5 + 20) and no other nonempty contiguous subsequence of S has a larger sum. Thus, if your program were given S as input, its output should be 30.
Your program should accept input and provide output in the format shown below, repeating until the user enters zero as the length of the sequence to be analyzed. You may assume that no sequence of length more than 50 will be given as input.
Sample Program Execution:
Enter length of sequence: 14
Enter item 1: 2
Enter item 2: 5
Enter item 3: -1
Enter item 4: -7
Enter item 5: 12
Enter item 6: 5
Enter item 7: 3
Enter item 8: -10
Enter item 9: 5
Enter item 10: -5
Enter item 11: 20
Enter item 12: -5
Enter item 13: 0
Enter item 14: 3
Maximum Segment Sum is 30
Enter length of sequence: 0