[Java] Java371 Lecture 3

info

This document is a class note about Java Programming taughted by Mr.Lu.

Flow Controls 流程控制

if (/* Condition: a boolean expression */) {
    // Selection body: conditional statements.
}

If the condition is evaluated true, then the conditional statements will be executed once.
If false, then the selection body will be ignored.
Note that the braces can be omitted when the body contains only single statement.

Multiple Branches

Use else if instead of else and if.

if (score >= 90)
    System.out.println("A");
else if (score >= 80)
    System.out.println("B");
else if (score >= 70)
    System.out.println("C");
else if (score >= 60)
    System.out.println("D");
else
    System.out.println("F");

Two common bugs

if (r > 0);
    double A = r * r * 3.14;
    System.out.println(A);

Do not attach semicolon to the codition. * If the parenthesis is followed by the semicolon in Line 2, Line 3 becomes unconditional and will be always executed.
Multiple conditional statements should be enclosed by braces.

The switch-case-break-default Statement

switch (target) {
    case v1:
        // Conditional statements.
        break; // Leaving (jump out the bracket).
    case v2:
        ...
    case vk:
        // Conditional statements.
        break; // Leaving (jump out the bracket).
    default:
        // Default statements.
}

example:

String symbol = "XS";

int size;
switch (symbol) {
    case "L":
        size = 10;
        break;
    case "M":
        size = 5;
        break;
    case "XS":
    case "S": // "XS" and "S" share the same action.
        size = 1;
        break;
    default:
        size = 0;
}
System.out.println(size); // Output 1;

switch expressions:

String symbol = "XS";

int size = switch (symbol) {
    case "L" -> 10;
    case "M" -> 5;
    case "S", "XS" -> 1;
    default -> 0;
}

System.out.println(size); // Output 1.

Working with Uncertainty

How to generate random numbers?

Math.random() produces numbers between 0.0 and 1.0, exclusive.
To generate integers ranging from 0 to 9, it is clear that (int)(Math.random() * 10),
In general, you could generate any integer between L and H by using (int)(Math.random() * (H - L + 1)) + L

Exercise

Q. First generate 3 random integers ranging from −50 to 50, inclusive. Then find the largest value of these integers.

int x = (int)(Math.random() * 101) - 50;
int y = (int)(Math.random() * 101) - 50;
int z = (int)(Math.random() * 101) - 50;

int max = x;
if (y > max) max = y;
if (z > max) max = z;
System.out.println("MAX = " + max);

However, this program is limited by the number of data.
To develop a reusable solution, we need arrays and loops.

The while Loops

tip

A while loop executes some statements repeatedly until the condition is false.

while (/* Condition: a boolean expression */) {
    // Loop body.
}

If the condition is evaluated true, execute the loop body once and re-check the condition.
The loop no longer continues when the condition is evaluated false.

Example: Summation

info

Write a program to sum up all integers from 1 to 100.

int sum = 0;
sum = sum + 1;
sum = sum + 2;
...
sum = sum + 100;

As you can see, there exist many similar statements and we proceed to wrap them by using a while loop!

int sum = 0;
int i = 1;
while (i < 100) {
    sum = sum + i;
    ++i;
}

Lurked Bugs 潛伏蟲蟲: Malfunctioned Loops

It is easy to make an infinite loop: always true.

while (true);

The common issues of writing loops are as follows:
- loops never start;
- loops never stop;
- loops do not finish the expected iterations.

Loop Design Strategy

Identify the statements that need to be repeated.
Wrap those statements by a loop.
Set a proper continuation condition.

Indefinite Loops 不定曖昧迴圈

tip

Indefinite loops are the loops with unknown number of iterations.

It is also called the sentinel-controlled loops, whose sentinel value is used to determine whether to execute the loop body
For example, the operating systems and the GUI apps.

Example: Cashier

info

Write a program to (1) sum over positive integers from consecutive inputs until the first non-positive integer occurs and (2) output the total value.

int total = 0, price = 0;
Scanner input = new Scanner(System.in);

System.out.println("Enter price?");
price = input.nextInt();
while (price > 0) {
total += price;
System.out.println("Enter price?");
price = input.nextInt();
}

System.out.println("TOTAL = " + total);
input.close();

The do-while Loops

tip

A do-while loop is similar to a while loop except that it first executes the loop body and then checks the loop condition.

do {
    // Loop body.
} while (/* Condition: a boolean expression */);

Do not miss a semicolon at the end of do-while loops.
The do-while loops are also called the posttest loops, in contrast to the while loops, which are the pretest loops.

Example: Cashier (Revisited)

info

Write a program which sums over positive integers from consecutive inputs and then outputs the sum when the input is nonpositive.

int total = 0, price = 0;
Scanner input = new Scanner(System.in);

do {
    total += price;
    System.out.println("Enter price?");
    price = input.nextInt();
} while (price > 0);

System.out.println("Total = " + total);
input.close();

The for loops

tip

A for loop uses an integer counter to control how many times the body is executed.

for (initial-action; condition; increment) {
    // Loop body.
}

initial-action: declare and initialize a counter.
condition: check if the loop continues.
increment: how the counter changes after each iteration.

Example: Summation (Revisited)

info

Write a program to sum up the integers from 1 to 100.

int sum = 0;
for (int i = 1; i <= 100; ++i)
    sum = sum + i;

Numerical Example: Monte Carlo Simulation

Write a program to estimate π.
Let N be the total number of points and M be the number of points falling in a quarter circle, illustrated in the next page.
The algorithm states as follows:
- For each round, draw a point by invoking Math.random() twice and check if the point falls in the quarter circle.
- If so, then do M++; otherwise, ignore it.
- Repeat the previous two steps for N rounds.
Hence, we can calculate the estimate

int N = 100000;
int M = 0;

for (int i = 1; i <= N; i++) {

    double x = Math.random();
    double y = Math.random();

    if (x * x + y * y < 1) M++;

}

System.out.println("pi ˜ " + 4.0 * M / N);

Note that ˆπ → π as n → ∞ by the law of large numbers
This algorithm is one example of Monte Carlo simulation.

Jump Statements: Example

tip

The statement break and continue are often used to provide additional controls in repetition structures.

break:

for (int i = 1; i <= 5; ++i) {

    if (i == 3) {
        break;
        // Early termination.
    }

    System.out.println(i);
}
// Output: 1 2

continue:

for (int i = 1; i <= 5; ++i) {

    if (i == 3) {
        continue;
        // Early termination.
    }

    System.out.println(i);
}
// Output: 1 2 4 5

Example: Primality Test

info

Write a program to check if the input integer is a prime number.

Sanner input = new Scanner(System.in);
System.out.println("Enter x > 2?");
int x = input.nextInt();
boolean isPrime = true;
input.close();

for (int y = 2; y <= Math.sqrt(x); y++){
    if (x % y == 0) {
        isPrime = false;
        break;
    }
}

if (isPrime) {
    System.out.println("Prime");
} else {
    System.out.println("Composite");
}

Example: Compunding

info

Write a program to determine the holding years for an investment doubling its value.

int r = 18; // In percentage.
int balance = 100;
int goal = 200;

int years = 0;
while (balance < goal) {
    balance *= (1 + r / 100.0);
    years ++;
}

System.out.println("Holding years = " + years);
System.out.println("Balance = " + balance);

...
int years = 0;
for (; balance < goal; years++) {
    balance *= (1 + r / 100.0);
}
...

...
int years = 0;
for (; ; years++) {
    balance *= (1 + r / 100.0);
    if (balance >= goal) break;
}
...

Remarks

The while loops are equivalent to the for loops.
You can always rewrite the for loops by the while loops, and versa.
In practice, you could use a for loop when the number of repetitions is known.
Otherwise, a while loop is preferred.

Nested Loops: Example

info

Write a program to print the 9 × 9 multiplication table.

for (int i = 1; i <= 9; ++i) {

    // In row 1, output each i * j.
    for (int j = i; j <= 9; ++j) {
        System.out.printf("%3d", i * j);
    }
    System.out.println();
}

Digression: Output Format

Use System.out.printf() to display formatted outputs.
For example,

System.out.printf("Pi = %4.2f", 3.1415926);
// Output 3.14;

Without specifying the width, only 6 digits after the decimal point are displayed.

By default, the output is right justified.
If a value requires more spaces than the specified width, then the width is automatically increased.
You may try various parameters such as the plus sign (+), the minus sign (-), and 0 in the middle of format specifiers.
- Say %+8.2f, %−8.2f, and %08.2f.

Triangle Exercises

4 kind of trangles

Analysis of Algorithm

A problem may be solved by various algorithms.
We compare these algorithms by measuring their efficiency.
Adopting a theoretical approach, we identify the growth rate of running time in function of input size n.
This introduces the notion of time complexity.

Example1: SUM

int sum = 0, i = 1; // Assign −> 2.
while (i <= n) { // Compare −> n + 1.
    sum=sum+i; //Addandassign−>2n.
    ++i; // Increase by 1 −> n.
}

Let n be any nonnegative number.
Then count the number of all runtime operations.
Note that we ignore declarations in the calculation. (Why?)
In this case, the total number of operations is 4n + 3.

Example2: TRIANGLE

Clearly, g (n) is the asymptotic upper bound of f (n).14
In other words, big O implies the worst case of the algorithm.
We then classify the algorithms in Big O sense.

Conclusion

We should strike a balance by making a trade-off between generality and efficiency.

To reuse the program, it must be a general solution whose assumption should be little and weak.
To speed up the program, it could be optimized for the desire cases (so making assumptions).
All in all, the time complexity is about the effort spent on the task but not how many time you sacrifice.

[Java] Java371 Lecture 3

Flow Controls 流程控制​

Multiple Branches​

Two common bugs​

The switch-case-break-default Statement​

Working with Uncertainty​

Exercise​

The while Loops​

Example: Summation​

Lurked Bugs 潛伏蟲蟲: Malfunctioned Loops​

Loop Design Strategy​

Indefinite Loops 不定曖昧迴圈​

Example: Cashier​

The do-while Loops​

Example: Cashier (Revisited)​

The for loops​

Example: Summation (Revisited)​

Numerical Example: Monte Carlo Simulation​

Jump Statements: Example​

Example: Primality Test​

Example: Compunding​

Remarks​

Nested Loops: Example​

Digression: Output Format​

Triangle Exercises​

4 kind of trangles​

Analysis of Algorithm​

Example1: SUM​

Example2: TRIANGLE​

Conclusion​

Flow Controls 流程控制

Multiple Branches

Two common bugs

The switch-case-break-default Statement

Working with Uncertainty

Exercise

The while Loops

Example: Summation

Lurked Bugs 潛伏蟲蟲: Malfunctioned Loops

Loop Design Strategy

Indefinite Loops 不定曖昧迴圈

Example: Cashier

The do-while Loops

Example: Cashier (Revisited)

The for loops

Example: Summation (Revisited)

Numerical Example: Monte Carlo Simulation

Jump Statements: Example

Example: Primality Test

Example: Compunding

Remarks

Nested Loops: Example

Digression: Output Format

Triangle Exercises

4 kind of trangles

Analysis of Algorithm

Example1: SUM

Example2: TRIANGLE

Conclusion