Control and simulation 0/2

Lesson 9 of 21

Simulation

Follow a process step by step, first by hand and then in code.

Part 1 of 8 Processes in steps

Solving a problem by doing its steps

Suppose you put 100 yen in a bank that adds 1% interest once a year and drops any fraction of a yen. How many years until you have 1,000 yen? You could look for a formula, but you don't need one. Start at 100, add one year of interest, check whether you have reached 1,000, and repeat. The number of times you repeated is the answer.

You have written this kind of loop before. The halving loop changed n and steps on every pass, and the answer was whatever steps held when the loop stopped. The bank needs the same loop with a different rule inside.

Many judge problems are like this, only with a longer story. Two bears put on weight every year. Three people pass cookies around. Each problem describes a process that moves in steps, and asks how things stand at the end, or how many steps it takes to get there. When the problem says exactly what happens in each step, you can solve it by doing the steps: a loop where one pass is one step of the story. This is called a simulation, and it needs nothing beyond the loops you already know.

The work is in getting the story into the loop correctly. For each simulation in this lesson, we will answer four questions:

  • Which numbers describe the process at a given moment?
  • How do they change in one step, and in what order?
  • When does the process stop?
  • How can you check that the program does what the story says?

Definition

State

The state of a process is the set of values that describe it completely at one moment. The state now and the rule for one step are enough to work out the state after the step.