算法设计与分析学习笔记

一、国庆作业

汉诺塔（港台：河内塔）（Tower of Hanoi）是根据一个传说形成的数学问题：

有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

每次只能移动一个圆盘；大盘不能叠在小盘上面。

解题思路：

• via

#include <stdio.h>

// 汉诺塔递归函数
void hanoi(int n, char A, char B, char C) {
    // 当只有一个盘子时，直接从 A 移动到 C
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", A, C);
        return;
    }
    // 先将 n-1 个盘子从 A 移动到 B，以 C 作为中间塔
    hanoi(n-1, A, C, B);
    // 移动第 n 个盘子从 A 到 C
    printf("Move disk %d from %c to %c\n", n, A, C);
    // 最后将 n-1 个盘子从 B 移动到 C，以 A 作为中间塔
    hanoi(n-1, B, A, C);
}

int main() {
    // 初始化盘子数量为 3
    int n = 3;
    // 输出汉诺塔移动步骤
    printf("Hanoi Tower moves:\n");
    // 调用 hanoi 函数进行汉诺塔问题求解
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

汉诺塔问题时间复杂度的分析：

插入排序的重要性质：

#include <stdio.h>

// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, j, key;
    // 从数组的第二个元素开始遍历
    for (i = 1; i < n; i++) {
        // 当前待排序的元素
        key = arr[i];
        // 找到 key 应该插入的位置
        j = i - 1;
        // 将比 key 大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        // 将 key 插入到正确的位置
        arr[j + 1] = key;
    }
}

// 打印数组函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    // 初始化一个待排序的数组
    int arr[] = {12, 11, 13, 5, 6};
    // 计算数组长度
    int n = sizeof(arr) / sizeof(arr[0]);

    // 打印原始数组
    printf("Original array: \n");
    printArray(arr, n);

    // 进行插入排序
    insertionSort(arr, n);

    // 打印排序后的数组
    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}