Programming and Computer Science in Java:

See Course Home Page.

**P&CS Programming Labs: Extra Credit Exercises
**You are not required to do these problems, but you will of course be given
credit if you elect to do them. You can solve all of these problems using
only those techniques covered in Lab #1.

35. Write a Java program which reads in two positive integers and uses
Euclid's method to find and print out their greatest common divisor (GCD).
If necessary, perform an Internet search (say, using Google) to find a clear
description of Euclid's GCD algorithm, but the *very terse* explanation is
that, given two numbers x and y, where x > y, the gcd(x,y) is in fact the
same as the gcd(y,x%y). *Demonstrate this to yourself with a few
examples worked out by hand*. So: to find the gcd(x,y), where
x>y, repeatedly reduce the two numbers to y,x%y until finally x%y is zero, at
which point y holds your answer. Again, this explanation is intentionally
terse, and there are many more complete explanations online.

36. Write a Java program which asks the user to randomly select a
number between 1 and 1 million, and then your program guesses the number.
This is achieved by setting two variables --"lo" and "hi" --
initially to 1 and 1 million, respectively. Your guess at each step is the
*average* of lo and hi, call this "mid". At each step, and
given a very suitable prompt by your program, the user will enter "0"
if you are correct, "1" if you are too low, and "2" if you
are too high (soon, when you know how to handle string input, we can do better
than this for user input; for now, though, this will do just fine). If
your guess is correct, print out "wahoo, got it in *count*
guesses", where of course count is replaced with the number of guesses your
program actually required. If your guess is incorrect, adjust
"lo" or "hi" accordingly. Note: say you are too
high. You would *not* set "hi" to "mid".
Why not? Because you know mid *cannot be the answer!* So you
would set "hi" to "mid - 1". Think about this, and do
the analogous operation for "lo" if you are too low.

*Thought questions: what is the maximum number of guesses you could
possibly require in this problem? Give an example number which in fact
requires that many guesses. Also, if instead of the range being
[1,1million], say the range was [1,n], for arbitrary n -- then how many guesses
would your program require in the worst case?*

37. The *Fibonacci Numbers* are the numbers 1, 1, 2, 3, 5, 8, 13,
21,.... Note that each Fibonacci Number is simply *the sum of the two
preceding Fibonacci Numbers.* So the next number in the sequence is 13
+ 21 = 34. Write a program which repeatedly reads in an integer n, exiting
when n < 0, and otherwise printing out the nth Fibonacci Number (where the
0th and 1st Fibonacci numbers are both 1, and the 2nd Fibonacci number is 2, and
so on).

38. Write a Java program which reads in a positive integer n and prints
out the *sum of the decimal digits of n*. So if the input is 536,
your program would output the sum 5 + 3 + 6, or 14.

39. Write a Java program which reads in a positive integer n and prints
out the *sum of the binary digits of n *(if you think about it, this is the
same thing as saying "the number of ones in the binary representation of
n"). So if the input is 29, this number in binary is 11101_{2},
and this number has 4 ones, and so your program would output 4. Likewise,
if the input is 536, this number in binary is 1000011000_{2}, and this
number has 3 ones, and so your program would output 3. *Hint: This
program is a very minor variant of the preceding program!*

40. Write a Java program which reads in a non-negative integer and
prints out whether or not that number is a *palindrome*. That is,
whether or not it is the *same forwards as backwards*. For example,
the following numbers are palindromes: 6, 22, 181, 23532.

41. A *perfect number* is a number which is the *sum of its
positive integer factors* (these are just the prime factors plus 1 and the
number itself). The first three perfect numbers are:

6 = 1 + 2 + 3,

28 = 1 + 2 + 4 + 7 + 14

496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248

Write a Java program which reads in a number n and prints out the nth perfect
number, where the 0th perfect number is 6. Your program should also
demonstrate this number is perfect by printing out the full sum, such as:

Enter a number [<=0 to exit]: 1

perfect number #1 is 28, and 28 = 1 + 2 + 4 + 7 + 14

Enter a number [<=0 to exit]: -1

Goodbye!

42. Write a Java program which reads in four whole numbers, a, b, c, and d. You are guaranteed that the product of some of those numbers equals the product of the rest of the numbers. So, perhaps a = b*c*d, or a*b = c*d, or a*d = b*c. Print out a line showing the correct equality. Always place a on the left-hand-side, and on both the left-hand and right-hand sides, list the integers in the same order as given in the input. So, if the input is 3 36 6 2, your output must be 3 * 6 * 2 = 36.

43. Write a Java program which reads in a positive integer r, and
prints out the number of lattice points strictly inside (hence, not on the
perimeter) the first quadrant of the circle centered at (0,0) with radius
r. A "lattice point" is a point which has integer coordinates,
and restricting this to the first quadrant requires that both x and y be
non-negative (thus, by this definition, (0,0) *is* in the first
quadrant). So if the input is 6, we can verify that the following nine
first-quadrant lattice points lie within that circle:
(0,0),(1,0),(0,1),(2,0), (1,1),(0,2), (2,1), (1,2), (2,2). Thus, the
answer on input of 6 is 9.

See Course Home Page.