Week 03: Homework 2
Range of Type Values, References, use of API
The Problem
The bunch of non-negative integer numbers written in a shape of the triangle:
is called the Euler–Bernoulli triangle and can be constructed using the following algorithm:
- the triangle is constructed row by row from the top down; the rows are indexed starting from zero (like elements in an array)
- the zeroth (top-most) row consists of the only element 1
- the first row comprises 0 and 1
- the second row begins from the right — put 0 and move to the left; at every step, we take the sum of the preceding number in the same row and the preceding number in the row above, ie, the sum of the nearest right and upper right numbers
- the third row starts at the left — put 0 and move to the right; at every step, we take the sum of the nearest left and upper left numbers
- all rows are constructed in the same way — every even indexed row begins on the right with 0 and is built right-to-left, and every odd indexed row begins on the left with 0 and is built left-to-right
The importance of this construction lies in the fact, that all non-zero numbers on the left side of the triangle represent the so-called Euler numbers, while all non-zero numbers on the right side are the so-called Bernoulli numbers. Both are important sequences in mathematics, and the described triangle gives the simplest algorithm to calculate them.
Your task is to write a program which will calculate the first n rows of the Euler–Bernoulli triangle. You may use a two-dimensional integer array, and your program will assign its elements values according to the above algorithm. Do not write code which will print the triangle as it’s done above (there are formatting problems when the numbers become multi-digit). However, using the constructed array, make your code to print all Euler and Bernoulli numbers contained in the calculated triangle…
The solution, which uses a two-dimensional integer array of long
s, is provided
to you at the start: EulerBernoulliTriangle.java. Download it
and study. Compile and run it. It should be done as follows:
% java EulerBernoulliTriangle 21
where the command line argument, 21
in the above example, must be an odd
positive number greater than 2
. The output will look as follows:
% java EulerBernoulliTriangle 21
The height of the triangle is 21
The Euler numbers:
1
1
5
61
1385
50521
2702765
199360981
19391512145
2404879675441
That's 10 Euler numbers
The Bernoulli numbers:
1
1
2
16
272
7936
353792
22368256
1903757312
209865342976
That's 10 Bernoulli numbers
However, attempts to calculate larger Euler and Bernoulli (EB) numbers soon run
into a problem: if you use the value of command line argument 27
and higher,
you will see that the EB stop growing and even become negative (which shouldn’t
happen – check the algorithm for their calculation). This is the consequence
of the finite range of the long
primitive type which is used in the program.
Your task is to modify the above program so it can calculate the EB numbers of arbitrary order. You should replace the long type onto a different one (which?!) and make appropriate changes in other places of the code.
Test the correctness of your output by comparing it with the Euler numbers from the picture:
Hint: look up the Java API docs, the package java.math
.
Assessment
You will get up to two marks, if you present a solution to the Homework exercise during the next week lab.