﻿ section 3

# 3 Description of Algorithm

## 3.1 If ~ END IF blocks and IF statements

### 3.1.1 IF ~ ELSE ~ END IF

Example 25.
A program that displays the solution of the quadratic equation ax2+bx+c=0 when coefficients a, b, c are entered.

```10 INPUT a,b,c
20 LET D=b^2-4*a*c
30 IF D>=0 THEN
40    PRINT (-b-SQR(D))/(2*a), (-b+SQR(D))/(2*a)
50 ELSE
60    PRINT "no solution"
70 END IF
80 END```

This program selects the process depending on the value of discriminant D = b2`-`4ac.
When D≥0, two solutions are calculated and displayed using the quadratic formula, and otherwise, “no solution” is displayed.
The inequality sign “≥” is substituted by “>=” in BASIC.
Like this, IF ~ ELSE ~ END IF is used to describe the process that executes ~ when a certain condition is true, and otherwise executes ~ .
An IF ~ ELSE ~ END IF block is described in the form shown below.

IF condition THEN
~
ELSE
~
END IF

The portion ~ can consist of multiple lines, which may be even blocks as FOF ~ NEXT blocks or IF ~ ELSE ~ END IF blocks.
In addition, if there are no statements between the ELSE line and the END-IF line, “ELSE” can be omitted.

### 3.1.2 IF ~ ELSEIF ~ ELSE ~ END IF

The Program in Example 25 displays two solutions when D=0. To separately handle the process for D=0, the following will do,

```100 INPUT a,b,c
110 LET D=b^2-4*a*c
120 IF D>0 THEN
130    PRINT (-b-SQR(D))/(2*a), (-b+SQR(D))/(2*a)
140 ELSE
150    IF D=0 THEN
160       PRINT -b/(2*a)
170    ELSE
180       PRINT "no solution"
190    END IF
200 END IF
210 END```

but the same process can be written as follows.

Example 26.

```100 INPUT a,b,c
110 LET D=b^2-4*a*c
120 IF D>0 THEN
130    PRINT (-b-SQR(D))/(2*a), (-b+SQR(D))/(2*a)
140 ELSEIF D=0 THEN
150    PRINT -b/(2*a)
160 ELSE
170    PRINT "no solution"
180 END IF
190 END```

### 3.1.3 IF statement

The program in Example 25 can also be written as follows.

```10 INPUT a,b,c
20 LET D=b^2-4*a*c
30 IF D>=0 THEN PRINT (-b-SQR(D))/(2*a), (-b+SQR(D))/(2*a) ELSE PRINT "no solution"
40 END```

If the number of the statements to be executed when the condition holds is only one, the number of the statements to be executed when the condition fails is only one, and if both of them are such statements called imperative statements, an IF statement in the form of the following is available

```IF condition THEN imperative_statement ELSE imperative_statement
```

LET statements, INPUT statements, PRINT statements, SET statements, PLOT statements, RANDOMIZE statements, and so on are imperative statements.
But a IF statement is not an imperative statement, that is, any IF statement can not be included in a IF statement of the above form.

If there is no statement to be executed when the condition is not true, the IF statement is written in the form

```IF condition THEN imperative_statement
```

For example, if you do not need to display “no solution” when D<0, the following will do.

```10 INPUT a,b,c
20 LET D=b^2-4*a*c
30 IF D>=0 THEN PRINT (-b-SQR(D))/(2*a), (-b+SQR(D))/(2*a)
40 END```

### 3.1.4 How to write conditions

Inequalities a≤b , a≥b and a≠b are written like `a<=b`, `a>=b` and `a<>b`, respectively.
Complicated conditions can be described using AND, OR, NOT and parentheses.
For example, conditions “p and q”, “p or q” are written as “p `AND q`” , “p `OR q`” ,respectively. NOT is written just before the subject to be negated.
Among AND, OR and NOT, NOT precedes AND and OR. Between AND and OR, AND precedes OR. If you want to change the priority, you can use parentheses.
Although “a<x and x<b” is written as a<x<b in mathematics, this style is not used in BASIC.

Example 27.
A Program that finds the sum of three-digit positive integers that can be divided by 3 or 8.

```10 LET t=0
20 FOR n=100 TO 999
30    IF MOD(n,3)=0 OR MOD(n,8)=0 THEN
40       LET t=t+n
50    END IF
60 NEXT n
70 PRINT t
80 END```

### 3.1.5 Pythagorean numbers

Three positive integers x, y, and z which satisfy the equation x2+y2=z2 are called Pythagorean numbers.
To systematically seek Pythagorean numbers, we make such a program as outputs `x`, `y` and `z= SQR(x^2+y^2)` when `z` is an integer changing the values of x and y successively.
Whether `z` is an integer or not can be known by checking whether `INT(z)` agrees with `z`.

The following program seeks Pythagorean numbers in the range of 1≤x≤y≤100.

Example 28.

```10 FOR x=1 TO 100
20    FOR y=x TO 100
30       LET z=SQR(x^2+y^2)
40       IF INT(z)=z THEN PRINT x,y,z
50    NEXT y
60 NEXT x
70 END```

[Note]
The above program will operate even with such old type BASIC as N88-BASIC. But correct answers may not be obtained.
In Full BASIC, correct answers can be obtained by the above program, since the result of a power or square root operation must be correct if it can be expressed within the significant digits.

## 3.2 DO ~ LOOP

### 3.2.1 DO ~ LOOP

A DO statement and a LOOP statement form a pair which describes a repetition.
Example 29. Endless loop

```10 LET A=0
20 DO
30    LET A=A+1
40    PRINT A
50 LOOP
60 END```

The statements written between the DO line and the LOOP line are repeatedly executed. In the above program, line 30 and line 40 are repeatedly executed.
[Supplement] When the above program is executed, click or select Break from the Run menu to abort the execution.

### 3.2.2 DO WHILE ~ LOOP

This type of a loop repeats while a condition holds.
Example 30.

```10 LET A=0
20 DO WHILE A<100
30    LET A=A+1
40    PRINT A
50 LOOP
60 END```

When line 20 in Example 29 is modified to the above, the repetition stops when the value of A becomes 100.

DO WHILE ~ LOOP is written in the following form. The operation of this structure is expressed in a flowchart as shown in the figure.

```DO WHILE condition

LOOP
```

In this loop structure, the condition is checked before executing the process to be repeated, so if the condition fails at the beginning, no repetition is executed.
In Example 30, for example, if line 10 is changed to “`10 LET A=100`”, line 30 and line 40 are never executed.

### 3.2.3 DO UNTIL ~ LOOP

DO UNTIL ~ LOOP is a repetitive structure specifying the condition to finish the repetition.

Example 31

```10 LET A=0
20 DO UNTIL A>=100
30    LET A=A+1
40    PRINT A
50 LOOP
60 END```

Example 31 has the same meaning as Example 30 has. Generally, if negation is used, “DO WHILE ~ LOOP” and “DO UNTIL ~ LOOP” can be mutually replaced. “UNTIL p” is same as “WHILE NOT p”. The selection depends on the intention of a program writer.

### 3.2.4 Factorization into prime factors

DO ~ LOOP enables a program that factorizes an entered positive integer.

A positive integer to be factorized is to be input into a variable n.
First, whether n is divisible by 2 is checked, and if so, 2 is output and n is replaced with the number n divided by 2. This is repeatedly executed while n is divisible by 2.
When n can no more be divided by 2, the divisor is increased to 3, and the same as above is repeated.
What should be done next is to increase the divisor to 5 and then repeat in the same way, but since it is difficult to have the computer answer the next prime, 1 is simply added to the divisor. Then the divisor next to 3 will be 4, but this will cause no problem, because n has been divided by 2 as much as possible.

Example 32 Factorization into prime factors

```110 INPUT n
120 LET f=2
130 DO UNTIL n=1
140    DO WHILE MOD(n,f)=0
150       PRINT f;
160       LET n=n/f
170    LOOP
180    LET f=f+1
190 LOOP
200 END```

A variable f represents the divisor (maybe a factor). In line 120, the first divisor 2 is set.
Through the repetition from lines 140 to 170, dividing by f is done as much as possible. When dividing can no longer be done, 1 is added to f (line 180).
This will be repeated in the DO ~ LOOP of line 130 through line 190, but the repetition must be stopped in some time. The condition is when all the factors are taken from n, and it is n=1. This is the condition written in line 130.

### 3.2.5 EXIT DO

An EXIT DO statement is an instruction to finish the repetition of a DO ~ LOOP and moves the control to the next line of the LOOP statement.
DO WHILE ~ LOOP or DO UNTIL ~ LOOP decides whether the body of the loop should be executed or not before it is executed.
But sometimes the decision is impossible at the beginning of a loop. In such a case, an EXIT DO statement is used.

The following program demands input repeatedly until a correct answer is input. In this case, it can not be judged before the input whether it is correct or not.

Example 33

```10 PRINT "2×3=?"
20 DO
30   INPUT n
40   IF n=2*3 THEN EXIT DO
50   PRINT "Incorrect. Type Again."
60 LOOP
70 PRINT "Right"
80 END```

The flow of processing of Example 33 is shown in the figure.

### 3.2.6 Base conversion

We make a program that expresses an entered positive integer in base 2.
Let n =11, for instance.
As 11=1×23+0×22+1×2+1, 11 is expressed as 1011 in base 2.
If you want to successively find these from the lower digit, do as shown below.

2）11 ･･･1
2） 5 ･･･1
2） 2 ･･･0
2） 1 ･･･1
0

Since the quotient of a divided by b is obtained by INT(a/b) and the remainder by MOD(a,b), the following program is obtained.

Example 34.

```10 INPUT n
20 DO
30    LET q=INT(n/2)
40    LET r=MOD(n,2)
50    PRINT r
60    IF q=0 THEN EXIT DO
70    LET n=q
80 LOOP
90 END```

### 3.2.7 Euclidean algorithm

We denote the greatest common divisor of two integers a and b as GCD(a,b). Then we have:

Let r be the remainder when a is divided by b.
If   r = 0 then GCD(a,b) = b, otherwise GCD(a,b) = GCD(b,r).

The greatest common divisor of two positive integers can be found when this property is repeatedly used as follows. This is called the Euclidean algorithm.

Divide a by b, and let r be the remainder.
If r=0 then b is the greatest common divisor.
If r>0 then this operation is executed again with b,r made new a,b.

In this operation, the value of b decreases each time it is repeated, and it will surely end after some repetitions.

Example 35.
A program that finds the greatest common divisor using Euclidean algorithm.

```10 INPUT a,b
20 DO
30    LET r=MOD(a,b)
40    IF r=0 THEN EXIT DO
50    LET a=b
60    LET b=r
70 LOOP
80 PRINT b
90 END```

It should be noted that assignment statements are used in such an order as shown in line 50 and line 60 to make the value of b,r the next value of a,b at the end of the repetition.

## 3.3 Arrays

### 3.3.1 DIM statement

In the beginning of a program, write
`DIM A(10)`
to prepare 10 variables A(1)，A(2)，A(3)，A(4)，A(5)，A(6)，A(7)，A(8)，A(9) and A(10), which can be used as ordinary variables.
A group of such variables is called an array, while each variable is called an indexed variable or an element of the array, and each number within the parentheses is called an index or a subscript.
Example.

```10 DIM A(10)
20 LET A(4)=15
30 PRINT A(4)
40 END```

In a DIM statement, the name of an array and the upper bound of indices are written in the form as shown above. The rule for naming an array is the same as for an ordinary variable. Note that only constants like 10, 20 can be written for the upper bound of indices.

[Note] Handling of arrays is different from that in minimal BASIC, the former standard for BASIC. Especially, it should be noted that the array index starts with 1.

On indexed variables, an expression containing a variable can be written for an index. For example:

```10 DIM B(4)
20 LET i=3
30 LET B(i)=17
40 PRINT B(i)
50 END```

If this feature is utilized, it becomes possible to select a variable on executing a program.
Such variable names as B1, B2 and B3 can be used In BASIC. In such a case, however, the numeric portions such as 1, 2 and 3 are part of variable names, and therefore, it is impossible to select any of B1, B2 or B3 by specifying a number with a program.

Example 36. Fibonacci Series.
The Fibonacci series { fn } is defined by   f1=1， f2=1， fn = fn-1+fn-2 (n = 3, 4, 5, …).
The following program finds the first 20 terms of he Fibonacci series using an array.

```100 DIM f(20)
110 LET f(1)=1
120 LET f(2)=1
130 FOR i=3 TO 20
140    LET f(i)=f(i-1)+f(i-2)
150 NEXT i
160 FOR i=1 TO 20
170    PRINT i,f(i)
180 NEXT i
190 END```

### 3.3.2 Frequency Distribution Table

Array can be utilized for making distribution tables.
Here we make a program that creates a frequency distribution table with class width 10 to summarize the scores of an examination of which full marks is 100 points, for example.
We prepare 11 indexed variables from m(0) to m(10), and represent the number of persons of 0 point to 9 points by m(0), the number of persons of 10 points to 19 points by m(1), the number of persons of 20 points to 29 points by m(2), and so on.
In order to use 11 indexed variables m(0),m(1), ... , m(10), we write such a DIM statement as

`  DIM m(0 TO 10)`

in the beginning of the program.
Then we write

`  MAT m=ZER`

to substitute zeros for all the elements of the array m.
When a score is entered, an index i, which indicates the rank, is calculated and 1 is added to the indexed variable indicated by the index i.
A negative number is to be entered for the end mark on finishing of input of all the scores.

[Note] MAT is the first 3 letters of “matrix”.

Example 37.

```100 DIM m(0 TO 10)
110 MAT m=ZER
120 DO
130    INPUT n
140    IF n<0 THEN EXIT DO
150    LET i=INT(n/10)
160    LET m(i)=m(i)+1
170 LOOP
180 FOR i=0 TO 10
190    PRINT i*10;" ~ ";i*10+9,m(i)
200 NEXT i
210 END```

Example 38.
A program that repeats 10000 times the simulation of finding the sum of spots on 10 dice, totalizes the results and displays them in a histogram.

```100 DIM A(10 TO 60)
110 MAT A=ZER
120 FOR k=1 TO 10000
130    LET t=0
140    FOR n=1 TO 10
150       LET t=t+INT(RND*6+1)
160    NEXT n
170    LET A(t)=A(t)+1
180 NEXT k
190 SET WINDOW 9,61,0,1000
200 FOR t=10 TO 60
210    PLOT LINES: t-0.5,A(t); t+0.5,A(t);
220 NEXT t
230 END```

Since the sum of the spots is in the range of 10 to 60, an array A with indices in the same range is prepared.

### 3.3.3 Sieve of Eratosthenes

The set of prime numbers can be obtained by the method of successively removing the composite numbers from the set of integers to leave only the prime numbers. This method has long well been known as the “sieve of Eratosthenes.”
Preparing a table with 2 or more integers sequentially arranged and marking composite numbers n2, (n+1)n, (n+2)n, …, multiples of n for n=2,3,4,…, prime numbers will remain last.

We prepare an array s with indices from 2 to 1000 and represent an integer n by an indexed variable s(n), expressing that n is marked by s(n)=1 and not by s(n)=0.

Example 39.

```100 DIM s(2 TO 1000)
110 MAT s=ZER
120 FOR n=2 TO 1000
130    IF s(n)=0 THEN
140       PRINT n
150       FOR  k=n^2 TO 1000 STEP n
160          LET s(k)=1
170       NEXT k
180    END IF
190 NEXT n
200 END
```

if an integer n is not marked when the process of marking all multiples of k is completed for all integers k with 2≤k<n, 　n can be judged to be prime.
The process is rationalized using this property, so that all are processed in FOR~NEXT at lines 120~190.
The multiples of n are marked by FOR~NEXT at lines 150~170.
When the value of k is sequentially increased by n from n2, the value of k may not become 1000, but the repetition ends when the value of k exceeds 1000 because of the property of FOR~NEXT , and so the program operates without problem.

### 3.3.4 Array declaration

Two-dimensional or three-dimensional arrays are also available.
For example, when `DIM A(2,3) `is written, 6 indexed variables, A(1,1), A(1,2), A(1,3), A(2,1), A(2,2), and A(2,3), are prepared.

More than one array can be declared in a DIM statement. In such a case, array declarations are delimited by commas. For example,

`  DIM A(4),B(10),C(20)`

Indices of an array are regarded to start with 1 in Full BASIC.
If you want indices to start with 0, write “OPTION BASE 0” in a line above the line where the first array declaration is written as shown below.

```10 OPTION BASE 0
20 DIM A(4)
30 LET A(0)=7
40 MAT PRINT A
50 END
```

If you desire to make the lower bound other than 0 or 1, or different for each array, use such a DIM statement as shown below.

` DIM A(-4 TO 5),B(0 TO 2, 1 TO 3)`

In this array declaration, 10 indexed variables from A(－4) to A(5) and 9 indexed variables from B(0,1) to B(2,3) are prepared.

### 3.3.5 Binomial coefficient (Pascal’s triangle)

Let's make Pascal's triangle or the table of number of combinations nCr utilizing a two-dimensional array.
We use the following recurrence to calculate nCr.
When r = 0 or r = n,   nCr = 1
When 0<r<n,             nCr = n-1Cr-1 　+n-1Cr

Example

```100 DIM C(1 TO 10, 0 TO 10)
110 MAT C=ZER
120 FOR n=1 TO 10
130    FOR r=0 TO n
140       IF r=0 OR r=n THEN
150          LET C(n,r)=1
160       ELSE
170          LET C(n,r)=C(n-1,r-1)+C(n-1,r)
180       END IF
190    NEXT r
200 NEXT n
210 MAT PRINT C;
220 END```

With the MAT PRINT statement used in line 210, the values of all indexed variables belonging to the array are collectively output. If a semicolon is written following the array name as in line 210, the numerical values are closely output.

### 3.3.6 MAT statement (input/output)

Full BASIC prepares devices convenient for processing arrays. For example, MAT INPUT statements and MAT PRINT statements make array input and output easy.

Example 41.

```10 DIM A(5)
20 MAT INPUT A
30 MAT PRINT A
40 END```

A MAT INPUT statement inputs numerical values collectively to an array. When the MAT INPUT statement in line 20, for example, is executed, 5 numerical values are to be input by delimiting by commas.
A MAT PRINT statement collectively outputs the values of all the indexed variables belonging to an array.
If such a MAT PRINT statement without semicolon written after the array name as in line 30 is executed, the numerical values are output at fixed positions.

A MAT READ statement substitutes numerical values for arrays from the DATA statements.
In the DATA statement, necessary number of numerical values should be written by delimiting by commas.
This is convenient when you want to enter the same data each time in programs in test stages.

Example 42. A program that finds the smallest value.

```10 DIM A(10)
20 DATA 45,61,73,91,43,12,65,34,96,12
40 LET k=1
50 FOR i=2 TO 10
60    IF a(i)<a(k) THEN LET k=i
70 NEXT i
80 PRINT a(k)
90 END```

### 3.3.7 Sort（Selection Sort）

We make a program that arranges entered 10 numerical values in increasing order.
We assume that 10 numerical values are entered to 10 indexed variables from a(1) to a(10).
We first exchange the smallest value in a(1), a(2), …, a(10) with a(1). Then a(1) becomes the smallest.
Next, the smallest one of the values from a(2) to a(10) is exchanged with a(2). Then a(2) becomes the second smallest.
If the similar process is executed repeatedly, the numerical values are arranged in increasing order in the array a.

Example 43.

```100 DIM a(10)
110 MAT INPUT a
120 FOR i=1 TO 9
130    LET k=i                       ! k is the index of the smallest value.
140    FOR j=i+1 TO 10
150       IF a(j)<a(k) THEN LET k=j
160    NEXT j
170    LET t=a(i)                    ! using t as a temporary variable,
180    LET a(i)=a(k)                 ! exchange the values in a(k) and a(i).
190    LET a(k)=t
200 NEXT i
210 MAT PRINT a;
220 END```

Lines 130~160 are the process of acquiring the index of the smallest value in a(i)~a(10) for variable k.
In lines 170~190, a temporary variable t is used to exchange the values of a(i) and a(k).
The portion of a line subsequent to ! is a comment. This does not affect the execution of a program. Comments are used for explaining the meaning of the program.
To see how this program is operating, you can move the MAT PRINT statement in line 210 to the suitable position.

### 3.3.8 Insertion Sort

By using a recursive way of thinking, you can make a sorting algorithm of rather different type.
If a(1)~a(i-1) are already arranged in increasing order, a(1)~a(i) will be arranged in increasing order by inserting the value of a(i) in the proper position and shifting the subsequent values backwards sequentially.
Then if you repeat the aforementioned process sequentially from i=2 to i=10, they will be arranged in increasing order.

Example 44.

```100 DIM a(10)
110 MAT INPUT a
120 FOR i=2 TO 10
130    LET b=a(i)                  ! a(i) is saved to b.
140    LET j=i                     ! j will means the position for inserting b.
150    DO WHILE j>1 AND a(j-1)>b
160       LET a(j)=a(j-1)          ! Shift the data backwards.
170       LET j=j-1
180    LOOP
190    LET a(j)=b
200 NEXT i
210 MAT PRINT a;
220 END```

In lines 130~180, the position for inserting the value of a(i) is sought, accompanied by the process of shifting the values in the variables backwards.
In the AND operation in line 150, the sequence of “`j>1`” and “`a(j-1)>b`” is important.
When j=1 , the condition “`j>1`”fails so that “`a(j-1)>b`” will not be tested.
In line 150, j=1 may occur, and so if “`a(j-1)>b`” were tested before “`j>1`”, the index would be out of range, resulting in an error.

## 3.4 Exception Handling

### 3.4.1 Error during execution (Exception)

If PRINT is spelled as PRIMT or NEXT corresponding to FOR does not exist, the compiler reports an error. This is a syntax error.
If 1/x is calculated when the value of x is 0, an error occurs, of course.
In BASIC, the largest number which can be handled is settled, and if the absolute value of the calculation result exceeds that value (MAXNUM), the error occurs (overflow).
Such errors that occur during execution are called exceptions and are discriminated from syntax errors.

The zero division error can be prevented by checking the divisor in advance of the division, but it is hardly possible to predict the overflow error. In such a case, action must be taken only after the error has occurred.

### 3.4.2 WHEN EXCEPTION structure

A WHEN EXCEPTION structure indicates the process to be executed when an exception has occurred.
We write these in the following form.

```WHEN EXCEPTION IN

Processes that may cause an exception

USE

The process to be executed when an exception has occurred

END WHEN
```

If an exception occurs in a statement written between a WHEN-EXCEPTION-IN line and a USE line, the execution of the statement is suspended and the control is moved to the line following the USE line.
On the other hand, if all the statements written between a WHEN-EXCEPTION-IN line and a USE line has been executed without causing an exception, statements written between the USE line and the END-WHEN line shall not be executed.

This structure is indispensable for drawing function graphs.

Example 46 The graph of y = tan x

```100 OPTION ANGLE DEGREES
110 DEF f(x)=TAN(x)
120 SET WINDOW -180,180,-4,4
130 DRAW AXES(90,1)
140 FOR x=-180 TO 180
150    WHEN EXCEPTION IN
160       PLOT LINES: x,f(x);
170    USE
180       PLOT LINES
190    END WHEN
200 NEXT x
210 END```

If the PLOT LINES at line 180 does not exist, the line segment connecting two points (89, TAN(89) and (91,TAN(91)), for example, shall be drawn.