Programming and Computer Science in Java:
Class Notes:  Lab #1 -- Extra Credit Exercises
    David Kosbie, 2002-2003

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 111012, and this number has 4 ones, and so your program would output 4.  Likewise, if the input is 536, this number in binary is 10000110002, 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