• 【蓝桥杯】C语言常见高级算法

    🌸个人主页：Yang-ai-cao
    📕系列专栏：蓝桥杯    C语言
       🍍博学而日参省乎己，知明而行无过矣

    目录

    🌸个人主页：Yang-ai-cao

    📕系列专栏：蓝桥杯    C语言

    🍍博学而日参省乎己，知明而行无过矣

    一、动态规划（Dynamic Programming）

    例子：斐波那契数列

    动态规划解法

    例子：0-1 背包问题

    动态规划解法

    二、贪心算法（Greedy Algorithm）

    例子：活动选择问题

    贪心算法解法

    三、回溯算法（Backtracking）

    例子：N皇后问题

    回溯算法解法

    四、分治算法（Divide and Conquer）

    例子：归并排序（Merge Sort）

    五、图算法（Graph Algorithms）

    例子：Dijkstra 算法（单源最短路径）

    贪心算法（Greedy Algorithm）

    例子：霍夫曼编码（Huffman Coding）

    总结

    一、动态规划（Dynamic Programming）

    例子：斐波那契数列

    动态规划解法
    1. #include 
    2.  
    3. // 计算斐波那契数列的第 n 项
    4. int fib(int n) {
    5.     // 创建一个数组来存储斐波那契数列
    6.     int f[n+1];
    7.     f[0] = 0;  // 第 0 项是 0
    8.     f[1] = 1;  // 第 1 项是 1
    9.  
    10.     // 通过迭代计算第 n 项
    11.     for (int i = 2; i <= n; i++) {
    12.         f[i] = f[i-1] + f[i-2];  // 当前项等于前两项之和
    13.     }
    14.     return f[n];  // 返回第 n 项
    15. }
    16.  
    17. int main() {
    18.     int n = 10;  // 计算第 10 项
    19.     printf("Fibonacci number is %d\n", fib(n));  // 输出结果
    20.     return 0;
    21. }

    例子：0-1 背包问题

    动态规划解法
    1. #include 
    2.  
    3. // 返回两个整数中的最大值
    4. int max(int a, int b) { return (a > b) ? a : b; }
    5.  
    6. // 解决 0-1 背包问题
    7. int knapSack(int W, int wt[], int val[], int n) {
    8.     // 创建一个二维数组 K，用于存储子问题的解
    9.     int K[n+1][W+1];
    10.  
    11.     // 填充 K 表
    12.     for (int i = 0; i <= n; i++) {
    13.         for (int w = 0; w <= W; w++) {
    14.             if (i == 0 || w == 0) {
    15.                 K[i][w] = 0;  // 基本情况：没有物品或容量为 0
    16.             } else if (wt[i-1] <= w) {
    17.                 // 选择当前物品或不选择当前物品，取最大值
    18.                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
    19.             } else {
    20.                 K[i][w] = K[i-1][w];  // 当前物品不能放入背包
    21.             }
    22.         }
    23.     }
    24.     return K[n][W];  // 返回最大价值
    25. }
    26.  
    27. int main() {
    28.     int val[] = {60, 100, 120};  // 物品的价值
    29.     int wt[] = {10, 20, 30};     // 物品的重量
    30.     int W = 50;                  // 背包的容量
    31.     int n = sizeof(val)/sizeof(val[0]);  // 物品的数量
    32.     printf("Maximum value in Knapsack = %d\n", knapSack(W, wt, val, n));  // 输出结果
    33.     return 0;
    34. }

    二、贪心算法（Greedy Algorithm）

    例子：活动选择问题

    贪心算法解法
    1. #include 
    2.  
    3. // 打印最大数量的可选活动
    4. void printMaxActivities(int s[], int f[], int n) {
    5.     int i = 0;  // 第一个活动总是被选择
    6.     printf("Selected activities: %d ", i);
    7.  
    8.     // 选择其余活动
    9.     for (int j = 1; j < n; j++) {
    10.         if (s[j] >= f[i]) {  // 如果当前活动的开始时间大于等于上一个活动的结束时间
    11.             printf("%d ", j);
    12.             i = j;  // 更新上一个被选择活动的索引
    13.         }
    14.     }
    15.     printf("\n");
    16. }
    17.  
    18. int main() {
    19.     int s[] = {1, 3, 0, 5, 8, 5};  // 活动的开始时间
    20.     int f[] = {2, 4, 6, 7, 9, 9};  // 活动的结束时间
    21.     int n = sizeof(s)/sizeof(s[0]);  // 活动的数量
    22.     printMaxActivities(s, f, n);  // 输出结果
    23.     return 0;
    24. }

    三、回溯算法（Backtracking）

    例子：N皇后问题

    回溯算法解法
    1. #include 
    2. #include 
    3.  
    4. #define N 4  // 棋盘大小
    5.  
    6. // 打印棋盘
    7. void printSolution(int board[N][N]) {
    8.     for (int i = 0; i < N; i++) {
    9.         for (int j = 0; j < N; j++) {
    10.             printf(" %d ", board[i][j]);
    11.         }
    12.         printf("\n");
    13.     }
    14. }
    15.  
    16. // 检查在 board[row][col] 放置皇后是否安全
    17. bool isSafe(int board[N][N], int row, int col) {
    18.     int i, j;
    19.  
    20.     // 检查当前行的左侧
    21.     for (i = 0; i < col; i++)
    22.         if (board[row][i])
    23.             return false;
    24.  
    25.     // 检查左上对角线
    26.     for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
    27.         if (board[i][j])
    28.             return false;
    29.  
    30.     // 检查左下对角线
    31.     for (i = row, j = col; j >= 0 && i < N; i++, j--)
    32.         if (board[i][j])
    33.             return false;
    34.  
    35.     return true;
    36. }
    37.  
    38. // 递归解决 N 皇后问题
    39. bool solveNQUtil(int board[N][N], int col) {
    40.     if (col >= N)  // 所有皇后已放置
    41.         return true;
    42.  
    43.     for (int i = 0; i < N; i++) {
    44.         if (isSafe(board, i, col)) {  // 检查放置在 board[i][col] 是否安全
    45.             board[i][col] = 1;  // 放置皇后
    46.  
    47.             if (solveNQUtil(board, col + 1))  // 递归放置其余皇后
    48.                 return true;
    49.  
    50.             board[i][col] = 0;  // 回溯：移除皇后
    51.         }
    52.     }
    53.     return false;  // 如果无法放置皇后
    54. }
    55.  
    56. // 解决 N 皇后问题
    57. bool solveNQ() {
    58.     int board[N][N] = { {0, 0, 0, 0},
    59.                         {0, 0, 0, 0},
    60.                         {0, 0, 0, 0},
    61.                         {0, 0, 0, 0} };
    62.  
    63.     if (solveNQUtil(board, 0) == false) {
    64.         printf("Solution does not exist");
    65.         return false;
    66.     }
    67.     printSolution(board);  // 打印解决方案
    68.     return true;
    69. }
    70.  
    71. int main() {
    72.     solveNQ();  // 解决问题
    73.     return 0;
    74. }

    四、分治算法（Divide and Conquer）

    例子：归并排序（Merge Sort）

    1. #include 
    2.  
    3. // 合并两个子数组
    4. void merge(int arr[], int l, int m, int r) {
    5.     int n1 = m - l + 1; // 左子数组的大小
    6.     int n2 = r - m; // 右子数组的大小
    7.     int L[n1], R[n2]; // 临时数组
    8.  
    9.     // 复制数据到临时数组 L[] 和 R[]
    10.     for (int i = 0; i < n1; i++)
    11.         L[i] = arr[l + i];
    12.     for (int j = 0; j < n2; j++)
    13.         R[j] = arr[m + 1 + j];
    14.  
    15.     // 合并临时数组到 arr[l..r]
    16.     int i = 0, j = 0, k = l;
    17.     while (i < n1 && j < n2) {
    18.         if (L[i] <= R[j]) {
    19.             arr[k] = L[i];
    20.             i++;
    21.         } else {
    22.             arr[k] = R[j];
    23.             j++;
    24.         }
    25.         k++;
    26.     }
    27.  
    28.     // 复制 L[] 剩余元素
    29.     while (i < n1) {
    30.         arr[k] = L[i];
    31.         i++;
    32.         k++;
    33.     }
    34.  
    35.     // 复制 R[] 剩余元素
    36.     while (j < n2) {
    37.         arr[k] = R[j];
    38.         j++;
    39.         k++;
    40.     }
    41. }
    42.  
    43. // 归并排序
    44. void mergeSort(int arr[], int l, int r) {
    45.     if (l < r) {
    46.         int m = l + (r - l) / 2; // 找到中点
    47.         mergeSort(arr, l, m); // 排序左半部分
    48.         mergeSort(arr, m + 1, r); // 排序右半部分
    49.         merge(arr, l, m, r); // 合并已排序的部分
    50.     }
    51. }
    52.  
    53. // 打印数组
    54. void printArray(int A[], int size) {
    55.     for (int i = 0; i < size; i++)
    56.         printf("%d ", A[i]);
    57.     printf("\n");
    58. }
    59.  
    60. int main() {
    61.     int arr[] = {12, 11, 13, 5, 6, 7};
    62.     int arr_size = sizeof(arr) / sizeof(arr[0]);
    63.  
    64.     printf("Given array is \n");
    65.     printArray(arr, arr_size);
    66.  
    67.     mergeSort(arr, 0, arr_size - 1);
    68.  
    69.     printf("\nSorted array is \n");
    70.     printArray(arr, arr_size);
    71.     return 0;
    72. }

    五、图算法（Graph Algorithms）

    例子：Dijkstra 算法（单源最短路径）

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. #define V 9 // 顶点数量
    6.  
    7. // 找到最小距离的顶点
    8. int minDistance(int dist[], bool sptSet[]) {
    9.     int min = INT_MAX, min_index;
    10.     for (int v = 0; v < V; v++)
    11.         if (sptSet[v] == false && dist[v] <= min)
    12.             min = dist[v], min_index = v;
    13.     return min_index;
    14. }
    15.  
    16. // 打印解
    17. void printSolution(int dist[], int n) {
    18.     printf("Vertex \t Distance from Source\n");
    19.     for (int i = 0; i < V; i++)
    20.         printf("%d \t\t %d\n", i, dist[i]);
    21. }
    22.  
    23. // Dijkstra 算法
    24. void dijkstra(int graph[V][V], int src) {
    25.     int dist[V]; // 最短距离数组
    26.     bool sptSet[V]; // sptSet[i] 为 true 表示顶点 i 已包含在最短路径树中
    27.  
    28.     // 初始化所有距离为无穷大，sptSet[] 为 false
    29.     for (int i = 0; i < V; i++)
    30.         dist[i] = INT_MAX, sptSet[i] = false;
    31.  
    32.     dist[src] = 0; // 源顶点距离为 0
    33.  
    34.     for (int count = 0; count < V - 1; count++) {
    35.         int u = minDistance(dist, sptSet); // 选取最小距离顶点
    36.         sptSet[u] = true; // 标记为已处理
    37.  
    38.         for (int v = 0; v < V; v++)
    39.             if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
    40.                 dist[v] = dist[u] + graph[u][v]; // 更新距离
    41.     }
    42.  
    43.     printSolution(dist, V); // 打印结果
    44. }
    45.  
    46. int main() {
    47.     int graph[V][V] = { {0, 4, 0, 0, 0, 0, 0, 8, 0},
    48.                         {4, 0, 8, 0, 0, 0, 0, 11, 0},
    49.                         {0, 8, 0, 7, 0, 4, 0, 0, 2},
    50.                         {0, 0, 7, 0, 9, 14, 0, 0, 0},
    51.                         {0, 0, 0, 9, 0, 10, 0, 0, 0},
    52.                         {0, 0, 4, 14, 10, 0, 2, 0, 0},
    53.                         {0, 0, 0, 0, 0, 2, 0, 1, 6},
    54.                         {8, 11, 0, 0, 0, 0, 1, 0, 7},
    55.                         {0, 0, 2, 0, 0, 0, 6, 7, 0} };
    56.  
    57.     dijkstra(graph, 0); // 调用 Dijkstra 算法
    58.  
    59.     return 0;
    60. }

    贪心算法（Greedy Algorithm）

    例子：霍夫曼编码（Huffman Coding）

    1. #include 
    2. #include 
    3.  
    4. #define MAX_TREE_HT 100
    5.  
    6. // 最小堆节点
    7. struct MinHeapNode {
    8.     char data; // 字符
    9.     unsigned freq; // 频率
    10.     struct MinHeapNode *left, *right; // 左右子节点
    11. };
    12.  
    13. // 最小堆
    14. struct MinHeap {
    15.     unsigned size; // 当前大小
    16.     unsigned capacity; // 容量
    17.     struct MinHeapNode **array; // 数组指针
    18. };
    19.  
    20. // 创建新节点
    21. struct MinHeapNode* newNode(char data, unsigned freq) {
    22.     struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
    23.     temp->left = temp->right = NULL;
    24.     temp->data = data;
    25.     temp->freq = freq;
    26.     return temp;
    27. }
    28.  
    29. // 创建最小堆
    30. struct MinHeap* createMinHeap(unsigned capacity) {
    31.     struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    32.     minHeap->size = 0;
    33.     minHeap->capacity = capacity;
    34.     minHeap->array = (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));
    35.     return minHeap;
    36. }
    37.  
    38. // 交换两个最小堆节点
    39. void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {
    40.     struct MinHeapNode* t = *a;
    41.     *a = *b;
    42.     *b = t;
    43. }
    44.  
    45. // 最小堆化
    46. void minHeapify(struct MinHeap* minHeap, int idx) {
    47.     int smallest = idx;
    48.     int left = 2 * idx + 1;
    49.     int right = 2 * idx + 2;
    50.  
    51.     if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
    52.         smallest = left;
    53.  
    54.     if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
    55.         smallest = right;
    56.  
    57.     if (smallest != idx) {
    58.         swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
    59.         minHeapify(minHeap, smallest);
    60.     }
    61. }
    62.  
    63. // 检查是否只有一个元素
    64. int isSizeOne(struct MinHeap* minHeap) {
    65.     return (minHeap->size == 1);
    66. }
    67.  
    68. // 提取最小值节点
    69. struct MinHeapNode* extractMin(struct MinHeap* minHeap) {
    70.     struct MinHeapNode* temp = minHeap->array[0];
    71.     minHeap->array[0] = minHeap->array[minHeap->size - 1];
    72.     --minHeap->size;
    73.     minHeapify(minHeap, 0);
    74.     return temp;
    75. }
    76.  
    77. // 插入节点到最小堆
    78. void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) {
    79.     ++minHeap->size;
    80.     int i = minHeap->size - 1;
    81.  
    82.     while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
    83.         minHeap->array[i] = minHeap->array[(i - 1) / 2];
    84.         i = (i - 1) / 2;
    85.     }
    86.     minHeap->array[i] = minHeapNode;
    87. }
    88.  
    89. // 构建最小堆
    90. void buildMinHeap(struct MinHeap* minHeap) {
    91.     int n = minHeap->size - 1;
    92.     for (int i = (n - 1) / 2; i >= 0; --i)
    93.         minHeapify(minHeap, i);
    94. }
    95.  
    96. // 打印数组
    97. void printArr(int arr[], int n) {
    98.     for (int i = 0; i < n; ++i)
    99.         printf("%d", arr[i]);
    100.     printf("\n");
    101. }
    102.  
    103. // 检查是否是叶子节点
    104. int isLeaf(struct MinHeapNode* root) {
    105.     return !(root->left) && !(root->right);
    106. }
    107.  
    108. // 创建并构建最小堆
    109. struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) {
    110.     struct MinHeap* minHeap = createMinHeap(size);
    111.  
    112.     for (int i = 0; i < size; ++i)
    113.         minHeap->array[i] = newNode(data[i], freq[i]);
    114.     minHeap->size = size;
    115.     buildMinHeap(minHeap);
    116.     return minHeap;
    117. }
    118.  
    119. // 构建霍夫曼树
    120. struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {
    121.     struct MinHeapNode *left, *right, *top;
    122.     struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);
    123.  
    124.     while (!isSizeOne(minHeap)) {
    125.         left = extractMin(minHeap);
    126.         right = extractMin(minHeap);
    127.  
    128.         top = newNode('$', left->freq + right->freq);
    129.         top->left = left;
    130.         top->right = right;
    131.  
    132.         insertMinHeap(minHeap, top);
    133.     }
    134.     return extractMin(minHeap);
    135. }
    136.  
    137. // 打印霍夫曼编码
    138. void printCodes(struct MinHeapNode* root, int arr[], int top) {
    139.     if (root->left) {
    140.         arr[top] = 0;
    141.         printCodes(root->left, arr, top + 1);
    142.     }
    143.  
    144.     if (root->right) {
    145.         arr[top] = 1;
    146.         printCodes(root->right, arr, top + 1);
    147.     }
    148.  
    149.     if (isLeaf(root)) {
    150.         printf("%c: ", root->data);
    151.         printArr(arr, top);
    152.     }
    153. }
    154.  
    155. // 霍夫曼编码
    156. void HuffmanCodes(char data[], int freq[], int size) {
    157.     struct MinHeapNode* root = buildHuffmanTree(data, freq, size);
    158.     int arr[MAX_TREE_HT], top = 0;
    159.     printCodes(root, arr, top);
    160. }
    161.  
    162. int main() {
    163.     char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    164.     int freq[] = {5, 9, 12, 13, 16, 45};
    165.     int size = sizeof(arr) / sizeof(arr[0]);
    166.  
    167.     HuffmanCodes(arr, freq, size); // 调用霍夫曼编码
    168.  
    169.     return 0;
    170. }

    总结

    • 分治算法通过递归地将问题分解为子问题，解决这些子问题然后合并其解，适用于排序、搜索等问题。
    • 图算法如Dijkstra算法，通过逐步扩展最短路径树，找到图中从单个源到所有其他顶点的最短路径。
    • 贪心算法如霍夫曼编码，通过每一步选择局部最优解，最终构建出全局最优解，适用于数据压缩等问题。
    • 贪心算法每一步都选择当前最优的选择，适用于能够通过局部最优达到全局最优的问题。
    • 回溯算法系统地搜索所有可能的解，通过尝试构建解并在不满足条件时回溯，适用于需要探索所有可能解的问题。
    • 动态规划通过存储子问题的解来避免重复计算，适用于有重叠子问题和最优子结构的问题。

       
  • 相关阅读:
    io集合管理
    Linux多线程网络通信
    python究竟可以用来做些什么
    常用短信平台一览，记得收藏哦
    SpringMVC——数据提交的优化，四种跳转方式以及日期的处理
    Bert不完全手册9. 长文本建模 BigBird & Longformer & Reformer & Performer
    ipv6地址概述——配置ipv6
    利用ROS camera_calibration对usb相机标定
    SSM框架真没那么难，这份阿里大佬的进阶实战笔记真给讲透了！
    Memtester框架是什么
  • 原文地址：https://blog.csdn.net/aaaa_hsjsueu/article/details/139455724