Java Reference
In-Depth Information
// Version 2
public boolean hasTwoTrueValues( boolean [ ] arr )
{
for( int i = 0; i < arr.length; i++ )
for( int j = i + 1; j < arr.length; j++ )
if( arr[ i ] && arr[ j ] )
return true;
return false;
}
// Version 3
public boolean hasTwoTrueValues( boolean [ ] arr )
{
for( int i = 0; i < arr.length; i++ )
if( arr[ i ] )
for( int j = i + 1; j < arr.length; j++ )
if( arr[ j ] )
return true;
return false;
}
IN PRACTICE
5.30
Give an efficient algorithm to determine whether an integer
i
exists
such that in an array of increasing integers. What is the run-
ning time of your algorithm?
A
i
=
i
A prime number has no factors besides 1 and itself. Do the following:
a.
5.31
Write a program to determine if a positive integer
N
is prime. In
terms of
N
, what is the worst-case running time of your program?
b.
Let
B
equal the number of bits in the binary representation of
N
.
What is the value of
B
?
c.
In terms of
B
, what is the worst-case running time of your program?
d.
Compare the running times to determine if a 20-bit number and a
40-bit number are prime.
An important problem in numerical analysis is to find a solution to the
equation for some arbitrary
F
. If the function is continuous
and has two points
low
and
high
such that and have
opposite signs, then a root must exist between
low
and
high
and can be
found by either a binary search or an interpolation search. Write a func-
tion that takes as parameters
F
,
low
, and
high
and solves for a zero.
What must you do to ensure termination?
5.32
F
( )
=
0
F low
(
)
F high
(
)
Search WWH ::
Custom Search