CS 364, Winter 2008
Homework 2 Solution Set
As with most programming, there are several ways to solve each problem. Here are some sample solutions using elements you’ve seen in class, or closely related to them. Code comments marked by # are a good way to understand what’s going on at each step of the programs.
Question 1:
Tools used to solve this problem:
- printing output text
- reading user input using <>
- removing newline characters using chomp()
- printing variables embedded in text
# Display a request for input
print "Enter Name1: ";
#Put the input from above into a variable
$name1 = <>;
# Repeat 4 more times for other inputs
print "Enter Name2: ";
$name2 = <>;
print "Enter Noun1: ";
$noun1 = <>;
print "Enter Noun2: ";
$noun2 = <>;
print "Enter a gerund: ";
$gerund = <>;
#Remove the 'newline' characters at the end of the variables
chomp($name1);
chomp($name2);
chomp($noun1);
chomp($noun2);
chomp($gerund);
# Print out the poem, substituting in the inputs
print "\n";
print "Here's a lovely poem:";
print "\n";
# Add Name1 and Name2 here
print "$name1 and $name2 went up the hill,";
print "\n";
# Add Noun1 here
print "to fetch a pail of $noun1,";
print "\n";
#Add Name1 and Noun1 here
print "$name1 fell down and broke his $noun2,";
print "\n";
#Add Name2 and the gerund here
print "and $name2 came $gerund after.";
print "\n";
print "\n";
Question 2:
New tools used to solve this problem
- using lc() to convert both strings to lowercase
- string comparison operators gt and lt to compare strings alphanumerically
- using if/elsif/else conditional structure
- using backslash (\”) to display double quotes within a print statement
# Get 2 user-supplied strings, taking care to remove newline characters
print "Enter String 1: ";
$string1 = <>;
chomp($string1);
print "Enter String 2: ";
$string2 = <>;
chomp($string2);
#convert both to lower-case in order to compare in a case-#insensitive manner
$lower1 = lc($string1);
$lower2 = lc($string2);
# Use string comparison on the lower-case strings to #determine their alphanumeric order
if($lower1 lt $lower2) {
#String 1 comes before String 2
print " \"$string1\" comes before \"$string2\" alphanumerically.";
print "\n";
}
elsif($lower1 gt $lower2) {
# Only when the first if() clause is not satisfied, the “else if” clause is tested
#String 1 comes after String 2
print " \"$string2\" comes before \"$string1\" alphanumerically.";
print "\n";
}
else {
#If String 1 comes neither before or after String 2, they must be identical
print " \"$string1\" and \"$string2\" are the same alphanumerically.";
print "\n";
}
Question 3:
Part A:
New tools used to solve this problem:
- initializing empty arrays @divisors = ()
- % operator to check whether a number is a perfect divisor (has remainder 0)
- push to add divisors we find to the list as we find them
- shift to take the first element off the top of the array
- while(@divisors) to stay in the while loop until the array is empty
print "Enter a positive integer: ";
$number = <>;
chomp($number);
# Initialize an empty array to hold the divisors we find
@divisors = ();
# Start testing divisor candidates, beginning with 1
$candidate = 1;
while($candidate <= $number/2) {
#If the candidate divisor cleanly divides our number, add it to the divisor array
if( ($number % $candidate) == 0 ) {
push (@divisors, $candidate);
}
# Test the next candidate at the next while loop iteration
$candidate++;
}
# Now that we've found all the divisors, print them out in increasing order
while(@divisors) {
$next = shift @divisors;
print "$next ";
}
print "\n";
Part B:
To solve this problem, we use a nested while loop. You’ll notice the code inside the while loop is identical to Part A.
New tools used:
- eq to test for string equality
- ! the negation operator, to continue so long as the input is NOT “quit”
- interpreting the input ambiguously as either string or number
$number = "";
#This loop only stops if the user enters "quit"
while(!($number eq "quit")) {
#The text here is different, but the rest is identical to part A
print "Enter a positive integer or \"quit\": ";
$number = <>;
chomp($number);
# Initialize an empty array to hold the divisors we find
@divisors = ();
# Start testing divisor candidates, beginning with 1
$candidate = 1;
while($candidate <= $number/2) {
#If the candidate divisor cleanly divides our number, #add it to the divisor array
if( ($number % $candidate) == 0 ) {
push (@divisors, $candidate);
}
# Test the next candidate at the next iteration
$candidate++;
}
# Now that we've found all the divisors, print them out
while(@divisors) {
$next = shift @divisors;
print "$next ";
}
print "\n";
} #This bracket closes the while loop that keeps asking until “quit” is entered
Question 4:
Part A:
The novelty in this problem is the use of chr() to get the character equivalent of a number. The other elements were used previously:
- incrementing numbers
- while loop
- printing variables
# Increment this number up to 127
$number = 1;
while($number < 128) {
# Get the character equivalent of the number
$character = chr($number);
# Print number/character pairs, one to a line
print "$number - $character";
print "\n";
# Get the next character at the next while iteration
$number++;
}
Part B:
#Same as above, except that $number is initialized and incremented in the for
# Makes for cleaner, easier to understand programs
for($number=1; $number < 128; $number++) {
$character = chr($number);
print "$number - $character";
print "\n";
}
Question 5:
Part A:
The largest integer is: 2147483647
There are several ways to approach this problem.
Simply incrementing by 1 until the largest number is reached takes a while (not really sure if it’ll ever finish).
Here’s a solution that works in 2 parts. The idea is to first get within the ballpark of the largest number by adding 1000000 repeatedly. Then, once we’re within 1000000 of the largest possible integer, we increment by 1 until we find it.
# Restrict us to integers. This prevents the number from becoming a floating point if it gets too large
# As a result, if we try to add 1 to the largest possible integer, the number becomes 0 or smaller.
use integer;
$counter = 1;
# Keep track of how many times we added 1000000
$multiplier = 0;
# Keep going as long as counter is getting larger
# If it ever becomes smaller than 1, we know we passed the largest integer
while($counter > 0) {
$counter += 1000000;
$multiplier++;
}
print "Number of 1000000 additions that put us over the top: $multiplier \n\n";
# Start about 1000000 before going over the top
$counter = ($multiplier-1) * 1000000;
#Keep adding 1 till we fall over the edge, and tell us the last number we reach
while(($counter+1) > 0) {
$counter++;
}
print "$counter \n";
Output:
Number of 1000000 additions that put us over the top: 2148
2147483647
Here's another solution that takes advantage of binary representations of numbers, and the fact that multiplying by 2 is the same as a bit shift.
#Prevent switching to floating-point arithmetic if the number gets too big
use integer;
$number = 1;
#Since we avoid switching over to floating point, if $big gets too large,
#it will wrap around and become smaller than zero.
$big = 1;
while($big>0) {
# In binary, $big will be a string of 1's. ex: if $number = 8, $big = 11111111 in binary format or 2 to the power 8, minus 1
$big = 2 ** $number -1;
print "$big \n";
$number++;
}
Output:
1
3
7
15
31
63
127
255
511
1023
2047
4095
8191
16383
32767
65535
131071
262143
524287
1048575
2097151
4194303
8388607
16777215
33554431
67108863
134217727
268435455
536870911
1073741823
2147483647
-2
Part B:
We’ll again use the idea of successive approximations. This time, we’ll use multiplication instead of addition.
The code below is an example of what can be done. We first use multiplication by 2 to get within the ballpark of the largest floating point number. We then use successively smaller multipliers, always slightly larger than 1, to reach the largest value.
The last estimates provided by this code are the same value, indicating that we’ve reached the largest value possible.
$counter = 2;
$multiplier = 0;
while(!($counter eq inf)) {
$counter *= 2;
$multiplier++;
}
$max = 2**($multiplier-1);
print "first ballpark estimate $max \n\n";
# Refine the estimate
while(!($max*1.00001 eq inf)) {
$max *= 1.00001;
}
print "more fine-grained estimate: $max \n\n";
# Refine the estimate
while(!($max*1.00000001 eq inf)) {
$max *= 1.00000001;
}
print "third pass estimate: $max \n\n";
# Refine the estimate
while(!($max*1.00000000001 eq inf)) {
$max *= 1.00000000001;
}
print "fourth pass estimate: $max \n\n";
# Refine the estimate
while(!($max*1.0000000000001 eq inf)) {
$max *= 1.0000000000001;
}
print "fifth pass estimate: $max \n\n";
# Refine the estimate
while(!($max*1.000000000000001 eq inf)) {
$max *= 1.000000000000001;
}
print "sixth pass estimate: $max \n\n";
# Refine the estimate
while(!($max*1.000000000000001 eq inf)) {
$max *= 1.000000000000001;
}
print "last estimate: $max \n\n";
Output:
first ballpark estimate 4.49423283715579e+307
more fine-grained estimate: 1.79769081122934e+308
third pass estimate: 1.79769313025196e+308
fourth pass estimate: 1.79769313485405e+308
fifth pass estimate: 1.79769313486231e+308
sixth pass estimate: 1.79769313486231e+308
last estimate: 1.79769313486231e+308