# 用 Python 計數與模擬

索引、遞迴，以及配對問題與生日問題，採 CS61A 的風格。

### Python 會顯示什麼？索引

*填空 · zh-hant*

Python 會顯示什麼？

```python
>>> v = [3, 1, 4, 1, 5, 9]
>>> v[1]
```

你的答案: 1 (允許的絕對誤差： 0)

#### 提示

1. Python 的位置從 0 開始編號，不是從 1。

2. `v[0]` 是 `3`，下一個是什麼？

#### 參考解答

`1`。Python 的位置從 0 開始，所以 `v[1]` 是**第二個**元素。在 R 裡，`v[1]` 則是第一個元素 `3`。

來源: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied

### Python 會顯示什麼？沒有循環使用

*單選 · zh-hant*

這裡會發生什麼事？

```python
>>> v = [3, 1, 4]
>>> v + 3
```

- [ ] added: `[6, 4, 7]`
- [ ] appended: `[3, 1, 4, 3]`
- [ ] error: `TypeError` 錯誤

你的答案: error

#### 提示

1. 兩個串列之間的 `+` 會把它們接起來。`3` 是串列嗎？

2. Python 不會把較短的值重複到和較長的一樣長。

#### 參考解答

Python 會引發 `TypeError: can only concatenate list (not "int") to list`。對串列而言，`+` 是串接，兩邊都必須是串列。要讓每個元素加 3，寫成 `[x + 3 for x in v]`，得到 `[6, 4, 7]`。

來源: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied

### 用遞迴計算二項式係數

*Python · zh-hant*

用**遞迴**完成 `choose(n, k)`，依據巴斯卡法則 $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$。不要使用 `math.comb` 或階乘。$k<0$ 或 $k>n$ 時傳回 0。

```python
def choose(n, k):
    """Return the number of ways to choose K items from N, using Pascal's rule.

    >>> choose(5, 2)
    10
    """
    pass
```

#### 公開測試

Small case

```pycon
>>> choose(5, 2)
10
```

Middle of a row

```pycon
>>> choose(10, 5)
252
```

Choose none or all

```pycon
>>> choose(4, 0)
1
>>> choose(4, 4)
1
```

Too many

```pycon
>>> choose(3, 5)
0
```

#### 提示

1. 有兩種基本情況：不可能的選法，以及一個都不選或全選。

2. $k$ 為 0 或等於 $n$ 時，恰好只有一種選法。

3. 其他情況，傳回兩個較小 `choose` 呼叫的和。

#### 參考解答

```python
def choose(n, k):
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    return choose(n - 1, k - 1) + choose(n - 1, k)
```

第一個基本情況處理不可能的要求，第二個是巴斯卡三角形的邊緣。每次遞迴呼叫都會讓 $n$ 變小，所以遞迴一定會結束。它會重複計算很多次，$n$ 小時沒有問題，這也正是之後學習記憶化（memoization）的好理由。

來源: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied

### Python 會顯示什麼？把真假值相加

*填空 · zh-hant*

Python 會顯示什麼？

```python
>>> deck = [2, 1, 3, 4]
>>> sum([card == position for position, card in enumerate(deck, start=1)])
```

你的答案: 2 (允許的絕對誤差： 0)

#### 提示

1. 裡面的串列是 `[False, False, True, True]`。

2. 在算術中，`True` 當作 `1`，`False` 當作 `0`。

#### 參考解答

`2`。3 號和 4 號牌在自己的位置上，所以串列是 `[False, False, True, True]`，加總就是在數 `True` 的個數。

來源: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied

### 數出配對數

*Python · zh-hant*

完成 `count_fixed_points(deck)`。`deck` 依翻開順序列出牌；第 $i$ 張翻開的若是 $i$ 號牌，就算一次配對。請傳回配對的次數。

```python
def count_fixed_points(deck):
    """Return how many cards in DECK sit in their own position.

    Positions are numbered from 1, like the cards.

    >>> count_fixed_points([1, 2, 3])
    3
    >>> count_fixed_points([2, 1, 3])
    1
    """
    pass
```

#### 公開測試

Every card matches

```pycon
>>> count_fixed_points([1, 2, 3])
3
```

One match

```pycon
>>> count_fixed_points([2, 1, 3])
1
```

No matches

```pycon
>>> count_fixed_points([3, 1, 2])
0
>>> count_fixed_points([2, 1])
0
```

Empty deck

```pycon
>>> count_fixed_points([])
0
```

#### 提示

1. `enumerate(deck, start=1)` 會同時給出每個位置和那張牌。

2. 把每張牌和它的位置比較，再把結果加總。

#### 參考解答

```python
def count_fixed_points(deck):
    return sum(card == position for position, card in enumerate(deck, start=1))
```

每次比較的結果是 `True` 或 `False`，`sum` 會把它們當作 1 或 0。空的牌堆沒有配對，加總為 0。

來源: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied

### 需要多少人？

*Python · zh-hant*

題目已提供 `birthday_match(k, days)`。請完成 `people_needed(p, days)`：傳回讓 `birthday_match(k, days)` 至少為 `p` 的最小人數 $k\ge1$。這正是 R 的 `qbirthday` 所計算的。假設 $0<p\le1$。

```python
def birthday_match(k, days=365):
    """Probability that at least two of K people share a birthday."""
    no_match = 1.0
    for i in range(k):
        no_match *= (days - i) / days
    return 1 - no_match


def people_needed(p, days=365):
    """Return the smallest number of people for which
    birthday_match reaches at least P.

    >>> people_needed(0.5)
    23
    """
    pass
```

#### 公開測試

Even odds

```pycon
>>> people_needed(0.5)
23
```

Ninety percent

```pycon
>>> people_needed(0.9)
41
```

Ninety-nine percent

```pycon
>>> people_needed(0.99)
57
```

A shorter year

```pycon
>>> people_needed(0.5, days=2)
2
```

#### 提示

1. 從一個人開始，逐次加人，直到機率夠大。

2. 適合用 `while` 迴圈：當 `birthday_match(k, days) < p` 時就繼續。

#### 參考解答

```python
def people_needed(p, days=365):
    k = 1
    while birthday_match(k, days) < p:
        k += 1
    return k
```

迴圈一定會停：有 `days + 1` 個人時必定有人同天生日，機率會達到 1。

來源: [Adapted from Blitzstein & Hwang, Introduction to Probability, §1.8 (R), rewritten in Python](http://stat110.net) · Original exercise; the book's R examples are paraphrased, not copied