____________________________________________________________________
Problem C
Recognizing Good ISBNs
Most books now published are assigned a code which uniquely identifies
the book. The International Standard Book Number, or ISBN, is normally a
sequence of 10 decimal digits, but in some cases, the capital letter X
may also appear as the tenth digit. Hyphens are included at various
places in the ISBN to make them easier to read, but have no other
significance. The sample input and expected output shown below illustrate
many valid, and a few invalid, forms for ISBNs.
Actually, only the first nine digits in an ISBN are used to identify a
book. The tenth character serves as a check digit to verify that the
preceding 9 digits are correctly formed. This check digit is selected so
that the value computed as shown in the following algorithm is evenly
divisible by 11. Since the check digit may sometimes need to be as large
as 10 to guarantee divisibility by 11, a special symbol was selected by
the ISBN designers to represent 10, and that is the role played by X.
The algorithm used to check an ISBN is relatively simple. Two sums, s1
and s2, are computed over the digits of the ISBN, with s2 being the sum
of the partial sums in s1 after each digit of the ISBN is added to it.
The ISBN is correct if the final value of s2 is evenly divisible by 11.
An example will clarify the procedure. Consider the (correct) ISBN
0-13-162959-X (for Tanenbaum's Computer Networks). First look at the
calculation of s1:
---------------------------------------------------------------
digits in the ISBN 0 1 3 1 6 2 9 5 9 10(X)
partial sums 0 1 4 5 11 13 22 27 36 46
---------------------------------------------------------------
The calculation of s2 is done by computing the total of the partial sums
in the calculation of s1:
---------------------------------------------------------------
s2 (running totals) 0 1 5 10 21 34 56 83 119 165
---------------------------------------------------------------
We now verify the correctness of the ISBN by noting that 165 is, indeed,
evenly divisible by 11.
The input data for this problem will contain one candidate ISBN per line
of input, perhaps preceded and/or followed by additional spaces. No line
will contain more than 80 characters, but the candidate ISBN may contain
illegal characters, and more or fewer than the required 10 digits. Valid
ISBNs may include hyphens at arbitrary locations. The end of file marks
the end of the input data.
The output should include a display of the candidate ISBN and a statement
of whether it is legal or illegal. The expected output shown below
illustrates the expected form.
Sample solution
Sample Input
0-89237-010-6
0-8306-3637-4
0-06-017758-6
This_is_garbage
1-56884-030-6
0-8230-2571-3
0-345-31386-0
0-671-88858-7
0-8104-5687-7
0-671-74119-5
0-812-52030-0
0-345-24865-1-150
0-452-26740-4
0-13-139072-4
0-1315-2447-X
Expected Output
0-89237-010-6 is correct.
0-8306-3637-4 is correct.
0-06-017758-6 is correct.
This_is_garbage is incorrect.
1-56884-030-6 is correct.
0-8230-2571-3 is correct.
0-345-31386-0 is correct.
0-671-88858-7 is correct.
0-8104-5687-7 is correct.
0-671-74119-5 is correct.
0-812-52030-0 is correct.
0-345-24865-1-150 is incorrect.
0-452-26740-4 is correct.
0-13-139072-4 is correct.
0-1315-2447-X is correct.
____________________________________________________________________
This page maintained by Ed Karrels.
Last updated September 17, 1996
|