Cycles in CS

Who among us does not remember an instructive story about how Tom Sawyer's aunt Polly's job was painting the fence: "Sighing, he dipped the brush into the bucket, picked up a Board fence, repeated the operation did it again..." (mark TWAIN. The Adventures Of Tom Sawyer).

Let us construct the algorithm for painting the fence. Suppose that we have a paint brush and enough paint. Write, for example, the following sequence of actions:

  • To approach the left edge of the fence.
  • To paint one Board.
  • Step to the right by the width of the Board.
  • To paint one Board.
  • Step to the right by the width of the Board.
  • To paint one Board.

It is clear that if we got to write this algorithm until the end, painting the fence will have a long delay. If we knew how many boards in the fence, we could complete the construction of the algorithm, assigning the desired number of rows. However, it is a long and monotonous occupation. And aunt Polly never thought of the boards in the fence. She just said, "are you Going to paint until the fence is not over". Without knowing, she took advantage of a very common way of organizing action cycle (repeat). Job aunt Polly can be written as the following algorithm:

  • Admiring the Moon, remember the Moon cycles algorithm
  • To approach the left edge of the fence.
  • While the fence did not end, repeat:
  • To paint one Board.
  • Step to the right by the width of the Board.
  • The end of the cycle.
  • To leave.

This means that the executor first checks whether the condition Q. If so, the actions P1, P2, ..., PN (a sequence of these actions is called the loop body), then the condition Q is tested again and so on. If Q is not performed, the contractor continues to step recorded after the line "End of cycle". It is seen that the words "the End" plays here the same role as the words "End of branch" in the entry fork. May of course happen that the condition Q are not met from the beginning (in the fence, there are no Boards!). Well, then the actions that constitute the loop body will not be committed even once.

So, a cycle (repetition) is a form of action in which the same sequence occurs a few times (or even once) as long as some condition is true.

Category: