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

     发布在:C/C++      浏览:44      评论:0 条评论

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

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

引例

绳索计算机及其算法

算法

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

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

总结

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

尺规计算机及其算法

算法

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

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

总结

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

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

算法

  1. 计算 = 信息处理

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

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

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

算法的有穷性

$$
序列 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}
$$

  1. 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)|
}
  1. 对于任意的 n,是否总有 | Hailstone(n) | < ∞ ?

好算法

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

Responses