Algorithms with-java-1.0

Solve problems with Java code Algorithms with Java

Sum 1..N – Example Calculate and print the sum of the first N positive numbers Scanner input = new Scanner(System.in); System.out.print("n = "); int n = input.nextInt(); int num = 1; int sum = 1; System.out.print("The sum 1"); while (num < n) { num++; sum += num; System.out.printf("+%d", num); } System.out.printf(" = %d%n", sum);

Calculating Sum 1..N Live Demo

Prime Number – Example Checking if a number is prime or not Scanner input = new Scanner(System.in); System.out.print("Enter a positive integer: "); int num = input.nextInt(); int divider = 2; int maxDivider = (int) Math.sqrt(num); boolean prime = true; while (prime && (divider <= maxDivider)) { if (num % divider == 0) { prime = false; } divider++; } System.out.println("Prime? " + prime);

Checking If a Number Is Prime Live Demo

Using break Operator break operator exits the inner-most loop Scanner input = new Scanner(System.in); int n = input.nextInt(); // "long" is the biggest integer type long factorial = 1; // Perform an infinite loop while (true) { if (n == 1) { break; } factorial *= n; n--; } System.out.println("n! = " + factorial);

Calculating Factorial Live Demo

Factorial – Example Calculating N factorial Scanner input = new Scanner(System.in); System.out.print("n = "); int n = input.nextInt(); long factorial = 1; do { factorial *= n; n--; } while (n > 0); System.out.println("n! = " + factorial);

Factorial (do ... while) Live Demo

Recursion Calling a Method by Itself

What is Recursion? Recursion is calling a method by itself Very powerful technique for implementing combinatorial algorithms Recursion should have Direct or indirect recursive calls The method calls itself directly or through other methods Exit criteria (bottom) Prevent infinite recursion

Factorial – Example N! (N Factorial) N! = N * (N – 1)! for N >= 0 and 0! = 1 5! = 5 * 4! or 5 * 4 * 3 * 2 * 1 * 1 = 120 4! = 4 * 3! or 4 * 3 * 2 * 1 * 1 = 24 3! = 3 * 2! or 3 * 2 * 1 * 1 = 6 2! = 2 * 1! or 2 * 1 * 1 = 2 1! = 1 * 0! or 1 * 1 = 1 0! = 1

Factorial – Example Calculating factorial: 0! = 1 n! = n* (n-1)!, n>0 Don't do this at home! Use iteration instead Recursive call: the method calls itself The bottom of the recursion public static int f actorial(int n) { if (n == 0) return 1; else return n * f actorial(n - 1); }

Product[N..M] – Example Calculating the product of all numbers in the interval [n..m]: int n = input.nextInt(); int m = input.nextInt(); int num = n; long product = 1; do { product *= num; num++; } while(num <= m); System.out.println("product[n..m] = " + product);

Product of the Numbers in the Interval [n..m] Live Demo

N^M – Example Calculating n^m Scanner input = new Scanner(System.in); int n = input.nextInt(); int m = input.nextInt(); long result = 1; for (int i = 0; i < m; i++) { result *= n; } System.out.println("n^m = " + result);

Using continue Operator continue operator ends iteration of the inner-most loop Example: Sum odd numbers p in [1, n] that are not divisors of 7: int n = input.nextInt(); int sum = 0; for (int i = 1; i <= n; i += 2) { if (i % 7 == 0) continue; sum += i; } System.out.println("sum = " + sum);

Using continue Operator Live Demo

Nested Loops Using Loop Inside a Loop

What Is Nested Loop? A composition of loops is called a nested loop Example: for (initialization; test; update) { for (initialization; test; update) { statements; } … }

Triangle – Example Print the following triangle on the console: 1 1 2 … 1 2 3 ... n int n = input.nextInt(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { System.out.print(j + " "); } System.out.println(); }

Primes[N, M] – Example Print all prime numbers in [n, m] int n = input.nextInt(); int m = input.nextInt(); for (int num = n; num <= m; num++) { boolean prime = true; int divider = 2; int maxDivider = (int) Math.sqrt(num); while (divider <= maxDivider) { if (num % divider == 0) { prime = false; break; } divider++; } if (prime) { System.out.printf("%d ", num); } }

Primes in Range [n, m] Live Demo

Nested Loops – Examples Print all four digit numbers ABCD such that A+B = C+D (happy numbers) for (int a = 1; a <= 9; a++) { for (int b = 0; b <= 9; b++) { for (int c = 0; c <= 9; c++) { for (int d = 0; d <= 9; d++) { if ((a + b) == (c + d)) { System.out.printf("%d,%d,%d,%d", a, b, c, d); } } } } } Can you improve this algorithm to use only 3 loops?

TOTO 6/49 – Examples Print all combinations from TOTO 6/49 for (int i1 = 1; i1 <= 44; i1++) for (int i2 = i1 + 1; i2 <= 45; i2++) for (int i3 = i2 + 1; i3 <= 46; i3++) for (int i4 = i3 + 1; i4 <= 47; i4++) for (int i5 = i4 + 1; i5 <= 48; i5++) for (int i6 = i5 + 1; i6 <= 49; i6++) System.out.printf( "%d %d %d %d %d %d%n", i1, i2, i3, i4, i5, i6); How long will it take to finish this?

Summary Loops could solve different problems Recursion could be handy as well We can use nested loops to implement more complex logic We can use continue and break operators to control the loop execution More to come with arrays' manipulation

Exercises Write a program that prints all the numbers from 1 to N. Write a program that prints all the numbers from 1 to N, that are not divisible by 3 and 7. Write a program that reads from the console a sequence of N integer numbers and returns the minimal and maximal of them. Write a program that calculates N!/K! for given N and K (1<N<K).

Exercises (3) Write a program that reads a number N and calculates the sum of the first N members of the sequence of Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, … In the combinatorial mathematics, the Catalan numbers are calculated by the following formula: Write a program to calculate the Catalan number by given N.

Exercises (4) Write a program that reads from the console a positive integer number N (N < 20) and outputs a matrix like the following: N = 3 N = 4 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 1 2 3 2 3 4 3 4 5

Exercises (5) Write a program that calculates for given N how many trailing zeros present at the end of the number N!. Examples: N = 10  N! = 36288 00  2 N = 20  N! = 243290200817664 0000  4 Does your program work for N = 50 000? Hint: The trailing zeros in N! are equal to the number of its prime divisors 5. Think why!

Algorithms with-java-1.0

Recommended

More Related Content

What's hot (20)

Similar to Algorithms with-java-1.0 (20)

More from BG Java EE Course (20)

Recently uploaded (20)

Algorithms with-java-1.0

Editor's Notes