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