Difference between revisions of "Simulation"

From PEGWiki
Jump to: navigation, search
(Created page with 'Simulation is a technique in programming where all events are processed in the order of occurrence. By translating real world logic into programming code, simulation speeds up ta…')
 
(Problem)
 
Line 3: Line 3:
 
== Example ==
 
== Example ==
 
=== Problem ===
 
=== Problem ===
Given M trees and the number of days each tree takes to grow a fruit, compute the total number of fruits after <math>N</math> days.
+
Given <math>M</math> trees and the number of days each tree takes to grow a fruit, compute the total number of fruits after <math>N</math> days.
 +
 
 
=== Solution ===
 
=== Solution ===
 
For each tree <math>i</math>, keep a variable <math>K_i</math> indicating the number of days it takes for the next fruit to grow. Simulate the situation day by day. On each day, decrease <math>K_i</math> by 1 and increase the fruit count by the number of <math>K_i</math>'s that equal zero, and reset these <math>K_i</math>'s. Output the total sum at the end.
 
For each tree <math>i</math>, keep a variable <math>K_i</math> indicating the number of days it takes for the next fruit to grow. Simulate the situation day by day. On each day, decrease <math>K_i</math> by 1 and increase the fruit count by the number of <math>K_i</math>'s that equal zero, and reset these <math>K_i</math>'s. Output the total sum at the end.

Latest revision as of 02:51, 8 May 2010

Simulation is a technique in programming where all events are processed in the order of occurrence. By translating real world logic into programming code, simulation speeds up tasks that may otherwise take a long time for human. Simulation does not provide alternative shortcuts to a solution; it simply speeds up the process.

Example[edit]

Problem[edit]

Given M trees and the number of days each tree takes to grow a fruit, compute the total number of fruits after N days.

Solution[edit]

For each tree i, keep a variable K_i indicating the number of days it takes for the next fruit to grow. Simulate the situation day by day. On each day, decrease K_i by 1 and increase the fruit count by the number of K_i's that equal zero, and reset these K_i's. Output the total sum at the end.

Analysis[edit]

This solution gives the correct answer, in \mathcal{O}(MN) time. This is fine if MN is small, but a better technique is required if MN is large.

Characteristics[edit]

When a problem is logically simple and can be directly done by human, simulation is very likely the solution. When the bounds on variables are small, simulation is a quick, safe, and convincing technique. When run time is a concern, other techniques such as dynamic programming may be required.