数据结构第三章作业

---

第一题

试推导求解n阶hanoi塔问题至少要执行移动操作move次数。

解：

设 \(n\) 阶hanoi塔问题所需的操作次数为 \(T_n\)。

我们有： $$ T_0 = 0 $$

\[ T_n = 2T_{n-1} + 1, \space n>0 \]

代换 \(a_n=T_n+1\)，得： $$ a_0 = 1 $$

\[ a_n = 2a_{n-1}, \space n>0 \]

从而， $$ a_n = 2^n $$ 因此， $$ T_n = 2^n-1 $$

---

第二题

试证明：若借助栈由输入序列 \(1, 2, \ldots, n\) 得到输出序列为 \(P_1, P_2, \ldots, P_n\)（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着 \(i < j < k\)，使 \(P_j < P_k < P_i\)。

证明：

假设存在 \(i < j < k\)，使 \(P_j < P_k < P_i\)。

则出栈顺序为 \(P_j, P_k, P_i\)，这与\(i<j<k\) 矛盾，因此假设不成立，原命题成立。

---

第三题

假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

1. 下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO

2. 通过对(1)的分析，写出一个算法，形式如下：bool Judge(char A[])，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组A[]中）。

解：

AD均合法。

#include <string.h>
#include <stdbool.h>
bool Judge(char A[]) {
    int n = strlen(A);
    int cnt = 0;
    for (int i =0; i < len; i++) {
        if (A[i] == 'I') {
            cnt++;
        } else {
            cnt--;
        }
        if (cnt < 0) return false;
    }
    return cnt == 0;
}