程序代写代做代考 data structure go Java algorithm html Loops

Loops
EECS2030: Advanced Object Oriented Programming Fall 2017
CHEN-WEI WANG
Motivation of Loops
• We may want to repeat the similar action(s) for a (bounded) number of times.
e.g., Print the “Hello World” message for 100 times
e.g., To find out the maximum value in a list of numbers
• We may want to repeat the similar action(s) under certain circumstances.
e.g., Keep letting users enter new input values for calculating
the BMI until they enter “quit”
• Loops allow us to repeat similar actions either
a specified number of times; or
a specified condition holds true.
3 of 77
for
while
Learning Outcomes
Understand about Loops :
• Motivation: Repetition of similar actions • Two common loops: for and while
• Primitive vs. Compound Statements
• Nesting loops within if statements
• Nesting if statements within loops
• Common Errors and Pitfalls
2 of 77
The for Loop (1)
for (int i = 0; i < 100; i ++) { System.out.println("Welcome to Java!"); } 4 of 77 The for Loop (2) i 0 1 2 ... 99 100 • The number of of times the loop body is executed. Actions print,i ++ print,i ++ print,i ++ print,i ++ – for (int i = 0; i < 100; i ++) { System.out.println("Welcome to Java!"); } i < 100 Enter/Stay Loop? Iteration 0 < 100 True 1 1 < 100 True 2 2 < 100 True 3 99 < 100 100 100 < 100 True False – (i.e., 100) corresponds to the number • # of times that we check the stay condition (SC) (i.e., 101) is # iterations of iterations (i.e., 100) plus 1. [ True ⇥ 100; False ⇥ 1 ] 5 of 77 The for Loop: Exercise (1) Compare the behaviour of this program for (int count = 0; count < 100; count ++) { System.out.println("Welcome to Java!"); } and this program for (int count = 1; count < 201; count += 2) { System.out.println("Welcome to Java!"); } Are the outputs same or different? It is similar to asking if the two intervals [0,1,2,...,100) and [1,3,5,...,201) contain the same number of integers. Same, both loop bodies run exactly 100 times and do not depend on the value of count. 7 of 77 The for Loop (3) The “initial-action” is executed only once, so it may be moved right before the for loop. The “action-after-each-iteration” is executed repetitively to make progress, so it may be moved to the end of the for loop body. for ( ; i < 100; ) { System.out.println("Welcome to Java!"); } int i = 0 i ++ 6 of 77 int i = 0; for (; i < 100; ) { System.out.println("Welcome to Java!"); i ++; } The for Loop: Exercise (2) Compare the behaviour of this program int count = 0; for (; count < 100; ) { System.out.println("Welcome to Java " + count + "!"); count ++; /* count = count + 1; */ } and this program int count = 1; for (; count <= 100; ) { System.out.println("Welcome to Java " + count + "!"); count ++; /* count = count + 1; */ } Are the outputs same or different? Different, both loop body run exactly 100 times and depend on the value of count. 8 of 77 The for Loop: Exercise (3) Compare the behaviour of the following three programs: Output: 12345 Output: 12345 Output: 23456 9 of 77 for (int i ; i <= 5 ; i ++) { System.out.print(i); } int i; for ( ; i <= 5 ; ) { System.out.print(i); i ++; } int i; for ( ; i <= 5 ; ) { i ++; System.out.print(i); } The while Loop (2) j 3 4 5 ... 102 103 • The number of of times the loop body is executed. Actions print,j ++ print,j ++ print,j ++ print, j ++ – int j = 3; while (j < 103) { System.out.println("Welcome to Java!"); j ++; /* j = j + 1; */ } j < 103 3 < 103 4 < 103 Enter/Stay Loop? True Iteration 1 2 5 < 103 True 3 102 < 103 True 100 103 < 103 True False – (i.e., 100) corresponds to the number • # of times that we check the stay condition (SC) (i.e., 101) is # iterations of iterations (i.e., 100) plus 1. [ True ⇥ 100; False ⇥ 1 ] 11 of 77 The while Loop (1) int count = 0; while (count < 100) { System.out.println("Welcome to Java!"); count ++; /* count = count + 1; */ } 10 of 77 The while Loop: Exercise (1) Compare the behaviour of this program int count = 0; while (count < 100) { System.out.println("Welcome to Java!"); count ++; /* count = count + 1; */ } and this program int count = 1; while (count <= 100) { System.out.println("Welcome to Java!"); count ++; /* count = count + 1; */ } Are the outputs same or different? Same, both loop bodies run exactly 100 times and do not depend on the value of count. 12 of 77 The while Loop: Exercise (2) Compare the behaviour of this program int count = 0; while (count < 100) { System.out.println("Welcome to Java " + count + "!"); count ++; /* count = count + 1; */ } and this program int count = 1; while (count <= 100) { System.out.println("Welcome to Java " + count + "!"); count ++; /* count = count + 1; */ } Are the outputs same or different? Different, both loop body run exactly 100 times and depend on the value of count. 13 of 77 Compound Loop: Exercise (1.1) How do you extend the following program System.out.println("Enter a radius value:"); double radius = input.nextDouble(); double area = radius * radius * 3.14; System.out.println("Area is " + area); with the ability to repeatedly prompt the user for a radius value, until they explicitly enter a negative radius value to terminate the program (in which case an error message is also printed)? System.out.println("Enter a radius value:"); double radius = input.nextDouble(); while (radius >= 0) {
double area = radius * radius * 3.14; System.out.println(“Area is ” + area); System.out.println(“Enter a radius value:”);
radius = input.nextDouble(); }
System.out.println(“Error: negative radius value.”); 15 of 77
Primitive Statement vs. Compound Statement
• A statement is a block of Java code that modifies value(s) of some variable(s).
• An assignment (=) statement is a primitive statement: it only modifies its left-hand-side (LHS) variable.
• An for or while loop statement is a compound statement: the loop body may modify more than one variables via other statements (e.g., assignments, if statements, and for or while statements).
e.g., a loop statement may contain as its body if statements
e.g., a loop statement may contain as its body loop statements e.g., an if statement may contain as its body loop statements
14 of 77
Compound Loop: Exercise (1.2)
Another alternative: Use a boolean variable isPositive
1 System.out.println(“Enter a radius value:”); 2 double radius = input.nextDouble();
3
4
boolean isPositive = radius >= 0;
5 6 7 8 9
double area = radius * radius * 3.14; System.out.println(“Area is ” + area); System.out.println(“Enter a radius value:”); radius = input.nextDouble();
while (isPositive)
{
isPositive = radius >= 0; }
10 System.out.println(“Error: negative radius value.”);
• In L2: What if user enters 2? What if user enters -2? • Say in L2 user entered 2, then in L8:
What if user enters 3? What if user enters -3?
• What if isPositive = radius >= 0 in L9 is missing? 16 of 77

Compound Loop: Exercise (1.3)
Another alternative: Use a boolean variable isNegative
1 System.out.println(“Enter a radius value:”); 2 double radius = input.nextDouble();
3
4
boolean isNegative = radius < 0; 5 6 7 8 9 double area = radius * radius * 3.14; System.out.println("Area is " + area); System.out.println("Enter a radius value:"); radius = input.nextDouble(); while (!isNegative) { isNegative = radius < 0; } 10 System.out.println("Error: negative radius value."); • In L2: What if user enters 2? What if user enters -2? • Say in L2 user entered 2, then in L8: What if user enters 3? What if user enters -3? • What if isNegative = radius < 0 in L9 is missing? 17 of 77 Converting between for and while Loops (2) • To convert a for loop to a while loop, move the initialization part immediately before the while loop and place the update part at the end of the while loop body. is equivalent to: where B is any valid Boolean expression. • However, when there is a loop counter (i.e., i, count, etc.) that you intend to explicitly maintain, stick to a for loop. 19 of 77 for(int i = 0 ; B ; i ++ ) { /* Actions */ } int i = 0; while(B) { /* Actions */ i ++; } Converting between for and while Loops (1) • To convert a while loop to a for loop, leave the initialization and update parts of the for loop empty. is equivalent to: where B is any valid Boolean expression. • However, when there is not a loop counter (i.e., i, count, etc.) that you intend to explicitly maintain, stick to a while loop. 18 of 77 while(B) { /* Actions */ } for( ; B ; ) { /* Actions */ } Stay Condition vs. Exit Condition (1) • A for loop or a while loop stays to repeat its body when its stay condition (SC) evaluates to true. exits when its SC evaluates to false. • Say we have two Boolean variables: boolean iP7sInStock, iP7sPlusInStock; • When does the following loop exit? !(iP7sInStock && iP7sPlusInStock) this is equivalent to !iP7sInStock || !iP7sPlusInStock • When does the following loop exit? !(iP7sInStock || iP7sPlusInStock) while(iP7sInStock && iP7sPlusInStock) { ... } while(iP7sInStock || iP7sPlusInStock) { ... } this is equivalent to !iP7sInStock && !iP7sPlusInStock 20 of 77 Stay Condition vs. Exit Condition (2) Consider the following loop: • It compiles, but has a logical error. Why? int x = input.nextInt(); while(10 <= x || x <= 20) { /* body of while loop */ } • Think about the exit condition : !(10 <= x || x <= 20) !(10 <= x) && !(x <= 20) 10 > x && x > 20
[* negation of stay condition] [* law of disjunction] [*lawofnegation]
• 10 > x && x > 20isequivalenttofalse,sincethereisno number larger than 10 and smaller than 20 at the same time.
• An exit condition being false means that there is no way to exit
from the loop! [infinite loops are BAD!] 21 of 77
Arrays: A Simple Data Structure
• An array is a linear sequence of elements. High
scores
• Types of elements in an array are the same. an array of integers
an array of doubles
an array of characters
an array of strings
indices
an array of booleans
• Each element in an array is associated with an integer index. • Range of valid indices of an array is constrained by its size.
[int[]] [double[]] [char[]] [String[]] [boolean[]]
The 1st element of an array has the index 0.
The 2nd has index 1.
The ith element has index i 1.
The last element of an array has the index value that is equal to
23 of 77the size of the array minus one.
Problems, Data Structures, and Algorithms
• A well-specified computational problem precisely describes the desired input/output relationship.
Input: A sequence of n numbers ha1, a2, . . . , ani
Output: The maximum number max in the input array, such that
max ai,where1i n
An instance of the problem: h3, 1, 2, 5, 4i
• A
data in order to facilitate access and modifications.
data structure is a systematic way to store and organize • An algorithm is:
A solution to a well-specified computational problem
A sequence of computational steps that takes value(s) as input
and produces value(s) as output
• Steps in an algorithm manipulate well-chosen data structure(s).
22 of 77
Arrays: Initialization and Indexing
• Initialize a new array object with a fixed size: String[] names = new String[10];
• Alternatively, initialize a new array explicitly with its contents: String[] names = {“Alan”, “Mark”, “Tom”};
• Access elements in an array through indexing: String first = names[0];
String last = names[names.length – 1];
An illegal index triggers an ArrayInexOutOfBoundsException.
24 of 77

Arrays: Iterations
• Iterate through an array using a for-loop:
for (int i = 0; i < names.length; i ++) { System.out.println (names[i]); } • Iterate through an array using a while-loop: int i = 0; while (i < names.length) { System.out.println (names[i]); i ++; } 25 of 77 The for Loop: Exercise (4) Problem: Given an array numbers of integers, how do you print its contents backwards? e.g.,Givenarray{1,2,3,4},print4 3 2 1. Solution 1: Change bounds and updates of loop counter. for(int i = numbers.length - 1; i >= 0; i –) { System.out.println(numbers[i]);
}
Solution 2: Change indexing.
for(int i = 0; i < names.length; i ++) { System.out.println(numbers[ names.length - i - 1 ]); } 27 of 77 The for Loop: Exercise (3) Problem: Given an array numbers of integers, how do you print its average? e.g., Given array {1, 2, 6, 8}, print 4.25. int sum = 0; for(int i = 0; i < numbers.length; i ++) { sum += numbers[i]; } double average = (double) sum / numbers.length; System.out.println("Average is " + average); Q: What’s the printout when the array is empty (e.g., int[] numbers = {};)? A: Division by zero (i.e., numbers.length is 0). Fix? 26 of 77 The for Loop: Exercise (5) Problem: Given an array names of strings, how do you print its contents separated by commas and ended with a period? e.g., Given array {”Alan”, ”Mark ”, ”Tom”}, print ”Names: Alan, Mark, Tom.” System.out.print("Names:") for(int i = 0; i < names.length; i ++) { System.out.print(names[i]); if (i < names.length - 1) { System.out.print(", "); } } System.out.println("."); 28 of 77 Array Iterations: Translating for to while (1) • Use either when you intend to iterate through the entire array. • int[] a = new int[100]; for(int i = 0; i < a.length; i ++) { /* Actions to repeat. */ } In a for loop, the initialization and update of the loop counter i are specified as part of the loop header. • int i = 0; while(i < a.length) { /* Actions to repeat. */ i ++; } In a while loop, the loop counter i Is initialized outside and before the loop header Is updated at the end of the loop body 29 of 77 Compound Loop: Exercise (2) Given an integer array: int[] a = {2, 1, 3, 4, -4, 10} How do you print out positive numbers only? Hint: Use a for loop to iterate over the array. In the loop body, conditionally print out positive numbers only. 1 2 3 4 5 for(int i = 0; i < a.length; i ++) { if (a[i] > 0) {
System.out.println(a[i]); }
}
Exercise: Write the equivalent using a while loop. 31 of 77
Array Iterations: Translating for to while (2)
• In both the for and while loops:
The stay/continuation conditions are identical.
The loop counter i is initialized only once before first entrance.
In each iteration, the loop counter i is executed at the end of the
loop body.
30 of 77
Compound Loop: Exercise (3.1)
• Problem: Given an array of numbers, determine if it contains all positive number.
1 int[] numbers = {2, 3, -1, 4, 5, 6, 8, 9, 100}; 2 boolean soFarOnlyPosNums = true;
3 inti=0;
4 while (i < numbers.length) { 5 6 7} 8 if (soFarOnlyPosNums) { /* print a msg. */ } 9 else { /* print another msg. */ } soFarOnlyPosNums = soFarOnlyPosNums && (numbers[i] > 0); i = i + 1;
• Change Line 5 to soFarOnlyPosNums = numbers[i] > 0;? • Hints: Run both versions on the following three arrays:
1. {2, 3, 1, 4, 5, 6, 8, 9, 100}
2. {2, 3, 100, 4, 5, 6, 8, 9, -1}
3. {2, 3, -1, 4, 5, 6, 8, 9, 100} 32 of 77
[all positive] [negative at the end] [negative in the middle]

Compound Loop: Exercise (3.1) Demo (1)
1 2 3 4 5 6 7
int[] ns = {2, 3, -1, 4, 5}; boolean soFarOnlyPosNums = true; int i = 0;
while (i < ns.length) { soFarOnlyPosNums = soFarOnlyPosNums && (ns[i] > 0);
i = i + 1; }
33 of 77
i
soFarOnlyPosNums i < ns.length stay? ns[i] ns[i] > 0
true
true
true
2
true
true
true
3
true
true
true
-1
false
true
true
4
false
true
true
5
0 true 1 true 2 false 3 true 4 true 5 false false false – –
Compound Loop: Exercise (3.2)
Problem: Given an array of numbers, determine if it contains all positive number. Also, for efficiency, exit from the loop as soon as you find a negative number.
1 2 3 4 5 6 7 8 9
35 of 77
int[] numbers = {2, 3, -1, 4, 5, 6, 8, 9, 100}; boolean soFarOnlyPosNums = true;
int i = 0;
while (soFarOnlyPosNums && i < numbers.length) { soFarOnlyPosNums = numbers[i] > 0;
i = i + 1; }
if (soFarOnlyPosNums) { /* print a msg. */ } else { /* print another msg. */ }
Compound Loop: Exercise (3.1) Demo (2)
1 2 3 4 5 6 7
int[] ns = {2, 3, -1, 4, 5}; boolean soFarOnlyPosNums = true; int i = 0;
while (i < ns.length) { soFarOnlyPosNums = ns[i] > 0; /* wrong */
i = i + 1; }
34 of 77
i
soFarOnlyPosNums i < ns.length stay? ns[i] ns[i] > 0
0 true 1 true 2 false 3 true 4 true
true
true
true
false
true
true
true
true
true
2
3
true
-1
true
true
4
true
true
true
5
5
false
false


true
Compound Loop: Exercise (3.2) Demo
1 2 3 4 5 6 7
int[] ns = {2, 3, -1, 4, 5, 6, 8, 9, 100}; boolean soFarOnlyPosNums = true;
int i = 0;
while (soFarOnlyPosNums && i < ns.length) { soFarOnlyPosNums = ns[i] > 0;
i = i + 1; }
i
soFarOnlyPosNums i < ns.length stay? ns[i] ns[i] > 0
true
true
true
2
true
true
true
3
true
true
true
-1
0 true 1 true 2 false 3 false true false – –
36 of 77

Compound Loop: Exercise (3.3) Summary
Four possible solutions (posNumsSoFar is initialized as true): 1. Scan the entire array and accumulate the result.
2. Scan the entire array but the result is not accumulative.
3. The result is accumulative until the early exit point.
4. The result is not accumulative until the early exit point.
37 of 77
for (int i = 0; i < ns.length; i ++) { posNumsSoFar = posNumsSoFar ns[i] > 0; }
&&
for (int i = 0; i < ns.length; i ++) { posNumsSoFar = ns[i] > 0; }
/* Not working. Why? */
for (int i = 0; posNumsSoFar posNumsSoFar = posNumsSoFar
&&
i < ns.length; i ++) { ns[i] > 0; }
&&
for (int i = 0; posNumsSoFar i < ns.length; i ++) { posNumsSoFar = ns[i] > 0; }
&&
Compound Loop: Exercise (4) Demo
1 2 3 4 5 6
int[] a = {2, 1, 3, 4, -4, 10}
int max = a[0];
for(int i = 0; i < a.length; i ++) { if (a[i] > max) { max = a[i]; } }
System.out.println(“Maximum is ” + max);
i a[i] a[i] > max
update max? max



02
0 2 false N 2
1 1 false N 2 2 3 true Y 3 3 4 true Y 4 4-4false N 4 510 true Y 10
39 of 77
Compound Loop: Exercise (4)
Given a non-empty integer array, e.g., int[] a = {2, 1, 3, 4, -4, 10}, find out its maximum element.
Hint: Iterate over the array. In the loop body, maintain the maximum found so far and update it when necessary.
1 2 3 4
int max = a[0];
for(int i = 0; i < a.length; i ++) { if(a[i]>max){ max=a[i];}} System.out.println(“Maximum is ” + max);
Q: Will the program still work if we change the initialization in L1 toint max = 0?
A: NO * Contents of a may be all smaller than this initial value (e.g., all negatives).
Q: Will the program still work if we change the initialization in L2
toint i = 1?
A: YES * a[0] > a[0] is always false anyway. 38 of 77
Compound Loop: Exercise (5)
Problem: Given an array a of integers, how do determine if it is sorted in a non-decreasing order?
e.g., Given {1, 2, 2, 4}, print true; given {2, 4, 3, 3} print false.
1 2 3 4
1 2 3 4
boolean isSorted = true; for(inti=0;i< a.length-1;i++){ isSorted = isSorted && (a[i] <= a[i + 1]); } Alternatively (with early exit): boolean isSorted = true; for(int i = 0; isSorted && i < a.length - 1 ; i ++) { isSorted = a[i] <= a[i + 1]; } 40 of 77 Compound Loop: Exercise (5) Demo [A] 1 2 3 4 5 int[] a = {1, 2, 2, 4} boolean isSorted = true; for(inti=0;i< a.length-1;i++){ isSorted = isSorted && (a[i] <= a[i + 1]); } i a[i] a[i + 1] a[i] <= a[i + 1] isSorted exit? – – – true 0N 012 true trueN 122 true trueN 224 true trueY 41 of 77 Compound Loop: Exercise (5) Demo [C] 1 2 3 4 5 int[] a = {2, 4, 3, 3} boolean isSorted = true; for(int i = 0; isSorted && i < a.length - 1 ; i ++) { isSorted = a[i] <= a[i + 1]; } exit? 1 4 3 false false Y i a[i] a[i + 1] a[i] <= a[i + 1] isSorted – – – true 0N 024 true trueN 43 of 77 Compound Loop: Exercise (5) Demo [B] 1 2 3 4 5 int[] a = {2, 4, 3, 3} boolean isSorted = true; for(inti=0;i< a.length-1;i++){ isSorted = isSorted && (a[i] <= a[i + 1]); } i a[i] a[i + 1] a[i] <= a[i + 1] isSorted exit? – – – true 0N 024 true trueN 1 4 3 false false N 23 3 true false Y 42 of 77 Checking Properties of Arrays (1) • Determine if all elements satisfy a property. • We need to repeatedly apply the logical conjunction . • As soon as we find an element that does not satisfy a property, then we exit from the loop. e.g., Determine if all elements in array a are positive. 1 2 3 4 1 2 3 4 boolean allPos = true; for(int i = 0; i < a.length; i ++) { allPos = allPos && (a[i] > 0); }
Alternatively (with early exit):
boolean allPos = true;
for(int i = 0; allPos && i < a.length; i ++) { allPos = a[i] > 0; }
44 of 77

Checking Properties of Arrays (1): Demo
1 2 3 4 5
int[] a = {2, 3, -1, 4, 5, 6, 8, 9, 100}; boolean allPos = true;
for(int i = 0; allPos && i < a.length; i ++) { allPos = a[i] > 0; }
i a[i] a[i] > 0
allPos
exit?


true
0N
0 2 true true N
1 3 true true N
2 -1 false false Y
• Question: Why do we initialize allPos as true in Line 2?
• Question: What if we change the stay condition in Line 3 to
only i < a.length? Intermediate values of allPos will be overwritten! 45 of 77 Checking Properties of Arrays (2) Demo 1 2 3 4 5 int[] a = {2, 3, -1, 4, 5, 6, 8, 9, 100}; boolean foundNegative = false; for(int i = 0; ! foundNegative && i < a.length; i ++) { foundNegative = a[i] < 0; } i a[i] a[i] < 0 0N 0 2 false false true N foundNegative exit? false Y • Question: Why do we initialize foundNegative as false in Line 2? 47 of 77 true true !foundNegative true N – – false true 1 3 2 -1 false false Checking Properties of Arrays (2) • Determine if at least one element satisfies a property. • we find an element that satisfies a property, then we exit from the loop. e.g., Is there at lease one negative element in array a? Version 1: Scanner the Entire Array 1 2 3 4 1 2 3 4 boolean foundNegative = false; for(int i = 0; i < a.length; i ++) { foundNegative = foundNegative || a[i] < 0; } Version 2: Possible Early Exit boolean foundNegative = false; for(int i = 0; ! foundNegative && i < a.length; i ++) { foundNegative = a[i] < 0; } 46 of 77 As soon as Observations • In some cases, you must iterate through the entire array in order to obtain the result. e.g., max, min, total, etc. • In other cases, you exit from the loop as soon as you obtain the result. e.g., to know if all numbers positive, it is certainly false as soon as you find the first negative number e.g., to know if there is at least one negative number, it is certainly true as soon as you find the first negative number 48 of 77 Compound Loop: Exercise (6.1) Problem: Read an integer from the user, indicating how many strings exactly they want to enter, prompt them for that many strings, and then print them out. 49 of 77 How many strings? 3 Enter a string: Alan Enter a string: Mark Enter a string: Tom You entered: Alan Mark Tom Compound Loop: Exercise (7.1) Problem: Read an integer from the user, indicating how many strings at most they want to enter, prompt them for up to that many strings, and then print them out as soon as exit is read. 51 of 77 How many strings? 4 Enter a string: Alan Enter a string: Mark Enter a string: exit You entered: Alan Mark Compound Loop: Exercise (6.2) 1 2 3 4 5 6 7 8 9 10 11 12 13 Scanner input = new Scanner(System.in); System.out.println("How many strings?"); int howMany = input.nextInt(); String[] strings = new String[howMany]; for(int i = 0; i < howMany; i ++) { System.out.println("Enter a string:"); String s = input.nextLine(); strings[i] = s; } System.out.println("You entered: "); for(int i = 0; i < strings.length ; i ++) { System.out.print(strings[i] + " "); } • In L10, the following three integer expressions have the same value: howMany, i, and strings.length. • Scope of loop counter i declared in L5 is limited to L6 to L8. • Scope of loop counter i declared in L11 is limited to L12. 50 of 77 Compound Loop: Exercise (7.2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Scanner input = new Scanner(System.in); System.out.println("How many strings?"); int howMany = input.nextInt(); boolean userWantsToContinue = true; String[] strings = new String[howMany]; for(int i = 0; i < howMany && userWantsToContinue; i ++) { System.out.println("Enter a string:"); String s = input.nextLine(); userWantsToContinue = !s.equals("exit"); if(userWantsToContinue) { strings[i] = s; } } System.out.println("You entered: "); for(int i = 0; i < strings.length ; i ++) { System.out.print(strings[i] + " "); } In L12, i may be that less than howMany slots are occupied. Is this correct? [ NO ] 52 of 77 Compound Loop: Exercise (7.3) How many strings? 4 Enter a string: Alan Enter a string: Mark Enter a string: exit You entered: Alan Mark null null • In L5, contents of array strings are all unknown: {null, null, null, null} • In L12, after exiting the loop, only two slots are filled: 53 of 77 {"Alan", "Mark", null, null} Compound Loop: Exercise (7.5) This version also works: 1 Scanner input = new Scanner(System.in); 2 System.out.println("How many strings?"); 3 int howMany = input.nextInt(); 4 5 String[] strings = new String[howMany]; 6 int numberOfStringsRead = 0; 7 for(inti=0;i= ns.length
57 of 77
[ not always! ] [ ArrayIndexOutOfBoundException ]
Arrays: Indexing and Short-Circuit Logic (3.2)
1 2 3 4 5 6 7 8 9
10 11 12
Scanner input = new Scanner(System.in); System.out.println(“How many integers?”); int howMany = input.nextInt();
int[] ns = new int[howMany];
for(int i = 0; i < howMany; i ++) { System.out.println("Enter an integer"); ns[i] = input.nextInt(); } System.out.println("Enter an index:"); int = input.nextInt(); i if( ns[i] % 2 == 1) { i < 0 || i >= ns.length ||
/* Error: invalid index or odd ns[i] */ }
else { println(ns[i] + ” at index ” + i + ” is even.”); }
• Does the above code work?
• Short-circuit effect of disjunction has L-to-R evaluations:
[ always! ] (i.e., i < 0 || i >= ns.length) evaluates to false.
ns[i] % 2 == 1 is evaluated only when the guard 59 of 77
Arrays: Indexing and Short-Circuit Logic (3.1)
1 2 3 4 5 6 7 8 9
10 11 12
Scanner input = new Scanner(System.in); System.out.println(“How many integers?”); int howMany = input.nextInt();
int[] ns = new int[howMany];
for(int i = 0; i < howMany; i ++) { System.out.println("Enter an integer"); ns[i] = input.nextInt(); } System.out.println("Enter an index:"); int = input.nextInt(); i if( println(ns[i] + " at index " + i + " is even."); } ns[i] % 2 == 0) { else { /* Error: invalid index or odd ns[i] */ } 0 <= i && i < ns.length && • Does the above code work? • Short-circuit effect of conjunction has L-to-R evaluations: ns[i] % 2 == 0 is evaluated only when the guard (i.e., 0 <= i && i < ns.length) evaluates to true. [ always! ] 58 of 77 Arrays: Indexing and Short-Circuit Logic (4) • * Short-circuit evaluations go from left to right. ) Order in which the operands are placed matters! • Consider the following changes to L10: ns[i]%2==0 &&0<=i&&i= ns.length?
0<=i&& ns[i]%2==0 &&i= ns.length? i= ns.length?
• When does each change to L10 work and crash?
|| i < 0 || i >= ns.length
i < 0 || || i >= ns.length
i >= ns.length || || i < 0 60 of 77 [crash] [ crash ] [works] [ crash ] [crash] [ works ] ns[i] % 2 == 1 ns[i] % 2 == 1 ns[i] % 2 == 1 Parallel Loops vs. Nested Loops Parallel Loops : Each loop completes an independent phase of work. e.g., Print an array from left to right, then right to left. System.out.println("Left to right:"); for(int i = 0; i < a.length; i ++) { System.out.println(a[i]); } System.out.println("Right to left:"); for(int i = 0; i < a.length; i ++) { System.out.println(a[a.length - i - 1]); } Nested Loops : Loop counters form all combinations of indices. for(int i = 0; i < a.length; i ++) { for(int j = 0; j < a.length; j ++) { System.out.println("(" + i + ", " + j + ")"); }} 61 of 77 • • Nested Loops: Finding Duplicates (2) 1 2 3 4 5 6 7 8 /* Version 1 with redundant scan */ int[] a = {1, 2, 3}; /* no duplicates */ boolean hasDup = false; for(int i = 0; i < a.length; i ++) { for(int j = 0; j < a.length; j ++) { hasDup = hasDup || (i != j && a[i] == a[j]); } /* end inner for */ } /* end outer for */ System.out.println(hasDup); j 0 1 2 i != j false true true a[i] 1 1 1 a[j] 1 2 3 a[i] == a[j] true false false 0 1 2 true false true 2 2 2 1 2 3 false true false 63 of 77 i 0 0 0 1 1 1 20true31 false 21true32 false 22false33 true hasDup false false false false false false false false false Nested Loops: Finding Duplicates (1) • Given an integer array a, determine if it contains any duplicates. e.g., Print false for {1, 2, 3, 4}. Print true for {1, 4, 2, 4}. • Hint: When can you conclude that there are duplicates? As soon as we find that two elements at difference indices happen to be the same 1 2 3 4 5 6 • Question: How do you modify the code, so that we exit from the loops as soon as the array is found containing duplicates? L2: for(...; && i < a.length; ...) L3: for(...; && j < a.length; ...) L4: hasDup = (i != j && a[i] == a[j]); 62 of 77 boolean hasDup = false; for(int i = 0; i < a.length; i ++) { for(int j = 0; j < a.length; j ++) { hasDup = hasDup || (i != j && a[i] == a[j]); } /* end inner for */ } /* end outer for */ System.out.println(hasDup); !hasDup !hasDup Nested Loops: Finding Duplicates (3) 1 2 3 4 5 6 7 8 /* Version 1 with redundant scan and no early exit */ int[] a = {4, 2, 4}; /* duplicates: a[0] and a[2] */ boolean hasDup = false; for(int i = 0; i < a.length; i ++) { for(int j = 0; j < a.length; j ++) { hasDup = hasDup || (i != j && a[i] == a[j]); } /* end inner for */ } /* end outer for */ System.out.println(hasDup); i hasDup j 0 1 2 i != j false true true a[i] 4 4 4 a[j] 4 2 4 a[i] == a[j] true false true 0 1 2 true false true 2 2 2 4 2 4 false true false 64 of 77 0 false 0 false 0 true 1 true 1 true 1 true 20 true 4 4 true true 21true42 false true 22false44 true true Nested Loops: Finding Duplicates (4) 1 2 3 4 5 6 7 8 /* Version 2 with redundant scan */ int[] a = {1, 2, 3}; /* no duplicates */ boolean hasDup = false; for(int i = 0; i < a.length && for(int j = 0; j < a.length && hasDup = !hasDup ; i ++) { ; j ++) { !hasDup ; } /* end inner for */ } /* end outer for */ i != j && a[i] == a[j] System.out.println(hasDup); j 0 1 2 i != j false true true a[i] 1 1 1 a[j] 1 2 3 a[i] == a[j] true false false 0 1 2 true false true 2 2 2 1 2 3 false true false 65 of 77 i 0 0 0 1 1 1 20true31 false 21true32 false 22false33 true hasDup false false false false false false false false false Nested Loops: Finding Duplicates (6) The previous two versions scan all pairs of array slots, but with redundancy: e.g., a[0] == a[2] and a[2] == a[0]. 1 2 3 4 5 6 7 8 67 of 77 i hasDup 0 false 0 false 0 false 1 false 1 false 2334 false false /* Version 3 with no redundant scan */ int[] a = {1, 2, 3, 4}; /* no duplicates */ boolean hasDup = false; for(int i = 0; i < a.length && ; i ++) { !hasDup for(int ; j < a.length && hasDup = ; } /* end inner for */ } /* end outer for */ System.out.println(hasDup); ; j ++) { j=i+1 !hasDup a[i] == a[j] j 1 2 3 a[i] 1 1 1 2 2 a[j] 2 3 4 3 4 a[i] == a[j] false false false 2 3 false false Nested Loops: Finding Duplicates (5) 1 2 3 4 5 6 7 8 /* Version 2 with redundant scan and early exit */ int[] a = {4, 2, 4}; /* duplicates: a[0] and a[2] */ boolean hasDup = false; for(int i = 0; i < a.length && for(int j = 0; j < a.length && hasDup = !hasDup ; i ++) { ; j ++) { !hasDup ; } /* end inner for */ } /* end outer for */ i != j && a[i] == a[j] System.out.println(hasDup); i j i != j a[i] a[j] a[i] == a[j] hasDup 00false44 true false 01true42 false false 02 true 4 4 true true 66 of 77 Nested Loops: Finding Duplicates (7) 1 2 3 4 5 6 7 8 9 10 /* Version 3 with no redundant scan: * array with duplicates causes early exit */ int[] a = {1, 2, 3, 2}; /* duplicates: a[1] and a[3] */ boolean hasDup = false; for(int i = 0; i < a.length && ; i ++) { !hasDup for(int ; j < a.length && hasDup = ; } /* end inner for */ } /* end outer for */ System.out.println(hasDup); ; j ++) { j=i+1 !hasDup a[i] == a[j] i j a[i] a[j] a[i] == a[j] hasDup 0 false 1 2 3 1 1 1 2 3 2 false false false 0 0 1223 false false 1322 false true false false 68 of 77 Common Error (1): Improper Initialization of Loop Counter boolean userWantsToContinue; while (userWantsToContinue) { /* some computations here */ String answer = input.nextLine(); userWantsToContinue = answer.equals("Y"); } The default value for an initialized boolean variable is false. Fix? boolean userWantsToContinue = true; while (userWantsToContinue) { /* some computations here */ String answer = input.nextLine(); userWantsToContinue = answer.equals("Y"); } 69 of 77 Common Error (3): Improper Update to Loop Counter Does the following loop print all slots of array a? int i = 0; while (i < a.length) { i ++; System.out.println(a[i]); } The indices used to print will be: 1, 2, 3, . . . , a.length Fix? int i = 0; while (i < a.length) { System.out.println(a[i]); i ++; }} 71 of 77 int i = 0; while (i < a.length) { i ++; System.out.println(a[i - 1]); Common Error (2): Improper Stay Condition for (int i = 0; i <= a.length; i ++) { System.out.println(a[i]); } The maximum index for array a is a.length - 1 Fix? for (int i = 0; i < a.length; i ++) { System.out.println(a[i]); } 70 of 77 Common Error (4): Improper Initialization of Loop Counter 1 2 3 4 5 6 String answer = input.nextLine(); boolean userWantsToContinue = answer.equals("Y"); while (userWantsToContinue) { /* stay condition (SC) */ /* some computations here */ answer = input.nextLine(); } What if the user’s answer in L1 is simply Y? * SC never gets updated when a new answer is read. Fix? String answer = input.nextLine(); boolean userWantsToContinue = answer.equals("Y"); while (userWantsToContinue) { /* some computations here */ answer = input.nextLine(); userWantsToContinue = answer.equals("Y"); An infinite loop!! } 72 of 77 Common Error (5): Improper Start Value of Loop Counter int i = a.length - 1; while (i >= 0) {
System.out.println(a[i]); i –; } while (i < a.length) { System.out.println(a[i]); i ++; } The value of loop counter i after the first while loop is 1! Fix? int i = a.length - 1; while (i >= 0) {
System.out.println(a[i]); i –; } i = 0;
while (i < a.length) { System.out.println(a[i]); i ++; } 73 of 77 Common Error (7): Misplaced Semicolon Semicolon (;) in Java marks the end of a statement (e.g., assignment, if statement, for, while). Output? Fix? 75 of 77 int[] ia = {1, 2, 3, 4}; for (int i = 0; i < 10; i ++); { System.out.println("Hello!"); } Hello! for (int i = 0; i < 10; i ++) { System.out.println("Hello!"); } Common Error (6): Wrong Syntax How about this? You meant: How about this? You meant: or while(int i = 0; i < 10; i ++) { ... } for(int i = 0; i < 10; i ++) { ... } for(i < 10) { ... } while(i < 10) { ... } for( ; i < 10 ; ) { ... } 74 of 77 Beyond this lecture. . . • Study the three online tutorials on loops: http://www3.cs.stonybrook.edu/ ̃jackie/teaching/ S17/cse114/index.html#tutorial_videos • Read Chapter 5 of the textbook. do { ... } while (...) loop continue and break • Seealso:https://docs.oracle.com/javase/tutorial/ java/nutsandbolts/branch.html • Forthiscourse,youareforbiddentousecontinueandbreak statements, since they potentially result in “spaghetti code”: http://www.open-of-course.org/courses/mod/page/ view.php?id=203. • Try all examples in the main text. • Complete all exercises in at the end of the chapter. • Try tracing the programs via: Paper and Pen Eclipse (breakpoints and debug) 76 of 77 Index (1) Learning Outcomes Motivation of Loops The for Loop (1) The for Loop (2) The for Loop (3) The for Loop: Exercise (1) The for Loop: Exercise (2) The for Loop: Exercise (3) The while Loop (1) The while Loop (2) The while Loop: Exercise (1) The while Loop: Exercise (2) Primitive Statement vs. Compound Statement Compound Loop: Exercise (1.1) 77 of 77 Index (3) Array Iterations: Translating for to while (2) Compound Loop: Exercise (2) Compound Loop: Exercise (3.1) Compound Loop: Exercise (3.1) Demo (1) Compound Loop: Exercise (3.1) Demo (2) Compound Loop: Exercise (3.2) Compound Loop: Exercise (3.2) Demo Compound Loop: Exercise (3.3) Summary Compound Loop: Exercise (4) Compound Loop: Exercise (4) Demo Compound Loop: Exercise (5) Compound Loop: Exercise (5) Demo [A] Compound Loop: Exercise (5) Demo [B] Compound Loop: Exercise (5) Demo [C] 79 of 77 Index (2) Compound Loop: Exercise (1.2) Compound Loop: Exercise (1.3) Converting between for and while Loops (1) Converting between for and while Loops (2) Stay Condition vs. Exit Condition (1) Stay Condition vs. Exit Condition (2) Problems, Data Structures, and Algorithms Arrays: A Simple Data Structure Arrays: Initialization and Indexing Arrays: Iterations The for Loop: Exercise (3) The for Loop: Exercise (4) The for Loop: Exercise (5) Array Iterations: Translating for to while (1) 78 of 77 Index (4) Checking Properties of Arrays (1) Checking Properties of Arrays (1): Demo Checking Properties of Arrays (2) Checking Properties of Arrays (2) Demo Observations Compound Loop: Exercise (6.1) Compound Loop: Exercise (6.2) Compound Loop: Exercise (7.1) Compound Loop: Exercise (7.2) Compound Loop: Exercise (7.3) Compound Loop: Exercise (7.4) Compound Loop: Exercise (7.5) Arrays: Indexing and Short-Circuit Logic (1) Arrays: Indexing and Short-Circuit Logic (2) 80 of 77 Index (5) Arrays: Indexing and Short-Circuit Logic (3.1) Arrays: Indexing and Short-Circuit Logic (3.2) Arrays: Indexing and Short-Circuit Logic (4) Parallel Loops vs. Nested Loops Nested Loops: Finding Duplicates (1) Nested Loops: Finding Duplicates (2) Nested Loops: Finding Duplicates (3) Nested Loops: Finding Duplicates (4) Nested Loops: Finding Duplicates (5) Nested Loops: Finding Duplicates (6) Nested Loops: Finding Duplicates (7) Common Error (1): Improper Initialization of Loop Counter 81 of 77 Index (6) Common Error (2): Improper Stay Condition Common Error (3): Improper Update to Loop Counter Common Error (4): Improper Initialization of Loop Counter Common Error (5): Improper Start Value of Loop Counter Common Error (6): Wrong Syntax Common Error (7): Misplaced Semicolon Beyond this lecture. . . 82 of 77