## 티스토리 뷰

**Comp Sci/Tips**

### How to Count (The Fencepost Problem) - Off by One Errors!

jeongtaebang 2018.04.26 18:13**1 ~ n : n items**

This is easy. You only need to read the last item's number to get the number of items.

**8 ~ 11 : 4 numbers**

11 - 8 = 3 numbers? WRONG!!!

Why? Subtraction = the number of spans between numbers, NOT a count of how many things

A span = distance or some quantity measure.

- 8am ~ 11am has 3 units (hours) of time
- 8cm ~ 11cm has 3 units (cm) of distance

8 ~ 11 floors means we are counting the number of things in the range, not the magnitude of the range.

**Conclusion 1 : Two ways to Count**! "Number of things in the range" vs "Magnitude of the range"

- first type of counting : b - a + 1
- second type of counting : b - a

**The Fencepost Problem:**

You are building a fence 100ft long, with fence posts every 10ft. How many posts do you need?

Using our newly found framework, we can think of the problem this way.

This fence needs ten 10ft spans. But we need the number of posts, which is actually the first type of counting. We need one extra.

Hence, we need 11 posts.

**Few Examples**

Days Worked : April 8th ~ April 13th = 6 days (first type)

Hours/Min/Seconds : 4am ~ 6am = 2 hours (second type)

Credits to __https://betterexplained.com/articles/learning-how-to-count-avoiding-the-fencepost-problem/__

#### 'Comp Sci > Tips' 카테고리의 다른 글

[Math] Definitions of Functions, Injection, Surjection, Bijection, and Inverse (0) | 2018.07.04 |
---|---|

How to Count - Number of Ways (경우의 수) (0) | 2018.04.26 |

How to Count (The Fencepost Problem) - Off by One Errors! (0) | 2018.04.26 |

Proof by Induction on Graphs - Why You Should Always Remove a Vertex (0) | 2018.01.07 |

How to Design - Case by Case (0) | 2017.12.18 |

How to Iterate over a fixed range of integers (0) | 2017.12.15 |

**댓글**

**공지사항**

**최근에 올라온 글**

**최근에 달린 댓글**

- Total
- 600

- Today
- 1

- Yesterday
- 1

**링크**

**TAG**

- HTTAA
- relation
- Edmonds
- #Mutual_Exclusivity
- codomain
- Walks
- #Constructive_Counting
- proof
- #Permutations
- Circuit
- Bijective
- #BMI
- #Mutual_Exhaustivity
- #Counting
- Component
- Paths
- definitions
- subgraph
- Independent Set
- Injective
- Graph
- cycle
- trail
- #Circular_Permutations
- image
- TIP
- Induction
- #Combinations
- degree
- surjective