Algorithms

JavaScript 8: Algorithms

An algorithm is like a recipe, it provides the steps which are to be taken to solve a problem. Algorithms do not have to be implemented on a computer but obviously we are concerned with ones which are.

Fibonacci Numbers

An algorithm for finding numbers in the Fibonacci sequence might be:

start with 0 and 1
add 0 and 1 to get the 3rd number in the sequence - 1
add the 2nd and 3rd numbers in the sequence so far to get the 4th - 2
to get the nth number continue to add the numbers (n-1)+(n-2)

Here is the code with some key items left out and replaced with '###' - can you restore the working version of the program?

function fib(){
var a=###; var b=###;
var astr=### + ' ' + ### + ' ';                 //initialise output string
document.fibform.fibout.value=###;              //output first 2 numbers
if ((document.fibform.numfib.value>0) && (document.fibform.numfib.value<=25)){
  for (i=0;i<document.fibform.numfib.value-2;i++) {
    var c=###;
    a=###; b=###;
    astr+=###+' ';
    document.fibform.fibout.value=###;
  }
 }
else {document.fibform.fibout.value='number out ###';}
}

Here is a working version:

Enter number of Fibonacci values to find (max 25):

Can you design a function to accept a number and decide whether it is a member of the Fibonacci sequence?

Greatest Common Divisor

Another problem which can be expressed in an algorithm is that of finding the greatest common divisor between two numbers. Before we look at the algorithm in detail try a working version:

Enter 2 integers, one in each box, to find their greatest common divisor:

Greatest Common Divisor:

The algorithm is as follows:

Input two integers for which the gcd will be found
Call the function with the two integers as parameters
Inside a loop check whether the second number divides into the first with zero remainder
If the remainder is zero then the gcd has been found
If the remainder is non-zero continue the loop
Inside the loop set the first variable to the second and the second variable to the result of the first mod the second
If the last value of the second variable is 1 then this was the gcd and there is no other gcd
If the last value is greater than 1 then the gcd is the current value of the second variable
Output a suitable string declaring the gcd or that there was none other than 1

Here is the function with key parts replaced by '###' - can you restore them?

function gcd(###,###){
var c; var astr=null;
  while (### % ### ### ###){
    c=###%###;
    ###=###;
    ###=###;
  }
  if (###==###){astr='No gcd other than 1';}
  else {astr='gcd is '+ ###;}
document.gcdform.gcdout.value=###;
}

Prime Numbers

The algorithm for testing whether a number is prime or not might be:

set a variable called 'prime' with the value 'true'
set a loop to run from 2 to the square root of the number to be tested
inside the loop test whether the number divides by the current loop counter with remainder zero
if the remainder is zero then set the prime variable to 'false' and exit the loop
if prime was set to false then output a message to say so
if prime remained true then output that the number was prime

Here is the code with key parts replaced with '###' - can you restore it?

function primefind(){
var astr='';document.primesform.primesout.value=astr;
var p=document.primesform.primetest.value;                 //an alias for a long name
### prime;
var j=###;
if ((p>0) && (p<=65536)){
     prime=###;
   for (j=###;j<= Math.floor(Math.###(p));j++){
     if (p % j == ###) {prime=###;break}}
   if (###==###) {astr+=p+' is prime';}
   else {###+=p+' is not prime. It divides by '+ ###+'.'};
   document.primesform.primesout.value=astr;}
else {document.primesform.primesout.value='number out of range, try again';}
}

Can you extend the code to output a list of prime numbers?

Here is the form from which the function is called:

<FORM NAME="primesform"><TABLE BORDER=0>
<TR><TD><FONT FACE="Arial" SIZE=-1>Enter a number to see if it's prime: </FONT>
<INPUT TYPE="text" NAME="primetest" SIZE=10 MAXLENGTH=10>
<INPUT TYPE="button" NAME="primesin" VALUE="Test Your Number!" onClick="primefind()">
<INPUT TYPE="reset"<>/TD></TR>
<TD><INPUT TYPE="text" NAME="primesout" SIZE=45 MAXLENGTH=45></TD>
</TR></TABLE></FORM>

Return to JavaScript Menu