Transcript Loop Statements - SUNY

CSE 114 – Computer Science I
Iteration
Cape Breton, Nova Scotia
What is Iteration?
•
Repeating a set of instructions a specified number of
times or until a specific result is achieved
•
How do we repeat steps?
–
–
–
Imagine 3 instructions A, B, & C
Instruction C can be jump A, meaning go back to A
Iteration might result in:
•
•
•
•
•
Execute A
Execute B
Execute C
Execute A
…
Why use iteration?
• To make our code more practical and efficient
• To make our code more flexible and dynamic
For Example
• How would we write code to print N!, where N
is a number entered by the user.
• Without iteration (or recursion) this would be
impractical!
Is this practical?
• Without iteration or recursion:
System.out.print("Enter N: ");
int N = Keyboard.readInt();
int factorial = 1;
if ((N == 1) || (N == 0)) factorial = 1;
else if (N == 2) factorial = 2 * 1;
else if (N == 3) factorial = 3 * 2 * 1;
else if (N == 4) factorial = 4 * 3 * 2 * 1;
else if (N == 5) factorial = 5 * 4 * 3 * 2 * 1;
…
System.out.println(factorial);
• Inefficient coding!
import java.util.Scanner;
Using Iteration
public class FactorialPrinter
Methods
{
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
System.out.print("Enter N: ");
int N = input.readInt();
int factorial = calculateFactorial(N);
System.out.println(factorial);Method argument
type and name
}
return type
public static int calculateFactorial(int n)
{
int count = n;
int fact = 1;
while (count > 0)
fact *= count--;
return fact;
}
return value
and
Helper
method
Can Anyone guess what 1000! is?
•
4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048004799886
1019719605863166687299480855890132382966994459099742450408707375991882362772718873251977950595099527612087497
5462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323
9584630755574091142624174743493475534286465766116677973966688202912073791438537195882498081268678383745597317
4613608537953452422158659320192809087829730843139284440328123155861103697680135730421616874760967587134831202
5478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810
2130927612448963599287051149649754199093422215668325720808213331861168115536158365469840467089756029009505376
1647584772842188967964624494516076535340819890138544248798495995331910172335555660213945039973628075013783761
5307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892
1879602238389714760885062768629671466746975629112340824392081601537808898939645182632436716167621791689097799
1190375403127462228998800519544441428201218736174599264295658174662830295557029902432415318161721046583203678
6906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958
6526822728070757813918581788896522081643483448259932660433676601769996128318607883861502794659551311565520360
9398818061213855860030143569452722420634463179746059468257310379008402443243846565724501440282188525247093519
0620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814
9001407673104466402598994902222217659043399018860185665264850617997023561938970178600408118897299183110211712
2984590164192106888438712185564612496079872290851929681937238864261483965738229112312502418664935314397013742
8531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602
7898643211390835062170950025973898635542771967428222487575867657523442202075736305694988250879689281627538488
6339690995982628095612145099487170124451646126037902930912088908694202851064018215439945715680594187274899809
4254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105
9339838357779394109700277534720000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000
• Impossible to calculate using Java’s primitive data types, instead
we would have to use the BigInteger class
– double type can estimate up until 170! (7.257415615308004 E306)
All programs need iteration
• Any exceptions?
– one and done programs
• Why do they all need iteration?
– because the start up, then wait for the user to act
• Most programs work as follows:
1.
2.
3.
4.
5.
Initialize variables
Present options to user
Wait for user input
Respond to user input
Go back to step 2
GUIs and
Iteration
• Think of a GUI. How does it work?
1.
2.
3.
4.
Draw the GUI
Check for input from user
Respond to user input, if any
Go back to Step 1
Java and iteration
• We have 3 types of statements
– while loop
– do … while loop
– for loop
• All 3 can be used to do similar things
• Which one should you use?
– a matter of individual preference/convenience
The while Statement
•Syntax Diagram:
“while”
‘(’
‘)’
boolean Expr
Statement
‘{’
‘}’
Statement
•Flowchart:
false
boolean
Expr
true
Statement(s)
Loop
Condition
Loop
Body
Bracketing is again important
• Use either:
while (boolean expression)
statement;
• Or:
Be careful NOT to
put a semicolon, ‘;’, here
while (boolean expression)
{
statement;
statement;
}
while statement example
• What does this method do?
public static String whatDoesThisDo(int x, char c)
{
String result = "";
while (x > 0)
• What do we get if we call:
{
result = result + c;
String s;
x--;
s = whatDoesThisDo(5,'A');
}
System.out.println(s);
return result;
s = whatDoesThisDo(0,'A');
}
System.out.println(s);
AAAAA
while statement example 2
• What does this method do?
public static String whatDoesThisDo2(int x, char c)
{
String result = "";
while (x > 0)
{
result = result + c;
x--;
• What do we get if we call:
c++;
}
String s;
return result;
s = whatDoesThisDo2(5, 'A');
}
System.out.println(s);
ABCDE
while statement example 3
• What does this method do?
public static String whatDoesThisDo3(int x, char c)
{
String result = "";
while (x > 0)
{
result = c + result;
x--;
• What do we get if we call:
c++;
}
String s;
return result;
s = whatDoesThisDo3(5, 'A');
}
System.out.println(s);
EDCBA
Using a flag
• A flag is a boolean loop control
boolean flag = true;
• How does it work?
–
–
–
–
flag used as loop condition
inside the loop, test for ending condition
when condition is reached, turn flag off
once turned off, loop ends
flag example
public static int factorial(int N)
{
boolean moreWorkFlag = true;
int factorial = 1;
while (moreWorkFlag)
{
factorial *= N;
N--;
• What do we get if we call:
if (N == 1)
moreWorkFlag = false; int fact;
fact = factorial(5);
}
System.out.println(fact);
return factorial;
}
120
The do-while Statement
•Syntax Diagram:
“do”
“while”
Statement
‘{’
Statements
‘}’
‘(’
boolean Expr
‘)’
•Flowchart:
Loop
Body
Statement(s)
true
Loop
Condition
boolean Expr
false
‘;’
Bracketing is again important
• Use either:
do
statement;
while (boolean expression);
• Or:
do
{
You MUST put a
semicolon, ‘;’, here
statement;
statement;
}while (boolean expression);
NOTE: though they can be used to do similar operations,
while statements and do-while statements are different
Java constructs.
do…while statement example
• What does this method do?
public static String whatDoesThisDoWhileDo(
int x, char c)
{
String result = "";
• What do we get if we call:
do
{
String s;
result += c;
s = whatDoesThisDoWhileDo(5,'A');
x--;
System.out.println(s);
} while (x > 0);
s = whatDoesThisDoWhileDo(0,'A');
System.out.println(s);
return result;
AAAAA
}
A
How could we fix this?
public static String whatDoesThisDoWhileDo
(int x, char c)
{
String result = "";
if (x > 0)
{
• Now what’s the output?
do
{
String s;
result += c;
s = whatDoesThisDoWhileDo(5,'A');
x--;
System.out.println(s);
} while (x > 0); s = whatDoesThisDoWhileDo(0,'A');
System.out.println(s);
}
AAAAA
return result;
}
So what’s the point?
• Why use do … while?
• For when you have a loop body that must execute
at least once
• Example: a program menu
Console Program Menu Example
String selection;
PrintStream out = System.out;
Scanner in = new Scanner(System.in);
int counter = 0;
do
{
out.println("Choose a Menu Option:");
out.println("P) Print Counter");
out.println("Q) Quit");
out.print("ENTER: ");
selection = in.nextLine();
if (selection.toUpperCase().equals("P"))
out.println("Counter: " + counter++);
}while(!selection.toUpperCase().equals("Q"));
out.println("Goodbye!");
Choose a
P) Print
Q) Quit
ENTER: P
Counter:
Choose a
P) Print
Q) Quit
ENTER: A
Choose a
P) Print
Q) Quit
ENTER: P
Counter:
Choose a
P) Print
Q) Quit
ENTER: Q
Menu Option:
Counter
0
Menu Option:
Counter
Menu Option:
Counter
1
Menu Option:
Counter
An Example Session
The for Statement
•Syntax Diagram:
“for”
Init.
Operation
‘(’
‘;’
‘)’
boolean
Expr
‘;’
Statement
‘{’
Statement
‘}’
Update
Operation
The for Statement
•Flowchart:
Initialization
false
Boolean Expr
true
Statement(s)
Update
A for loop example
public static int indexOf(String s, char c)
{
for (int i = 0; i < s.length(); i++)
if (s.charAt(i) == c)
return i;
return -1;
• What’s the output?
}
3
-1
2
String word = "London Calling";
int index = indexOf(word, 'd');
System.out.println(index);
index = indexOf(word, 'x');
System.out.println(index);
index = indexOf(word, 'n');
System.out.println(index);
for loops and counting
• for loops are popular for counting loops
– through the indices of a string
– through the indices of an array (later)
– through iterations of an algorithm
• Good for algorithms that require a known number
of iterations
– counter-controlled loops
Do you understand the order of operations?
for (int i = 0; i < 10; i++)
System.out.print(i);
1) int i = 0;
2) i < 10;
3) System.out.print(i);
4) i++;
5) i < 10;
6) System.out.print(i);
7) i++;
8) i < 10;
9) System.out.print(i);
10) i++;
11) …
i is 0
i is 1
i is 2
i is 3
Examples of for Statements
int sum = 0;
for (int i=1; i<=4; i++)
sum = sum + i;
sum
0
1
3
6
10
i
1
2
3
4
5
int sum = 0;
sum
j
for (int j=1; j<=4; j++)
0
1
{
1
3
sum = sum + j;
4
5
j++;
Be careful not to
double the update of your
}
counting variable
Examples of for Statements
int product = 1;
for (int i=1; i<4; i+=1)
product *= i;
Can be used
equivalently in
many cases
int product = 1;
for (int j = 1; j<= 3; j+=1)
product *= j;
product
1
1
2
6
i
1
2
3
4
product
1
1
2
6
j
1
2
3
4
Equivalence of Loops
for ( INIT ; BOOL_EXPR; UPDATE )
{
LOOP_BODY
}
INIT
while ( BOOL_EXPR )
{
LOOP_BODY
UPDATE
}
INIT
if ( BOOL_EXPR )
{
do
{
LOOP_BODY
UPDATE
} while ( BOOL_EXPR );
}
Are these loops equivalent?
int sum = 0, count = 0;
while (count < x)
{
sum += y;
count++;
}
System.out.println("sum is " + sum);
• Test using:
int sum = 0, count = 0;
for (count = 0; count < x; count++)
sum += y;
System.out.println("sum is " + sum);
Sum is 15
int sum = 0, count = 0;
do
{ sum += y;
count++;
}while (count < x);
System.out.println("sum is " + sum);
x=5, y=3
OUTPUT:
Sum is 15
Sum is 15
x=0, y=3
OUTPUT:
Sum is 0
Sum is 0
Sum is 3
Not Equivalent!
The empty statement
• Syntax Diagram:
• WATCH OUT!
• ;
‘;’
This is a valid line of code that
does nothing, but can create
unexpected problems.
if (score > 21);
System.out.println("Bust! You Lose");
if (score > 21 )
System.out.println("Bust! You Lose");
else;
System.out.println("Hit or Stay?");
The empty statement (cont’d)
Compiler
int sum = 0;
Error
for (int i = 1; i <= 4; i++);
sum = sum + i;
int sum = 0, i = 1;
while (i <= 4);
Infinite loop!
{
sum = sum + i;
i = i + 1;
}
Nested Loops
for (int i = 1; i <= 10; i++)
{
for (int j = 1; j <= 10; j++)
{
int product = i*j;
System.out.print(product + “ ”);
}
System.out.print(“\n”);
}
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20
3 6 9 12 15 18 21 24 27 30
…
Beware Improper Nesting
int sum = 0, count = 0;
if (x > 0)
{ do
{ sum += y;
count++;
}while (count < x);
System.out.println(sum);
}
IS NOT
int sum = 0, count = 0;
if (x > 0)
do
{ sum += y;
count++;
}while (count < x);
System.out.println(sum);
This loop is regarded as
a single statement
Advice: Align your brackets
• Indenting properly is really important:
if (flag)
{
if (y > 0)
{
x = 0;
}
GOOD
}
if (flag)
{
if (y > 0)
{
x = 0;}
}
BAD
Local Variables and Blocks
• A block (a compound statement) is the set
of statements between a pair of matching
braces (curly brackets)
• A variable declared inside a block is known
only inside that block
– it is local to the block, therefore it is called a
local variable
– when the block finishes executing, local
variables disappear
– references to it outside the block cause a
compiler error
Local Variables and Blocks (cont’d)
• Some programming languages (e.g., C and
C++) allow the variable name to be reused
outside the local block
– it is confusing and not recommended,
nevertheless, it is allowed
• However, a variable name in Java can be
declared only once for a method
– although the variable does not exist outside the
block, other blocks in the same method cannot
reuse the variable's name
When and Where to Declare Variables
• Declaring variables outside all blocks but within the
method definition makes them available within all the
blocks
Good programming Practice:
• declare variables just before you use them
• initialize variables when you declare them
• do not declare variables inside loops
– it takes time during execution to create and destroy variables,
so it is better to do it just once for loops)
• OK to declare loop counters in the Init field of for
loops, e.g.
for(int i=0; i <10; i++)…
– the Init field executes only once, when the for loop is first
entered
Java Comments
• Important for you and for others wishing to use
your code.
• Always specify author, version.
• For classes, explain what the class is and how it is
to be used.
• For methods, explain what it does.
• For programs, explain the input and output.
• 2 ways to add comments
// Everything after the double slashes is ignored
/* Everything inside the slash star is ignored */