C++ 数据结构(一)绪论(1)计算
in C/C++ with 0 comment, Views is 71

C++ 数据结构(一)绪论(1)计算

in C/C++ with 0 comment, Views is 71

讲义下载:《清华大学数据结构讲义》

视频观看:《C++ 数据结构 邓俊辉【清华大学公开课】》

引例

绳索计算机及其算法

算法

取 12 段等长的绳索,首尾联接成环
从 A 点起,将 4 段绳索沿 l 伸直并固定于 B
沿另一个方向找到第 3 段绳索的终点 C
移动点 C,将剩余的 3 + 5 段绳索伸直

1.png

总结

这里的计算机就是上述可以重复机械做出垂线的一个过程工具

尺规计算机及其算法

算法

从 A 发出一条与 AB 不重合的射线 $ \rho $
在 $ \rho $ 上取 AC' = C'D' = D'B'
联接 B'B
经 D' 做 B'B 的平行线,交 AB 于 D
经 C' 做 B'B 的平行线,交 AB 于 C

2.png

总结

这里的计算机就是上述用于重复机械做出三等分的尺规工具

其中还包括了一个子程序:过直线外一点,做平行线

算法

计算 = 信息处理

计算就是,借助某种工具,遵照一定规则,以明确而机械的形式进行

计算模型 = 计算机 = 信息处理工具

所谓算法,即在特定计算模型下,用于解决特定问题的指令序列

算法的有穷性

$$ 序列 Hailstone \left( n \right) = \begin{cases} \left \{ 1 \right \} & , \; n \leqslant 1 \\ \\ \left \{ n \right \} \cup Hailstone \left( \frac{n}{2} \right) & , \; n 偶 \\ \\ \left \{ n \right \} \cup Hailstone \left( 3n + 1 \right) & , \; n 奇 \\ \end{cases} $$

Hailstone (42) = { 42, 21, 64, 32, ..., 1}

int hailstone(int n) { // 计算序列 Hailstone(n) 的长度
    int length = 1;    // 从 1 开始,以下按定义逐步递推,并累计步数,直至 n = 1
    while (1 < n) {
        (n % 2) ? n = 3 * n + 1 : n = n / 2;
        length++;
    }
    return length;     // 返回 |Hailstone(n)|
}

对于任意的 n,是否总有 | Hailstone(n) | < ∞ ?

好算法

下一篇:《C++ 数据结构(一)绪论(2)计算模型》

Responses
选择表情