created 02/22/2018
Instructions: Write each of these programs as specified.
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.
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.
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.
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 BigInteger
s.
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.
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.
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.
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