Java Reference
In-Depth Information
computer science related to the
P
=
NP
? conjecture. Solving this conjecture
is one of the seven key challenges proposed by the Clay Mathematics Institute
4
in its Millenium problem collection, with a rewarding of one million dollars.
9.6 Exercices
Exercise 9.1 (Binomial coe
cients and Pascal triangles)
The
choose function
C
n,k
=
n
k
is the number of different ways one can choose
k
objects among a set of
n
objects. We have
n
k
=
n
!
(
n
−
k
)!
k
!
for 0
n
, where
x
! denotes the factorial of integer
x
. Binomial
coecients arise naturally in the polynomial expansion of
≤
k
≤
n
k
x
k
.
n
(
x
+1)
n
=
k
=0
Scholar Blaise Pascal (1623-1662) used the following recurrence relation:
-
C
n,k
=
C
n−
1
,k−
1
+
C
n−
1
,k
,and
-
C
n,n
=
C
n,
0
= 1 (terminal states)
to compute coecients
C
n,k
in a triangle shape depicted as below for
n
= 5. Rows are indexed by
n
, and columns by
k
≤
n
.
1
11
121
1331
14641
15101051
-
Give a plain recursive function for computing the
C
n,k
coecients,
and use that procedure to compute the Pascal triangle.
-
Try running the program with
n
= 35. What happens? Please explain.
4
http://www.claymath.org/millennium/P_vs_NP/
Search WWH ::
Custom Search