Algorithm Examples
Contained herein are examples of algorithms to solve the given problems. Use them as a guide to how to write algorithms, remembering that the 'answers' given are one person's version of a good answer/algorithm. You may be able to write a different but perfectly well constructed answer.
Example 1
A standard deck of cards contains 52 cards (if you don’t include the jokers). There are 4 suits: club, diamond, heart, and spade. Each of the 4 suits has a card of each of 13 ranks: ace, 2, 3, 4, …, 10, jack, queen, and king. Write an algorithm to shuffle a deck of cards (i.e., put them in a reasonably random order).
Solution
1) pos = 1
2) If pos > 52 then goto (9)
3) newPos = random number between 1 and 52
4) temp = Card[newPos]
5) Card[newPos] = Card[pos]
6) Card[pos] = temp
7) Increment pos
8) Goto (2)
9) Output “Deck shuffled”
Example 2
For this problem you are to write an algorithm that simulates part of the control of a car engine. The engine has 8 cylinders (i.e., it is a V-8). However, not all of the 8 cylinders may be used all of the time. The car has 3 driving modes that the driver can choose to put the car in: economy (E), touring (T), and sporting (S). If the car is in S mode, all 8 cylinders are used. If the car is in T mode, only 6 cylinders are used. If the car is in E mode, only 4 cylinders are used. If fewer than 8 cylinders are used, every 5 miles the engine randomly chooses which of the 8 different cylinders to use. Your algorithm should simulate someone driving a car, from the time they start the car until they turn off the car. You will need a “loop” that keeps incrementing the number of miles driven during the trip so that you know how to manage the engine cylinders. Note that at any time the driver can switch the driving mode (E, T, S); thus you will have to continually check for that throughout your “loop.” Every 5 miles your algorithm should output which of the 8 cylinders is in use. Also, at the end of the algorithm, output the total number of miles traveled.
Solution
1) mode = ‘S’ // assume this is initial driving mode
2) set cylinder[1..8] = on
3) numMiles = 0
4) car = on
5) if car == off then goto (30)
6) if numMiles is not evenly divisible by 5 then goto (27)
7) mode = current driving mode of car // ‘S’, ‘T’, or ‘E’
8) set cylinder[1..8] = on
9) if mode == ‘S’ then goto (22)
10) c1 = choose random number between 1 and 8
11) c2 = choose random number between 1 and 8
12) if c2 == c1 then goto (11)
13) cylinder[c1] = off
14) cylinder[c2] = off
15) if mode == ‘T’ then goto (22)
16) c3 = choose random number between 1 and 8
17) if (c3 == c1) or (c3 == c2) then goto (16)
18) c4 = choose random number between 1 and 8
19) if (c4 == c1) or (c4 == c2) or (c4 == c3) then goto (18)
20) cylinder[c3] = off
21) cylinder[c4] = off
22) c = 1
23) output “At mile “, numMiles, “ cylinder “, c, “ is “
24) if cylinder[c] == on then output “on” else output “off”
25) c = c + 1
26) if c < 9 then goto (23)
27) numMiles = numMiles + 1
28) car = current state of ignition // on or off
29) goto (5)
30) Output “Finished trip after ”, numMiles, “ miles”
Example 3
Suppose you have a block maze, like the one pictured to the right. You wish to find a path from the little green man to the red bull's ey
1) Start at the target block. Label it with 0, being zero steps away from the target.
2) Mark each (unlabeled white) block adjoining the target block with a 1, since it is one step away from the target.
3) Mark each (unlabeled white) block adjoining the block labeled 1 with a 2, since it is two steps away from the target.
4) Continue this scheme until the block with 'greeny' on it is labeled.
5) Beginning at the block where greeny is, follow the path block-by-block as in a countdown, moving block to block in
declining numeric order until you reach the target block.
Solution #2
1) Set n = 0
2) Label target block with value of n
3) n = n + 1
Label with value n every (unlabeled white) block adjacent to block(s) labeled with n - 1.
4) Repeat step 3 until Start block is labeled.
5) From start block, follow path of declining numeric valued blocks.
e. But, you don't just want to find any path, you wish to find the shortest path. As you can see, there are infinitely many paths 'green man' can take - most of them involving going around in circles. So, supposing he's not going to spend time going in circles, write an algorithm that finds the shortest path from start (where 'greeny' is placed) to target (where the red bull's eye is placed). Note: a move is restricted to up, down, right, or left one block.
Solution #1
