Transcript backtracking

8 Nov
1. Backtracking
2. Structure clashes & program
decomposition
Backtracking
In the forms of iteration and selection used in JSP, the
condition test precedes execution of a part:
1.
we use read-ahead rule to handle serial input files if
pattern is a single character or record
2.
we use multiple read ahead rule if pattern is some
fixed number, n, of characters (or records)
3.
use backtracking if there is no fixed number, n
Backtracking
Problem: A cardfile of punched cards is sorted into
ascending sequence of values of a key which
appears in each card.
• 1st card for each group with a common key value
is a header card
• Other records are detail cards.
– Each detail card carries an integer amount
Sample CardFile
• It is required to produce a report showing the
totals of amount for all keys
Corresponding data structures
Basic Program Structure
Backtracking
Modified problem: file has a record-type field:
– 'header‘ - indicates group-id of the set of records
that follow
– 'detail' - indicates that record belongs to a group
and contains data
– other – if not of type ‘header’ or ‘detail’, record is
an error
• Program should detect the following errors:
• header missing
• detail cards have some other identifier (not ‘detail’)
– Groups containing errors should be listed as an
errorlist (not totaled)
Structure of Error List & Program
Backtracking
Recognition problem: We cannot recognize a good group with any
predetermined fixed read ahead. We tackle the recognition problem
using ‘backtracking’ in 3 stages:
Stage a:
Assume (posit) that a group will be good (ignore the recognition difficulty) and
design the full program accordingly.
Stage a
Stage b:
Verify each data along the way – if any data contradicts the assumption of
good data, issue a quit statement that branches to the second selection
(badgroup)
Replace ‘select’ and ‘or’ with ‘posit’ and ‘admit’; check for header and detail
errors and issue quit statements
Stage b
Stage c:
Modify the program text resulting from stage b. to ensure that side-effects are
repealed where necessary
–
note state of file and buffer (immediately following posit)
–
restore state of file and buffer (immediately following admit)
Comment:
By breaking the problem into distinct stages, we isolate difficulties and can
focus on correct design of each partial solution
Backtracking control structure
• Backtracking control structure
• Javal implentation of backTracking
Exception Handling in Java
Backtracking
• structure diagram and structure text
• Java implementation
Try (стараться)..catch (поймать)..finally(окончательно)
in JSP
• Java Exception Handling in JSP
Example: TryException
• NumberFormatException and
ArrayOutOfBoundsException are unchecked
(несдержанный)
If a checked (задержанный) exception throws an
exception, you must either catch it or else declare in
the method header that the exception is thrown.
HelloRead2
Sample Cardfile
H 0001
D 0001 012
D 0001 020
H 0002
D 0002 015
H 0003
D 0003 025
D 0003 -015