---
date: 2017-04-24 11:11:46 +0800 +0800
iscjklanguage: true
lastmod: 2023-11-23 21:05:06 +0900 +0900
publishdate: 2017-04-24 11:11:46 +0800 +0800
title: 编程珠玑 1-9 证明
---

~~似乎找到了丢失的脑子~~  
中午书到货了，下午上课时翻了翻编程珠玑，对于第一章的习题 9 比较困惑  

问题大致如下：
空间很廉价，时间很宝贵且向量很稀疏的情况下，如何设计一种技术，在第一次访问向量的项时将其初始化为 0  

通俗点说就是有一个很长的数组，只会用到其中几个元素。所以不想去遍历数组将每一项初始化为 0， 设计一种惰性的初始化方法  

书后解法：
借助于两个长度为 n 的数组 `from` 和 `to` 和一个整型变量 `top`。在访问数组的某一项 `i` 时先判断
`from[i] < top && to[from[i]] == i`。如果成立则此项已经初始化过，如果不成立则执行下面操作初始化

```
from[i] = top;
to[top] = i;
data[i] = 0;
top++;  // top 初始值为 0
```

好吧，你可能对于这个问题会想 `from[i]` 的值如果为一个负数，那么 `to[from[i]]` 会是什么？
这的确是书中没有提及的，不过很容易解决：

对于 4 bytes 的 int 类型来说，其范围为 –2,147,483,648 到 2,147,483,647
那么对 `from[i]` 的值加上 2,147,483,648，这样便转移到安全的范围了

回到这个问题的解决方法上来，蠢作者起初认为，这个方法仅保证了已经被初始化过的项不会被再次初始化，存在随机的值使得条件成立，不过概率很小
但是仔细考虑觉得给出的第二个条件比较奇怪 为什么特意判断 `to[from[i]] == i` 呢  

于是在纸上写写画画， x 代表未经初始化的随机值：

```
index 0 1 2
data  x x x
from  x x x
to    x x x

top = 0
```

访问 `index = 1` 由于 `from[i] < top` 不满足，进行初始化

```
index 0 1 2
data  x 0 x
from  x 0 x
to    1 x x

top = 1
```

如果访问 `index = 0`
那么要满足 `from[i] < top` 即 `from[i] < 1` 则 `from[i]` 只能为 0
而第二个条件则是 `to[from[i]] == i` 显然不满足

```
index 0 1 2
data  x 0 x
from  x 0 x
to    1 x x
```

凭感觉猜测：不存在一个未访问过的 `i` 使得 `from[i] < top && to[from[i]] == i` 成立

给出如下的数学证明：  

1) `top = 0` 时，因为 `from[i] >= 0` 恒成立，所以 `from[i] >= top` 恒成立

2) `top > 0` 时，利用反证法，存在索引 `i (i ∈ {未访问的 i})`，有 `from[i] < top && to[from[i]] == i` 成立。即 `to[x] = i (x < top, x = from[i], i ∈ {未访问的 i})` 成立。但是根据前提对于任意的 `x < top` 有 `to[x] = i (i ∈ {访问过的 i})`， 与假设产生矛盾。所以猜想正确