created 02/22/2018


Chapter 86 Programming Exercises

Instructions: Write each of these programs as specified.


Exercise 1 — Warm-up

Write a program that asks the user for N and adds up the integers between 1 and N. Print out the result. Do this in a loop.

Then, use the formula

SUM (1 to N) = N*(N+1)/2

to compute the same thing. Print out that result. Hopefully your results are the same for both methods.

? java Exercise01
N  : 1000
Series  Sum: 500500
Formula Sum: 500500

? java Exercise01
N  : 1000000000
Series  Sum: 500000000500000000
Formula Sum: 500000000500000000

? java Exercise01
N  : rats
Exception in thread "main" java.lang.NumberFormatException:
 

Click here to go back to the main menu.


Exercise 2 — Add up Integers in a Range

Write a program that asks the user for N and M and adds up the integers between N and M (inclusive). Print out the result. Do this in a loop.

Then, use the formula

SUM(N to M) = SUM( 1 to M ) - SUM( 1 to N-1 )  

to compute the same thing. Print out that result. Hopefully your results are the same for both methods.

? java Exercise02
M (start): 10
N (end)  : 100
Series  Sum: 5005
Formula Sum: 5005

? java Exercise02
M (start): 1000
N (end)  : 2000
Series  Sum: 1501500
Formula Sum: 1501500

? java Exercise02
M (start): 10000000
N (end)  : 23000000
Series  Sum: 214500016500000
Formula Sum: 214500016500000

? java Exercise02
M (start): -1000
N (end)  : 1000
Series  Sum: 0
Formula Sum: 0

Click here to go back to the main menu.


Exercise 3 — Sum of Odds

Write a program that asks the user for N and adds up the first N odd integers. Print out the result. Do this in a loop. Use the fact that the N'th odd number is 2*N + 1

Then, write out N2 and compare the two results.

Click here Back to the main menu.


Exercise 4 — Factorial and Combinations

N factorial is the product of all integers 1 through N. Usually it is written N! Factorial of zero is one, by definition: 0! = 1. Pseudo-code:

set fact = 1
for j from 1 to N
  fact = fact * j

N! quickly gets very big. A rule-of-thumb: never compute N!. Even if a formula is written with N! there is usually a way to avoid computing it directly.

Write a program that prompts the user for an N and then writes out N! computed with data type long and then computed with BigIntegers. Notice that the long overflows quickly and gives no indication that this has happened.

Write both factorial functions as static methods of your class. The long version should accept a long argument and return a long value. The BigInteger version should accept a reference to a BigInteger and an argument and return a BigInteger reference.

? java Exercise04
N  : 10
Long Factorial: 3628800
Big  Factorial: 3628800

? java Exercise04
N  : 20
Long Factorial: 2432902008176640000
Big  Factorial: 2432902008176640000

? java Exercise04
N  : 21
Long Factorial: -4249290049419214848
Big  Factorial: 51090942171709440000

Once the above is working, modify the program so that it includes a static method that computes combinations of N things taken R at a time. The main method should prompt the user for N and R. Usually the formula is written

NCR = N!/(R!*(N-R!))

The rule-of-thumb says to not compute the three factorials but to do cancellation between numerator and denominator to simplify the calculation. In the formula (as given) there are N integers in the numerator and N integers in the denominator. For example, with 10C6:

10 9 8 7 6 5 4 3 2 1
--------------------
4 3 2 1 6 5 4 3 2 1

Find whichever of R or (N-R) is larger. Calculate the numerator in a loop that starts at max+1. Calculate the denominator in a loop that goes up to N-max.

? java Exercise04
N  : 10
R  : 6
10 things taken 6 at a time = 210

? java Exercise04
N  : 37
R  : 10
37 things taken 10 at a time = 348330136

? java Exercise04
N  : 55
R  : 20
55 things taken 20 at a time = 505037289962205

? java Exercise04
N  : 789
R  : 1
789 things taken 1 at a time = 789
?

Click here Back to the main menu.


Exercise 5 — Fibonacci

If factorial is here, can Fibonacci be far behind? Like factorial, the Fibonacci sequence grows rapidly. It is a sequence of integers that starts out as

1, 1

The next term in the series is the sum of the previous two:

1, 1, 2

This keeps going as long as you want:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

The rule for the N'th term of the sequence is is:

Fib( 1 ) = 1
Fib( 2 ) = 1
Fib( N ) = Fib( N-2 ) + Fib( N-1 )

Write a program that asks the user for N and prints out the N'th term of the series.

? java Exercise05
N  : 10
Fibonacci = 55

? java Exercise05
N  : 20
Fibonacci = 6765

? java Exercise05
N  : 100
Fibonacci = 354224848179261915075

N can be a long and the counting loop that calculates the terms can be an ordinary for loop that counts up to N. It is unlikely that anyone will want to calculate Fibonacci for an N that takes a BigInteger to express. This is similar to the pow() method, that takes an int argument for the same reason.

If you compute this recursively, it will be very much slower and your program will likely run out of memory:

Click here Back to the main menu.


Exercise 6 — Prime Improvement

Make the two improvements to the prime number detection method of the chapter:

  public static Boolean isPrime( BigInteger N )
  {
    BigInteger trial;
    
    trial = new BigInteger( "2" );
    while ( trial.compareTo( N ) < 0 )
    {
      if ( N.mod(trial).equals( BigInteger.ZERO ) )
        return false;
      trial = trial.add( BigInteger.ONE );
    } 
    return true;    
  }

1. If N is even, immediately return false. Otherwise, there is no need to test if any multiple of two divides the number. So, after testing if the number is even, start the trial divisor at three and increment by two each iteration.

2. Trial divisors need not be any larger than the square root of the number, since if the number equals the product N*M, one of N or M must be equal or smaller than the square root.

To implement this, you don't need to calculate the square root of N. The loop generates a sequence of trial divisors. As soon as the square of the current trial divisor exceeds the suspected prime, end the loop.

Click here Back to the main menu.


Exercise 7 — Greatest Common Divisor, GCD

Write a program that asks the user for M and N and computes their gcd. The integers might be very large, so use BigInteger

The greatest common divisor of two positive integers is the largest integer that divides them both with no remainder. For example,

gcd( 25, 15 ) == 5, because 5 is the largest integer that divides both 25 and 15

gcd( 36, 24 ) == 12

gcd( 21, 10 ) == 1, because 1 is the only divisor 21 and 10 have in common

gcd( 28, 7 ) == 7

gcd( N, 0 ) == N, because  N divides N and N also divides 0 (with result 0)

To calculate the gcd( M, N ) do this:

while M not equal N
{
  if M > N
    M = M - n
  else
    N = N - M
}   
return M

For example, say M=36 and N=24

M=36 not equal N=24
  M = 26-24 = 12
  
M=12 not equal N=24
  N = 24 - 12 = 12
  
M and N are equal, gcd = 12

Write a program that asks the user for M and N and computes their gcd. (There is a faster algorithm for computing the gcd.)

The class BigInteger has a gcd( BigInteger N) method. Use this in your program to see if your code is working.

Click here Back to the main menu.


End of Exercises