------------------------------- prog 1 ------------------------------- program that has -- one class, -- that class contains one method: main -- does all its work in main -- work: sum up all integers from 1 to 100 and print the sum. has no user input output: 5050 ------------------------------- prog 2 ------------------------------- program that has -- one class, -- that class contains two methods: main and summer -- main gets a positive integer from the kayboard -- main calls summer, passes that integer to summer -- summer sums up all positive integers from 1 to the one given at the kayboard and passed in to summer -- summer returns the sum to main -- main prints the sum input: 100 output: 5050 input: 5 output: 15 input: 4321 output: 9337681 ------------------------------- prog 3 ------------------------------- program that has -- two classes, Main, and Summer -- Main contain the main method -- Summer contains the method summer -- in Main.main create an object of class Summer -- in Main.main, get a positive integer from the keyboard -- in Main.main, call the summer method in the object of class Summer pass it the integer from the user -- summer works as it did in prog 2... returns the sum of integers from 1 to the one passed to it -- Main.main prints the sum input: 100 output: 5050 input: 5 output: 15 input: 4321 output: 9337681 ------------------------------- prog 4 ------------------------------- program that has -- three classes: Main, Prodder, Summer -- Main and Summer same as prog 3 basically -- Prodder is like Summer except it has a method "product" instead of "summer" -- method product computed the product of the integers from 1 to the positive integer passed to it -- in Main.main, get a positive integer from the user keyboard -- in Main.main, make one object of class Summer, and make another object of class Prodder -- call the product method of the object of class Prodder... it return to Main.main a positive integer -- then pass that returned integer into the summer method of the object of class Summer... it returns to Main.main another integer -- Main.main prints out the integer returned from the Summer object call to summer method input: 5 output: 7,260 input: 7 output: 12,703,320 input: 10 output: 6,584,096,534,400 input: 11 output: 796,675,481,078,400 input: 12 output: 114,721,266,640,780,800 input: 13 output: 941,149,951,220,278,784 input of 14 will overflow a variable of type "long" long is 8 bytes and holds integers from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 ------------------------------------- prog 5 ------------------------------------- Input: a sequence (array) of non-negative integers each element has a value smaller than 1,000,000 the sequence is no longer than 100,000 elements output: the order of the output sequence is "sorted" is a specific way every element that is non-prime will appear in the same spot in the output sequence that it has in the input sequence the remaining output spots will be occupied by the prime elements, but appearing in sorted order smallest to largest 1) write the Java program to do this 2) analyze its worst-case time complexity of your algorithm what are the parameters we need to characterize the problem? Sample input/output in: 23 101 12 45 17 59 06 21 43 88 the primes here (in orignal order) are: 23 97 12 45 17 59 06 21 43 88 . . . . . ^ ^ ^ ^ ^ 23 97 17 59 43 sorted the primes are 17 23 43 59 97 now putting them back into the original sequence in the original prime places... . . 12 45 . . 06 21 . 88 ^ ^ ^ ^ ^ 17 23 43 59 97 out: 17 23 12 45 43 59 06 21 97 88 ------------------------------------- prog 6 ------------------------------------- Lets write a program or 3 to mess with the Fibonacci sequence. The Fibonnaci sequence is a sequence of non-negative integers. For these programs, let's define the Fibonacci sequence this way fib(1) = 0 // the first fib num is 0 fib(2) = 1 // the second fib num is 1 fib(n) = fib(n-1) fib(n-2) for n>=3 so the first few elements in the sequence are 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 From this example, we see that the 5th element in the sequence is fib(5) is 3, and the 11th element in the sequence is fib(11) is 55, the 16th element is 610, etc. 1) write a program that will compute the nth element in the Fibonacci sequence. Do this with a main program, and a recursive methods "fib" that takes one parameter, an integer n. fib will return an int which is the value of the nth element in the sequence. Make this program read an integer from the keyboard in main, and compute (and print out) the fib of the integer. 2) write an equivalent program that reads the integer from the keyboard, but this time fib is iterative, not recursive Consider this... can you use your recursive program and compute fib(45) ? Can you compute fib(45) with your iterative version? 3) write slight changes to each of your (1) and (2) programs to make new programs that will print the first N fibonacci numbers (not just the single number fib(n)). Do one for the interative fib, and one for the recursive. ------------------------------------- prog 7 ------------------------------------- Now do these 4 more programs like in problem 6 (iterative and recursive, single N and whole sequence) for the factorial formula. The sequence of factorials is a sequence of positive integers where fact(1) = 1 fact(n) = fact(n-1) * n for n > 1 Analyse the time complexity of each program