Algorithms
From Wikiversity
Contents |
[edit] Introduction
[edit] Definition
Let's start with a definition of algorithms. Merriam-Webster Online defines it as " a step-by-step procedure for solving a problem or accomplishing some end, especially by a computer" [1]
[edit] Examples
An example of an algorithm would be solving a jigsaw puzzle. The first step is to take a piece and check its size. The second step is to see where it can fit. The third step is to put it in its proper position. Then repeat the process until you're done. That would be an iterative algorithm.
Another important example would be sorting a hand of cards. There are multiple ways of doing this, but one general method is to take the lowest card and move it to the leftmost (or rightmost) position. Next, find the second lowest card and move it to the second leftmost position. Repeat until the cards are sorted.
[edit] Writing an algorithm
To explain the making of an algorithm, we'll take an example of a few commonly used ones.
The first will be a simple function that finds a specified character in a string. It will return -1 if the character is not found, or else the last position in the string at which that character appears.
Pseudocode
Function FindCharacter (CharacterToFind, StringToSearch) returns Position
Step 1.
Position := -1
PositionInString := 0
Step 2.
Let character C := PositionInString in StringToSearch
If character C equals CharacterToFind then Position := PositionInString
PositionInString := PositionInString + 1
If PositionInString < length of StringToSearch then go back to Step 2
Return Position
End Function
C code
int findChar(char ch, const char *s) { int i, n = strlen(s); int position = -1; for (i=0; i < n; ++i) { if (s[i] == ch) position = i; } return position; }
[edit] Recursive Algorithms
The Dictionary.com defintion of recursive: "An expression, such as a polynomial, each term of which is determined by application of a formula to preceding terms." [2]
In computer science, recursive generally refers to an algorithm that calls itself, usually on a subset of the same problem.
An example of a recursive algorithm would be one that travels through a binary search tree and prints out each node's information.
