(a + b)^n == a^n
+ (n choose 1) a^(n-1)*b
+ (n choose 2) a^(n-2)*b^2
+ (n choose 3) a^(n-3)*b^3
+ ...
+ (n choose 1) a*b^(n-1)
+ b^n.
As discussed in class, use two arrays to construct rows of Pascal's
triangle one at a time, following the recursion
(n choose k) = (n-1 choose k) + (n-1 choose k-1).
Watch out for overflow! Because these numbers are extremely large,
even when n is of only modest size, store all values as
type double. Before adding two numbers together, check
that the sum is not greater than DBL_MAX.
You may set 1500 as an upper limit of accepted user-specified values
for n. Determine the smallest value of n for which
floating point overflow occurs for some choice of k,
and explain in your report the strategy you used to find these values of
n and k.
Be careful that your program does not print more digits than it can accurately compute. The IEEE double precision format supports about 16 decimal digits of precision. Hence, do not print more than 16 decimal digits to the screen. Format large numbers in scientific notation with at most 15 digits in the mantissa.
Finally, make sure your program reports an overflow error only if the user's requested value of n choose k is too large to represent with type double. If overflow occurs in the computation of some element of the triangle, say m choose j, that isn't needed to compute the user's requested value of n choose k, then that occurrence can be safely ignored, and calculations can proceed. One way to proceed is simply to set the overflowed value to -1.0 and make sure that it is not used to calculate subsequent values of m+1 choose j etc. For example, although 1500 choose 300 is too large to store as type double, 1500 choose 100 is not; see the sample input/output below.
n-choose-k calculator. Enter n and k such that (1500 >= n >= k >= 0): 5 3 5 choose 3 = 10. n-choose-k calculator. Enter n and k such that (1500 >= n >= k >= 0): 10 5 10 choose 5 = 252. n-choose-k calculator. Enter n and k such that (1500 >= n >= k >= 0): 20 5 20 choose 5 = 15504. n-choose-k calculator. Enter n and k such that (1500 >= n >= k >= 0): 20 10 20 choose 10 = 184756. n-choose-k calculator. Enter n and k such that (1500 >= n >= k >= 0): 50 25 50 choose 25 = 126410606437752. n-choose-k calculator. Enter n and k such that (1500 >= n >= k >= 0): 100 50 100 choose 50 = 1.00891344545564e+29. n-choose-k calculator. Enter n and k such that (1500 >= n >= k >= 0): 500 200 500 choose 200 = 5.05494984993553e+144. n-choose-k calculator. Enter n and k such that (1500 >= n >= k >= 0): 1500 100 1500 choose 100 = 1.48993278712698e+158. n-choose-k calculator. Enter n and k such that (1500 >= n >= k >= 0): 2000 100 nChooseK.cpp:67: failed assertion `NMAX >= n && n >= k && k >= 0' Abort n-choose-k calculator. Enter n and k such that (1500 >= n >= k >= 0): 1500 300 Error in function nChooseK(): maximum representable floating point value 1.79769e+308 exceeded!
Submit a file p5.zip which produces two files when decompressed: report.xxx and p5.cpp.