Algorithms and Data Structures
Excercise 1
Introduction

The first exercise is an easy algorithm for reviewing C programming. Write the programs, and refresh your knowledge of C, if you forgot it.

Question 1 [PostScriptg for printing]

(1)Calculate the check digit (in this case, check digit is represented with "?" for each of the following International Standard Book Numbers:

(2)Complete the following 3x3 magic square by filling in the blanks:

magic

(1) is a question about checking errors of ISBNs. ISBN is constructed by 10 digits. The first 9 digits are actual codes, and the last digit (which is called the check digit) is used for checking whether the other digits are correct or not. The check digit is a remainder of dividing a control number by 11. The control number is defined as the following sum: the 1st digit multiplied by 1,  plus the 2nd digit multiplied  by 2, plus the 3rd digit multiplied by 3,,,,,, ,and plus the 9th digit multiplied by 9. When the check digit is 10, then it is displayed as X.

For example, a check digit of ISBN:4-08-873104 is 2.
ISBN

If you want to know more details about the check digit, read the following web site:
ISBN and Barcode
http://muse.cc.kurume-it.ac.jp/home/general/sibhome/isbn/isbnindex.html

(2) is a question about magic squares. In a magic square, the sum of numbers in all lines, in all columns and on the two diagonals yields the same result. Example
In the case of N*N magic squares, the sum total is (N3+N)/2.

Problem 2

Write a  program which calculates the check digit of ISBN.

Execution example 1
% ./a.out
Input ISBN:  4 0 8 8 7 3 1 0 4
Check Number:  2

More generally, ignore the excessive input characters, and output a result in a form near the actual ISBN.

Execution example 2
% ./a.out
Input ISBN:  4-08-873104
ISBN => 4-08-873104-2

In the execution example 1, you may output 10 even if the inspection number is 10. The number is divided in the space when an input is processed. By inputting like this, it can read one character at a time by the %d of a scanf function.

In the execution example 2, it is necessary to convert a character (character type) to a number (integer) or to convert a number (integer) to a character (character type), so please be careful not to get confused.

In the execution example 2, it will be good to read as a character by using %c of a scanf function since characters other than a number are mixed with the input. (%d cannot be used well). If the read character is not a number ('0'-'9'), it will be ignored. If the read character is a number, the read character must be changed into an integer type using an atoi function. A standard function called isdigit is convenient to check whether a certain character is a number or not.

In order to make the form near actual ISBN, it is necessary to copy all the read characters into an array or something, and to change the calculated check digit into a character (if it becomes ten, the character is X).

Problem 3

Write the program which outputs one 3x3 magic square. What method is sufficient to make the magic square? However, don't make a program which outputs the answer embedded beforehand.

Execution example
% ./a.out
   4   3   8
   9   5   1
   2   7   6

Some methods are introduced for your reference below.

Round robin way

Check the all candidate of solutions. Even if it looks simply, the candidate of 362880 (9!) kinds of solutions exists. Since it makes 9 pile loop in the program, it will not take too much time by present computers.

Using a random number

Place numbers which are generated by a random number generator, and check whether it is the magic square. It repeats until the solution is found.

Using a formula

A general solution exists in the (odd number) x (odd number) case of the magic square. If you know this formula, you can use it to solve the problem.


The original Japanese document was written by Naoki Wakamatsu
This translation document was written by Kenichi Maezu <m5061121@u-aizu.ac.jp>
and Hajime Matsui <m5061122@u-aizu.ac.jp> and checked by L. Pichl.